MLIR  22.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"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/Support/DebugLog.h"
23 #include <cassert>
24 #include <optional>
25 
26 using namespace mlir;
27 using namespace mlir::dataflow;
28 
29 #define DEBUG_TYPE "dataflow"
30 
31 //===----------------------------------------------------------------------===//
32 // AbstractSparseLattice
33 //===----------------------------------------------------------------------===//
34 
37 
38  // Push all users of the value to the queue.
39  for (Operation *user : cast<Value>(anchor).getUsers())
40  for (DataFlowAnalysis *analysis : useDefSubscribers)
41  solver->enqueue({solver->getProgramPointAfter(user), analysis});
42 }
43 
44 //===----------------------------------------------------------------------===//
45 // AbstractSparseForwardDataFlowAnalysis
46 //===----------------------------------------------------------------------===//
47 
49  DataFlowSolver &solver)
50  : DataFlowAnalysis(solver) {
51  registerAnchorKind<CFGEdge>();
52 }
53 
54 LogicalResult
56  // Mark the entry block arguments as having reached their pessimistic
57  // fixpoints.
58  for (Region &region : top->getRegions()) {
59  if (region.empty())
60  continue;
61  for (Value argument : region.front().getArguments())
63  }
64 
65  return initializeRecursively(top);
66 }
67 
68 LogicalResult
69 AbstractSparseForwardDataFlowAnalysis::initializeRecursively(Operation *op) {
70  LDBG() << "Initializing recursively for operation: " << op->getName();
71 
72  // Initialize the analysis by visiting every owner of an SSA value (all
73  // operations and blocks).
74  if (failed(visitOperation(op))) {
75  LDBG() << "Failed to visit operation: " << op->getName();
76  return failure();
77  }
78 
79  for (Region &region : op->getRegions()) {
80  LDBG() << "Processing region with " << region.getBlocks().size()
81  << " blocks";
82  for (Block &block : region) {
83  LDBG() << "Processing block with " << block.getNumArguments()
84  << " arguments";
85  getOrCreate<Executable>(getProgramPointBefore(&block))
86  ->blockContentSubscribe(this);
87  visitBlock(&block);
88  for (Operation &op : block) {
89  LDBG() << "Recursively initializing nested operation: " << op.getName();
90  if (failed(initializeRecursively(&op))) {
91  LDBG() << "Failed to initialize nested operation: " << op.getName();
92  return failure();
93  }
94  }
95  }
96  }
97 
98  LDBG() << "Successfully completed recursive initialization for operation: "
99  << op->getName();
100  return success();
101 }
102 
103 LogicalResult
105  if (!point->isBlockStart())
106  return visitOperation(point->getPrevOp());
107  visitBlock(point->getBlock());
108  return success();
109 }
110 
111 LogicalResult
112 AbstractSparseForwardDataFlowAnalysis::visitOperation(Operation *op) {
113  // Exit early on operations with no results.
114  if (op->getNumResults() == 0)
115  return success();
116 
117  // If the containing block is not executable, bail out.
118  if (op->getBlock() != nullptr &&
119  !getOrCreate<Executable>(getProgramPointBefore(op->getBlock()))->isLive())
120  return success();
121 
122  // Get the result lattices.
124  resultLattices.reserve(op->getNumResults());
125  for (Value result : op->getResults()) {
126  AbstractSparseLattice *resultLattice = getLatticeElement(result);
127  resultLattices.push_back(resultLattice);
128  }
129 
130  // The results of a region branch operation are determined by control-flow.
131  if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
132  visitRegionSuccessors(getProgramPointAfter(branch), branch,
133  /*successor=*/RegionBranchPoint::parent(),
134  resultLattices);
135  return success();
136  }
137 
138  // Grab the lattice elements of the operands.
140  operandLattices.reserve(op->getNumOperands());
141  for (Value operand : op->getOperands()) {
142  AbstractSparseLattice *operandLattice = getLatticeElement(operand);
143  operandLattice->useDefSubscribe(this);
144  operandLattices.push_back(operandLattice);
145  }
146 
147  if (auto call = dyn_cast<CallOpInterface>(op))
148  return visitCallOperation(call, operandLattices, resultLattices);
149 
150  // Invoke the operation transfer function.
151  return visitOperationImpl(op, operandLattices, resultLattices);
152 }
153 
154 void AbstractSparseForwardDataFlowAnalysis::visitBlock(Block *block) {
155  // Exit early on blocks with no arguments.
156  if (block->getNumArguments() == 0)
157  return;
158 
159  // If the block is not executable, bail out.
160  if (!getOrCreate<Executable>(getProgramPointBefore(block))->isLive())
161  return;
162 
163  // Get the argument lattices.
165  argLattices.reserve(block->getNumArguments());
166  for (BlockArgument argument : block->getArguments()) {
167  AbstractSparseLattice *argLattice = getLatticeElement(argument);
168  argLattices.push_back(argLattice);
169  }
170 
171  // The argument lattices of entry blocks are set by region control-flow or the
172  // callgraph.
173  if (block->isEntryBlock()) {
174  // Check if this block is the entry block of a callable region.
175  auto callable = dyn_cast<CallableOpInterface>(block->getParentOp());
176  if (callable && callable.getCallableRegion() == block->getParent())
177  return visitCallableOperation(callable, argLattices);
178 
179  // Check if the lattices can be determined from region control flow.
180  if (auto branch = dyn_cast<RegionBranchOpInterface>(block->getParentOp())) {
181  return visitRegionSuccessors(getProgramPointBefore(block), branch,
182  block->getParent(), argLattices);
183  }
184 
185  // Otherwise, we can't reason about the data-flow.
187  RegionSuccessor(block->getParent()),
188  argLattices, /*firstIndex=*/0);
189  }
190 
191  // Iterate over the predecessors of the non-entry block.
192  for (Block::pred_iterator it = block->pred_begin(), e = block->pred_end();
193  it != e; ++it) {
194  Block *predecessor = *it;
195 
196  // If the edge from the predecessor block to the current block is not live,
197  // bail out.
198  auto *edgeExecutable =
199  getOrCreate<Executable>(getLatticeAnchor<CFGEdge>(predecessor, block));
200  edgeExecutable->blockContentSubscribe(this);
201  if (!edgeExecutable->isLive())
202  continue;
203 
204  // Check if we can reason about the data-flow from the predecessor.
205  if (auto branch =
206  dyn_cast<BranchOpInterface>(predecessor->getTerminator())) {
207  SuccessorOperands operands =
208  branch.getSuccessorOperands(it.getSuccessorIndex());
209  for (auto [idx, lattice] : llvm::enumerate(argLattices)) {
210  if (Value operand = operands[idx]) {
211  join(lattice,
212  *getLatticeElementFor(getProgramPointBefore(block), operand));
213  } else {
214  // Conservatively consider internally produced arguments as entry
215  // points.
216  setAllToEntryStates(lattice);
217  }
218  }
219  } else {
220  return setAllToEntryStates(argLattices);
221  }
222  }
223 }
224 
226  CallOpInterface call,
228  ArrayRef<AbstractSparseLattice *> resultLattices) {
229  // If the call operation is to an external function, attempt to infer the
230  // results from the call arguments.
231  auto callable =
232  dyn_cast_if_present<CallableOpInterface>(call.resolveCallable());
233  if (!getSolverConfig().isInterprocedural() ||
234  (callable && !callable.getCallableRegion())) {
235  visitExternalCallImpl(call, operandLattices, resultLattices);
236  return success();
237  }
238 
239  // Otherwise, the results of a call operation are determined by the
240  // callgraph.
241  const auto *predecessors = getOrCreateFor<PredecessorState>(
243  // If not all return sites are known, then conservatively assume we can't
244  // reason about the data-flow.
245  if (!predecessors->allPredecessorsKnown()) {
246  setAllToEntryStates(resultLattices);
247  return success();
248  }
249  for (Operation *predecessor : predecessors->getKnownPredecessors())
250  for (auto &&[operand, resLattice] :
251  llvm::zip(predecessor->getOperands(), resultLattices))
252  join(resLattice,
253  *getLatticeElementFor(getProgramPointAfter(call), operand));
254  return success();
255 }
256 
258  CallableOpInterface callable,
259  ArrayRef<AbstractSparseLattice *> argLattices) {
260  Block *entryBlock = &callable.getCallableRegion()->front();
261  const auto *callsites = getOrCreateFor<PredecessorState>(
262  getProgramPointBefore(entryBlock), getProgramPointAfter(callable));
263  // If not all callsites are known, conservatively mark all lattices as
264  // having reached their pessimistic fixpoints.
265  if (!callsites->allPredecessorsKnown() ||
266  !getSolverConfig().isInterprocedural()) {
267  return setAllToEntryStates(argLattices);
268  }
269  for (Operation *callsite : callsites->getKnownPredecessors()) {
270  auto call = cast<CallOpInterface>(callsite);
271  for (auto it : llvm::zip(call.getArgOperands(), argLattices))
272  join(std::get<1>(it),
274  std::get<0>(it)));
275  }
276 }
277 
278 void AbstractSparseForwardDataFlowAnalysis::visitRegionSuccessors(
279  ProgramPoint *point, RegionBranchOpInterface branch,
281  const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
282  assert(predecessors->allPredecessorsKnown() &&
283  "unexpected unresolved region successors");
284 
285  for (Operation *op : predecessors->getKnownPredecessors()) {
286  // Get the incoming successor operands.
287  std::optional<OperandRange> operands;
288 
289  // Check if the predecessor is the parent op.
290  if (op == branch) {
291  operands = branch.getEntrySuccessorOperands(successor);
292  // Otherwise, try to deduce the operands from a region return-like op.
293  } else if (auto regionTerminator =
294  dyn_cast<RegionBranchTerminatorOpInterface>(op)) {
295  operands = regionTerminator.getSuccessorOperands(successor);
296  }
297 
298  if (!operands) {
299  // We can't reason about the data-flow.
300  return setAllToEntryStates(lattices);
301  }
302 
303  ValueRange inputs = predecessors->getSuccessorInputs(op);
304  assert(inputs.size() == operands->size() &&
305  "expected the same number of successor inputs as operands");
306 
307  unsigned firstIndex = 0;
308  if (inputs.size() != lattices.size()) {
309  if (!point->isBlockStart()) {
310  if (!inputs.empty())
311  firstIndex = cast<OpResult>(inputs.front()).getResultNumber();
313  branch,
315  branch->getResults().slice(firstIndex, inputs.size())),
316  lattices, firstIndex);
317  } else {
318  if (!inputs.empty())
319  firstIndex = cast<BlockArgument>(inputs.front()).getArgNumber();
320  Region *region = point->getBlock()->getParent();
322  branch,
323  RegionSuccessor(region, region->getArguments().slice(
324  firstIndex, inputs.size())),
325  lattices, firstIndex);
326  }
327  }
328 
329  for (auto it : llvm::zip(*operands, lattices.drop_front(firstIndex)))
330  join(std::get<1>(it), *getLatticeElementFor(point, std::get<0>(it)));
331  }
332 }
333 
334 const AbstractSparseLattice *
336  Value value) {
338  addDependency(state, point);
339  return state;
340 }
341 
344  for (AbstractSparseLattice *lattice : lattices)
345  setToEntryState(lattice);
346 }
347 
349  AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs) {
350  propagateIfChanged(lhs, lhs->join(rhs));
351 }
352 
353 //===----------------------------------------------------------------------===//
354 // AbstractSparseBackwardDataFlowAnalysis
355 //===----------------------------------------------------------------------===//
356 
358  DataFlowSolver &solver, SymbolTableCollection &symbolTable)
359  : DataFlowAnalysis(solver), symbolTable(symbolTable) {
360  registerAnchorKind<CFGEdge>();
361 }
362 
363 LogicalResult
365  return initializeRecursively(top);
366 }
367 
368 LogicalResult
369 AbstractSparseBackwardDataFlowAnalysis::initializeRecursively(Operation *op) {
370  if (failed(visitOperation(op)))
371  return failure();
372 
373  for (Region &region : op->getRegions()) {
374  for (Block &block : region) {
375  getOrCreate<Executable>(getProgramPointBefore(&block))
376  ->blockContentSubscribe(this);
377  // Initialize ops in reverse order, so we can do as much initial
378  // propagation as possible without having to go through the
379  // solver queue.
380  for (auto it = block.rbegin(); it != block.rend(); it++)
381  if (failed(initializeRecursively(&*it)))
382  return failure();
383  }
384  }
385  return success();
386 }
387 
388 LogicalResult
390  // For backward dataflow, we don't have to do any work for the blocks
391  // themselves. CFG edges between blocks are processed by the BranchOp
392  // logic in `visitOperation`, and entry blocks for functions are tied
393  // to the CallOp arguments by visitOperation.
394  if (point->isBlockStart())
395  return success();
396  return visitOperation(point->getPrevOp());
397 }
398 
402  resultLattices.reserve(values.size());
403  for (Value result : values) {
404  AbstractSparseLattice *resultLattice = getLatticeElement(result);
405  resultLattices.push_back(resultLattice);
406  }
407  return resultLattices;
408 }
409 
411 AbstractSparseBackwardDataFlowAnalysis::getLatticeElementsFor(
412  ProgramPoint *point, ValueRange values) {
414  resultLattices.reserve(values.size());
415  for (Value result : values) {
416  const AbstractSparseLattice *resultLattice =
417  getLatticeElementFor(point, result);
418  resultLattices.push_back(resultLattice);
419  }
420  return resultLattices;
421 }
422 
424  return MutableArrayRef<OpOperand>(operands.getBase(), operands.size());
425 }
426 
427 LogicalResult
428 AbstractSparseBackwardDataFlowAnalysis::visitOperation(Operation *op) {
429  LDBG() << "Visiting operation: " << op->getName() << " with "
430  << op->getNumOperands() << " operands and " << op->getNumResults()
431  << " results";
432 
433  // If we're in a dead block, bail out.
434  if (op->getBlock() != nullptr &&
435  !getOrCreate<Executable>(getProgramPointBefore(op->getBlock()))
436  ->isLive()) {
437  LDBG() << "Operation is in dead block, bailing out";
438  return success();
439  }
440 
441  LDBG() << "Creating lattice elements for " << op->getNumOperands()
442  << " operands and " << op->getNumResults() << " results";
443  SmallVector<AbstractSparseLattice *> operandLattices =
446  getLatticeElementsFor(getProgramPointAfter(op), op->getResults());
447 
448  // Block arguments of region branch operations flow back into the operands
449  // of the parent op
450  if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
451  LDBG() << "Processing RegionBranchOpInterface operation";
452  visitRegionSuccessors(branch, operandLattices);
453  return success();
454  }
455 
456  if (auto branch = dyn_cast<BranchOpInterface>(op)) {
457  LDBG() << "Processing BranchOpInterface operation with "
458  << op->getNumSuccessors() << " successors";
459 
460  // Block arguments of successor blocks flow back into our operands.
461 
462  // We remember all operands not forwarded to any block in a BitVector.
463  // We can't just cut out a range here, since the non-forwarded ops might
464  // be non-contiguous (if there's more than one successor).
465  BitVector unaccounted(op->getNumOperands(), true);
466 
467  for (auto [index, block] : llvm::enumerate(op->getSuccessors())) {
468  SuccessorOperands successorOperands = branch.getSuccessorOperands(index);
469  OperandRange forwarded = successorOperands.getForwardedOperands();
470  if (!forwarded.empty()) {
471  MutableArrayRef<OpOperand> operands = op->getOpOperands().slice(
472  forwarded.getBeginOperandIndex(), forwarded.size());
473  for (OpOperand &operand : operands) {
474  unaccounted.reset(operand.getOperandNumber());
475  if (std::optional<BlockArgument> blockArg =
477  successorOperands, operand.getOperandNumber(), block)) {
478  meet(getLatticeElement(operand.get()),
479  *getLatticeElementFor(getProgramPointAfter(op), *blockArg));
480  }
481  }
482  }
483  }
484  // Operands not forwarded to successor blocks are typically parameters
485  // of the branch operation itself (for example the boolean for if/else).
486  for (int index : unaccounted.set_bits()) {
487  OpOperand &operand = op->getOpOperand(index);
488  visitBranchOperand(operand);
489  }
490  return success();
491  }
492 
493  // For function calls, connect the arguments of the entry blocks to the
494  // operands of the call op that are forwarded to these arguments.
495  if (auto call = dyn_cast<CallOpInterface>(op)) {
496  LDBG() << "Processing CallOpInterface operation";
497  Operation *callableOp = call.resolveCallableInTable(&symbolTable);
498  if (auto callable = dyn_cast_or_null<CallableOpInterface>(callableOp)) {
499  // Not all operands of a call op forward to arguments. Such operands are
500  // stored in `unaccounted`.
501  BitVector unaccounted(op->getNumOperands(), true);
502 
503  // If the call invokes an external function (or a function treated as
504  // external due to config), defer to the corresponding extension hook.
505  // By default, it just does `visitCallOperand` for all operands.
506  OperandRange argOperands = call.getArgOperands();
507  MutableArrayRef<OpOperand> argOpOperands =
508  operandsToOpOperands(argOperands);
509  Region *region = callable.getCallableRegion();
510  if (!region || region->empty() ||
511  !getSolverConfig().isInterprocedural()) {
512  visitExternalCallImpl(call, operandLattices, resultLattices);
513  return success();
514  }
515 
516  // Otherwise, propagate information from the entry point of the function
517  // back to operands whenever possible.
518  Block &block = region->front();
519  for (auto [blockArg, argOpOperand] :
520  llvm::zip(block.getArguments(), argOpOperands)) {
521  meet(getLatticeElement(argOpOperand.get()),
522  *getLatticeElementFor(getProgramPointAfter(op), blockArg));
523  unaccounted.reset(argOpOperand.getOperandNumber());
524  }
525 
526  // Handle the operands of the call op that aren't forwarded to any
527  // arguments.
528  for (int index : unaccounted.set_bits()) {
529  OpOperand &opOperand = op->getOpOperand(index);
530  visitCallOperand(opOperand);
531  }
532  return success();
533  }
534  }
535 
536  // When the region of an op implementing `RegionBranchOpInterface` has a
537  // terminator implementing `RegionBranchTerminatorOpInterface` or a
538  // return-like terminator, the region's successors' arguments flow back into
539  // the "successor operands" of this terminator.
540  //
541  // A successor operand with respect to an op implementing
542  // `RegionBranchOpInterface` is an operand that is forwarded to a region
543  // successor's input. There are two types of successor operands: the operands
544  // of this op itself and the operands of the terminators of the regions of
545  // this op.
546  if (auto terminator = dyn_cast<RegionBranchTerminatorOpInterface>(op)) {
547  LDBG() << "Processing RegionBranchTerminatorOpInterface operation";
548  if (auto branch = dyn_cast<RegionBranchOpInterface>(op->getParentOp())) {
549  visitRegionSuccessorsFromTerminator(terminator, branch);
550  return success();
551  }
552  }
553 
554  if (op->hasTrait<OpTrait::ReturnLike>()) {
555  LDBG() << "Processing ReturnLike operation";
556  // Going backwards, the operands of the return are derived from the
557  // results of all CallOps calling this CallableOp.
558  if (auto callable = dyn_cast<CallableOpInterface>(op->getParentOp())) {
559  LDBG() << "Callable parent found, visiting callable operation";
560  return visitCallableOperation(op, callable, operandLattices);
561  }
562  }
563 
564  LDBG() << "Using default visitOperationImpl for operation: " << op->getName();
565  return visitOperationImpl(op, operandLattices, resultLattices);
566 }
567 
569  Operation *op, CallableOpInterface callable,
570  ArrayRef<AbstractSparseLattice *> operandLattices) {
571  const PredecessorState *callsites = getOrCreateFor<PredecessorState>(
573  if (callsites->allPredecessorsKnown()) {
574  for (Operation *call : callsites->getKnownPredecessors()) {
575  SmallVector<const AbstractSparseLattice *> callResultLattices =
576  getLatticeElementsFor(getProgramPointAfter(op), call->getResults());
577  for (auto [op, result] : llvm::zip(operandLattices, callResultLattices))
578  meet(op, *result);
579  }
580  } else {
581  // If we don't know all the callers, we can't know where the
582  // returned values go. Note that, in particular, this will trigger
583  // for the return ops of any public functions.
584  setAllToExitStates(operandLattices);
585  }
586  return success();
587 }
588 
589 void AbstractSparseBackwardDataFlowAnalysis::visitRegionSuccessors(
590  RegionBranchOpInterface branch,
591  ArrayRef<AbstractSparseLattice *> operandLattices) {
592  Operation *op = branch.getOperation();
593  SmallVector<RegionSuccessor> successors;
594  SmallVector<Attribute> operands(op->getNumOperands(), nullptr);
595  branch.getEntrySuccessorRegions(operands, successors);
596 
597  // All operands not forwarded to any successor. This set can be non-contiguous
598  // in the presence of multiple successors.
599  BitVector unaccounted(op->getNumOperands(), true);
600 
601  for (RegionSuccessor &successor : successors) {
602  OperandRange operands = branch.getEntrySuccessorOperands(successor);
603  MutableArrayRef<OpOperand> opoperands = operandsToOpOperands(operands);
604  ValueRange inputs = successor.getSuccessorInputs();
605  for (auto [operand, input] : llvm::zip(opoperands, inputs)) {
606  meet(getLatticeElement(operand.get()),
607  *getLatticeElementFor(getProgramPointAfter(op), input));
608  unaccounted.reset(operand.getOperandNumber());
609  }
610  }
611  // All operands not forwarded to regions are typically parameters of the
612  // branch operation itself (for example the boolean for if/else).
613  for (int index : unaccounted.set_bits()) {
614  visitBranchOperand(op->getOpOperand(index));
615  }
616 }
617 
618 void AbstractSparseBackwardDataFlowAnalysis::
619  visitRegionSuccessorsFromTerminator(
620  RegionBranchTerminatorOpInterface terminator,
621  RegionBranchOpInterface branch) {
622  assert(isa<RegionBranchTerminatorOpInterface>(terminator) &&
623  "expected a `RegionBranchTerminatorOpInterface` op");
624  assert(terminator->getParentOp() == branch.getOperation() &&
625  "expected `branch` to be the parent op of `terminator`");
626 
627  SmallVector<Attribute> operandAttributes(terminator->getNumOperands(),
628  nullptr);
629  SmallVector<RegionSuccessor> successors;
630  terminator.getSuccessorRegions(operandAttributes, successors);
631  // All operands not forwarded to any successor. This set can be
632  // non-contiguous in the presence of multiple successors.
633  BitVector unaccounted(terminator->getNumOperands(), true);
634 
635  for (const RegionSuccessor &successor : successors) {
636  ValueRange inputs = successor.getSuccessorInputs();
637  OperandRange operands = terminator.getSuccessorOperands(successor);
638  MutableArrayRef<OpOperand> opOperands = operandsToOpOperands(operands);
639  for (auto [opOperand, input] : llvm::zip(opOperands, inputs)) {
640  meet(getLatticeElement(opOperand.get()),
641  *getLatticeElementFor(getProgramPointAfter(terminator), input));
642  unaccounted.reset(const_cast<OpOperand &>(opOperand).getOperandNumber());
643  }
644  }
645  // Visit operands of the branch op not forwarded to the next region.
646  // (Like e.g. the boolean of `scf.conditional`)
647  for (int index : unaccounted.set_bits()) {
648  visitBranchOperand(terminator->getOpOperand(index));
649  }
650 }
651 
652 const AbstractSparseLattice *
653 AbstractSparseBackwardDataFlowAnalysis::getLatticeElementFor(
654  ProgramPoint *point, Value value) {
656  addDependency(state, point);
657  return state;
658 }
659 
662  for (AbstractSparseLattice *lattice : lattices)
663  setToExitState(lattice);
664 }
665 
667  AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs) {
668  propagateIfChanged(lhs, lhs->meet(rhs));
669 }
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.
LatticeAnchor anchor
The lattice anchor to which the state belongs.
This class represents an argument of a Block.
Definition: Value.h:309
Block represents an ordered list of Operations.
Definition: Block.h:33
unsigned getNumArguments()
Definition: Block.h:128
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
Definition: Block.cpp:27
pred_iterator pred_begin()
Definition: Block.h:236
Operation * getTerminator()
Get the terminator operation of this block.
Definition: Block.cpp:244
reverse_iterator rend()
Definition: Block.h:146
BlockArgListType getArguments()
Definition: Block.h:87
Operation & front()
Definition: Block.h:153
bool isEntryBlock()
Return if this block is the entry block in the parent region.
Definition: Block.cpp:36
pred_iterator pred_end()
Definition: Block.h:239
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Definition: Block.cpp:31
reverse_iterator rbegin()
Definition: Block.h:145
Base class for all data-flow analyses.
void addDependency(AnalysisState *state, ProgramPoint *point)
Create a dependency between the given analysis state and lattice anchor on this analysis.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
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.
The general data-flow analysis solver.
void enqueue(WorkItem item)
Push a work item onto the worklist.
ProgramPoint * getProgramPointAfter(Operation *op)
This class represents an operand of an operation.
Definition: Value.h:257
This class implements the operand iterators for the Operation class.
Definition: ValueRange.h:43
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:749
OpOperand & getOpOperand(unsigned idx)
Definition: Operation.h:388
unsigned getNumSuccessors()
Definition: Operation.h:706
unsigned getNumOperands()
Definition: Operation.h:346
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:677
OperationName getName()
The name of an operation is the key identifier for it.
Definition: Operation.h:119
MutableArrayRef< OpOperand > getOpOperands()
Definition: Operation.h:383
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:378
SuccessorRange getSuccessors()
Definition: Operation.h:703
result_range getResults()
Definition: Operation.h:415
unsigned getNumResults()
Return the number of results held by this operation.
Definition: Operation.h:404
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:387
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
virtual void setToExitState(AbstractSparseLattice *lattice)=0
Set the given lattice element(s) at control flow exit point(s) and propagate the update if it chaned.
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 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 LogicalResult visitCallableOperation(Operation *op, CallableOpInterface callable, ArrayRef< AbstractSparseLattice * > operandLattices)
Visits a callable operation.
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) and propagate the update if it chaned.
virtual LogicalResult visitOperationImpl(Operation *op, ArrayRef< AbstractSparseLattice * > operandLattices, ArrayRef< const AbstractSparseLattice * > resultLattices)=0
The operation transfer function.
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 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.
void setAllToEntryStates(ArrayRef< AbstractSparseLattice * > lattices)
virtual void setToEntryState(AbstractSparseLattice *lattice)=0
Set the given lattice element(s) at control flow entry point(s).
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.
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,...
virtual LogicalResult visitCallOperation(CallOpInterface call, ArrayRef< const AbstractSparseLattice * > operandLattices, ArrayRef< AbstractSparseLattice * > resultLattices)
Visits a call operation.
virtual void visitCallableOperation(CallableOpInterface callable, ArrayRef< AbstractSparseLattice * > argLattices)
Visits a callable operation.
virtual LogicalResult visitOperationImpl(Operation *op, ArrayRef< const AbstractSparseLattice * > operandLattices, ArrayRef< AbstractSparseLattice * > resultLattices)=0
The operation transfer function.
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:344
detail::InFlightRemark failed(Location loc, RemarkOpts opts)
Report an optimization remark that failed.
Definition: Remarks.h:491
detail::InFlightRemark analysis(Location loc, RemarkOpts opts)
Report an optimization analysis remark.
Definition: Remarks.h:497
Include the generated interface declarations.
This trait indicates that a terminator operation is "return-like".
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.
Block * getBlock() const
Get the block contains this program point.