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(
62 dyn_cast_if_present<CallableOpInterface>(call.resolveCallable());
64 (callable && !callable.getCallableRegion())) {
69 const auto *predecessors =
70 getOrCreateFor<PredecessorState>(call.getOperation(), call);
73 if (!predecessors->allPredecessorsKnown())
76 for (
Operation *predecessor : predecessors->getKnownPredecessors()) {
94 *latticeAtCalleeReturn, latticeAfterCall);
100 if (!getOrCreateFor<Executable>(op, op->
getBlock())->isLive())
115 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op))
120 if (
auto call = dyn_cast<CallOpInterface>(op))
121 return visitCallOperation(call, *before, after);
127 void AbstractDenseForwardDataFlowAnalysis::visitBlock(
Block *block) {
129 if (!getOrCreateFor<Executable>(block, block)->isLive())
139 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
140 if (callable && callable.getCallableRegion() == block->
getParent()) {
141 const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
145 if (!callsites->allPredecessorsKnown() ||
148 for (
Operation *callsite : callsites->getKnownPredecessors()) {
151 if (
Operation *prev = callsite->getPrevNode())
164 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp()))
175 Block *predecessor = *it;
176 if (!getOrCreateFor<Executable>(
177 block, getProgramPoint<CFGEdge>(predecessor, block))
190 const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
191 assert(predecessors->allPredecessorsKnown() &&
192 "unexpected unresolved region successors");
194 for (
Operation *op : predecessors->getKnownPredecessors()) {
221 std::optional<unsigned> regionFrom =
222 op == branch ? std::optional<unsigned>()
224 if (
auto *toBlock = point.dyn_cast<
Block *>()) {
225 unsigned regionTo = toBlock->getParent()->getRegionNumber();
229 assert(point.get<
Operation *>() == branch &&
230 "expected to be visiting the branch itself");
235 branch, regionFrom, std::nullopt, *before, after);
237 join(after, *before);
260 for (
Block &block : region) {
262 for (
Operation &op : llvm::reverse(block)) {
272 if (
auto *op = llvm::dyn_cast_if_present<Operation *>(point))
274 else if (
auto *block = llvm::dyn_cast_if_present<Block *>(point))
281 void AbstractDenseBackwardDataFlowAnalysis::visitCallOperation(
285 Operation *callee = call.resolveCallable(&symbolTable);
287 auto callable = dyn_cast_or_null<CallableOpInterface>(callee);
292 (callable && (!callable.getCallableRegion() ||
293 callable.getCallableRegion()->empty()))) {
301 Region *region = callable.getCallableRegion();
319 : &calleeEntryBlock->front();
324 latticeAtCalleeEntry, latticeBeforeCall);
329 if (!getOrCreateFor<Executable>(op, op->
getBlock())->isLive())
343 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op))
346 if (
auto call = dyn_cast<CallOpInterface>(op))
347 return visitCallOperation(call, *after, before);
353 void AbstractDenseBackwardDataFlowAnalysis::visitBlock(
Block *block) {
355 if (!getOrCreateFor<Executable>(block, block)->isLive())
362 auto isExitBlock = [](
Block *b) {
370 return isa_and_nonnull<RegionBranchTerminatorOpInterface>(
373 if (isExitBlock(block)) {
377 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
378 if (callable && callable.getCallableRegion() == block->
getParent()) {
379 const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
382 if (!callsites->allPredecessorsKnown() ||
387 for (
Operation *callsite : callsites->getKnownPredecessors()) {
389 if (
Operation *next = callsite->getNextNode())
402 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp())) {
403 visitRegionBranchOperation(block, branch, block->
getParent(), before);
414 if (!getOrCreateFor<Executable>(block,
415 getProgramPoint<CFGEdge>(block, successor))
421 if (successor->empty())
428 void AbstractDenseBackwardDataFlowAnalysis::visitRegionBranchOperation(
436 branch.getSuccessorRegions(branchPoint, successors);
439 if (successor.isParent() || successor.getSuccessor()->empty()) {
440 if (
Operation *next = branch->getNextNode())
445 Region *successorRegion = successor.getSuccessor();
446 assert(!successorRegion->
empty() &&
"unexpected empty successor region");
447 Block *successorBlock = &successorRegion->
front();
449 if (!getOrCreateFor<Executable>(point, successorBlock)->isLive())
452 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.
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.