MLIR  17.0.0git
Liveness.h
Go to the documentation of this file.
1 //===- Liveness.h - Liveness analysis for MLIR ------------------*- 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 contains an analysis for computing liveness information from a
10 // given top-level operation. The current version of the analysis uses a
11 // traditional algorithm to resolve detailed live-range information about all
12 // values within the specified regions. It is also possible to query liveness
13 // information on block level.
14 //
15 //===----------------------------------------------------------------------===//
16
17 #ifndef MLIR_ANALYSIS_LIVENESS_H
18 #define MLIR_ANALYSIS_LIVENESS_H
19
20 #include <vector>
21
22 #include "mlir/Support/LLVM.h"
26
27 namespace mlir {
28
29 class Block;
30 class LivenessBlockInfo;
31 class Operation;
32 class Region;
33 class Value;
34
35 /// Represents an analysis for computing liveness information from a
36 /// given top-level operation. The analysis iterates over all associated
37 /// regions that are attached to the given top-level operation. It
38 /// computes liveness information for every value and block that are
39 /// included in the mentioned regions. It relies on a fixpoint iteration
40 /// to compute all live-in and live-out values of all included blocks.
41 /// Sample usage:
42 /// Liveness liveness(topLevelOp);
43 /// auto &allInValues = liveness.getLiveIn(block);
44 /// auto &allOutValues = liveness.getLiveOut(block);
45 /// auto allOperationsInWhichValueIsLive = liveness.resolveLiveness(value);
46 /// bool isDeafAfter = liveness.isDeadAfter(value, operation);
47 class Liveness {
48 public:
49  using OperationListT = std::vector<Operation *>;
52
53 public:
54  /// Creates a new Liveness analysis that computes liveness
55  /// information for all associated regions.
56  Liveness(Operation *op);
57
58  /// Returns the operation this analysis was constructed from.
59  Operation *getOperation() const { return operation; }
60
61  /// Gets liveness info (if any) for the given value.
62  /// This includes all operations in which the given value is live.
63  /// Note that the operations in this list are not ordered and the current
64  /// implementation is computationally expensive (as it iterates over all
65  /// blocks in which the given value is live).
67
68  /// Gets liveness info (if any) for the block.
69  const LivenessBlockInfo *getLiveness(Block *block) const;
70
71  /// Returns a reference to a set containing live-in values (unordered).
72  const ValueSetT &getLiveIn(Block *block) const;
73
74  /// Returns a reference to a set containing live-out values (unordered).
75  const ValueSetT &getLiveOut(Block *block) const;
76
77  /// Returns true if value is not live after operation.
78  bool isDeadAfter(Value value, Operation *operation) const;
79
80  /// Dumps the liveness information in a human readable format.
81  void dump() const;
82
83  /// Dumps the liveness information to the given stream.
84  void print(raw_ostream &os) const;
85
86 private:
87  /// Initializes the internal mappings.
88  void build();
89
90 private:
91  /// The operation this analysis was constructed from.
92  Operation *operation;
93
94  /// Maps blocks to internal liveness information.
95  BlockMapT blockMapping;
96 };
97
98 /// This class represents liveness information on block level.
100 public:
101  /// A typedef declaration of a value set.
103
104 public:
105  /// Returns the underlying block.
106  Block *getBlock() const { return block; }
107
108  /// Returns all values that are live at the beginning
109  /// of the block (unordered).
110  const ValueSetT &in() const { return inValues; }
111
112  /// Returns all values that are live at the end
113  /// of the block (unordered).
114  const ValueSetT &out() const { return outValues; }
115
116  /// Returns true if the given value is in the live-in set.
117  bool isLiveIn(Value value) const;
118
119  /// Returns true if the given value is in the live-out set.
120  bool isLiveOut(Value value) const;
121
122  /// Gets the start operation for the given value. This is the first operation
123  /// the given value is considered to be live. This could either be the start
124  /// operation of the current block (in case the value is live-in) or the
125  /// operation that defines the given value (must be referenced in this block).
126  Operation *getStartOperation(Value value) const;
127
128  /// Gets the end operation for the given value using the start operation
129  /// provided (must be referenced in this block).
130  Operation *getEndOperation(Value value, Operation *startOperation) const;
131
132  /// Get the set of values that are currently live (if any) for the current op.
133  /// This analysis takes an expansive view of "live" in that if a value is
134  /// defined by or within the operation or is fully consumed (as in last user)
135  /// by or within the operation the value is considered "live". The values in
136  /// the list are not ordered.
137  ///
138  /// This check is quite expensive as it does not cache the results of the
139  /// computation, so the currently live values have to be recomputed for each
140  /// op.
142
143 private:
144  /// The underlying block.
145  Block *block = nullptr;
146
147  /// The set of all live in values.
148  ValueSetT inValues;
149
150  /// The set of all live out values.
151  ValueSetT outValues;
152
153  friend class Liveness;
154 };
155
156 } // namespace mlir
157
158 #endif // MLIR_ANALYSIS_LIVENESS_H
Block represents an ordered list of Operations.
Definition: Block.h:30
This class represents liveness information on block level.
Definition: Liveness.h:99
Block * getBlock() const
Returns the underlying block.
Definition: Liveness.h:106
Liveness::ValueSetT ValueSetT
A typedef declaration of a value set.
Definition: Liveness.h:102
bool isLiveIn(Value value) const
Returns true if the given value is in the live-in set.
Definition: Liveness.cpp:353
Operation * getStartOperation(Value value) const
Gets the start operation for the given value.
Definition: Liveness.cpp:364
const ValueSetT & in() const
Returns all values that are live at the beginning of the block (unordered).
Definition: Liveness.h:110
ValueSetT currentlyLiveValues(Operation *op) const
Get the set of values that are currently live (if any) for the current op.
Definition: Liveness.cpp:396
bool isLiveOut(Value value) const
Returns true if the given value is in the live-out set.
Definition: Liveness.cpp:358
const ValueSetT & out() const
Returns all values that are live at the end of the block (unordered).
Definition: Liveness.h:114
Operation * getEndOperation(Value value, Operation *startOperation) const
Gets the end operation for the given value using the start operation provided (must be referenced in ...
Definition: Liveness.cpp:375
Represents an analysis for computing liveness information from a given top-level operation.
Definition: Liveness.h:47
bool isDeadAfter(Value value, Operation *operation) const
Returns true if value is not live after operation.
Definition: Liveness.cpp:241
Liveness(Operation *op)
Creates a new Liveness analysis that computes liveness information for all associated regions.
Definition: Liveness.cpp:157
Operation * getOperation() const
Returns the operation this analysis was constructed from.
Definition: Liveness.h:59
DenseMap< Block *, LivenessBlockInfo > BlockMapT
Definition: Liveness.h:50
OperationListT resolveLiveness(Value value) const
Gets liveness info (if any) for the given value.
Definition: Liveness.cpp:177
const LivenessBlockInfo * getLiveness(Block *block) const
Gets liveness info (if any) for the block.
Definition: Liveness.cpp:225
SmallPtrSet< Value, 16 > ValueSetT
Definition: Liveness.h:51
void print(raw_ostream &os) const
Dumps the liveness information to the given stream.
Definition: Liveness.cpp:260
const ValueSetT & getLiveOut(Block *block) const
Returns a reference to a set containing live-out values (unordered).
Definition: Liveness.cpp:236
const ValueSetT & getLiveIn(Block *block) const
Returns a reference to a set containing live-in values (unordered).
Definition: Liveness.cpp:231
std::vector< Operation * > OperationListT
Definition: Liveness.h:49
void dump() const
Dumps the liveness information in a human readable format.
Definition: Liveness.cpp:257
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:75
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:93
Include the generated interface declarations.