1 //===- Liveness.cpp - Liveness analysis for MLIR --------------------------===//
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 // Implementation of the liveness analysis.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "mlir/Analysis/Liveness.h"
14 #include "mlir/IR/Block.h"
15 #include "mlir/IR/Operation.h"
16 #include "mlir/IR/Region.h"
17 #include "mlir/IR/Value.h"
18 #include "llvm/ADT/SetOperations.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/Support/raw_ostream.h"
21
22 using namespace mlir;
23
24 namespace {
25 /// Builds and holds block information during the construction phase.
26 struct BlockInfoBuilder {
27 using ValueSetT = Liveness::ValueSetT;
28
29 /// Constructs an empty block builder.
BlockInfoBuilder__anon43a71c3e0111::BlockInfoBuilder30 BlockInfoBuilder() : block(nullptr) {}
31
32 /// Fills the block builder with initial liveness information.
BlockInfoBuilder__anon43a71c3e0111::BlockInfoBuilder33 BlockInfoBuilder(Block *block) : block(block) {
34 auto gatherOutValues = [&](Value value) {
35 // Check whether this value will be in the outValues set (its uses escape
36 // this block). Due to the SSA properties of the program, the uses must
37 // occur after the definition. Therefore, we do not have to check
38 // additional conditions to detect an escaping value.
39 for (Operation *useOp : value.getUsers()) {
40 Block *ownerBlock = useOp->getBlock();
41 // Find an owner block in the current region. Note that a value does not
42 // escape this block if it is used in a nested region.
43 ownerBlock = block->getParent()->findAncestorBlockInRegion(*ownerBlock);
44 assert(ownerBlock && "Use leaves the current parent region");
45 if (ownerBlock != block) {
46 outValues.insert(value);
47 break;
48 }
49 }
50 };
51
52 // Mark all block arguments (phis) as defined.
53 for (BlockArgument argument : block->getArguments()) {
54 // Insert value into the set of defined values.
55 defValues.insert(argument);
56
57 // Gather all out values of all arguments in the current block.
58 gatherOutValues(argument);
59 }
60
61 // Gather out values of all operations in the current block.
62 for (Operation &operation : *block)
63 for (Value result : operation.getResults())
64 gatherOutValues(result);
65
66 // Mark all nested operation results as defined, and nested operation
67 // operands as used. All defined value will be removed from the used set
68 // at the end.
69 block->walk([&](Operation *op) {
70 for (Value result : op->getResults())
71 defValues.insert(result);
72 for (Value operand : op->getOperands())
73 useValues.insert(operand);
74 });
75 llvm::set_subtract(useValues, defValues);
76 }
77
78 /// Updates live-in information of the current block. To do so it uses the
79 /// default liveness-computation formula: newIn = use union out \ def. The
80 /// methods returns true, if the set has changed (newIn != in), false
81 /// otherwise.
updateLiveIn__anon43a71c3e0111::BlockInfoBuilder82 bool updateLiveIn() {
83 ValueSetT newIn = useValues;
84 llvm::set_union(newIn, outValues);
85 llvm::set_subtract(newIn, defValues);
86
87 // It is sufficient to check the set sizes (instead of their contents) since
88 // the live-in set can only grow monotonically during all update operations.
89 if (newIn.size() == inValues.size())
90 return false;
91
92 inValues = std::move(newIn);
93 return true;
94 }
95
96 /// Updates live-out information of the current block. It iterates over all
97 /// successors and unifies their live-in values with the current live-out
98 /// values.
updateLiveOut__anon43a71c3e0111::BlockInfoBuilder99 void updateLiveOut(const DenseMap<Block *, BlockInfoBuilder> &builders) {
100 for (Block *succ : block->getSuccessors()) {
101 const BlockInfoBuilder &builder = builders.find(succ)->second;
102 llvm::set_union(outValues, builder.inValues);
103 }
104 }
105
106 /// The current block.
107 Block *block;
108
109 /// The set of all live in values.
110 ValueSetT inValues;
111
112 /// The set of all live out values.
113 ValueSetT outValues;
114
115 /// The set of all defined values.
116 ValueSetT defValues;
117
118 /// The set of all used values.
119 ValueSetT useValues;
120 };
121 } // namespace
122
123 /// Builds the internal liveness block mapping.
buildBlockMapping(Operation * operation,DenseMap<Block *,BlockInfoBuilder> & builders)124 static void buildBlockMapping(Operation *operation,
125 DenseMap<Block *, BlockInfoBuilder> &builders) {
126 SetVector<Block *> toProcess;
127
128 operation->walk<WalkOrder::PreOrder>([&](Block *block) {
129 BlockInfoBuilder &builder =
130 builders.try_emplace(block, block).first->second;
131
132 if (builder.updateLiveIn())
133 toProcess.insert(block->pred_begin(), block->pred_end());
134 });
135
136 // Propagate the in and out-value sets (fixpoint iteration).
137 while (!toProcess.empty()) {
138 Block *current = toProcess.pop_back_val();
139 BlockInfoBuilder &builder = builders[current];
140
141 // Update the current out values.
142 builder.updateLiveOut(builders);
143
144 // Compute (potentially) updated live in values.
145 if (builder.updateLiveIn())
146 toProcess.insert(current->pred_begin(), current->pred_end());
147 }
148 }
149
150 //===----------------------------------------------------------------------===//
151 // Liveness
152 //===----------------------------------------------------------------------===//
153
154 /// Creates a new Liveness analysis that computes liveness information for all
155 /// associated regions.
Liveness(Operation * op)156 Liveness::Liveness(Operation *op) : operation(op) { build(); }
157
158 /// Initializes the internal mappings.
build()159 void Liveness::build() {
160 // Build internal block mapping.
161 DenseMap<Block *, BlockInfoBuilder> builders;
162 buildBlockMapping(operation, builders);
163
164 // Store internal block data.
165 for (auto &entry : builders) {
166 BlockInfoBuilder &builder = entry.second;
167 LivenessBlockInfo &info = blockMapping[entry.first];
168
169 info.block = builder.block;
170 info.inValues = std::move(builder.inValues);
171 info.outValues = std::move(builder.outValues);
172 }
173 }
174
175 /// Gets liveness info (if any) for the given value.
resolveLiveness(Value value) const176 Liveness::OperationListT Liveness::resolveLiveness(Value value) const {
177 OperationListT result;
178 SmallPtrSet<Block *, 32> visited;
179 SmallVector<Block *, 8> toProcess;
180
181 // Start with the defining block
182 Block *currentBlock;
183 if (Operation *defOp = value.getDefiningOp())
184 currentBlock = defOp->getBlock();
185 else
186 currentBlock = value.cast<BlockArgument>().getOwner();
187 toProcess.push_back(currentBlock);
188 visited.insert(currentBlock);
189
190 // Start with all associated blocks
191 for (OpOperand &use : value.getUses()) {
192 Block *useBlock = use.getOwner()->getBlock();
193 if (visited.insert(useBlock).second)
194 toProcess.push_back(useBlock);
195 }
196
197 while (!toProcess.empty()) {
198 // Get block and block liveness information.
199 Block *block = toProcess.back();
200 toProcess.pop_back();
201 const LivenessBlockInfo *blockInfo = getLiveness(block);
202
203 // Note that start and end will be in the same block.
204 Operation *start = blockInfo->getStartOperation(value);
205 Operation *end = blockInfo->getEndOperation(value, start);
206
207 result.push_back(start);
208 while (start != end) {
209 start = start->getNextNode();
210 result.push_back(start);
211 }
212
213 for (Block *successor : block->getSuccessors()) {
214 if (getLiveness(successor)->isLiveIn(value) &&
215 visited.insert(successor).second)
216 toProcess.push_back(successor);
217 }
218 }
219
220 return result;
221 }
222
223 /// Gets liveness info (if any) for the block.
getLiveness(Block * block) const224 const LivenessBlockInfo *Liveness::getLiveness(Block *block) const {
225 auto it = blockMapping.find(block);
226 return it == blockMapping.end() ? nullptr : &it->second;
227 }
228
229 /// Returns a reference to a set containing live-in values.
getLiveIn(Block * block) const230 const Liveness::ValueSetT &Liveness::getLiveIn(Block *block) const {
231 return getLiveness(block)->in();
232 }
233
234 /// Returns a reference to a set containing live-out values.
getLiveOut(Block * block) const235 const Liveness::ValueSetT &Liveness::getLiveOut(Block *block) const {
236 return getLiveness(block)->out();
237 }
238
239 /// Returns true if `value` is not live after `operation`.
isDeadAfter(Value value,Operation * operation) const240 bool Liveness::isDeadAfter(Value value, Operation *operation) const {
241 Block *block = operation->getBlock();
242 const LivenessBlockInfo *blockInfo = getLiveness(block);
243
244 // The given value escapes the associated block.
245 if (blockInfo->isLiveOut(value))
246 return false;
247
248 Operation *endOperation = blockInfo->getEndOperation(value, operation);
249 // If the operation is a real user of `value` the first check is sufficient.
250 // If not, we will have to test whether the end operation is executed before
251 // the given operation in the block.
252 return endOperation == operation || endOperation->isBeforeInBlock(operation);
253 }
254
255 /// Dumps the liveness information in a human readable format.
dump() const256 void Liveness::dump() const { print(llvm::errs()); }
257
258 /// Dumps the liveness information to the given stream.
print(raw_ostream & os) const259 void Liveness::print(raw_ostream &os) const {
260 os << "// ---- Liveness -----\n";
261
262 // Builds unique block/value mappings for testing purposes.
263 DenseMap<Block *, size_t> blockIds;
264 DenseMap<Operation *, size_t> operationIds;
265 DenseMap<Value, size_t> valueIds;
266 operation->walk<WalkOrder::PreOrder>([&](Block *block) {
267 blockIds.insert({block, blockIds.size()});
268 for (BlockArgument argument : block->getArguments())
269 valueIds.insert({argument, valueIds.size()});
270 for (Operation &operation : *block) {
271 operationIds.insert({&operation, operationIds.size()});
272 for (Value result : operation.getResults())
273 valueIds.insert({result, valueIds.size()});
274 }
275 });
276
277 // Local printing helpers
278 auto printValueRef = [&](Value value) {
279 if (value.getDefiningOp())
280 os << "val_" << valueIds[value];
281 else {
282 auto blockArg = value.cast<BlockArgument>();
283 os << "arg" << blockArg.getArgNumber() << "@"
284 << blockIds[blockArg.getOwner()];
285 }
286 os << " ";
287 };
288
289 auto printValueRefs = [&](const ValueSetT &values) {
290 std::vector<Value> orderedValues(values.begin(), values.end());
291 std::sort(orderedValues.begin(), orderedValues.end(),
292 [&](Value left, Value right) {
293 return valueIds[left] < valueIds[right];
294 });
295 for (Value value : orderedValues)
296 printValueRef(value);
297 };
298
299 // Dump information about in and out values.
300 operation->walk<WalkOrder::PreOrder>([&](Block *block) {
301 os << "// - Block: " << blockIds[block] << "\n";
302 const auto *liveness = getLiveness(block);
303 os << "// --- LiveIn: ";
304 printValueRefs(liveness->inValues);
305 os << "\n// --- LiveOut: ";
306 printValueRefs(liveness->outValues);
307 os << "\n";
308
309 // Print liveness intervals.
310 os << "// --- BeginLiveness";
311 for (Operation &op : *block) {
312 if (op.getNumResults() < 1)
313 continue;
314 os << "\n";
315 for (Value result : op.getResults()) {
316 os << "// ";
317 printValueRef(result);
318 os << ":";
319 auto liveOperations = resolveLiveness(result);
320 std::sort(liveOperations.begin(), liveOperations.end(),
321 [&](Operation *left, Operation *right) {
322 return operationIds[left] < operationIds[right];
323 });
324 for (Operation *operation : liveOperations) {
325 os << "\n// ";
326 operation->print(os);
327 }
328 }
329 }
330 os << "\n// --- EndLiveness\n";
331 });
332 os << "// -------------------\n";
333 }
334
335 //===----------------------------------------------------------------------===//
336 // LivenessBlockInfo
337 //===----------------------------------------------------------------------===//
338
339 /// Returns true if the given value is in the live-in set.
isLiveIn(Value value) const340 bool LivenessBlockInfo::isLiveIn(Value value) const {
341 return inValues.count(value);
342 }
343
344 /// Returns true if the given value is in the live-out set.
isLiveOut(Value value) const345 bool LivenessBlockInfo::isLiveOut(Value value) const {
346 return outValues.count(value);
347 }
348
349 /// Gets the start operation for the given value (must be referenced in this
350 /// block).
getStartOperation(Value value) const351 Operation *LivenessBlockInfo::getStartOperation(Value value) const {
352 Operation *definingOp = value.getDefiningOp();
353 // The given value is either live-in or is defined
354 // in the scope of this block.
355 if (isLiveIn(value) || !definingOp)
356 return &block->front();
357 return definingOp;
358 }
359
360 /// Gets the end operation for the given value using the start operation
361 /// provided (must be referenced in this block).
getEndOperation(Value value,Operation * startOperation) const362 Operation *LivenessBlockInfo::getEndOperation(Value value,
363 Operation *startOperation) const {
364 // The given value is either dying in this block or live-out.
365 if (isLiveOut(value))
366 return &block->back();
367
368 // Resolve the last operation (must exist by definition).
369 Operation *endOperation = startOperation;
370 for (Operation *useOp : value.getUsers()) {
371 // Find the associated operation in the current block (if any).
372 useOp = block->findAncestorOpInBlock(*useOp);
373 // Check whether the use is in our block and after the current end
374 // operation.
375 if (useOp && endOperation->isBeforeInBlock(useOp))
376 endOperation = useOp;
377 }
378 return endOperation;
379 }
380