20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/Support/Casting.h"
36 for (
Block &block : region) {
47 if (
auto *op = llvm::dyn_cast_if_present<Operation *>(point))
49 else if (
auto *block = llvm::dyn_cast_if_present<Block *>(point))
56 void AbstractDenseForwardDataFlowAnalysis::visitCallOperation(
59 const auto *predecessors =
60 getOrCreateFor<PredecessorState>(call.getOperation(), call);
63 if (!predecessors->allPredecessorsKnown())
66 for (
Operation *predecessor : predecessors->getKnownPredecessors()) {
84 *latticeAtCalleeReturn, latticeAfterCall);
90 if (!getOrCreateFor<Executable>(op, op->
getBlock())->isLive())
105 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op))
110 if (
auto call = dyn_cast<CallOpInterface>(op))
111 return visitCallOperation(call, after);
117 void AbstractDenseForwardDataFlowAnalysis::visitBlock(
Block *block) {
119 if (!getOrCreateFor<Executable>(block, block)->isLive())
129 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
130 if (callable && callable.getCallableRegion() == block->
getParent()) {
131 const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
134 if (!callsites->allPredecessorsKnown())
136 for (
Operation *callsite : callsites->getKnownPredecessors()) {
139 if (
Operation *prev = callsite->getPrevNode())
152 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp()))
163 Block *predecessor = *it;
164 if (!getOrCreateFor<Executable>(
165 block, getProgramPoint<CFGEdge>(predecessor, block))
178 const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
179 assert(predecessors->allPredecessorsKnown() &&
180 "unexpected unresolved region successors");
182 for (
Operation *op : predecessors->getKnownPredecessors()) {
209 std::optional<unsigned> regionFrom =
210 op == branch ? std::optional<unsigned>()
212 if (
auto *toBlock = point.dyn_cast<
Block *>()) {
213 unsigned regionTo = toBlock->getParent()->getRegionNumber();
217 assert(point.get<
Operation *>() == branch &&
218 "expected to be visiting the branch itself");
223 branch, regionFrom, std::nullopt, *before, after);
225 join(after, *before);
248 for (
Block &block : region) {
250 for (
Operation &op : llvm::reverse(block)) {
260 if (
auto *op = llvm::dyn_cast_if_present<Operation *>(point))
262 else if (
auto *block = llvm::dyn_cast_if_present<Block *>(point))
269 void AbstractDenseBackwardDataFlowAnalysis::visitCallOperation(
272 Operation *callee = call.resolveCallable(&symbolTable);
273 auto callable = dyn_cast_or_null<CallableOpInterface>(callee);
279 Region *region = callable.getCallableRegion();
280 if (!region || region->
empty())
299 : &calleeEntryBlock->front();
304 latticeAtCalleeEntry, latticeBeforeCall);
309 if (!getOrCreateFor<Executable>(op, op->
getBlock())->isLive())
323 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op))
326 if (
auto call = dyn_cast<CallOpInterface>(op))
327 return visitCallOperation(call, before);
333 void AbstractDenseBackwardDataFlowAnalysis::visitBlock(
Block *block) {
335 if (!getOrCreateFor<Executable>(block, block)->isLive())
342 auto isExitBlock = [](
Block *b) {
350 return isa_and_nonnull<RegionBranchTerminatorOpInterface>(
353 if (isExitBlock(block)) {
357 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
358 if (callable && callable.getCallableRegion() == block->
getParent()) {
359 const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
362 if (!callsites->allPredecessorsKnown())
365 for (
Operation *callsite : callsites->getKnownPredecessors()) {
367 if (
Operation *next = callsite->getNextNode())
380 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp())) {
381 visitRegionBranchOperation(block, branch, block->
getParent(), before);
392 if (!getOrCreateFor<Executable>(block,
393 getProgramPoint<CFGEdge>(block, successor))
399 if (successor->empty())
406 void AbstractDenseBackwardDataFlowAnalysis::visitRegionBranchOperation(
414 branch.getSuccessorRegions(branchPoint, successors);
417 if (successor.isParent() || successor.getSuccessor()->empty()) {
418 if (
Operation *next = branch->getNextNode())
423 Region *successorRegion = successor.getSuccessor();
424 assert(!successorRegion->
empty() &&
"unexpected empty successor region");
425 Block *successorBlock = &successorRegion->
front();
427 if (!getOrCreateFor<Executable>(point, successorBlock)->isLive())
430 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.
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.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
This class represents an efficient way to signal success or failure.
Fundamental IR components are supported as first-class program points.