19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/Support/Casting.h"
34 if (isa<RegionBranchOpInterface, CallOpInterface>(op))
46 for (
Block &block : region) {
63 void AbstractDenseForwardDataFlowAnalysis::visitCallOperation(
69 dyn_cast_if_present<CallableOpInterface>(call.resolveCallable());
71 (callable && !callable.getCallableRegion())) {
76 const auto *predecessors = getOrCreateFor<PredecessorState>(
80 if (!predecessors->allPredecessorsKnown())
83 for (
Operation *predecessor : predecessors->getKnownPredecessors()) {
102 *latticeAtCalleeReturn, latticeAfterCall);
124 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
131 if (
auto call = dyn_cast<CallOpInterface>(op)) {
132 visitCallOperation(call, *before, after);
140 void AbstractDenseForwardDataFlowAnalysis::visitBlock(
Block *block) {
143 if (!getOrCreateFor<Executable>(point, point)->isLive())
153 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
154 if (callable && callable.getCallableRegion() == block->
getParent()) {
155 const auto *callsites = getOrCreateFor<PredecessorState>(
160 if (!callsites->allPredecessorsKnown() ||
163 for (
Operation *callsite : callsites->getKnownPredecessors()) {
176 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp()))
187 Block *predecessor = *it;
188 if (!getOrCreateFor<Executable>(
189 point, getLatticeAnchor<CFGEdge>(predecessor, block))
203 const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
204 assert(predecessors->allPredecessorsKnown() &&
205 "unexpected unresolved region successors");
207 for (
Operation *op : predecessors->getKnownPredecessors()) {
230 std::optional<unsigned> regionFrom =
231 op == branch ? std::optional<unsigned>()
232 : op->getBlock()->getParent()->getRegionNumber();
239 "expected to be visiting the branch itself");
242 if (op->getParentOp() == branch || op == branch) {
244 branch, regionFrom, std::nullopt, *before, after);
246 join(after, *before);
259 if (isa<RegionBranchOpInterface, CallOpInterface>(op))
272 for (
Block &block : region) {
274 for (
Operation &op : llvm::reverse(block)) {
291 void AbstractDenseBackwardDataFlowAnalysis::visitCallOperation(
295 Operation *callee = call.resolveCallableInTable(&symbolTable);
297 auto callable = dyn_cast_or_null<CallableOpInterface>(callee);
302 (callable && (!callable.getCallableRegion() ||
303 callable.getCallableRegion()->empty()))) {
311 Region *region = callable.getCallableRegion();
332 latticeAtCalleeEntry, latticeBeforeCall);
352 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
357 if (
auto call = dyn_cast<CallOpInterface>(op)) {
358 visitCallOperation(call, *after, before);
366 void AbstractDenseBackwardDataFlowAnalysis::visitBlock(
Block *block) {
377 auto isExitBlock = [](
Block *b) {
385 return isa_and_nonnull<RegionBranchTerminatorOpInterface>(
388 if (isExitBlock(block)) {
392 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
393 if (callable && callable.getCallableRegion() == block->
getParent()) {
394 const auto *callsites = getOrCreateFor<PredecessorState>(
398 if (!callsites->allPredecessorsKnown() ||
403 for (
Operation *callsite : callsites->getKnownPredecessors()) {
415 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp())) {
416 visitRegionBranchOperation(point, branch, block->
getParent(), before);
427 if (!getOrCreateFor<Executable>(point,
428 getLatticeAnchor<CFGEdge>(block, successor))
438 void AbstractDenseBackwardDataFlowAnalysis::visitRegionBranchOperation(
446 branch.getSuccessorRegions(branchPoint, successors);
449 if (successor.isParent() || successor.getSuccessor()->empty()) {
452 Region *successorRegion = successor.getSuccessor();
453 assert(!successorRegion->
empty() &&
"unexpected empty successor region");
454 Block *successorBlock = &successorRegion->
front();
456 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.