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