21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/Support/Casting.h"
39 solver->
enqueue({user, analysis});
49 registerPointKind<CFGEdge>();
59 for (
Value argument : region.front().getArguments())
63 return initializeRecursively(top);
67 AbstractSparseForwardDataFlowAnalysis::initializeRecursively(
Operation *op) {
72 for (
Block &block : region) {
73 getOrCreate<Executable>(&block)->blockContentSubscribe(
this);
76 if (failed(initializeRecursively(&op)))
85 if (
Operation *op = llvm::dyn_cast_if_present<Operation *>(point))
87 else if (
Block *block = llvm::dyn_cast_if_present<Block *>(point))
94 void AbstractSparseForwardDataFlowAnalysis::visitOperation(
Operation *op) {
100 if (!getOrCreate<Executable>(op->
getBlock())->isLive())
108 resultLattices.push_back(resultLattice);
112 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
113 return visitRegionSuccessors({branch}, branch,
124 operandLattices.push_back(operandLattice);
127 if (
auto call = dyn_cast<CallOpInterface>(op)) {
131 dyn_cast_if_present<CallableOpInterface>(call.resolveCallable());
133 (callable && !callable.getCallableRegion())) {
139 const auto *predecessors = getOrCreateFor<PredecessorState>(op, call);
142 if (!predecessors->allPredecessorsKnown())
144 for (
Operation *predecessor : predecessors->getKnownPredecessors())
145 for (
auto it : llvm::zip(predecessor->getOperands(), resultLattices))
154 void AbstractSparseForwardDataFlowAnalysis::visitBlock(
Block *block) {
160 if (!getOrCreate<Executable>(block)->isLive())
168 argLattices.push_back(argLattice);
175 auto callable = dyn_cast<CallableOpInterface>(block->
getParentOp());
176 if (callable && callable.getCallableRegion() == block->
getParent()) {
177 const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
180 if (!callsites->allPredecessorsKnown() ||
184 for (
Operation *callsite : callsites->getKnownPredecessors()) {
185 auto call = cast<CallOpInterface>(callsite);
186 for (
auto it : llvm::zip(call.getArgOperands(), argLattices))
193 if (
auto branch = dyn_cast<RegionBranchOpInterface>(block->
getParentOp())) {
194 return visitRegionSuccessors(block, branch, block->
getParent(),
207 Block *predecessor = *it;
211 auto *edgeExecutable =
212 getOrCreate<Executable>(getProgramPoint<CFGEdge>(predecessor, block));
213 edgeExecutable->blockContentSubscribe(
this);
214 if (!edgeExecutable->isLive())
221 branch.getSuccessorOperands(it.getSuccessorIndex());
223 if (
Value operand = operands[idx]) {
237 void AbstractSparseForwardDataFlowAnalysis::visitRegionSuccessors(
240 const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
241 assert(predecessors->allPredecessorsKnown() &&
242 "unexpected unresolved region successors");
244 for (
Operation *op : predecessors->getKnownPredecessors()) {
246 std::optional<OperandRange> operands;
250 operands = branch.getEntrySuccessorOperands(successor);
252 }
else if (
auto regionTerminator =
253 dyn_cast<RegionBranchTerminatorOpInterface>(op)) {
254 operands = regionTerminator.getSuccessorOperands(successor);
262 ValueRange inputs = predecessors->getSuccessorInputs(op);
263 assert(inputs.size() == operands->size() &&
264 "expected the same number of successor inputs as operands");
266 unsigned firstIndex = 0;
267 if (inputs.size() != lattices.size()) {
268 if (llvm::dyn_cast_if_present<Operation *>(point)) {
270 firstIndex = cast<OpResult>(inputs.front()).getResultNumber();
274 branch->getResults().slice(firstIndex, inputs.size())),
275 lattices, firstIndex);
278 firstIndex = cast<BlockArgument>(inputs.front()).getArgNumber();
279 Region *region = point.get<
Block *>()->getParent();
283 firstIndex, inputs.size())),
284 lattices, firstIndex);
288 for (
auto it : llvm::zip(*operands, lattices.drop_front(firstIndex)))
319 registerPointKind<CFGEdge>();
324 return initializeRecursively(top);
328 AbstractSparseBackwardDataFlowAnalysis::initializeRecursively(
Operation *op) {
331 for (
Block &block : region) {
332 getOrCreate<Executable>(&block)->blockContentSubscribe(
this);
336 for (
auto it = block.
rbegin(); it != block.
rend(); it++)
337 if (failed(initializeRecursively(&*it)))
346 if (
Operation *op = llvm::dyn_cast_if_present<Operation *>(point))
348 else if (llvm::dyn_cast_if_present<Block *>(point))
362 resultLattices.reserve(values.size());
363 for (
Value result : values) {
365 resultLattices.push_back(resultLattice);
367 return resultLattices;
371 AbstractSparseBackwardDataFlowAnalysis::getLatticeElementsFor(
374 resultLattices.reserve(values.size());
375 for (
Value result : values) {
377 getLatticeElementFor(point, result);
378 resultLattices.push_back(resultLattice);
380 return resultLattices;
387 void AbstractSparseBackwardDataFlowAnalysis::visitOperation(
Operation *op) {
389 if (!getOrCreate<Executable>(op->
getBlock())->isLive())
399 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
400 visitRegionSuccessors(branch, operandLattices);
404 if (
auto branch = dyn_cast<BranchOpInterface>(op)) {
415 if (!forwarded.empty()) {
419 unaccounted.reset(operand.getOperandNumber());
420 if (std::optional<BlockArgument> blockArg =
422 successorOperands, operand.getOperandNumber(), block)) {
424 *getLatticeElementFor(op, *blockArg));
431 for (
int index : unaccounted.set_bits()) {
440 if (
auto call = dyn_cast<CallOpInterface>(op)) {
441 Operation *callableOp = call.resolveCallable(&symbolTable);
442 if (
auto callable = dyn_cast_or_null<CallableOpInterface>(callableOp)) {
453 Region *region = callable.getCallableRegion();
460 for (
auto [blockArg, argOpOperand] :
463 *getLatticeElementFor(op, blockArg));
464 unaccounted.reset(argOpOperand.getOperandNumber());
469 for (
int index : unaccounted.set_bits()) {
487 if (
auto terminator = dyn_cast<RegionBranchTerminatorOpInterface>(op)) {
488 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op->
getParentOp())) {
489 visitRegionSuccessorsFromTerminator(terminator, branch);
497 if (
auto callable = dyn_cast<CallableOpInterface>(op->
getParentOp())) {
499 getOrCreateFor<PredecessorState>(op, callable);
503 getLatticeElementsFor(op, call->getResults());
504 for (
auto [op, result] :
505 llvm::zip(operandLattices, callResultLattices))
521 void AbstractSparseBackwardDataFlowAnalysis::visitRegionSuccessors(
522 RegionBranchOpInterface branch,
527 branch.getEntrySuccessorRegions(operands, successors);
534 OperandRange operands = branch.getEntrySuccessorOperands(successor);
536 ValueRange inputs = successor.getSuccessorInputs();
537 for (
auto [operand, input] : llvm::zip(opoperands, inputs)) {
539 unaccounted.reset(operand.getOperandNumber());
544 for (
int index : unaccounted.set_bits()) {
549 void AbstractSparseBackwardDataFlowAnalysis::
550 visitRegionSuccessorsFromTerminator(
551 RegionBranchTerminatorOpInterface terminator,
552 RegionBranchOpInterface branch) {
553 assert(isa<RegionBranchTerminatorOpInterface>(terminator) &&
554 "expected a `RegionBranchTerminatorOpInterface` op");
555 assert(terminator->getParentOp() == branch.getOperation() &&
556 "expected `branch` to be the parent op of `terminator`");
561 terminator.getSuccessorRegions(operandAttributes, successors);
564 BitVector unaccounted(terminator->getNumOperands(),
true);
567 ValueRange inputs = successor.getSuccessorInputs();
568 OperandRange operands = terminator.getSuccessorOperands(successor);
570 for (
auto [opOperand, input] : llvm::zip(opOperands, inputs)) {
572 *getLatticeElementFor(terminator, input));
573 unaccounted.reset(
const_cast<OpOperand &
>(opOperand).getOperandNumber());
578 for (
int index : unaccounted.set_bits()) {
584 AbstractSparseBackwardDataFlowAnalysis::getLatticeElementFor(
ProgramPoint point,
static MutableArrayRef< OpOperand > operandsToOpOperands(OperandRange &operands)
virtual void onUpdate(DataFlowSolver *solver) const
This function is called by the solver when the analysis state is updated to enqueue more work items.
ProgramPoint point
The program point to which the state belongs.
This class represents an argument of a Block.
Block represents an ordered list of Operations.
unsigned getNumArguments()
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
pred_iterator pred_begin()
Operation * getTerminator()
Get the terminator operation of this block.
BlockArgListType getArguments()
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.
reverse_iterator rbegin()
Base class for all data-flow analyses.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
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.
The general data-flow analysis solver.
void enqueue(WorkItem item)
Push a work item onto the worklist.
This class represents an operand of an operation.
This class implements the operand iterators for the Operation class.
unsigned getBeginOperandIndex() const
Return the operand index of the first element of this range.
Operation is the basic unit of execution within MLIR.
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
OpOperand & getOpOperand(unsigned idx)
unsigned getNumOperands()
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.
MutableArrayRef< OpOperand > getOpOperands()
operand_range getOperands()
Returns an iterator on the underlying Value's.
SuccessorRange getSuccessors()
result_range getResults()
unsigned getNumResults()
Return the number of results 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.
BlockArgListType getArguments()
This class models how operands are forwarded to block arguments in control flow.
OperandRange getForwardedOperands() const
Get the range of operands that are simply forwarded to the successor.
This class represents a collection of SymbolTables.
This class provides an abstraction over the different types of ranges over Values.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
user_range getUsers() const
virtual void setToExitState(AbstractSparseLattice *lattice)=0
Set the given lattice element(s) at control flow exit point(s).
SmallVector< AbstractSparseLattice * > getLatticeElements(ValueRange values)
Get the lattice elements for a range of values.
AbstractSparseBackwardDataFlowAnalysis(DataFlowSolver &solver, SymbolTableCollection &symbolTable)
virtual void visitBranchOperand(OpOperand &operand)=0
virtual void visitOperationImpl(Operation *op, ArrayRef< AbstractSparseLattice * > operandLattices, ArrayRef< const AbstractSparseLattice * > resultLattices)=0
The operation transfer function.
virtual void visitCallOperand(OpOperand &operand)=0
LogicalResult visit(ProgramPoint point) override
Visit a program point.
void meet(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs)
Join the lattice element and propagate and update if it changed.
virtual void visitExternalCallImpl(CallOpInterface call, ArrayRef< AbstractSparseLattice * > operandLattices, ArrayRef< const AbstractSparseLattice * > resultLattices)=0
The transfer function for calls to external functions.
virtual AbstractSparseLattice * getLatticeElement(Value value)=0
Get the lattice element for a value.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting the operation and everything nested under it.
void setAllToExitStates(ArrayRef< AbstractSparseLattice * > lattices)
Set the given lattice element(s) at control flow exit point(s).
LogicalResult visit(ProgramPoint point) override
Visit a program point.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting every owner of an SSA value: all operations and blocks.
virtual void visitOperationImpl(Operation *op, ArrayRef< const AbstractSparseLattice * > operandLattices, ArrayRef< AbstractSparseLattice * > resultLattices)=0
The operation transfer function.
virtual AbstractSparseLattice * getLatticeElement(Value value)=0
Get the lattice element of a value.
virtual void visitExternalCallImpl(CallOpInterface call, ArrayRef< const AbstractSparseLattice * > argumentLattices, ArrayRef< AbstractSparseLattice * > resultLattices)=0
The transfer function for calls to external functions.
AbstractSparseForwardDataFlowAnalysis(DataFlowSolver &solver)
void setAllToEntryStates(ArrayRef< AbstractSparseLattice * > lattices)
virtual void setToEntryState(AbstractSparseLattice *lattice)=0
Set the given lattice element(s) at control flow entry point(s).
virtual void visitNonControlFlowArgumentsImpl(Operation *op, const RegionSuccessor &successor, ArrayRef< AbstractSparseLattice * > argLattices, unsigned firstIndex)=0
Given an operation with region control-flow, the lattices of the operands, and a region successor,...
const AbstractSparseLattice * getLatticeElementFor(ProgramPoint point, Value value)
Get a read-only lattice element for a value and add it as a dependency to a program point.
void join(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs)
Join the lattice element and propagate and update if it changed.
This class represents an abstract lattice.
void onUpdate(DataFlowSolver *solver) const override
When the lattice gets updated, propagate an update to users of the value using its use-def chain to s...
virtual ChangeResult join(const AbstractSparseLattice &rhs)
Join the information contained in 'rhs' into this lattice.
virtual ChangeResult meet(const AbstractSparseLattice &rhs)
Meet (intersect) the information in this lattice with 'rhs'.
void useDefSubscribe(DataFlowAnalysis *analysis)
Subscribe an analysis to updates of the lattice.
This analysis state represents a set of live control-flow "predecessors" of a program point (either a...
bool allPredecessorsKnown() const
Returns true if all predecessors are known.
ArrayRef< Operation * > getKnownPredecessors() const
Get the known predecessors.
std::optional< BlockArgument > getBranchSuccessorArgument(const SuccessorOperands &operands, unsigned operandIndex, Block *successor)
Return the BlockArgument corresponding to operand operandIndex in some successor if operandIndex is w...
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Include the generated interface declarations.
This trait indicates that a terminator operation is "return-like".
Fundamental IR components are supported as first-class program points.