1 //===-IntegerRangeAnalysis.h - Integer range analysis -----------*- 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 file declares the dataflow analysis class for integer range inference 10 // so that it can be used in transformations over the `arith` dialect such as 11 // branch elimination or signed->unsigned rewriting 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef MLIR_ANALYSIS_DATAFLOW_INTEGERANGEANALYSIS_H 16 #define MLIR_ANALYSIS_DATAFLOW_INTEGERANGEANALYSIS_H 17 18 #include "mlir/Analysis/DataFlow/SparseAnalysis.h" 19 #include "mlir/Interfaces/InferIntRangeInterface.h" 20 21 namespace mlir { 22 namespace dataflow { 23 24 /// This lattice value represents the integer range of an SSA value. 25 class IntegerValueRange { 26 public: 27 /// Create a maximal range ([0, uint_max(t)] / [int_min(t), int_max(t)]) 28 /// range that is used to mark the value as unable to be analyzed further, 29 /// where `t` is the type of `value`. 30 static IntegerValueRange getPessimisticValueState(Value value); 31 32 /// Create an integer value range lattice value. IntegerValueRange(ConstantIntRanges value)33 IntegerValueRange(ConstantIntRanges value) : value(std::move(value)) {} 34 35 /// Get the known integer value range. getValue()36 const ConstantIntRanges &getValue() const { return value; } 37 38 /// Compare two ranges. 39 bool operator==(const IntegerValueRange &rhs) const { 40 return value == rhs.value; 41 } 42 43 /// Take the union of two ranges. join(const IntegerValueRange & lhs,const IntegerValueRange & rhs)44 static IntegerValueRange join(const IntegerValueRange &lhs, 45 const IntegerValueRange &rhs) { 46 return lhs.value.rangeUnion(rhs.value); 47 } 48 49 /// Print the integer value range. print(raw_ostream & os)50 void print(raw_ostream &os) const { os << value; } 51 52 private: 53 /// The known integer value range. 54 ConstantIntRanges value; 55 }; 56 57 /// This lattice element represents the integer value range of an SSA value. 58 /// When this lattice is updated, it automatically updates the constant value 59 /// of the SSA value (if the range can be narrowed to one). 60 class IntegerValueRangeLattice : public Lattice<IntegerValueRange> { 61 public: 62 using Lattice::Lattice; 63 64 /// If the range can be narrowed to an integer constant, update the constant 65 /// value of the SSA value. 66 void onUpdate(DataFlowSolver *solver) const override; 67 }; 68 69 /// Integer range analysis determines the integer value range of SSA values 70 /// using operations that define `InferIntRangeInterface` and also sets the 71 /// range of iteration indices of loops with known bounds. 72 class IntegerRangeAnalysis 73 : public SparseDataFlowAnalysis<IntegerValueRangeLattice> { 74 public: 75 using SparseDataFlowAnalysis::SparseDataFlowAnalysis; 76 77 /// Visit an operation. Invoke the transfer function on each operation that 78 /// implements `InferIntRangeInterface`. 79 void visitOperation(Operation *op, 80 ArrayRef<const IntegerValueRangeLattice *> operands, 81 ArrayRef<IntegerValueRangeLattice *> results) override; 82 83 /// Visit block arguments or operation results of an operation with region 84 /// control-flow for which values are not defined by region control-flow. This 85 /// function calls `InferIntRangeInterface` to provide values for block 86 /// arguments or tries to reduce the range on loop induction variables with 87 /// known bounds. 88 void 89 visitNonControlFlowArguments(Operation *op, const RegionSuccessor &successor, 90 ArrayRef<IntegerValueRangeLattice *> argLattices, 91 unsigned firstIndex) override; 92 }; 93 94 } // end namespace dataflow 95 } // end namespace mlir 96 97 #endif // MLIR_ANALYSIS_DATAFLOW_INTEGERANGEANALYSIS_H 98