1//===- SparseAnalysis.cpp - Sparse data-flow analysis ---------------------===//
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#include "mlir/Analysis/DataFlow/SparseAnalysis.h"
10#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
11#include "mlir/Analysis/DataFlowFramework.h"
12#include "mlir/IR/Attributes.h"
13#include "mlir/IR/Operation.h"
14#include "mlir/IR/Region.h"
15#include "mlir/IR/SymbolTable.h"
16#include "mlir/IR/Value.h"
17#include "mlir/IR/ValueRange.h"
18#include "mlir/Interfaces/CallInterfaces.h"
19#include "mlir/Interfaces/ControlFlowInterfaces.h"
20#include "mlir/Support/LLVM.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/Support/DebugLog.h"
23#include <cassert>
24#include <optional>
25
26using namespace mlir;
27using namespace mlir::dataflow;
28
29#define DEBUG_TYPE "dataflow"
30
31//===----------------------------------------------------------------------===//
32// AbstractSparseLattice
33//===----------------------------------------------------------------------===//
34
35void AbstractSparseLattice::onUpdate(DataFlowSolver *solver) const {
36 AnalysisState::onUpdate(solver);
37
38 // Push all users of the value to the queue.
39 for (Operation *user : cast<Value>(Val: anchor).getUsers())
40 for (DataFlowAnalysis *analysis : useDefSubscribers)
41 solver->enqueue(item: {solver->getProgramPointAfter(op: user), analysis});
42}
43
44//===----------------------------------------------------------------------===//
45// AbstractSparseForwardDataFlowAnalysis
46//===----------------------------------------------------------------------===//
47
48AbstractSparseForwardDataFlowAnalysis::AbstractSparseForwardDataFlowAnalysis(
49 DataFlowSolver &solver)
50 : DataFlowAnalysis(solver) {
51 registerAnchorKind<CFGEdge>();
52}
53
54LogicalResult
55AbstractSparseForwardDataFlowAnalysis::initialize(Operation *top) {
56 // Mark the entry block arguments as having reached their pessimistic
57 // fixpoints.
58 for (Region &region : top->getRegions()) {
59 if (region.empty())
60 continue;
61 for (Value argument : region.front().getArguments())
62 setToEntryState(getLatticeElement(value: argument));
63 }
64
65 return initializeRecursively(op: top);
66}
67
68LogicalResult
69AbstractSparseForwardDataFlowAnalysis::initializeRecursively(Operation *op) {
70 LDBG() << "Initializing recursively for operation: "
71 << OpWithFlags(op, OpPrintingFlags().skipRegions());
72
73 // Initialize the analysis by visiting every owner of an SSA value (all
74 // operations and blocks).
75 if (failed(Result: visitOperation(op))) {
76 LDBG() << "Failed to visit operation: "
77 << OpWithFlags(op, OpPrintingFlags().skipRegions());
78 return failure();
79 }
80
81 for (Region &region : op->getRegions()) {
82 LDBG() << "Processing region with " << region.getBlocks().size()
83 << " blocks";
84 for (Block &block : region) {
85 LDBG() << "Processing block with " << block.getNumArguments()
86 << " arguments";
87 getOrCreate<Executable>(anchor: getProgramPointBefore(block: &block))
88 ->blockContentSubscribe(analysis: this);
89 visitBlock(block: &block);
90 for (Operation &op : block) {
91 LDBG() << "Recursively initializing nested operation: "
92 << OpWithFlags(&op, OpPrintingFlags().skipRegions());
93 if (failed(Result: initializeRecursively(op: &op))) {
94 LDBG() << "Failed to initialize nested operation: "
95 << OpWithFlags(&op, OpPrintingFlags().skipRegions());
96 return failure();
97 }
98 }
99 }
100 }
101
102 LDBG() << "Successfully completed recursive initialization for operation: "
103 << OpWithFlags(op, OpPrintingFlags().skipRegions());
104 return success();
105}
106
107LogicalResult
108AbstractSparseForwardDataFlowAnalysis::visit(ProgramPoint *point) {
109 if (!point->isBlockStart())
110 return visitOperation(op: point->getPrevOp());
111 visitBlock(block: point->getBlock());
112 return success();
113}
114
115LogicalResult
116AbstractSparseForwardDataFlowAnalysis::visitOperation(Operation *op) {
117 // Exit early on operations with no results.
118 if (op->getNumResults() == 0)
119 return success();
120
121 // If the containing block is not executable, bail out.
122 if (op->getBlock() != nullptr &&
123 !getOrCreate<Executable>(anchor: getProgramPointBefore(block: op->getBlock()))->isLive())
124 return success();
125
126 // Get the result lattices.
127 SmallVector<AbstractSparseLattice *> resultLattices;
128 resultLattices.reserve(N: op->getNumResults());
129 for (Value result : op->getResults()) {
130 AbstractSparseLattice *resultLattice = getLatticeElement(value: result);
131 resultLattices.push_back(Elt: resultLattice);
132 }
133
134 // The results of a region branch operation are determined by control-flow.
135 if (auto branch = dyn_cast<RegionBranchOpInterface>(Val: op)) {
136 visitRegionSuccessors(point: getProgramPointAfter(op: branch), branch,
137 successor: RegionSuccessor(branch.getOperation()),
138 lattices: resultLattices);
139 return success();
140 }
141
142 // Grab the lattice elements of the operands.
143 SmallVector<const AbstractSparseLattice *> operandLattices;
144 operandLattices.reserve(N: op->getNumOperands());
145 for (Value operand : op->getOperands()) {
146 AbstractSparseLattice *operandLattice = getLatticeElement(value: operand);
147 operandLattice->useDefSubscribe(analysis: this);
148 operandLattices.push_back(Elt: operandLattice);
149 }
150
151 if (auto call = dyn_cast<CallOpInterface>(Val: op))
152 return visitCallOperation(call, operandLattices, resultLattices);
153
154 // Invoke the operation transfer function.
155 return visitOperationImpl(op, operandLattices, resultLattices);
156}
157
158void AbstractSparseForwardDataFlowAnalysis::visitBlock(Block *block) {
159 // Exit early on blocks with no arguments.
160 if (block->getNumArguments() == 0)
161 return;
162
163 // If the block is not executable, bail out.
164 if (!getOrCreate<Executable>(anchor: getProgramPointBefore(block))->isLive())
165 return;
166
167 // Get the argument lattices.
168 SmallVector<AbstractSparseLattice *> argLattices;
169 argLattices.reserve(N: block->getNumArguments());
170 for (BlockArgument argument : block->getArguments()) {
171 AbstractSparseLattice *argLattice = getLatticeElement(value: argument);
172 argLattices.push_back(Elt: argLattice);
173 }
174
175 // The argument lattices of entry blocks are set by region control-flow or the
176 // callgraph.
177 if (block->isEntryBlock()) {
178 // Check if this block is the entry block of a callable region.
179 auto callable = dyn_cast<CallableOpInterface>(Val: block->getParentOp());
180 if (callable && callable.getCallableRegion() == block->getParent())
181 return visitCallableOperation(callable, argLattices);
182
183 // Check if the lattices can be determined from region control flow.
184 if (auto branch = dyn_cast<RegionBranchOpInterface>(Val: block->getParentOp())) {
185 return visitRegionSuccessors(point: getProgramPointBefore(block), branch,
186 successor: block->getParent(), lattices: argLattices);
187 }
188
189 // All block arguments are non-successor-inputs.
190 return visitNonControlFlowArgumentsImpl(point: getProgramPointBefore(block),
191 op: block->getParentOp(),
192 successor: RegionSuccessor(block->getParent()),
193 nonSuccessorInputs: block->getArguments(), nonSuccessorInputLattices: argLattices);
194 }
195
196 // Iterate over the predecessors of the non-entry block.
197 for (Block::pred_iterator it = block->pred_begin(), e = block->pred_end();
198 it != e; ++it) {
199 Block *predecessor = *it;
200
201 // If the edge from the predecessor block to the current block is not live,
202 // bail out.
203 auto *edgeExecutable =
204 getOrCreate<Executable>(anchor: getLatticeAnchor<CFGEdge>(args&: predecessor, args&: block));
205 edgeExecutable->blockContentSubscribe(analysis: this);
206 if (!edgeExecutable->isLive())
207 continue;
208
209 // Check if we can reason about the data-flow from the predecessor.
210 if (auto branch =
211 dyn_cast<BranchOpInterface>(Val: predecessor->getTerminator())) {
212 SuccessorOperands operands =
213 branch.getSuccessorOperands(index: it.getSuccessorIndex());
214 for (auto [idx, lattice] : llvm::enumerate(First&: argLattices)) {
215 if (Value operand = operands[idx]) {
216 join(lhs: lattice,
217 rhs: *getLatticeElementFor(point: getProgramPointBefore(block), value: operand));
218 } else {
219 // Conservatively consider internally produced arguments as entry
220 // points.
221 setAllToEntryStates(lattice);
222 }
223 }
224 } else {
225 return setAllToEntryStates(argLattices);
226 }
227 }
228}
229
230LogicalResult AbstractSparseForwardDataFlowAnalysis::visitCallOperation(
231 CallOpInterface call,
232 ArrayRef<const AbstractSparseLattice *> operandLattices,
233 ArrayRef<AbstractSparseLattice *> resultLattices) {
234 // If the call operation is to an external function, attempt to infer the
235 // results from the call arguments.
236 auto isExternalCallable = [&]() {
237 auto callable =
238 dyn_cast_if_present<CallableOpInterface>(Val: call.resolveCallable());
239 return callable && !callable.getCallableRegion();
240 };
241 if (!getSolverConfig().isInterprocedural() || isExternalCallable()) {
242 visitExternalCallImpl(call, argumentLattices: operandLattices, resultLattices);
243 return success();
244 }
245
246 // Otherwise, the results of a call operation are determined by the
247 // callgraph.
248 const auto *predecessors = getOrCreateFor<PredecessorState>(
249 dependent: getProgramPointAfter(op: call), anchor: getProgramPointAfter(op: call));
250 // If not all return sites are known, then conservatively assume we can't
251 // reason about the data-flow.
252 if (!predecessors->allPredecessorsKnown()) {
253 setAllToEntryStates(resultLattices);
254 return success();
255 }
256
257 // Only the forwarded results receive the values returned by the callee. Any
258 // other result is produced by the call operation itself and nothing is known
259 // about it here.
260 ResultRange forwardedResults = call.getForwardedResults();
261 unsigned firstForwarded = forwardedResults.empty()
262 ? resultLattices.size()
263 : forwardedResults[0].getResultNumber();
264 setAllToEntryStates(resultLattices.take_front(N: firstForwarded));
265 setAllToEntryStates(
266 resultLattices.drop_front(N: firstForwarded + forwardedResults.size()));
267 ArrayRef<AbstractSparseLattice *> forwardedResultLattices =
268 resultLattices.slice(N: firstForwarded, M: forwardedResults.size());
269
270 for (Operation *predecessor : predecessors->getKnownPredecessors())
271 for (auto &&[operand, resLattice] :
272 llvm::zip_equal(t: predecessor->getOperands(), u&: forwardedResultLattices))
273 join(lhs: resLattice,
274 rhs: *getLatticeElementFor(point: getProgramPointAfter(op: call), value: operand));
275 return success();
276}
277
278void AbstractSparseForwardDataFlowAnalysis::visitCallableOperation(
279 CallableOpInterface callable,
280 ArrayRef<AbstractSparseLattice *> argLattices) {
281 Block *entryBlock = &callable.getCallableRegion()->front();
282 const auto *callsites = getOrCreateFor<PredecessorState>(
283 dependent: getProgramPointBefore(block: entryBlock), anchor: getProgramPointAfter(op: callable));
284 // If not all callsites are known, conservatively mark all lattices as
285 // having reached their pessimistic fixpoints.
286 if (!callsites->allPredecessorsKnown() ||
287 !getSolverConfig().isInterprocedural()) {
288 return setAllToEntryStates(argLattices);
289 }
290 for (Operation *callsite : callsites->getKnownPredecessors()) {
291 auto call = cast<CallOpInterface>(Val: callsite);
292 for (auto it : llvm::zip(t: call.getArgOperands(), u&: argLattices))
293 join(lhs: std::get<1>(t&: it),
294 rhs: *getLatticeElementFor(point: getProgramPointBefore(block: entryBlock),
295 value: std::get<0>(t&: it)));
296 }
297}
298
299void AbstractSparseForwardDataFlowAnalysis::visitRegionSuccessors(
300 ProgramPoint *point, RegionBranchOpInterface branch,
301 RegionSuccessor successor, ArrayRef<AbstractSparseLattice *> lattices) {
302 const auto *predecessors = getOrCreateFor<PredecessorState>(dependent: point, anchor: point);
303 assert(predecessors->allPredecessorsKnown() &&
304 "unexpected unresolved region successors");
305
306 for (Operation *op : predecessors->getKnownPredecessors()) {
307 // Get the incoming successor operands.
308 std::optional<OperandRange> operands;
309
310 // Check if the predecessor is the parent op.
311 if (op == branch) {
312 operands = branch.getEntrySuccessorOperands(successor);
313 // Otherwise, try to deduce the operands from a region return-like op.
314 } else if (auto regionTerminator =
315 dyn_cast<RegionBranchTerminatorOpInterface>(Val: op)) {
316 operands = regionTerminator.getSuccessorOperands(successor);
317 }
318
319 if (!operands) {
320 // We can't reason about the data-flow.
321 return setAllToEntryStates(lattices);
322 }
323
324 ValueRange inputs = predecessors->getSuccessorInputs(predecessor: op);
325 assert(inputs.size() == operands->size() &&
326 "expected the same number of successor inputs as operands");
327
328 auto valueToLattices = [&](Value v) { return getLatticeElement(value: v); };
329 unsigned firstIndex = 0;
330 if (inputs.size() != lattices.size()) {
331 if (!point->isBlockStart()) {
332 if (!inputs.empty())
333 firstIndex = cast<OpResult>(Val: inputs.front()).getResultNumber();
334 SmallVector<Value> nonSuccessorInputs =
335 branch.getNonSuccessorInputs(successor);
336 SmallVector<AbstractSparseLattice *> nonSuccessorInputLattices =
337 llvm::map_to_vector(C&: nonSuccessorInputs, F&: valueToLattices);
338 visitNonControlFlowArgumentsImpl(point, op: branch, successor,
339 nonSuccessorInputs,
340 nonSuccessorInputLattices);
341 } else {
342 if (!inputs.empty())
343 firstIndex = cast<BlockArgument>(Val: inputs.front()).getArgNumber();
344 Region *region = point->getBlock()->getParent();
345 SmallVector<Value> nonSuccessorInputs =
346 branch.getNonSuccessorInputs(successor: RegionSuccessor(region));
347 SmallVector<AbstractSparseLattice *> nonSuccessorInputLattices =
348 llvm::map_to_vector(C&: nonSuccessorInputs, F&: valueToLattices);
349 visitNonControlFlowArgumentsImpl(point, op: branch, successor: RegionSuccessor(region),
350 nonSuccessorInputs,
351 nonSuccessorInputLattices);
352 }
353 }
354
355 for (auto [lattice, operand] :
356 llvm::zip(t: lattices.drop_front(N: firstIndex), u&: *operands))
357 join(lhs: lattice, rhs: *getLatticeElementFor(point, value: operand));
358 }
359}
360
361const AbstractSparseLattice *
362AbstractSparseForwardDataFlowAnalysis::getLatticeElementFor(ProgramPoint *point,
363 Value value) {
364 AbstractSparseLattice *state = getLatticeElement(value);
365 addDependency(state, point);
366 return state;
367}
368
369void AbstractSparseForwardDataFlowAnalysis::setAllToEntryStates(
370 ArrayRef<AbstractSparseLattice *> lattices) {
371 for (AbstractSparseLattice *lattice : lattices)
372 setToEntryState(lattice);
373}
374
375void AbstractSparseForwardDataFlowAnalysis::join(
376 AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs) {
377 propagateIfChanged(state: lhs, changed: lhs->join(rhs));
378}
379
380//===----------------------------------------------------------------------===//
381// AbstractSparseBackwardDataFlowAnalysis
382//===----------------------------------------------------------------------===//
383
384AbstractSparseBackwardDataFlowAnalysis::AbstractSparseBackwardDataFlowAnalysis(
385 DataFlowSolver &solver, SymbolTableCollection &symbolTable)
386 : DataFlowAnalysis(solver), symbolTable(symbolTable) {
387 registerAnchorKind<CFGEdge>();
388}
389
390LogicalResult
391AbstractSparseBackwardDataFlowAnalysis::initialize(Operation *top) {
392 return initializeRecursively(op: top);
393}
394
395LogicalResult
396AbstractSparseBackwardDataFlowAnalysis::initializeRecursively(Operation *op) {
397 if (failed(Result: visitOperation(op)))
398 return failure();
399
400 for (Region &region : op->getRegions()) {
401 for (Block &block : region) {
402 getOrCreate<Executable>(anchor: getProgramPointBefore(block: &block))
403 ->blockContentSubscribe(analysis: this);
404 // Initialize ops in reverse order, so we can do as much initial
405 // propagation as possible without having to go through the
406 // solver queue.
407 for (auto it = block.rbegin(); it != block.rend(); it++)
408 if (failed(Result: initializeRecursively(op: &*it)))
409 return failure();
410 }
411 }
412 return success();
413}
414
415LogicalResult
416AbstractSparseBackwardDataFlowAnalysis::visit(ProgramPoint *point) {
417 // For backward dataflow, we don't have to do any work for the blocks
418 // themselves. CFG edges between blocks are processed by the BranchOp
419 // logic in `visitOperation`, and entry blocks for functions are tied
420 // to the CallOp arguments by visitOperation.
421 if (point->isBlockStart())
422 return success();
423 return visitOperation(op: point->getPrevOp());
424}
425
426SmallVector<AbstractSparseLattice *>
427AbstractSparseBackwardDataFlowAnalysis::getLatticeElements(ValueRange values) {
428 SmallVector<AbstractSparseLattice *> resultLattices;
429 resultLattices.reserve(N: values.size());
430 for (Value result : values) {
431 AbstractSparseLattice *resultLattice = getLatticeElement(value: result);
432 resultLattices.push_back(Elt: resultLattice);
433 }
434 return resultLattices;
435}
436
437SmallVector<const AbstractSparseLattice *>
438AbstractSparseBackwardDataFlowAnalysis::getLatticeElementsFor(
439 ProgramPoint *point, ValueRange values) {
440 SmallVector<const AbstractSparseLattice *> resultLattices;
441 resultLattices.reserve(N: values.size());
442 for (Value result : values) {
443 const AbstractSparseLattice *resultLattice =
444 getLatticeElementFor(point, value: result);
445 resultLattices.push_back(Elt: resultLattice);
446 }
447 return resultLattices;
448}
449
450static MutableArrayRef<OpOperand> operandsToOpOperands(OperandRange &operands) {
451 return MutableArrayRef<OpOperand>(operands.getBase(), operands.size());
452}
453
454LogicalResult
455AbstractSparseBackwardDataFlowAnalysis::visitOperation(Operation *op) {
456 LDBG() << "Visiting operation: "
457 << OpWithFlags(op, OpPrintingFlags().skipRegions()) << " with "
458 << op->getNumOperands() << " operands and " << op->getNumResults()
459 << " results";
460
461 // If we're in a dead block, bail out.
462 if (op->getBlock() != nullptr &&
463 !getOrCreate<Executable>(anchor: getProgramPointBefore(block: op->getBlock()))
464 ->isLive()) {
465 LDBG() << "Operation is in dead block, bailing out";
466 return success();
467 }
468
469 LDBG() << "Creating lattice elements for " << op->getNumOperands()
470 << " operands and " << op->getNumResults() << " results";
471 SmallVector<AbstractSparseLattice *> operandLattices =
472 getLatticeElements(values: op->getOperands());
473 SmallVector<const AbstractSparseLattice *> resultLattices =
474 getLatticeElementsFor(point: getProgramPointAfter(op), values: op->getResults());
475
476 // Block arguments of region branch operations flow back into the operands
477 // of the parent op
478 if (auto branch = dyn_cast<RegionBranchOpInterface>(Val: op)) {
479 LDBG() << "Processing RegionBranchOpInterface operation";
480 visitRegionSuccessors(branch, operands: operandLattices);
481 return success();
482 }
483
484 if (auto branch = dyn_cast<BranchOpInterface>(Val: op)) {
485 LDBG() << "Processing BranchOpInterface operation with "
486 << op->getNumSuccessors() << " successors";
487
488 // Block arguments of successor blocks flow back into our operands.
489
490 // We remember all operands not forwarded to any block in a BitVector.
491 // We can't just cut out a range here, since the non-forwarded ops might
492 // be non-contiguous (if there's more than one successor).
493 BitVector unaccounted(op->getNumOperands(), true);
494
495 for (auto [index, block] : llvm::enumerate(First: op->getSuccessors())) {
496 SuccessorOperands successorOperands = branch.getSuccessorOperands(index);
497 OperandRange forwarded = successorOperands.getForwardedOperands();
498 if (!forwarded.empty()) {
499 MutableArrayRef<OpOperand> operands = op->getOpOperands().slice(
500 N: forwarded.getBeginOperandIndex(), M: forwarded.size());
501 for (OpOperand &operand : operands) {
502 unaccounted.reset(Idx: operand.getOperandNumber());
503 if (std::optional<BlockArgument> blockArg =
504 detail::getBranchSuccessorArgument(
505 operands: successorOperands, operandIndex: operand.getOperandNumber(), successor: block)) {
506 meet(lhs: getLatticeElement(value: operand.get()),
507 rhs: *getLatticeElementFor(point: getProgramPointAfter(op), value: *blockArg));
508 }
509 }
510 }
511 }
512 // Operands not forwarded to successor blocks are typically parameters
513 // of the branch operation itself (for example the boolean for if/else).
514 for (int index : unaccounted.set_bits()) {
515 OpOperand &operand = op->getOpOperand(idx: index);
516 visitBranchOperand(operand);
517 }
518 return success();
519 }
520
521 // For function calls, connect the arguments of the entry blocks to the
522 // operands of the call op that are forwarded to these arguments.
523 if (auto call = dyn_cast<CallOpInterface>(Val: op)) {
524 LDBG() << "Processing CallOpInterface operation";
525 Operation *callableOp = call.resolveCallableInTable(symbolTable: &symbolTable);
526 if (auto callable = dyn_cast_or_null<CallableOpInterface>(Val: callableOp)) {
527 // Not all operands of a call op forward to arguments. Such operands are
528 // stored in `unaccounted`.
529 BitVector unaccounted(op->getNumOperands(), true);
530
531 // If the call invokes an external function (or a function treated as
532 // external due to config), defer to the corresponding extension hook.
533 // By default, it just does `visitCallOperand` for all operands.
534 OperandRange argOperands = call.getArgOperands();
535 MutableArrayRef<OpOperand> argOpOperands =
536 operandsToOpOperands(operands&: argOperands);
537 Region *region = callable.getCallableRegion();
538 if (!region || region->empty() ||
539 !getSolverConfig().isInterprocedural()) {
540 visitExternalCallImpl(call, operandLattices, resultLattices);
541 return success();
542 }
543
544 // Otherwise, propagate information from the entry point of the function
545 // back to operands whenever possible.
546 Block &block = region->front();
547 for (auto [blockArg, argOpOperand] :
548 llvm::zip(t: block.getArguments(), u&: argOpOperands)) {
549 meet(lhs: getLatticeElement(value: argOpOperand.get()),
550 rhs: *getLatticeElementFor(point: getProgramPointAfter(op), value: blockArg));
551 unaccounted.reset(Idx: argOpOperand.getOperandNumber());
552 }
553
554 // Handle the operands of the call op that aren't forwarded to any
555 // arguments.
556 for (int index : unaccounted.set_bits()) {
557 OpOperand &opOperand = op->getOpOperand(idx: index);
558 visitCallOperand(operand&: opOperand);
559 }
560 return success();
561 }
562 }
563
564 // When the region of an op implementing `RegionBranchOpInterface` has a
565 // terminator implementing `RegionBranchTerminatorOpInterface` or a
566 // return-like terminator, the region's successors' arguments flow back into
567 // the "successor operands" of this terminator.
568 //
569 // A successor operand with respect to an op implementing
570 // `RegionBranchOpInterface` is an operand that is forwarded to a region
571 // successor's input. There are two types of successor operands: the operands
572 // of this op itself and the operands of the terminators of the regions of
573 // this op.
574 if (auto terminator = dyn_cast<RegionBranchTerminatorOpInterface>(Val: op)) {
575 LDBG() << "Processing RegionBranchTerminatorOpInterface operation";
576 if (auto branch = dyn_cast<RegionBranchOpInterface>(Val: op->getParentOp())) {
577 visitRegionSuccessorsFromTerminator(terminator, branch);
578 return success();
579 }
580 }
581
582 if (op->hasTrait<OpTrait::ReturnLike>()) {
583 LDBG() << "Processing ReturnLike operation";
584 // Going backwards, the operands of the return are derived from the
585 // results of all CallOps calling this CallableOp.
586 if (auto callable = dyn_cast<CallableOpInterface>(Val: op->getParentOp())) {
587 LDBG() << "Callable parent found, visiting callable operation";
588 return visitCallableOperation(op, callable, operandLattices);
589 }
590 }
591
592 LDBG() << "Using default visitOperationImpl for operation: "
593 << OpWithFlags(op, OpPrintingFlags().skipRegions());
594 return visitOperationImpl(op, operandLattices, resultLattices);
595}
596
597LogicalResult AbstractSparseBackwardDataFlowAnalysis::visitCallableOperation(
598 Operation *op, CallableOpInterface callable,
599 ArrayRef<AbstractSparseLattice *> operandLattices) {
600 const PredecessorState *callsites = getOrCreateFor<PredecessorState>(
601 dependent: getProgramPointAfter(op), anchor: getProgramPointAfter(op: callable));
602 if (callsites->allPredecessorsKnown()) {
603 for (Operation *call : callsites->getKnownPredecessors()) {
604 // Only the forwarded results of the call receive the values returned by
605 // the callee.
606 ResultRange forwardedResults =
607 cast<CallOpInterface>(Val: call).getForwardedResults();
608 SmallVector<const AbstractSparseLattice *> callResultLattices =
609 getLatticeElementsFor(point: getProgramPointAfter(op), values: forwardedResults);
610 for (auto [op, result] : llvm::zip(t&: operandLattices, u&: callResultLattices))
611 meet(lhs: op, rhs: *result);
612 }
613 } else {
614 // If we don't know all the callers, we can't know where the
615 // returned values go. Note that, in particular, this will trigger
616 // for the return ops of any public functions.
617 setAllToExitStates(operandLattices);
618 }
619 return success();
620}
621
622void AbstractSparseBackwardDataFlowAnalysis::visitRegionSuccessors(
623 RegionBranchOpInterface branch,
624 ArrayRef<AbstractSparseLattice *> operandLattices) {
625 // Not all operands are forwarded to a successor. This set can be
626 // non-contiguous in the presence of multiple successors.
627 BitVector unaccounted(branch->getNumOperands(), true);
628 RegionBranchSuccessorMapping mapping;
629 branch.getSuccessorOperandInputMapping(mapping, src: RegionBranchPoint::parent());
630 for (const auto &[operand, inputs] : mapping) {
631 for (Value input : inputs) {
632 meet(lhs: getLatticeElement(value: operand->get()),
633 rhs: *getLatticeElementFor(point: getProgramPointAfter(op: branch), value: input));
634 unaccounted.reset(Idx: operand->getOperandNumber());
635 }
636 }
637 Operation *op = branch.getOperation();
638 SmallVector<RegionSuccessor> successors;
639 SmallVector<Attribute> operands(op->getNumOperands(), nullptr);
640 branch.getEntrySuccessorRegions(operands, regions&: successors);
641 for (RegionSuccessor &successor : successors) {
642 if (successor.isOperation())
643 continue;
644 auto valueToArgument = [](Value value) {
645 return cast<BlockArgument>(Val&: value);
646 };
647 SmallVector<BlockArgument> noControlFlowArguments = llvm::map_to_vector(
648 C: branch.getNonSuccessorInputs(successor), F&: valueToArgument);
649 visitNonControlFlowArguments(successor, arguments: noControlFlowArguments);
650 }
651
652 // All operands not forwarded to regions are typically parameters of the
653 // branch operation itself (for example the boolean for if/else).
654 for (int index : unaccounted.set_bits()) {
655 visitBranchOperand(operand&: branch->getOpOperand(idx: index));
656 }
657}
658
659void AbstractSparseBackwardDataFlowAnalysis::
660 visitRegionSuccessorsFromTerminator(
661 RegionBranchTerminatorOpInterface terminator,
662 RegionBranchOpInterface branch) {
663 assert(terminator->getParentOp() == branch.getOperation() &&
664 "expected `branch` to be the parent op of `terminator`");
665
666 // Not all operands are forwarded to a successor. This set can be
667 // non-contiguous in the presence of multiple successors.
668 BitVector unaccounted(terminator->getNumOperands(), true);
669
670 RegionBranchSuccessorMapping mapping;
671 branch.getSuccessorOperandInputMapping(mapping,
672 src: RegionBranchPoint(terminator));
673 for (const auto &[operand, inputs] : mapping) {
674 for (Value input : inputs) {
675 meet(lhs: getLatticeElement(value: operand->get()),
676 rhs: *getLatticeElementFor(point: getProgramPointAfter(op: terminator), value: input));
677 unaccounted.reset(Idx: operand->getOperandNumber());
678 }
679 }
680
681 // Visit operands of the branch op not forwarded to the next region.
682 // (Like e.g. the boolean of `scf.conditional`)
683 for (int index : unaccounted.set_bits()) {
684 visitBranchOperand(operand&: terminator->getOpOperand(idx: index));
685 }
686}
687
688const AbstractSparseLattice *
689AbstractSparseBackwardDataFlowAnalysis::getLatticeElementFor(
690 ProgramPoint *point, Value value) {
691 AbstractSparseLattice *state = getLatticeElement(value);
692 addDependency(state, point);
693 return state;
694}
695
696void AbstractSparseBackwardDataFlowAnalysis::setAllToExitStates(
697 ArrayRef<AbstractSparseLattice *> lattices) {
698 for (AbstractSparseLattice *lattice : lattices)
699 setToExitState(lattice);
700}
701
702void AbstractSparseBackwardDataFlowAnalysis::meet(
703 AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs) {
704 propagateIfChanged(state: lhs, changed: lhs->meet(rhs));
705}
706