19 #include "llvm/ADT/STLExtras.h"
33 if (isa<RegionBranchOpInterface, CallOpInterface>(op))
45 for (
Block &block : region) {
62 void AbstractDenseForwardDataFlowAnalysis::visitCallOperation(
68 dyn_cast_if_present<CallableOpInterface>(call.resolveCallable());
70 (callable && !callable.getCallableRegion())) {
75 const auto *predecessors = getOrCreateFor<PredecessorState>(
79 if (!predecessors->allPredecessorsKnown())
82 for (
Operation *predecessor : predecessors->getKnownPredecessors()) {
101 *latticeAtCalleeReturn, latticeAfterCall);
123 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
130 if (
auto call = dyn_cast<CallOpInterface>(op)) {
131 visitCallOperation(call, *before, after);
139 void AbstractDenseForwardDataFlowAnalysis::visitBlock(
Block *block) {
142 if (!getOrCreateFor<Executable>(point, point)->isLive())
152 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
153 if (callable && callable.getCallableRegion() == block->
getParent()) {
154 const auto *callsites = getOrCreateFor<PredecessorState>(
159 if (!callsites->allPredecessorsKnown() ||
162 for (
Operation *callsite : callsites->getKnownPredecessors()) {
175 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp()))
186 Block *predecessor = *it;
187 if (!getOrCreateFor<Executable>(
188 point, getLatticeAnchor<CFGEdge>(predecessor, block))
202 const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
203 assert(predecessors->allPredecessorsKnown() &&
204 "unexpected unresolved region successors");
206 for (
Operation *op : predecessors->getKnownPredecessors()) {
229 std::optional<unsigned> regionFrom =
230 op == branch ? std::optional<unsigned>()
231 : op->getBlock()->getParent()->getRegionNumber();
238 "expected to be visiting the branch itself");
241 if (op->getParentOp() == branch || op == branch) {
243 branch, regionFrom, std::nullopt, *before, after);
245 join(after, *before);
258 if (isa<RegionBranchOpInterface, CallOpInterface>(op))
271 for (
Block &block : region) {
273 for (
Operation &op : llvm::reverse(block)) {
290 void AbstractDenseBackwardDataFlowAnalysis::visitCallOperation(
294 Operation *callee = call.resolveCallableInTable(&symbolTable);
296 auto callable = dyn_cast_or_null<CallableOpInterface>(callee);
301 (callable && (!callable.getCallableRegion() ||
302 callable.getCallableRegion()->empty()))) {
310 Region *region = callable.getCallableRegion();
331 latticeAtCalleeEntry, latticeBeforeCall);
351 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
356 if (
auto call = dyn_cast<CallOpInterface>(op)) {
357 visitCallOperation(call, *after, before);
365 void AbstractDenseBackwardDataFlowAnalysis::visitBlock(
Block *block) {
376 auto isExitBlock = [](
Block *b) {
384 return isa_and_nonnull<RegionBranchTerminatorOpInterface>(
387 if (isExitBlock(block)) {
391 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
392 if (callable && callable.getCallableRegion() == block->
getParent()) {
393 const auto *callsites = getOrCreateFor<PredecessorState>(
397 if (!callsites->allPredecessorsKnown() ||
402 for (
Operation *callsite : callsites->getKnownPredecessors()) {
414 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp())) {
415 visitRegionBranchOperation(point, branch, block->
getParent(), before);
426 if (!getOrCreateFor<Executable>(point,
427 getLatticeAnchor<CFGEdge>(block, successor))
437 void AbstractDenseBackwardDataFlowAnalysis::visitRegionBranchOperation(
445 branch.getSuccessorRegions(branchPoint, successors);
448 if (successor.isParent() || successor.getSuccessor()->empty()) {
451 Region *successorRegion = successor.getSuccessor();
452 assert(!successorRegion->
empty() &&
"unexpected empty successor region");
453 Block *successorBlock = &successorRegion->
front();
455 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.