MLIR  16.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"
23 #include "llvm/ADT/ArrayRef.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/SmallPtrSet.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.
141  ValueSetT currentlyLiveValues(Operation *op) const;
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
Include the generated interface declarations.
Block * getBlock() const
Returns the underlying block.
Definition: Liveness.h:106
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:28
Block represents an ordered list of Operations.
Definition: Block.h:29
This class represents liveness information on block level.
Definition: Liveness.h:99
void print(raw_ostream &os) const
Dumps the liveness information to the given stream.
Definition: Liveness.cpp:260
const ValueSetT & out() const
Returns all values that are live at the end of the block (unordered).
Definition: Liveness.h:114
static constexpr const bool value
bool isDeadAfter(Value value, Operation *operation) const
Returns true if value is not live after operation.
Definition: Liveness.cpp:241
const ValueSetT & getLiveOut(Block *block) const
Returns a reference to a set containing live-out values (unordered).
Definition: Liveness.cpp:236
Represents an analysis for computing liveness information from a given top-level operation.
Definition: Liveness.h:47
Operation * getOperation() const
Returns the operation this analysis was constructed from.
Definition: Liveness.h:59
const LivenessBlockInfo * getLiveness(Block *block) const
Gets liveness info (if any) for the block.
Definition: Liveness.cpp:225
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
void dump() const
Dumps the liveness information in a human readable format.
Definition: Liveness.cpp:257
std::vector< Operation * > OperationListT
Definition: Liveness.h:49
OperationListT resolveLiveness(Value value) const
Gets liveness info (if any) for the given value.
Definition: Liveness.cpp:177
const ValueSetT & in() const
Returns all values that are live at the beginning of the block (unordered).
Definition: Liveness.h:110
Liveness(Operation *op)
Creates a new Liveness analysis that computes liveness information for all associated regions...
Definition: Liveness.cpp:157
const ValueSetT & getLiveIn(Block *block) const
Returns a reference to a set containing live-in values (unordered).
Definition: Liveness.cpp:231
SmallPtrSet< Value, 16 > ValueSetT
Definition: Liveness.h:51