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
27namespace mlir {
28
29class Block;
30class LivenessBlockInfo;
31class Operation;
32class Region;
33class 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);
47class Liveness {
48public:
49 using OperationListT = std::vector<Operation *>;
50 using BlockMapT = DenseMap<Block *, LivenessBlockInfo>;
51 using ValueSetT = SmallPtrSet<Value, 16>;
52
53public:
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).
66 OperationListT resolveLiveness(Value value) const;
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
86private:
87 /// Initializes the internal mappings.
88 void build();
89
90private:
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.
99class LivenessBlockInfo {
100public:
101 /// A typedef declaration of a value set.
102 using ValueSetT = Liveness::ValueSetT;
103
104public:
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
143private:
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
159

source code of mlir/include/mlir/Analysis/Liveness.h