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/STLExtras.h"
19#include "llvm/ADT/SetOperations.h"
20#include "llvm/ADT/SetVector.h"
21#include "llvm/Support/raw_ostream.h"
22
23using namespace mlir;
24
25namespace {
26/// Builds and holds block information during the construction phase.
27struct BlockInfoBuilder {
28 using ValueSetT = Liveness::ValueSetT;
29
30 /// Constructs an empty block builder.
31 BlockInfoBuilder() = default;
32
33 /// Fills the block builder with initial liveness information.
34 BlockInfoBuilder(Block *block) : block(block) {
35 auto gatherOutValues = [&](Value value) {
36 // Check whether this value will be in the outValues set (its uses escape
37 // this block). Due to the SSA properties of the program, the uses must
38 // occur after the definition. Therefore, we do not have to check
39 // additional conditions to detect an escaping value.
40 for (Operation *useOp : value.getUsers()) {
41 Block *ownerBlock = useOp->getBlock();
42 // Find an owner block in the current region. Note that a value does not
43 // escape this block if it is used in a nested region.
44 ownerBlock = block->getParent()->findAncestorBlockInRegion(block&: *ownerBlock);
45 assert(ownerBlock && "Use leaves the current parent region");
46 if (ownerBlock != block) {
47 outValues.insert(Ptr: value);
48 break;
49 }
50 }
51 };
52
53 // Mark all block arguments (phis) as defined.
54 for (BlockArgument argument : block->getArguments()) {
55 // Insert value into the set of defined values.
56 defValues.insert(Ptr: argument);
57
58 // Gather all out values of all arguments in the current block.
59 gatherOutValues(argument);
60 }
61
62 // Gather out values of all operations in the current block.
63 for (Operation &operation : *block)
64 for (Value result : operation.getResults())
65 gatherOutValues(result);
66
67 // Mark all nested operation results as defined, and nested operation
68 // operands as used. All defined value will be removed from the used set
69 // at the end.
70 block->walk(callback: [&](Operation *op) {
71 for (Value result : op->getResults())
72 defValues.insert(Ptr: result);
73 for (Value operand : op->getOperands())
74 useValues.insert(Ptr: operand);
75 });
76 llvm::set_subtract(S1&: useValues, S2: defValues);
77 }
78
79 /// Updates live-in information of the current block. To do so it uses the
80 /// default liveness-computation formula: newIn = use union out \ def. The
81 /// methods returns true, if the set has changed (newIn != in), false
82 /// otherwise.
83 bool updateLiveIn() {
84 ValueSetT newIn = useValues;
85 llvm::set_union(S1&: newIn, S2: outValues);
86 llvm::set_subtract(S1&: newIn, S2: defValues);
87
88 // It is sufficient to check the set sizes (instead of their contents) since
89 // the live-in set can only grow monotonically during all update operations.
90 if (newIn.size() == inValues.size())
91 return false;
92
93 inValues = std::move(newIn);
94 return true;
95 }
96
97 /// Updates live-out information of the current block. It iterates over all
98 /// successors and unifies their live-in values with the current live-out
99 /// values.
100 void updateLiveOut(const DenseMap<Block *, BlockInfoBuilder> &builders) {
101 for (Block *succ : block->getSuccessors()) {
102 const BlockInfoBuilder &builder = builders.find(Val: succ)->second;
103 llvm::set_union(S1&: outValues, S2: builder.inValues);
104 }
105 }
106
107 /// The current block.
108 Block *block{nullptr};
109
110 /// The set of all live in values.
111 ValueSetT inValues;
112
113 /// The set of all live out values.
114 ValueSetT outValues;
115
116 /// The set of all defined values.
117 ValueSetT defValues;
118
119 /// The set of all used values.
120 ValueSetT useValues;
121};
122} // namespace
123
124/// Builds the internal liveness block mapping.
125static void buildBlockMapping(Operation *operation,
126 DenseMap<Block *, BlockInfoBuilder> &builders) {
127 SetVector<Block *> toProcess;
128
129 operation->walk<WalkOrder::PreOrder>(callback: [&](Block *block) {
130 BlockInfoBuilder &builder =
131 builders.try_emplace(Key: block, Args&: block).first->second;
132
133 if (builder.updateLiveIn())
134 toProcess.insert(Start: block->pred_begin(), End: block->pred_end());
135 });
136
137 // Propagate the in and out-value sets (fixpoint iteration).
138 while (!toProcess.empty()) {
139 Block *current = toProcess.pop_back_val();
140 BlockInfoBuilder &builder = builders[current];
141
142 // Update the current out values.
143 builder.updateLiveOut(builders);
144
145 // Compute (potentially) updated live in values.
146 if (builder.updateLiveIn())
147 toProcess.insert(Start: current->pred_begin(), End: current->pred_end());
148 }
149}
150
151//===----------------------------------------------------------------------===//
152// Liveness
153//===----------------------------------------------------------------------===//
154
155/// Creates a new Liveness analysis that computes liveness information for all
156/// associated regions.
157Liveness::Liveness(Operation *op) : operation(op) { build(); }
158
159/// Initializes the internal mappings.
160void Liveness::build() {
161 // Build internal block mapping.
162 DenseMap<Block *, BlockInfoBuilder> builders;
163 buildBlockMapping(operation, builders);
164
165 // Store internal block data.
166 for (auto &entry : builders) {
167 BlockInfoBuilder &builder = entry.second;
168 LivenessBlockInfo &info = blockMapping[entry.first];
169
170 info.block = builder.block;
171 info.inValues = std::move(builder.inValues);
172 info.outValues = std::move(builder.outValues);
173 }
174}
175
176/// Gets liveness info (if any) for the given value.
177Liveness::OperationListT Liveness::resolveLiveness(Value value) const {
178 OperationListT result;
179 SmallPtrSet<Block *, 32> visited;
180 SmallVector<Block *, 8> toProcess;
181
182 // Start with the defining block
183 Block *currentBlock;
184 if (Operation *defOp = value.getDefiningOp())
185 currentBlock = defOp->getBlock();
186 else
187 currentBlock = cast<BlockArgument>(Val&: value).getOwner();
188 toProcess.push_back(Elt: currentBlock);
189 visited.insert(Ptr: currentBlock);
190
191 // Start with all associated blocks
192 for (OpOperand &use : value.getUses()) {
193 Block *useBlock = use.getOwner()->getBlock();
194 if (visited.insert(Ptr: useBlock).second)
195 toProcess.push_back(Elt: useBlock);
196 }
197
198 while (!toProcess.empty()) {
199 // Get block and block liveness information.
200 Block *block = toProcess.back();
201 toProcess.pop_back();
202 const LivenessBlockInfo *blockInfo = getLiveness(block);
203
204 // Note that start and end will be in the same block.
205 Operation *start = blockInfo->getStartOperation(value);
206 Operation *end = blockInfo->getEndOperation(value, startOperation: start);
207
208 result.push_back(x: start);
209 while (start != end) {
210 start = start->getNextNode();
211 result.push_back(x: start);
212 }
213
214 for (Block *successor : block->getSuccessors()) {
215 if (getLiveness(block: successor)->isLiveIn(value) &&
216 visited.insert(Ptr: successor).second)
217 toProcess.push_back(Elt: successor);
218 }
219 }
220
221 return result;
222}
223
224/// Gets liveness info (if any) for the block.
225const LivenessBlockInfo *Liveness::getLiveness(Block *block) const {
226 auto it = blockMapping.find(Val: block);
227 return it == blockMapping.end() ? nullptr : &it->second;
228}
229
230/// Returns a reference to a set containing live-in values.
231const Liveness::ValueSetT &Liveness::getLiveIn(Block *block) const {
232 return getLiveness(block)->in();
233}
234
235/// Returns a reference to a set containing live-out values.
236const Liveness::ValueSetT &Liveness::getLiveOut(Block *block) const {
237 return getLiveness(block)->out();
238}
239
240/// Returns true if `value` is not live after `operation`.
241bool Liveness::isDeadAfter(Value value, Operation *operation) const {
242 Block *block = operation->getBlock();
243 const LivenessBlockInfo *blockInfo = getLiveness(block);
244
245 // The given value escapes the associated block.
246 if (blockInfo->isLiveOut(value))
247 return false;
248
249 Operation *endOperation = blockInfo->getEndOperation(value, startOperation: operation);
250 // If the operation is a real user of `value` the first check is sufficient.
251 // If not, we will have to test whether the end operation is executed before
252 // the given operation in the block.
253 return endOperation == operation || endOperation->isBeforeInBlock(other: operation);
254}
255
256/// Dumps the liveness information in a human readable format.
257void Liveness::dump() const { print(os&: llvm::errs()); }
258
259/// Dumps the liveness information to the given stream.
260void Liveness::print(raw_ostream &os) const {
261 os << "// ---- Liveness -----\n";
262
263 // Builds unique block/value mappings for testing purposes.
264 DenseMap<Block *, size_t> blockIds;
265 DenseMap<Operation *, size_t> operationIds;
266 DenseMap<Value, size_t> valueIds;
267 operation->walk<WalkOrder::PreOrder>(callback: [&](Block *block) {
268 blockIds.insert(KV: {block, blockIds.size()});
269 for (BlockArgument argument : block->getArguments())
270 valueIds.insert(KV: {argument, valueIds.size()});
271 for (Operation &operation : *block) {
272 operationIds.insert(KV: {&operation, operationIds.size()});
273 for (Value result : operation.getResults())
274 valueIds.insert(KV: {result, valueIds.size()});
275 }
276 });
277
278 // Local printing helpers
279 auto printValueRef = [&](Value value) {
280 if (value.getDefiningOp())
281 os << "val_" << valueIds[value];
282 else {
283 auto blockArg = cast<BlockArgument>(Val&: value);
284 os << "arg" << blockArg.getArgNumber() << "@"
285 << blockIds[blockArg.getOwner()];
286 }
287 os << " ";
288 };
289
290 auto printValueRefs = [&](const ValueSetT &values) {
291 std::vector<Value> orderedValues(values.begin(), values.end());
292 llvm::sort(C&: orderedValues, Comp: [&](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>(callback: [&](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 << "// --- BeginLivenessIntervals";
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(value: result);
320 llvm::sort(C&: liveOperations, Comp: [&](Operation *left, Operation *right) {
321 return operationIds[left] < operationIds[right];
322 });
323 for (Operation *operation : liveOperations) {
324 os << "\n// ";
325 operation->print(os);
326 }
327 }
328 }
329 os << "\n// --- EndLivenessIntervals\n";
330
331 // Print currently live values.
332 os << "// --- BeginCurrentlyLive\n";
333 for (Operation &op : *block) {
334 auto currentlyLive = liveness->currentlyLiveValues(op: &op);
335 if (currentlyLive.empty())
336 continue;
337 os << "// ";
338 op.print(os);
339 os << " [";
340 printValueRefs(currentlyLive);
341 os << "\b]\n";
342 }
343 os << "// --- EndCurrentlyLive\n";
344 });
345 os << "// -------------------\n";
346}
347
348//===----------------------------------------------------------------------===//
349// LivenessBlockInfo
350//===----------------------------------------------------------------------===//
351
352/// Returns true if the given value is in the live-in set.
353bool LivenessBlockInfo::isLiveIn(Value value) const {
354 return inValues.count(Ptr: value);
355}
356
357/// Returns true if the given value is in the live-out set.
358bool LivenessBlockInfo::isLiveOut(Value value) const {
359 return outValues.count(Ptr: value);
360}
361
362/// Gets the start operation for the given value (must be referenced in this
363/// block).
364Operation *LivenessBlockInfo::getStartOperation(Value value) const {
365 Operation *definingOp = value.getDefiningOp();
366 // The given value is either live-in or is defined
367 // in the scope of this block.
368 if (isLiveIn(value) || !definingOp)
369 return &block->front();
370 return definingOp;
371}
372
373/// Gets the end operation for the given value using the start operation
374/// provided (must be referenced in this block).
375Operation *LivenessBlockInfo::getEndOperation(Value value,
376 Operation *startOperation) const {
377 // The given value is either dying in this block or live-out.
378 if (isLiveOut(value))
379 return &block->back();
380
381 // Resolve the last operation (must exist by definition).
382 Operation *endOperation = startOperation;
383 for (Operation *useOp : value.getUsers()) {
384 // Find the associated operation in the current block (if any).
385 useOp = block->findAncestorOpInBlock(op&: *useOp);
386 // Check whether the use is in our block and after the current end
387 // operation.
388 if (useOp && endOperation->isBeforeInBlock(other: useOp))
389 endOperation = useOp;
390 }
391 return endOperation;
392}
393
394/// Return the values that are currently live as of the given operation.
395LivenessBlockInfo::ValueSetT
396LivenessBlockInfo::currentlyLiveValues(Operation *op) const {
397 ValueSetT liveSet;
398
399 // Given a value, check which ops are within its live range. For each of
400 // those ops, add the value to the set of live values as-of that op.
401 auto addValueToCurrentlyLiveSets = [&](Value value) {
402 // Determine the live range of this value inside this block.
403 Operation *startOfLiveRange = value.getDefiningOp();
404 Operation *endOfLiveRange = nullptr;
405 // If it's a live in or a block argument, then the start is the beginning
406 // of the block.
407 if (isLiveIn(value) || isa<BlockArgument>(Val: value))
408 startOfLiveRange = &block->front();
409 else
410 startOfLiveRange = block->findAncestorOpInBlock(op&: *startOfLiveRange);
411
412 // If it's a live out, then the end is the back of the block.
413 if (isLiveOut(value))
414 endOfLiveRange = &block->back();
415
416 // We must have at least a startOfLiveRange at this point. Given this, we
417 // can use the existing getEndOperation to find the end of the live range.
418 if (startOfLiveRange && !endOfLiveRange)
419 endOfLiveRange = getEndOperation(value, startOperation: startOfLiveRange);
420
421 assert(endOfLiveRange && "Must have endOfLiveRange at this point!");
422 // If this op is within the live range, insert the value into the set.
423 if (!(op->isBeforeInBlock(other: startOfLiveRange) ||
424 endOfLiveRange->isBeforeInBlock(other: op)))
425 liveSet.insert(Ptr: value);
426 };
427
428 // Handle block arguments if any.
429 for (Value arg : block->getArguments())
430 addValueToCurrentlyLiveSets(arg);
431
432 // Handle live-ins. Between the live ins and all the op results that gives us
433 // every value in the block.
434 for (Value in : inValues)
435 addValueToCurrentlyLiveSets(in);
436
437 // Now walk the block and handle all values used in the block and values
438 // defined by the block.
439 for (Operation &walkOp :
440 llvm::make_range(block->begin(), ++op->getIterator()))
441 for (auto result : walkOp.getResults())
442 addValueToCurrentlyLiveSets(result);
443
444 return liveSet;
445}
446

source code of mlir/lib/Analysis/Liveness.cpp