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 17 #include "llvm/ADT/DynamicAPInt.h" 18 #include "llvm/Support/raw_ostream.h" 19 20 namespace mlir { 21 namespace presburger { 22 using llvm::DynamicAPInt; 23 24 /// A class to represent fractions. The sign of the fraction is represented 25 /// in the sign of the numerator; the denominator is always positive. 26 /// 27 /// Note that overflows may occur if the numerator or denominator are not 28 /// representable by 64-bit integers. 29 struct Fraction { 30 /// Default constructor initializes the represented rational number to zero. 31 Fraction() = default; 32 33 /// Construct a Fraction from a numerator and denominator. 34 Fraction(const DynamicAPInt &oNum, const DynamicAPInt &oDen = DynamicAPInt(1)) 35 : num(oNum), den(oDen) { 36 if (den < 0) { 37 num = -num; 38 den = -den; 39 } 40 } 41 /// Overloads for passing literals. 42 Fraction(const DynamicAPInt &num, int64_t den) 43 : Fraction(num, DynamicAPInt(den)) {} 44 Fraction(int64_t num, const DynamicAPInt &den = DynamicAPInt(1)) 45 : Fraction(DynamicAPInt(num), den) {} 46 Fraction(int64_t num, int64_t den) 47 : Fraction(DynamicAPInt(num), DynamicAPInt(den)) {} 48 49 // Return the value of the fraction as an integer. This should only be called 50 // when the fraction's value is really an integer. 51 DynamicAPInt getAsInteger() const { 52 assert(num % den == 0 && "Get as integer called on non-integral fraction!"); 53 return num / den; 54 } 55 56 llvm::raw_ostream &print(llvm::raw_ostream &os) const { 57 return os << "(" << num << "/" << den << ")"; 58 } 59 60 /// The numerator and denominator, respectively. The denominator is always 61 /// positive. 62 DynamicAPInt num{0}, den{1}; 63 }; 64 65 /// Three-way comparison between two fractions. 66 /// Returns +1, 0, and -1 if the first fraction is greater than, equal to, or 67 /// less than the second fraction, respectively. 68 inline int compare(const Fraction &x, const Fraction &y) { 69 DynamicAPInt diff = x.num * y.den - y.num * x.den; 70 if (diff > 0) 71 return +1; 72 if (diff < 0) 73 return -1; 74 return 0; 75 } 76 77 inline DynamicAPInt floor(const Fraction &f) { return floorDiv(f.num, f.den); } 78 79 inline DynamicAPInt ceil(const Fraction &f) { return ceilDiv(f.num, f.den); } 80 81 inline Fraction operator-(const Fraction &x) { return Fraction(-x.num, x.den); } 82 83 inline bool operator<(const Fraction &x, const Fraction &y) { 84 return compare(x, y) < 0; 85 } 86 87 inline bool operator<=(const Fraction &x, const Fraction &y) { 88 return compare(x, y) <= 0; 89 } 90 91 inline bool operator==(const Fraction &x, const Fraction &y) { 92 return compare(x, y) == 0; 93 } 94 95 inline bool operator!=(const Fraction &x, const Fraction &y) { 96 return compare(x, y) != 0; 97 } 98 99 inline bool operator>(const Fraction &x, const Fraction &y) { 100 return compare(x, y) > 0; 101 } 102 103 inline bool operator>=(const Fraction &x, const Fraction &y) { 104 return compare(x, y) >= 0; 105 } 106 107 inline Fraction abs(const Fraction &f) { 108 assert(f.den > 0 && "denominator of fraction must be positive!"); 109 return Fraction(abs(f.num), f.den); 110 } 111 112 inline Fraction reduce(const Fraction &f) { 113 if (f == Fraction(0)) 114 return Fraction(0, 1); 115 DynamicAPInt g = gcd(abs(f.num), abs(f.den)); 116 return Fraction(f.num / g, f.den / g); 117 } 118 119 inline Fraction operator*(const Fraction &x, const Fraction &y) { 120 return reduce(Fraction(x.num * y.num, x.den * y.den)); 121 } 122 123 inline Fraction operator/(const Fraction &x, const Fraction &y) { 124 return reduce(Fraction(x.num * y.den, x.den * y.num)); 125 } 126 127 inline Fraction operator+(const Fraction &x, const Fraction &y) { 128 return reduce(Fraction(x.num * y.den + x.den * y.num, x.den * y.den)); 129 } 130 131 inline Fraction operator-(const Fraction &x, const Fraction &y) { 132 return reduce(Fraction(x.num * y.den - x.den * y.num, x.den * y.den)); 133 } 134 135 // Find the integer nearest to a given fraction. 136 inline DynamicAPInt round(const Fraction &f) { 137 DynamicAPInt rem = f.num % f.den; 138 return (f.num / f.den) + (rem > f.den / 2); 139 } 140 141 inline Fraction &operator+=(Fraction &x, const Fraction &y) { 142 x = x + y; 143 return x; 144 } 145 146 inline Fraction &operator-=(Fraction &x, const Fraction &y) { 147 x = x - y; 148 return x; 149 } 150 151 inline Fraction &operator/=(Fraction &x, const Fraction &y) { 152 x = x / y; 153 return x; 154 } 155 156 inline Fraction &operator*=(Fraction &x, const Fraction &y) { 157 x = x * y; 158 return x; 159 } 160 161 inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Fraction &x) { 162 x.print(os); 163 return os; 164 } 165 166 } // namespace presburger 167 } // namespace mlir 168 169 #endif // MLIR_ANALYSIS_PRESBURGER_FRACTION_H 170