19 #include "llvm/ADT/STLExtras.h"
33 if (isa<RegionBranchOpInterface, CallOpInterface>(op))
45 for (
Block &block : region) {
62 void AbstractDenseForwardDataFlowAnalysis::visitCallOperation(
67 auto isExternalCallable = [&]() {
69 dyn_cast_if_present<CallableOpInterface>(call.resolveCallable());
70 return callable && !callable.getCallableRegion();
77 const auto *predecessors = getOrCreateFor<PredecessorState>(
81 if (!predecessors->allPredecessorsKnown())
84 for (
Operation *predecessor : predecessors->getKnownPredecessors()) {
103 *latticeAtCalleeReturn, latticeAfterCall);
125 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
132 if (
auto call = dyn_cast<CallOpInterface>(op)) {
133 visitCallOperation(call, *before, after);
141 void AbstractDenseForwardDataFlowAnalysis::visitBlock(
Block *block) {
144 if (!getOrCreateFor<Executable>(point, point)->isLive())
154 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
155 if (callable && callable.getCallableRegion() == block->
getParent()) {
156 const auto *callsites = getOrCreateFor<PredecessorState>(
161 if (!callsites->allPredecessorsKnown() ||
164 for (
Operation *callsite : callsites->getKnownPredecessors()) {
177 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp()))
188 Block *predecessor = *it;
189 if (!getOrCreateFor<Executable>(
190 point, getLatticeAnchor<CFGEdge>(predecessor, block))
204 const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
205 assert(predecessors->allPredecessorsKnown() &&
206 "unexpected unresolved region successors");
208 for (
Operation *op : predecessors->getKnownPredecessors()) {
231 std::optional<unsigned> regionFrom =
232 op == branch ? std::optional<unsigned>()
233 : op->getBlock()->getParent()->getRegionNumber();
240 "expected to be visiting the branch itself");
243 if (op->getParentOp() == branch || op == branch) {
245 branch, regionFrom, std::nullopt, *before, after);
247 join(after, *before);
260 if (isa<RegionBranchOpInterface, CallOpInterface>(op))
273 for (
Block &block : region) {
275 for (
Operation &op : llvm::reverse(block)) {
292 void AbstractDenseBackwardDataFlowAnalysis::visitCallOperation(
302 Operation *callee = call.resolveCallableInTable(&symbolTable);
304 auto callable = dyn_cast_or_null<CallableOpInterface>(callee);
309 (!callable.getCallableRegion() || callable.getCallableRegion()->empty()))
316 Region *region = callable.getCallableRegion();
337 latticeAtCalleeEntry, latticeBeforeCall);
357 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
362 if (
auto call = dyn_cast<CallOpInterface>(op)) {
363 visitCallOperation(call, *after, before);
371 void AbstractDenseBackwardDataFlowAnalysis::visitBlock(
Block *block) {
382 auto isExitBlock = [](
Block *b) {
390 return isa_and_nonnull<RegionBranchTerminatorOpInterface>(
393 if (isExitBlock(block)) {
397 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
398 if (callable && callable.getCallableRegion() == block->
getParent()) {
399 const auto *callsites = getOrCreateFor<PredecessorState>(
403 if (!callsites->allPredecessorsKnown() ||
408 for (
Operation *callsite : callsites->getKnownPredecessors()) {
420 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp())) {
421 visitRegionBranchOperation(point, branch, block->
getParent(), before);
432 if (!getOrCreateFor<Executable>(point,
433 getLatticeAnchor<CFGEdge>(block, successor))
443 void AbstractDenseBackwardDataFlowAnalysis::visitRegionBranchOperation(
451 branch.getSuccessorRegions(branchPoint, successors);
454 if (successor.isParent() || successor.getSuccessor()->empty()) {
457 Region *successorRegion = successor.getSuccessor();
458 assert(!successorRegion->
empty() &&
"unexpected empty successor region");
459 Block *successorBlock = &successorRegion->
front();
461 if (!getOrCreateFor<Executable>(point,
Block represents an ordered list of Operations.
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
pred_iterator pred_begin()
SuccessorRange getSuccessors()
Operation * getTerminator()
Get the terminator operation of this block.
bool isEntryBlock()
Return if this block is the entry block in the parent region.
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
ProgramPoint * getProgramPointAfter(Operation *op)
ProgramPoint * getProgramPointBefore(Operation *op)
Get a uniqued program point instance.
const DataFlowConfig & getSolverConfig() const
Return the configuration of the solver used for this analysis.
This class provides the API for ops that are known to be terminators.
Operation is the basic unit of execution within MLIR.
std::enable_if_t< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT > walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one),...
Block * getBlock()
Returns the operation block that contains this operation.
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Implement a predecessor iterator for blocks.
This class represents a point being branched from in the methods of the RegionBranchOpInterface.
static constexpr RegionBranchPoint parent()
Returns an instance of RegionBranchPoint representing the parent operation.
This class represents a successor of a region.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
unsigned getRegionNumber()
Return the number of this region in the parent operation.
virtual void setToExitState(AbstractDenseLattice *lattice)=0
Set the dense lattice before at the control flow exit point and propagate the update if it changed.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting every program point whose execution may modify the program state;...
virtual void visitCallControlFlowTransfer(CallOpInterface call, CallControlFlowAction action, const AbstractDenseLattice &after, AbstractDenseLattice *before)
Propagate the dense lattice backwards along the call control flow edge, which can be either entering ...
virtual const AbstractDenseLattice * getLatticeFor(ProgramPoint *dependent, LatticeAnchor anchor)=0
Get the dense lattice on the given lattice anchor and add dependent as its dependency.
virtual void initializeEquivalentLatticeAnchor(Operation *top) override
Initialize lattice anchor equivalence class from the provided top-level operation.
virtual void buildOperationEquivalentLatticeAnchor(Operation *op)
Visit an operation.
LogicalResult visit(ProgramPoint *point) override
Visit a program point that modifies the state of the program.
virtual LogicalResult visitOperationImpl(Operation *op, const AbstractDenseLattice &after, AbstractDenseLattice *before)=0
Propagate the dense lattice after the execution of an operation to the lattice before its execution.
void meet(AbstractDenseLattice *lhs, const AbstractDenseLattice &rhs)
Meet a lattice with another lattice and propagate an update if it changed.
virtual LogicalResult processOperation(Operation *op)
Visit an operation.
virtual AbstractDenseLattice * getLattice(LatticeAnchor anchor)=0
Get the dense lattice before the execution of the lattice anchor.
virtual void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch, RegionBranchPoint regionFrom, RegionBranchPoint regionTo, const AbstractDenseLattice &after, AbstractDenseLattice *before)
Propagate the dense lattice backwards along the control flow edge from regionFrom to regionTo regions...
virtual LogicalResult visitOperationImpl(Operation *op, const AbstractDenseLattice &before, AbstractDenseLattice *after)=0
Propagate the dense lattice before the execution of an operation to the lattice after its execution.
void visitRegionBranchOperation(ProgramPoint *point, RegionBranchOpInterface branch, AbstractDenseLattice *after)
Visit a program point within a region branch operation with predecessors in it.
virtual void initializeEquivalentLatticeAnchor(Operation *top) override
Initialize lattice anchor equivalence class from the provided top-level operation.
void join(AbstractDenseLattice *lhs, const AbstractDenseLattice &rhs)
Join a lattice with another and propagate an update if it changed.
virtual void setToEntryState(AbstractDenseLattice *lattice)=0
Set the dense lattice at control flow entry point and propagate an update if it changed.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting every program point whose execution may modify the program state;...
virtual void visitCallControlFlowTransfer(CallOpInterface call, CallControlFlowAction action, const AbstractDenseLattice &before, AbstractDenseLattice *after)
Propagate the dense lattice forward along the call control flow edge, which can be either entering or...
virtual LogicalResult processOperation(Operation *op)
Visit an operation.
virtual void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch, std::optional< unsigned > regionFrom, std::optional< unsigned > regionTo, const AbstractDenseLattice &before, AbstractDenseLattice *after)
Propagate the dense lattice forward along the control flow edge from regionFrom to regionTo regions o...
virtual void buildOperationEquivalentLatticeAnchor(Operation *op)
Visit an operation.
virtual AbstractDenseLattice * getLattice(LatticeAnchor anchor)=0
Get the dense lattice on the given lattice anchor.
LogicalResult visit(ProgramPoint *point) override
Visit a program point that modifies the state of the program.
virtual const AbstractDenseLattice * getLatticeFor(ProgramPoint *dependent, LatticeAnchor anchor)=0
Get the dense lattice on the given lattice anchor and add dependent as its dependency.
This class represents a dense lattice.
Include the generated interface declarations.
Program point represents a specific location in the execution of a program.
bool isBlockStart() const
Operation * getPrevOp() const
Get the previous operation of this program point.
Operation * getNextOp() const
Get the next operation of this program point.
Block * getBlock() const
Get the block contains this program point.