MLIR  16.0.0git
IntegerRangeAnalysis.h
Go to the documentation of this file.
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 
20 
21 namespace mlir {
22 namespace dataflow {
23 
24 /// This lattice value represents the integer range of an SSA value.
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 getMaxRange(Value value);
31 
32  /// Create an integer value range lattice value.
34  : value(std::move(value)) {}
35 
36  /// Whether the range is uninitialized. This happens when the state hasn't
37  /// been set during the analysis.
38  bool isUninitialized() const { return !value.has_value(); }
39 
40  /// Get the known integer value range.
41  const ConstantIntRanges &getValue() const {
42  assert(!isUninitialized());
43  return *value;
44  }
45 
46  /// Compare two ranges.
47  bool operator==(const IntegerValueRange &rhs) const {
48  return value == rhs.value;
49  }
50 
51  /// Take the union of two ranges.
53  const IntegerValueRange &rhs) {
54  if (lhs.isUninitialized())
55  return rhs;
56  if (rhs.isUninitialized())
57  return lhs;
58  return IntegerValueRange{lhs.getValue().rangeUnion(rhs.getValue())};
59  }
60 
61  /// Print the integer value range.
62  void print(raw_ostream &os) const { os << value; }
63 
64 private:
65  /// The known integer value range.
67 };
68 
69 /// This lattice element represents the integer value range of an SSA value.
70 /// When this lattice is updated, it automatically updates the constant value
71 /// of the SSA value (if the range can be narrowed to one).
72 class IntegerValueRangeLattice : public Lattice<IntegerValueRange> {
73 public:
74  using Lattice::Lattice;
75 
76  /// If the range can be narrowed to an integer constant, update the constant
77  /// value of the SSA value.
78  void onUpdate(DataFlowSolver *solver) const override;
79 };
80 
81 /// Integer range analysis determines the integer value range of SSA values
82 /// using operations that define `InferIntRangeInterface` and also sets the
83 /// range of iteration indices of loops with known bounds.
85  : public SparseDataFlowAnalysis<IntegerValueRangeLattice> {
86 public:
88 
89  /// At an entry point, we cannot reason about interger value ranges.
90  void setToEntryState(IntegerValueRangeLattice *lattice) override {
92  lattice->getPoint())));
93  }
94 
95  /// Visit an operation. Invoke the transfer function on each operation that
96  /// implements `InferIntRangeInterface`.
97  void visitOperation(Operation *op,
99  ArrayRef<IntegerValueRangeLattice *> results) override;
100 
101  /// Visit block arguments or operation results of an operation with region
102  /// control-flow for which values are not defined by region control-flow. This
103  /// function calls `InferIntRangeInterface` to provide values for block
104  /// arguments or tries to reduce the range on loop induction variables with
105  /// known bounds.
106  void
109  unsigned firstIndex) override;
110 };
111 
112 } // end namespace dataflow
113 } // end namespace mlir
114 
115 #endif // MLIR_ANALYSIS_DATAFLOW_INTEGERANGEANALYSIS_H
A set of arbitrary-precision integers representing bounds on a given integer value.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
The general data-flow analysis solver.
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:31
This class represents a successor of a region.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
Integer range analysis determines the integer value range of SSA values using operations that define ...
void visitOperation(Operation *op, ArrayRef< const IntegerValueRangeLattice * > operands, ArrayRef< IntegerValueRangeLattice * > results) override
Visit an operation.
void setToEntryState(IntegerValueRangeLattice *lattice) override
At an entry point, we cannot reason about interger value ranges.
void visitNonControlFlowArguments(Operation *op, const RegionSuccessor &successor, ArrayRef< IntegerValueRangeLattice * > argLattices, unsigned firstIndex) override
Visit block arguments or operation results of an operation with region control-flow for which values ...
This lattice element represents the integer value range of an SSA value.
void onUpdate(DataFlowSolver *solver) const override
If the range can be narrowed to an integer constant, update the constant value of the SSA value.
This lattice value represents the integer range of an SSA value.
IntegerValueRange(Optional< ConstantIntRanges > value=std::nullopt)
Create an integer value range lattice value.
const ConstantIntRanges & getValue() const
Get the known integer value range.
void print(raw_ostream &os) const
Print the integer value range.
bool isUninitialized() const
Whether the range is uninitialized.
bool operator==(const IntegerValueRange &rhs) const
Compare two ranges.
static IntegerValueRange getMaxRange(Value value)
Create a maximal range ([0, uint_max(t)] / [int_min(t), int_max(t)]) range that is used to mark the v...
static IntegerValueRange join(const IntegerValueRange &lhs, const IntegerValueRange &rhs)
Take the union of two ranges.
This class represents a lattice holding a specific value of type ValueT.
ChangeResult join(const AbstractSparseLattice &rhs) override
Join the information contained in the 'rhs' lattice into this lattice.
Value getPoint() const
Return the program point this lattice is located at.
A sparse (forward) data-flow analysis for propagating SSA value lattices across the IR by implementin...
SparseDataFlowAnalysis(DataFlowSolver &solver)
Include the generated interface declarations.