MLIR  18.0.0git
Fraction.h
Go to the documentation of this file.
1 //===- Fraction.h - MLIR Fraction Class -------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This is a simple class to represent fractions. It supports arithmetic,
10 // comparison, floor, and ceiling operations.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef MLIR_ANALYSIS_PRESBURGER_FRACTION_H
15 #define MLIR_ANALYSIS_PRESBURGER_FRACTION_H
16 
19 
20 namespace mlir {
21 namespace presburger {
22 
23 /// A class to represent fractions. The sign of the fraction is represented
24 /// in the sign of the numerator; the denominator is always positive.
25 ///
26 /// Note that overflows may occur if the numerator or denominator are not
27 /// representable by 64-bit integers.
28 struct Fraction {
29  /// Default constructor initializes the represented rational number to zero.
30  Fraction() = default;
31 
32  /// Construct a Fraction from a numerator and denominator.
33  Fraction(const MPInt &oNum, const MPInt &oDen = MPInt(1)) : num(oNum), den(oDen) {
34  if (den < 0) {
35  num = -num;
36  den = -den;
37  }
38  }
39  /// Overloads for passing literals.
40  Fraction(const MPInt &num, int64_t den = 1) : Fraction(num, MPInt(den)) {}
41  Fraction(int64_t num, const MPInt &den = MPInt(1)) : Fraction(MPInt(num), den) {}
42  Fraction(int64_t num, int64_t den) : Fraction(MPInt(num), MPInt(den)) {}
43 
44  // Return the value of the fraction as an integer. This should only be called
45  // when the fraction's value is really an integer.
46  MPInt getAsInteger() const {
47  assert(num % den == 0 && "Get as integer called on non-integral fraction!");
48  return num / den;
49  }
50 
51  llvm::raw_ostream &print(llvm::raw_ostream &os) const {
52  return os << "(" << num << "/" << den << ")";
53  }
54 
55  /// The numerator and denominator, respectively. The denominator is always
56  /// positive.
57  MPInt num{0}, den{1};
58 };
59 
60 /// Three-way comparison between two fractions.
61 /// Returns +1, 0, and -1 if the first fraction is greater than, equal to, or
62 /// less than the second fraction, respectively.
63 inline int compare(const Fraction &x, const Fraction &y) {
64  MPInt diff = x.num * y.den - y.num * x.den;
65  if (diff > 0)
66  return +1;
67  if (diff < 0)
68  return -1;
69  return 0;
70 }
71 
72 inline MPInt floor(const Fraction &f) { return floorDiv(f.num, f.den); }
73 
74 inline MPInt ceil(const Fraction &f) { return ceilDiv(f.num, f.den); }
75 
76 inline Fraction operator-(const Fraction &x) { return Fraction(-x.num, x.den); }
77 
78 inline bool operator<(const Fraction &x, const Fraction &y) {
79  return compare(x, y) < 0;
80 }
81 
82 inline bool operator<=(const Fraction &x, const Fraction &y) {
83  return compare(x, y) <= 0;
84 }
85 
86 inline bool operator==(const Fraction &x, const Fraction &y) {
87  return compare(x, y) == 0;
88 }
89 
90 inline bool operator!=(const Fraction &x, const Fraction &y) {
91  return compare(x, y) != 0;
92 }
93 
94 inline bool operator>(const Fraction &x, const Fraction &y) {
95  return compare(x, y) > 0;
96 }
97 
98 inline bool operator>=(const Fraction &x, const Fraction &y) {
99  return compare(x, y) >= 0;
100 }
101 
102 inline Fraction reduce(const Fraction &f) {
103  if (f == Fraction(0))
104  return Fraction(0, 1);
105  MPInt g = gcd(f.num, f.den);
106  return Fraction(f.num / g, f.den / g);
107 }
108 
109 inline Fraction operator*(const Fraction &x, const Fraction &y) {
110  return reduce(Fraction(x.num * y.num, x.den * y.den));
111 }
112 
113 inline Fraction operator/(const Fraction &x, const Fraction &y) {
114  return reduce(Fraction(x.num * y.den, x.den * y.num));
115 }
116 
117 inline Fraction operator+(const Fraction &x, const Fraction &y) {
118  return reduce(Fraction(x.num * y.den + x.den * y.num, x.den * y.den));
119 }
120 
121 inline Fraction operator-(const Fraction &x, const Fraction &y) {
122  return reduce(Fraction(x.num * y.den - x.den * y.num, x.den * y.den));
123 }
124 
125 inline Fraction& operator+=(Fraction &x, const Fraction &y) {
126  x = x + y;
127  return x;
128 }
129 
130 inline Fraction& operator-=(Fraction &x, const Fraction &y) {
131  x = x - y;
132  return x;
133 }
134 
135 inline Fraction& operator/=(Fraction &x, const Fraction &y) {
136  x = x / y;
137  return x;
138 }
139 
140 inline Fraction& operator*=(Fraction &x, const Fraction &y) {
141  x = x * y;
142  return x;
143 }
144 
145 inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Fraction &x) {
146  x.print(os);
147  return os;
148 }
149 
150 } // namespace presburger
151 } // namespace mlir
152 
153 #endif // MLIR_ANALYSIS_PRESBURGER_FRACTION_H
This class provides support for multi-precision arithmetic.
Definition: MPInt.h:87
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt gcd(const MPInt &a, const MPInt &b)
Definition: MPInt.h:399
llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const Fraction &x)
Definition: Fraction.h:145
Fraction & operator-=(Fraction &x, const Fraction &y)
Definition: Fraction.h:130
Fraction operator+(const Fraction &x, const Fraction &y)
Definition: Fraction.h:117
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt ceilDiv(const MPInt &lhs, const MPInt &rhs)
Definition: MPInt.h:374
bool operator==(const Fraction &x, const Fraction &y)
Definition: Fraction.h:86
bool operator>(const Fraction &x, const Fraction &y)
Definition: Fraction.h:94
bool operator<(const Fraction &x, const Fraction &y)
Definition: Fraction.h:78
int compare(const Fraction &x, const Fraction &y)
Three-way comparison between two fractions.
Definition: Fraction.h:63
bool operator>=(const Fraction &x, const Fraction &y)
Definition: Fraction.h:98
Fraction reduce(const Fraction &f)
Definition: Fraction.h:102
Fraction operator-(const Fraction &x)
Definition: Fraction.h:76
bool operator<=(const Fraction &x, const Fraction &y)
Definition: Fraction.h:82
Fraction & operator*=(Fraction &x, const Fraction &y)
Definition: Fraction.h:140
MPInt ceil(const Fraction &f)
Definition: Fraction.h:74
Fraction & operator/=(Fraction &x, const Fraction &y)
Definition: Fraction.h:135
bool operator!=(const Fraction &x, const Fraction &y)
Definition: Fraction.h:90
Fraction & operator+=(Fraction &x, const Fraction &y)
Definition: Fraction.h:125
Fraction operator*(const Fraction &x, const Fraction &y)
Definition: Fraction.h:109
MPInt floor(const Fraction &f)
Definition: Fraction.h:72
Fraction operator/(const Fraction &x, const Fraction &y)
Definition: Fraction.h:113
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt floorDiv(const MPInt &lhs, const MPInt &rhs)
Definition: MPInt.h:382
This header declares functions that assist transformations in the MemRef dialect.
A class to represent fractions.
Definition: Fraction.h:28
Fraction(const MPInt &num, int64_t den=1)
Overloads for passing literals.
Definition: Fraction.h:40
Fraction()=default
Default constructor initializes the represented rational number to zero.
MPInt getAsInteger() const
Definition: Fraction.h:46
Fraction(int64_t num, const MPInt &den=MPInt(1))
Definition: Fraction.h:41
Fraction(int64_t num, int64_t den)
Definition: Fraction.h:42
MPInt num
The numerator and denominator, respectively.
Definition: Fraction.h:57
llvm::raw_ostream & print(llvm::raw_ostream &os) const
Definition: Fraction.h:51
Fraction(const MPInt &oNum, const MPInt &oDen=MPInt(1))
Construct a Fraction from a numerator and denominator.
Definition: Fraction.h:33