MLIR  18.0.0git
SparseAnalysis.cpp
Go to the documentation of this file.
1 //===- SparseAnalysis.cpp - Sparse data-flow analysis ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
12 #include "mlir/IR/Attributes.h"
13 #include "mlir/IR/Operation.h"
14 #include "mlir/IR/Region.h"
15 #include "mlir/IR/SymbolTable.h"
16 #include "mlir/IR/Value.h"
17 #include "mlir/IR/ValueRange.h"
20 #include "mlir/Support/LLVM.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/Support/Casting.h"
24 #include <cassert>
25 #include <optional>
26 
27 using namespace mlir;
28 using namespace mlir::dataflow;
29 
30 //===----------------------------------------------------------------------===//
31 // AbstractSparseLattice
32 //===----------------------------------------------------------------------===//
33 
36 
37  // Push all users of the value to the queue.
38  for (Operation *user : point.get<Value>().getUsers())
39  for (DataFlowAnalysis *analysis : useDefSubscribers)
40  solver->enqueue({user, analysis});
41 }
42 
43 //===----------------------------------------------------------------------===//
44 // AbstractSparseForwardDataFlowAnalysis
45 //===----------------------------------------------------------------------===//
46 
48  DataFlowSolver &solver)
49  : DataFlowAnalysis(solver) {
50  registerPointKind<CFGEdge>();
51 }
52 
55  // Mark the entry block arguments as having reached their pessimistic
56  // fixpoints.
57  for (Region &region : top->getRegions()) {
58  if (region.empty())
59  continue;
60  for (Value argument : region.front().getArguments())
62  }
63 
64  return initializeRecursively(top);
65 }
66 
68 AbstractSparseForwardDataFlowAnalysis::initializeRecursively(Operation *op) {
69  // Initialize the analysis by visiting every owner of an SSA value (all
70  // operations and blocks).
71  visitOperation(op);
72  for (Region &region : op->getRegions()) {
73  for (Block &block : region) {
74  getOrCreate<Executable>(&block)->blockContentSubscribe(this);
75  visitBlock(&block);
76  for (Operation &op : block)
77  if (failed(initializeRecursively(&op)))
78  return failure();
79  }
80  }
81 
82  return success();
83 }
84 
86  if (Operation *op = llvm::dyn_cast_if_present<Operation *>(point))
87  visitOperation(op);
88  else if (Block *block = llvm::dyn_cast_if_present<Block *>(point))
89  visitBlock(block);
90  else
91  return failure();
92  return success();
93 }
94 
95 void AbstractSparseForwardDataFlowAnalysis::visitOperation(Operation *op) {
96  // Exit early on operations with no results.
97  if (op->getNumResults() == 0)
98  return;
99 
100  // If the containing block is not executable, bail out.
101  if (!getOrCreate<Executable>(op->getBlock())->isLive())
102  return;
103 
104  // Get the result lattices.
106  resultLattices.reserve(op->getNumResults());
107  for (Value result : op->getResults()) {
108  AbstractSparseLattice *resultLattice = getLatticeElement(result);
109  resultLattices.push_back(resultLattice);
110  }
111 
112  // The results of a region branch operation are determined by control-flow.
113  if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
114  return visitRegionSuccessors({branch}, branch,
115  /*successor=*/RegionBranchPoint::parent(),
116  resultLattices);
117  }
118 
119  // The results of a call operation are determined by the callgraph.
120  if (auto call = dyn_cast<CallOpInterface>(op)) {
121  const auto *predecessors = getOrCreateFor<PredecessorState>(op, call);
122  // If not all return sites are known, then conservatively assume we can't
123  // reason about the data-flow.
124  if (!predecessors->allPredecessorsKnown())
125  return setAllToEntryStates(resultLattices);
126  for (Operation *predecessor : predecessors->getKnownPredecessors())
127  for (auto it : llvm::zip(predecessor->getOperands(), resultLattices))
128  join(std::get<1>(it), *getLatticeElementFor(op, std::get<0>(it)));
129  return;
130  }
131 
132  // Grab the lattice elements of the operands.
134  operandLattices.reserve(op->getNumOperands());
135  for (Value operand : op->getOperands()) {
136  AbstractSparseLattice *operandLattice = getLatticeElement(operand);
137  operandLattice->useDefSubscribe(this);
138  operandLattices.push_back(operandLattice);
139  }
140 
141  // Invoke the operation transfer function.
142  visitOperationImpl(op, operandLattices, resultLattices);
143 }
144 
145 void AbstractSparseForwardDataFlowAnalysis::visitBlock(Block *block) {
146  // Exit early on blocks with no arguments.
147  if (block->getNumArguments() == 0)
148  return;
149 
150  // If the block is not executable, bail out.
151  if (!getOrCreate<Executable>(block)->isLive())
152  return;
153 
154  // Get the argument lattices.
156  argLattices.reserve(block->getNumArguments());
157  for (BlockArgument argument : block->getArguments()) {
158  AbstractSparseLattice *argLattice = getLatticeElement(argument);
159  argLattices.push_back(argLattice);
160  }
161 
162  // The argument lattices of entry blocks are set by region control-flow or the
163  // callgraph.
164  if (block->isEntryBlock()) {
165  // Check if this block is the entry block of a callable region.
166  auto callable = dyn_cast<CallableOpInterface>(block->getParentOp());
167  if (callable && callable.getCallableRegion() == block->getParent()) {
168  const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
169  // If not all callsites are known, conservatively mark all lattices as
170  // having reached their pessimistic fixpoints.
171  if (!callsites->allPredecessorsKnown())
172  return setAllToEntryStates(argLattices);
173  for (Operation *callsite : callsites->getKnownPredecessors()) {
174  auto call = cast<CallOpInterface>(callsite);
175  for (auto it : llvm::zip(call.getArgOperands(), argLattices))
176  join(std::get<1>(it), *getLatticeElementFor(block, std::get<0>(it)));
177  }
178  return;
179  }
180 
181  // Check if the lattices can be determined from region control flow.
182  if (auto branch = dyn_cast<RegionBranchOpInterface>(block->getParentOp())) {
183  return visitRegionSuccessors(block, branch, block->getParent(),
184  argLattices);
185  }
186 
187  // Otherwise, we can't reason about the data-flow.
189  RegionSuccessor(block->getParent()),
190  argLattices, /*firstIndex=*/0);
191  }
192 
193  // Iterate over the predecessors of the non-entry block.
194  for (Block::pred_iterator it = block->pred_begin(), e = block->pred_end();
195  it != e; ++it) {
196  Block *predecessor = *it;
197 
198  // If the edge from the predecessor block to the current block is not live,
199  // bail out.
200  auto *edgeExecutable =
201  getOrCreate<Executable>(getProgramPoint<CFGEdge>(predecessor, block));
202  edgeExecutable->blockContentSubscribe(this);
203  if (!edgeExecutable->isLive())
204  continue;
205 
206  // Check if we can reason about the data-flow from the predecessor.
207  if (auto branch =
208  dyn_cast<BranchOpInterface>(predecessor->getTerminator())) {
209  SuccessorOperands operands =
210  branch.getSuccessorOperands(it.getSuccessorIndex());
211  for (auto [idx, lattice] : llvm::enumerate(argLattices)) {
212  if (Value operand = operands[idx]) {
213  join(lattice, *getLatticeElementFor(block, operand));
214  } else {
215  // Conservatively consider internally produced arguments as entry
216  // points.
217  setAllToEntryStates(lattice);
218  }
219  }
220  } else {
221  return setAllToEntryStates(argLattices);
222  }
223  }
224 }
225 
226 void AbstractSparseForwardDataFlowAnalysis::visitRegionSuccessors(
227  ProgramPoint point, RegionBranchOpInterface branch,
229  const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
230  assert(predecessors->allPredecessorsKnown() &&
231  "unexpected unresolved region successors");
232 
233  for (Operation *op : predecessors->getKnownPredecessors()) {
234  // Get the incoming successor operands.
235  std::optional<OperandRange> operands;
236 
237  // Check if the predecessor is the parent op.
238  if (op == branch) {
239  operands = branch.getEntrySuccessorOperands(successor);
240  // Otherwise, try to deduce the operands from a region return-like op.
241  } else if (auto regionTerminator =
242  dyn_cast<RegionBranchTerminatorOpInterface>(op)) {
243  operands = regionTerminator.getSuccessorOperands(successor);
244  }
245 
246  if (!operands) {
247  // We can't reason about the data-flow.
248  return setAllToEntryStates(lattices);
249  }
250 
251  ValueRange inputs = predecessors->getSuccessorInputs(op);
252  assert(inputs.size() == operands->size() &&
253  "expected the same number of successor inputs as operands");
254 
255  unsigned firstIndex = 0;
256  if (inputs.size() != lattices.size()) {
257  if (llvm::dyn_cast_if_present<Operation *>(point)) {
258  if (!inputs.empty())
259  firstIndex = cast<OpResult>(inputs.front()).getResultNumber();
261  branch,
263  branch->getResults().slice(firstIndex, inputs.size())),
264  lattices, firstIndex);
265  } else {
266  if (!inputs.empty())
267  firstIndex = cast<BlockArgument>(inputs.front()).getArgNumber();
268  Region *region = point.get<Block *>()->getParent();
270  branch,
271  RegionSuccessor(region, region->getArguments().slice(
272  firstIndex, inputs.size())),
273  lattices, firstIndex);
274  }
275  }
276 
277  for (auto it : llvm::zip(*operands, lattices.drop_front(firstIndex)))
278  join(std::get<1>(it), *getLatticeElementFor(point, std::get<0>(it)));
279  }
280 }
281 
282 const AbstractSparseLattice *
284  Value value) {
286  addDependency(state, point);
287  return state;
288 }
289 
292  for (AbstractSparseLattice *lattice : lattices)
293  setToEntryState(lattice);
294 }
295 
297  AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs) {
298  propagateIfChanged(lhs, lhs->join(rhs));
299 }
300 
301 //===----------------------------------------------------------------------===//
302 // AbstractSparseBackwardDataFlowAnalysis
303 //===----------------------------------------------------------------------===//
304 
306  DataFlowSolver &solver, SymbolTableCollection &symbolTable)
307  : DataFlowAnalysis(solver), symbolTable(symbolTable) {
308  registerPointKind<CFGEdge>();
309 }
310 
313  return initializeRecursively(top);
314 }
315 
317 AbstractSparseBackwardDataFlowAnalysis::initializeRecursively(Operation *op) {
318  visitOperation(op);
319  for (Region &region : op->getRegions()) {
320  for (Block &block : region) {
321  getOrCreate<Executable>(&block)->blockContentSubscribe(this);
322  // Initialize ops in reverse order, so we can do as much initial
323  // propagation as possible without having to go through the
324  // solver queue.
325  for (auto it = block.rbegin(); it != block.rend(); it++)
326  if (failed(initializeRecursively(&*it)))
327  return failure();
328  }
329  }
330  return success();
331 }
332 
335  if (Operation *op = llvm::dyn_cast_if_present<Operation *>(point))
336  visitOperation(op);
337  else if (llvm::dyn_cast_if_present<Block *>(point))
338  // For backward dataflow, we don't have to do any work for the blocks
339  // themselves. CFG edges between blocks are processed by the BranchOp
340  // logic in `visitOperation`, and entry blocks for functions are tied
341  // to the CallOp arguments by visitOperation.
342  return success();
343  else
344  return failure();
345  return success();
346 }
347 
351  resultLattices.reserve(values.size());
352  for (Value result : values) {
353  AbstractSparseLattice *resultLattice = getLatticeElement(result);
354  resultLattices.push_back(resultLattice);
355  }
356  return resultLattices;
357 }
358 
360 AbstractSparseBackwardDataFlowAnalysis::getLatticeElementsFor(
361  ProgramPoint point, ValueRange values) {
363  resultLattices.reserve(values.size());
364  for (Value result : values) {
365  const AbstractSparseLattice *resultLattice =
366  getLatticeElementFor(point, result);
367  resultLattices.push_back(resultLattice);
368  }
369  return resultLattices;
370 }
371 
373  return MutableArrayRef<OpOperand>(operands.getBase(), operands.size());
374 }
375 
376 void AbstractSparseBackwardDataFlowAnalysis::visitOperation(Operation *op) {
377  // If we're in a dead block, bail out.
378  if (!getOrCreate<Executable>(op->getBlock())->isLive())
379  return;
380 
381  SmallVector<AbstractSparseLattice *> operandLattices =
384  getLatticeElementsFor(op, op->getResults());
385 
386  // Block arguments of region branch operations flow back into the operands
387  // of the parent op
388  if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
389  visitRegionSuccessors(branch, operandLattices);
390  return;
391  }
392 
393  if (auto branch = dyn_cast<BranchOpInterface>(op)) {
394  // Block arguments of successor blocks flow back into our operands.
395 
396  // We remember all operands not forwarded to any block in a BitVector.
397  // We can't just cut out a range here, since the non-forwarded ops might
398  // be non-contiguous (if there's more than one successor).
399  BitVector unaccounted(op->getNumOperands(), true);
400 
401  for (auto [index, block] : llvm::enumerate(op->getSuccessors())) {
402  SuccessorOperands successorOperands = branch.getSuccessorOperands(index);
403  OperandRange forwarded = successorOperands.getForwardedOperands();
404  if (!forwarded.empty()) {
405  MutableArrayRef<OpOperand> operands = op->getOpOperands().slice(
406  forwarded.getBeginOperandIndex(), forwarded.size());
407  for (OpOperand &operand : operands) {
408  unaccounted.reset(operand.getOperandNumber());
409  if (std::optional<BlockArgument> blockArg =
411  successorOperands, operand.getOperandNumber(), block)) {
412  meet(getLatticeElement(operand.get()),
413  *getLatticeElementFor(op, *blockArg));
414  }
415  }
416  }
417  }
418  // Operands not forwarded to successor blocks are typically parameters
419  // of the branch operation itself (for example the boolean for if/else).
420  for (int index : unaccounted.set_bits()) {
421  OpOperand &operand = op->getOpOperand(index);
422  visitBranchOperand(operand);
423  }
424  return;
425  }
426 
427  // For function calls, connect the arguments of the entry blocks to the
428  // operands of the call op that are forwarded to these arguments.
429  if (auto call = dyn_cast<CallOpInterface>(op)) {
430  Operation *callableOp = call.resolveCallable(&symbolTable);
431  if (auto callable = dyn_cast_or_null<CallableOpInterface>(callableOp)) {
432  // Not all operands of a call op forward to arguments. Such operands are
433  // stored in `unaccounted`.
434  BitVector unaccounted(op->getNumOperands(), true);
435 
436  OperandRange argOperands = call.getArgOperands();
437  MutableArrayRef<OpOperand> argOpOperands =
438  operandsToOpOperands(argOperands);
439  Region *region = callable.getCallableRegion();
440  if (region && !region->empty()) {
441  Block &block = region->front();
442  for (auto [blockArg, argOpOperand] :
443  llvm::zip(block.getArguments(), argOpOperands)) {
444  meet(getLatticeElement(argOpOperand.get()),
445  *getLatticeElementFor(op, blockArg));
446  unaccounted.reset(argOpOperand.getOperandNumber());
447  }
448  }
449  // Handle the operands of the call op that aren't forwarded to any
450  // arguments.
451  for (int index : unaccounted.set_bits()) {
452  OpOperand &opOperand = op->getOpOperand(index);
453  visitCallOperand(opOperand);
454  }
455  return;
456  }
457  }
458 
459  // When the region of an op implementing `RegionBranchOpInterface` has a
460  // terminator implementing `RegionBranchTerminatorOpInterface` or a
461  // return-like terminator, the region's successors' arguments flow back into
462  // the "successor operands" of this terminator.
463  //
464  // A successor operand with respect to an op implementing
465  // `RegionBranchOpInterface` is an operand that is forwarded to a region
466  // successor's input. There are two types of successor operands: the operands
467  // of this op itself and the operands of the terminators of the regions of
468  // this op.
469  if (auto terminator = dyn_cast<RegionBranchTerminatorOpInterface>(op)) {
470  if (auto branch = dyn_cast<RegionBranchOpInterface>(op->getParentOp())) {
471  visitRegionSuccessorsFromTerminator(terminator, branch);
472  return;
473  }
474  }
475 
476  if (op->hasTrait<OpTrait::ReturnLike>()) {
477  // Going backwards, the operands of the return are derived from the
478  // results of all CallOps calling this CallableOp.
479  if (auto callable = dyn_cast<CallableOpInterface>(op->getParentOp())) {
480  const PredecessorState *callsites =
481  getOrCreateFor<PredecessorState>(op, callable);
482  if (callsites->allPredecessorsKnown()) {
483  for (Operation *call : callsites->getKnownPredecessors()) {
484  SmallVector<const AbstractSparseLattice *> callResultLattices =
485  getLatticeElementsFor(op, call->getResults());
486  for (auto [op, result] :
487  llvm::zip(operandLattices, callResultLattices))
488  meet(op, *result);
489  }
490  } else {
491  // If we don't know all the callers, we can't know where the
492  // returned values go. Note that, in particular, this will trigger
493  // for the return ops of any public functions.
494  setAllToExitStates(operandLattices);
495  }
496  return;
497  }
498  }
499 
500  visitOperationImpl(op, operandLattices, resultLattices);
501 }
502 
503 void AbstractSparseBackwardDataFlowAnalysis::visitRegionSuccessors(
504  RegionBranchOpInterface branch,
505  ArrayRef<AbstractSparseLattice *> operandLattices) {
506  Operation *op = branch.getOperation();
507  SmallVector<RegionSuccessor> successors;
508  SmallVector<Attribute> operands(op->getNumOperands(), nullptr);
509  branch.getEntrySuccessorRegions(operands, successors);
510 
511  // All operands not forwarded to any successor. This set can be non-contiguous
512  // in the presence of multiple successors.
513  BitVector unaccounted(op->getNumOperands(), true);
514 
515  for (RegionSuccessor &successor : successors) {
516  OperandRange operands = branch.getEntrySuccessorOperands(successor);
517  MutableArrayRef<OpOperand> opoperands = operandsToOpOperands(operands);
518  ValueRange inputs = successor.getSuccessorInputs();
519  for (auto [operand, input] : llvm::zip(opoperands, inputs)) {
520  meet(getLatticeElement(operand.get()), *getLatticeElementFor(op, input));
521  unaccounted.reset(operand.getOperandNumber());
522  }
523  }
524  // All operands not forwarded to regions are typically parameters of the
525  // branch operation itself (for example the boolean for if/else).
526  for (int index : unaccounted.set_bits()) {
527  visitBranchOperand(op->getOpOperand(index));
528  }
529 }
530 
531 void AbstractSparseBackwardDataFlowAnalysis::
532  visitRegionSuccessorsFromTerminator(
533  RegionBranchTerminatorOpInterface terminator,
534  RegionBranchOpInterface branch) {
535  assert(isa<RegionBranchTerminatorOpInterface>(terminator) &&
536  "expected a `RegionBranchTerminatorOpInterface` op");
537  assert(terminator->getParentOp() == branch.getOperation() &&
538  "expected `branch` to be the parent op of `terminator`");
539 
540  SmallVector<Attribute> operandAttributes(terminator->getNumOperands(),
541  nullptr);
542  SmallVector<RegionSuccessor> successors;
543  terminator.getSuccessorRegions(operandAttributes, successors);
544  // All operands not forwarded to any successor. This set can be
545  // non-contiguous in the presence of multiple successors.
546  BitVector unaccounted(terminator->getNumOperands(), true);
547 
548  for (const RegionSuccessor &successor : successors) {
549  ValueRange inputs = successor.getSuccessorInputs();
550  OperandRange operands = terminator.getSuccessorOperands(successor);
551  MutableArrayRef<OpOperand> opOperands = operandsToOpOperands(operands);
552  for (auto [opOperand, input] : llvm::zip(opOperands, inputs)) {
553  meet(getLatticeElement(opOperand.get()),
554  *getLatticeElementFor(terminator, input));
555  unaccounted.reset(const_cast<OpOperand &>(opOperand).getOperandNumber());
556  }
557  }
558  // Visit operands of the branch op not forwarded to the next region.
559  // (Like e.g. the boolean of `scf.conditional`)
560  for (int index : unaccounted.set_bits()) {
561  visitBranchOperand(terminator->getOpOperand(index));
562  }
563 }
564 
565 const AbstractSparseLattice *
566 AbstractSparseBackwardDataFlowAnalysis::getLatticeElementFor(ProgramPoint point,
567  Value value) {
569  addDependency(state, point);
570  return state;
571 }
572 
575  for (AbstractSparseLattice *lattice : lattices)
576  setToExitState(lattice);
577 }
578 
580  AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs) {
581  propagateIfChanged(lhs, lhs->meet(rhs));
582 }
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.
Definition: Value.h:315
Block represents an ordered list of Operations.
Definition: Block.h:30
unsigned getNumArguments()
Definition: Block.h:121
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
Definition: Block.cpp:26
pred_iterator pred_begin()
Definition: Block.h:226
Operation * getTerminator()
Get the terminator operation of this block.
Definition: Block.cpp:238
reverse_iterator rend()
Definition: Block.h:139
BlockArgListType getArguments()
Definition: Block.h:80
bool isEntryBlock()
Return if this block is the entry block in the parent region.
Definition: Block.cpp:35
pred_iterator pred_end()
Definition: Block.h:229
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Definition: Block.cpp:30
reverse_iterator rbegin()
Definition: Block.h:138
Base class for all data-flow analyses.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
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.
Definition: Value.h:263
This class implements the operand iterators for the Operation class.
Definition: ValueRange.h:42
unsigned getBeginOperandIndex() const
Return the operand index of the first element of this range.
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:728
OpOperand & getOpOperand(unsigned idx)
Definition: Operation.h:383
unsigned getNumOperands()
Definition: Operation.h:341
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:234
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:213
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:655
MutableArrayRef< OpOperand > getOpOperands()
Definition: Operation.h:378
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:373
SuccessorRange getSuccessors()
Definition: Operation.h:682
result_range getResults()
Definition: Operation.h:410
unsigned getNumResults()
Return the number of results held by this operation.
Definition: Operation.h:399
Implement a predecessor iterator for blocks.
Definition: BlockSupport.h:51
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.
Definition: Region.h:26
BlockArgListType getArguments()
Definition: Region.h:81
bool empty()
Definition: Region.h:60
Block & front()
Definition: Region.h:65
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.
Definition: SymbolTable.h:283
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:378
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
user_range getUsers() const
Definition: Value.h:224
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 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.
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)
Definition: Matchers.h:285
Include the generated interface declarations.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:72
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
This trait indicates that a terminator operation is "return-like".
Fundamental IR components are supported as first-class program points.