19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/Support/Casting.h"
35 for (
Block &block : region) {
46 if (
auto *op = llvm::dyn_cast_if_present<Operation *>(point))
48 else if (
auto *block = llvm::dyn_cast_if_present<Block *>(point))
55 void AbstractDenseForwardDataFlowAnalysis::visitCallOperation(
61 dyn_cast_if_present<CallableOpInterface>(call.resolveCallable());
63 (callable && !callable.getCallableRegion())) {
68 const auto *predecessors =
69 getOrCreateFor<PredecessorState>(call.getOperation(), call);
72 if (!predecessors->allPredecessorsKnown())
75 for (
Operation *predecessor : predecessors->getKnownPredecessors()) {
93 *latticeAtCalleeReturn, latticeAfterCall);
99 if (!getOrCreateFor<Executable>(op, op->
getBlock())->isLive())
114 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op))
119 if (
auto call = dyn_cast<CallOpInterface>(op))
120 return visitCallOperation(call, *before, after);
126 void AbstractDenseForwardDataFlowAnalysis::visitBlock(
Block *block) {
128 if (!getOrCreateFor<Executable>(block, block)->isLive())
138 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
139 if (callable && callable.getCallableRegion() == block->
getParent()) {
140 const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
144 if (!callsites->allPredecessorsKnown() ||
147 for (
Operation *callsite : callsites->getKnownPredecessors()) {
150 if (
Operation *prev = callsite->getPrevNode())
163 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp()))
174 Block *predecessor = *it;
175 if (!getOrCreateFor<Executable>(
176 block, getProgramPoint<CFGEdge>(predecessor, block))
189 const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
190 assert(predecessors->allPredecessorsKnown() &&
191 "unexpected unresolved region successors");
193 for (
Operation *op : predecessors->getKnownPredecessors()) {
220 std::optional<unsigned> regionFrom =
221 op == branch ? std::optional<unsigned>()
223 if (
auto *toBlock = point.dyn_cast<
Block *>()) {
224 unsigned regionTo = toBlock->getParent()->getRegionNumber();
228 assert(point.get<
Operation *>() == branch &&
229 "expected to be visiting the branch itself");
234 branch, regionFrom, std::nullopt, *before, after);
236 join(after, *before);
259 for (
Block &block : region) {
261 for (
Operation &op : llvm::reverse(block)) {
271 if (
auto *op = llvm::dyn_cast_if_present<Operation *>(point))
273 else if (
auto *block = llvm::dyn_cast_if_present<Block *>(point))
280 void AbstractDenseBackwardDataFlowAnalysis::visitCallOperation(
284 Operation *callee = call.resolveCallable(&symbolTable);
286 auto callable = dyn_cast_or_null<CallableOpInterface>(callee);
291 (callable && (!callable.getCallableRegion() ||
292 callable.getCallableRegion()->empty()))) {
300 Region *region = callable.getCallableRegion();
318 : &calleeEntryBlock->front();
323 latticeAtCalleeEntry, latticeBeforeCall);
328 if (!getOrCreateFor<Executable>(op, op->
getBlock())->isLive())
342 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op))
345 if (
auto call = dyn_cast<CallOpInterface>(op))
346 return visitCallOperation(call, *after, before);
352 void AbstractDenseBackwardDataFlowAnalysis::visitBlock(
Block *block) {
354 if (!getOrCreateFor<Executable>(block, block)->isLive())
361 auto isExitBlock = [](
Block *b) {
369 return isa_and_nonnull<RegionBranchTerminatorOpInterface>(
372 if (isExitBlock(block)) {
376 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
377 if (callable && callable.getCallableRegion() == block->
getParent()) {
378 const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
381 if (!callsites->allPredecessorsKnown() ||
386 for (
Operation *callsite : callsites->getKnownPredecessors()) {
388 if (
Operation *next = callsite->getNextNode())
401 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp())) {
402 visitRegionBranchOperation(block, branch, block->
getParent(), before);
413 if (!getOrCreateFor<Executable>(block,
414 getProgramPoint<CFGEdge>(block, successor))
420 if (successor->empty())
427 void AbstractDenseBackwardDataFlowAnalysis::visitRegionBranchOperation(
435 branch.getSuccessorRegions(branchPoint, successors);
438 if (successor.isParent() || successor.getSuccessor()->empty()) {
439 if (
Operation *next = branch->getNextNode())
444 Region *successorRegion = successor.getSuccessor();
445 assert(!successorRegion->
empty() &&
"unexpected empty successor region");
446 Block *successorBlock = &successorRegion->
front();
448 if (!getOrCreateFor<Executable>(point, successorBlock)->isLive())
451 if (successorBlock->
empty())
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.
const DataFlowConfig & getSolverConfig() const
Return the configuration of the solver used for this analysis.
void addDependency(AnalysisState *state, ProgramPoint point)
Create a dependency between the given analysis state and program point on this analysis.
This class provides the API for ops that are known to be terminators.
Operation is the basic unit of execution within MLIR.
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
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 ...
LogicalResult visit(ProgramPoint point) override
Visit a program point that modifies the state of the program.
virtual void 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 void processOperation(Operation *op)
Visit an operation.
const AbstractDenseLattice * getLatticeFor(ProgramPoint dependent, ProgramPoint point)
Get the dense lattice before the execution of the program point point and declare that the dependent ...
virtual AbstractDenseLattice * getLattice(ProgramPoint point)=0
Get the dense lattice before the execution of the program point.
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...
const AbstractDenseLattice * getLatticeFor(ProgramPoint dependent, ProgramPoint point)
Get the dense lattice after the execution of the given program point and add it as a dependency to a ...
virtual AbstractDenseLattice * getLattice(ProgramPoint point)=0
Get the dense lattice after the execution of the given program point.
void join(AbstractDenseLattice *lhs, const AbstractDenseLattice &rhs)
Join a lattice with another and propagate an update if it changed.
void visitRegionBranchOperation(ProgramPoint point, RegionBranchOpInterface branch, AbstractDenseLattice *after)
Visit a program point within a region branch operation with predecessors in it.
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...
LogicalResult visit(ProgramPoint point) override
Visit a program point that modifies the state of the program.
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 processOperation(Operation *op)
Visit an operation.
virtual void 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.
This class represents a dense lattice.
Include the generated interface declarations.
Fundamental IR components are supported as first-class program points.