MLIR  21.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 // One can also implement InferIntRangeInterface on ops in custom dialects,
14 // and then use this analysis to propagate ranges with custom semantics.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #ifndef MLIR_ANALYSIS_DATAFLOW_INTEGERANGEANALYSIS_H
19 #define MLIR_ANALYSIS_DATAFLOW_INTEGERANGEANALYSIS_H
20 
23 
24 namespace mlir {
25 class RewriterBase;
26 namespace dataflow {
27 
28 /// This lattice element represents the integer value range of an SSA value.
29 /// When this lattice is updated, it automatically updates the constant value
30 /// of the SSA value (if the range can be narrowed to one).
31 class IntegerValueRangeLattice : public Lattice<IntegerValueRange> {
32 public:
33  using Lattice::Lattice;
34 
35  /// If the range can be narrowed to an integer constant, update the constant
36  /// value of the SSA value.
37  void onUpdate(DataFlowSolver *solver) const override;
38 };
39 
40 /// Integer range analysis determines the integer value range of SSA values
41 /// using operations that define `InferIntRangeInterface` and also sets the
42 /// range of iteration indices of loops with known bounds.
43 ///
44 /// This analysis depends on DeadCodeAnalysis, and will be a silent no-op
45 /// if DeadCodeAnalysis is not loaded in the same solver context.
47  : public SparseForwardDataFlowAnalysis<IntegerValueRangeLattice> {
48 public:
50 
51  /// At an entry point, we cannot reason about interger value ranges.
52  void setToEntryState(IntegerValueRangeLattice *lattice) override {
54  lattice->getAnchor())));
55  }
56 
57  /// Visit an operation. Invoke the transfer function on each operation that
58  /// implements `InferIntRangeInterface`.
59  LogicalResult
62  ArrayRef<IntegerValueRangeLattice *> results) override;
63 
64  /// Visit block arguments or operation results of an operation with region
65  /// control-flow for which values are not defined by region control-flow. This
66  /// function calls `InferIntRangeInterface` to provide values for block
67  /// arguments or tries to reduce the range on loop induction variables with
68  /// known bounds.
69  void
72  unsigned firstIndex) override;
73 };
74 
75 /// Succeeds if an op can be converted to its unsigned equivalent without
76 /// changing its semantics. This is the case when none of its openands or
77 /// results can be below 0 when analyzed from a signed perspective.
78 LogicalResult staticallyNonNegative(DataFlowSolver &solver, Operation *op);
79 
80 /// Succeeds when a value is statically non-negative in that it has a lower
81 /// bound on its value (if it is treated as signed) and that bound is
82 /// non-negative.
83 /// Note, the results of this query may not be accurate for `index` if you plan
84 /// to use a non-64-bit index.
85 LogicalResult staticallyNonNegative(DataFlowSolver &solver, Value v);
86 
87 LogicalResult maybeReplaceWithConstant(DataFlowSolver &solver,
88  RewriterBase &rewriter, Value value);
89 
90 } // end namespace dataflow
91 } // end namespace mlir
92 
93 #endif // MLIR_ANALYSIS_DATAFLOW_INTEGERANGEANALYSIS_H
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
The general data-flow analysis solver.
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...
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
This class represents a successor of a region.
This class coordinates the application of a rewrite on a set of IR, providing a way for clients to tr...
Definition: PatternMatch.h:358
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
Integer range analysis determines the integer value range of SSA values using operations that define ...
void setToEntryState(IntegerValueRangeLattice *lattice) override
At an entry point, we cannot reason about interger value ranges.
LogicalResult visitOperation(Operation *op, ArrayRef< const IntegerValueRangeLattice * > operands, ArrayRef< IntegerValueRangeLattice * > results) override
Visit an operation.
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 class represents a lattice holding a specific value of type ValueT.
Value getAnchor() const
Return the value this lattice is located at.
ChangeResult join(const AbstractSparseLattice &rhs) override
Join the information contained in the 'rhs' lattice into this lattice.
A sparse forward data-flow analysis for propagating SSA value lattices across the IR by implementing ...
SparseForwardDataFlowAnalysis(DataFlowSolver &solver)
LogicalResult staticallyNonNegative(DataFlowSolver &solver, Operation *op)
Succeeds if an op can be converted to its unsigned equivalent without changing its semantics.
LogicalResult maybeReplaceWithConstant(DataFlowSolver &solver, RewriterBase &rewriter, Value value)
Patterned after SCCP.
Include the generated interface declarations.