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 isExternalCallable = [&]() {
232  auto callable =
233  dyn_cast_if_present<CallableOpInterface>(call.resolveCallable());
234  return callable && !callable.getCallableRegion();
235  };
236  if (!getSolverConfig().isInterprocedural() || isExternalCallable()) {
237  visitExternalCallImpl(call, operandLattices, resultLattices);
238  return success();
239  }
240 
241  // Otherwise, the results of a call operation are determined by the
242  // callgraph.
243  const auto *predecessors = getOrCreateFor<PredecessorState>(
245  // If not all return sites are known, then conservatively assume we can't
246  // reason about the data-flow.
247  if (!predecessors->allPredecessorsKnown()) {
248  setAllToEntryStates(resultLattices);
249  return success();
250  }
251  for (Operation *predecessor : predecessors->getKnownPredecessors())
252  for (auto &&[operand, resLattice] :
253  llvm::zip(predecessor->getOperands(), resultLattices))
254  join(resLattice,
255  *getLatticeElementFor(getProgramPointAfter(call), operand));
256  return success();
257 }
258 
260  CallableOpInterface callable,
261  ArrayRef<AbstractSparseLattice *> argLattices) {
262  Block *entryBlock = &callable.getCallableRegion()->front();
263  const auto *callsites = getOrCreateFor<PredecessorState>(
264  getProgramPointBefore(entryBlock), getProgramPointAfter(callable));
265  // If not all callsites are known, conservatively mark all lattices as
266  // having reached their pessimistic fixpoints.
267  if (!callsites->allPredecessorsKnown() ||
268  !getSolverConfig().isInterprocedural()) {
269  return setAllToEntryStates(argLattices);
270  }
271  for (Operation *callsite : callsites->getKnownPredecessors()) {
272  auto call = cast<CallOpInterface>(callsite);
273  for (auto it : llvm::zip(call.getArgOperands(), argLattices))
274  join(std::get<1>(it),
276  std::get<0>(it)));
277  }
278 }
279 
280 void AbstractSparseForwardDataFlowAnalysis::visitRegionSuccessors(
281  ProgramPoint *point, RegionBranchOpInterface branch,
283  const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
284  assert(predecessors->allPredecessorsKnown() &&
285  "unexpected unresolved region successors");
286 
287  for (Operation *op : predecessors->getKnownPredecessors()) {
288  // Get the incoming successor operands.
289  std::optional<OperandRange> operands;
290 
291  // Check if the predecessor is the parent op.
292  if (op == branch) {
293  operands = branch.getEntrySuccessorOperands(successor);
294  // Otherwise, try to deduce the operands from a region return-like op.
295  } else if (auto regionTerminator =
296  dyn_cast<RegionBranchTerminatorOpInterface>(op)) {
297  operands = regionTerminator.getSuccessorOperands(successor);
298  }
299 
300  if (!operands) {
301  // We can't reason about the data-flow.
302  return setAllToEntryStates(lattices);
303  }
304 
305  ValueRange inputs = predecessors->getSuccessorInputs(op);
306  assert(inputs.size() == operands->size() &&
307  "expected the same number of successor inputs as operands");
308 
309  unsigned firstIndex = 0;
310  if (inputs.size() != lattices.size()) {
311  if (!point->isBlockStart()) {
312  if (!inputs.empty())
313  firstIndex = cast<OpResult>(inputs.front()).getResultNumber();
315  branch,
317  branch->getResults().slice(firstIndex, inputs.size())),
318  lattices, firstIndex);
319  } else {
320  if (!inputs.empty())
321  firstIndex = cast<BlockArgument>(inputs.front()).getArgNumber();
322  Region *region = point->getBlock()->getParent();
324  branch,
325  RegionSuccessor(region, region->getArguments().slice(
326  firstIndex, inputs.size())),
327  lattices, firstIndex);
328  }
329  }
330 
331  for (auto it : llvm::zip(*operands, lattices.drop_front(firstIndex)))
332  join(std::get<1>(it), *getLatticeElementFor(point, std::get<0>(it)));
333  }
334 }
335 
336 const AbstractSparseLattice *
338  Value value) {
340  addDependency(state, point);
341  return state;
342 }
343 
346  for (AbstractSparseLattice *lattice : lattices)
347  setToEntryState(lattice);
348 }
349 
351  AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs) {
352  propagateIfChanged(lhs, lhs->join(rhs));
353 }
354 
355 //===----------------------------------------------------------------------===//
356 // AbstractSparseBackwardDataFlowAnalysis
357 //===----------------------------------------------------------------------===//
358 
360  DataFlowSolver &solver, SymbolTableCollection &symbolTable)
361  : DataFlowAnalysis(solver), symbolTable(symbolTable) {
362  registerAnchorKind<CFGEdge>();
363 }
364 
365 LogicalResult
367  return initializeRecursively(top);
368 }
369 
370 LogicalResult
371 AbstractSparseBackwardDataFlowAnalysis::initializeRecursively(Operation *op) {
372  if (failed(visitOperation(op)))
373  return failure();
374 
375  for (Region &region : op->getRegions()) {
376  for (Block &block : region) {
377  getOrCreate<Executable>(getProgramPointBefore(&block))
378  ->blockContentSubscribe(this);
379  // Initialize ops in reverse order, so we can do as much initial
380  // propagation as possible without having to go through the
381  // solver queue.
382  for (auto it = block.rbegin(); it != block.rend(); it++)
383  if (failed(initializeRecursively(&*it)))
384  return failure();
385  }
386  }
387  return success();
388 }
389 
390 LogicalResult
392  // For backward dataflow, we don't have to do any work for the blocks
393  // themselves. CFG edges between blocks are processed by the BranchOp
394  // logic in `visitOperation`, and entry blocks for functions are tied
395  // to the CallOp arguments by visitOperation.
396  if (point->isBlockStart())
397  return success();
398  return visitOperation(point->getPrevOp());
399 }
400 
404  resultLattices.reserve(values.size());
405  for (Value result : values) {
406  AbstractSparseLattice *resultLattice = getLatticeElement(result);
407  resultLattices.push_back(resultLattice);
408  }
409  return resultLattices;
410 }
411 
413 AbstractSparseBackwardDataFlowAnalysis::getLatticeElementsFor(
414  ProgramPoint *point, ValueRange values) {
416  resultLattices.reserve(values.size());
417  for (Value result : values) {
418  const AbstractSparseLattice *resultLattice =
419  getLatticeElementFor(point, result);
420  resultLattices.push_back(resultLattice);
421  }
422  return resultLattices;
423 }
424 
426  return MutableArrayRef<OpOperand>(operands.getBase(), operands.size());
427 }
428 
429 LogicalResult
430 AbstractSparseBackwardDataFlowAnalysis::visitOperation(Operation *op) {
431  LDBG() << "Visiting operation: " << op->getName() << " with "
432  << op->getNumOperands() << " operands and " << op->getNumResults()
433  << " results";
434 
435  // If we're in a dead block, bail out.
436  if (op->getBlock() != nullptr &&
437  !getOrCreate<Executable>(getProgramPointBefore(op->getBlock()))
438  ->isLive()) {
439  LDBG() << "Operation is in dead block, bailing out";
440  return success();
441  }
442 
443  LDBG() << "Creating lattice elements for " << op->getNumOperands()
444  << " operands and " << op->getNumResults() << " results";
445  SmallVector<AbstractSparseLattice *> operandLattices =
448  getLatticeElementsFor(getProgramPointAfter(op), op->getResults());
449 
450  // Block arguments of region branch operations flow back into the operands
451  // of the parent op
452  if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
453  LDBG() << "Processing RegionBranchOpInterface operation";
454  visitRegionSuccessors(branch, operandLattices);
455  return success();
456  }
457 
458  if (auto branch = dyn_cast<BranchOpInterface>(op)) {
459  LDBG() << "Processing BranchOpInterface operation with "
460  << op->getNumSuccessors() << " successors";
461 
462  // Block arguments of successor blocks flow back into our operands.
463 
464  // We remember all operands not forwarded to any block in a BitVector.
465  // We can't just cut out a range here, since the non-forwarded ops might
466  // be non-contiguous (if there's more than one successor).
467  BitVector unaccounted(op->getNumOperands(), true);
468 
469  for (auto [index, block] : llvm::enumerate(op->getSuccessors())) {
470  SuccessorOperands successorOperands = branch.getSuccessorOperands(index);
471  OperandRange forwarded = successorOperands.getForwardedOperands();
472  if (!forwarded.empty()) {
473  MutableArrayRef<OpOperand> operands = op->getOpOperands().slice(
474  forwarded.getBeginOperandIndex(), forwarded.size());
475  for (OpOperand &operand : operands) {
476  unaccounted.reset(operand.getOperandNumber());
477  if (std::optional<BlockArgument> blockArg =
479  successorOperands, operand.getOperandNumber(), block)) {
480  meet(getLatticeElement(operand.get()),
481  *getLatticeElementFor(getProgramPointAfter(op), *blockArg));
482  }
483  }
484  }
485  }
486  // Operands not forwarded to successor blocks are typically parameters
487  // of the branch operation itself (for example the boolean for if/else).
488  for (int index : unaccounted.set_bits()) {
489  OpOperand &operand = op->getOpOperand(index);
490  visitBranchOperand(operand);
491  }
492  return success();
493  }
494 
495  // For function calls, connect the arguments of the entry blocks to the
496  // operands of the call op that are forwarded to these arguments.
497  if (auto call = dyn_cast<CallOpInterface>(op)) {
498  LDBG() << "Processing CallOpInterface operation";
499  Operation *callableOp = call.resolveCallableInTable(&symbolTable);
500  if (auto callable = dyn_cast_or_null<CallableOpInterface>(callableOp)) {
501  // Not all operands of a call op forward to arguments. Such operands are
502  // stored in `unaccounted`.
503  BitVector unaccounted(op->getNumOperands(), true);
504 
505  // If the call invokes an external function (or a function treated as
506  // external due to config), defer to the corresponding extension hook.
507  // By default, it just does `visitCallOperand` for all operands.
508  OperandRange argOperands = call.getArgOperands();
509  MutableArrayRef<OpOperand> argOpOperands =
510  operandsToOpOperands(argOperands);
511  Region *region = callable.getCallableRegion();
512  if (!region || region->empty() ||
513  !getSolverConfig().isInterprocedural()) {
514  visitExternalCallImpl(call, operandLattices, resultLattices);
515  return success();
516  }
517 
518  // Otherwise, propagate information from the entry point of the function
519  // back to operands whenever possible.
520  Block &block = region->front();
521  for (auto [blockArg, argOpOperand] :
522  llvm::zip(block.getArguments(), argOpOperands)) {
523  meet(getLatticeElement(argOpOperand.get()),
524  *getLatticeElementFor(getProgramPointAfter(op), blockArg));
525  unaccounted.reset(argOpOperand.getOperandNumber());
526  }
527 
528  // Handle the operands of the call op that aren't forwarded to any
529  // arguments.
530  for (int index : unaccounted.set_bits()) {
531  OpOperand &opOperand = op->getOpOperand(index);
532  visitCallOperand(opOperand);
533  }
534  return success();
535  }
536  }
537 
538  // When the region of an op implementing `RegionBranchOpInterface` has a
539  // terminator implementing `RegionBranchTerminatorOpInterface` or a
540  // return-like terminator, the region's successors' arguments flow back into
541  // the "successor operands" of this terminator.
542  //
543  // A successor operand with respect to an op implementing
544  // `RegionBranchOpInterface` is an operand that is forwarded to a region
545  // successor's input. There are two types of successor operands: the operands
546  // of this op itself and the operands of the terminators of the regions of
547  // this op.
548  if (auto terminator = dyn_cast<RegionBranchTerminatorOpInterface>(op)) {
549  LDBG() << "Processing RegionBranchTerminatorOpInterface operation";
550  if (auto branch = dyn_cast<RegionBranchOpInterface>(op->getParentOp())) {
551  visitRegionSuccessorsFromTerminator(terminator, branch);
552  return success();
553  }
554  }
555 
556  if (op->hasTrait<OpTrait::ReturnLike>()) {
557  LDBG() << "Processing ReturnLike operation";
558  // Going backwards, the operands of the return are derived from the
559  // results of all CallOps calling this CallableOp.
560  if (auto callable = dyn_cast<CallableOpInterface>(op->getParentOp())) {
561  LDBG() << "Callable parent found, visiting callable operation";
562  return visitCallableOperation(op, callable, operandLattices);
563  }
564  }
565 
566  LDBG() << "Using default visitOperationImpl for operation: " << op->getName();
567  return visitOperationImpl(op, operandLattices, resultLattices);
568 }
569 
571  Operation *op, CallableOpInterface callable,
572  ArrayRef<AbstractSparseLattice *> operandLattices) {
573  const PredecessorState *callsites = getOrCreateFor<PredecessorState>(
575  if (callsites->allPredecessorsKnown()) {
576  for (Operation *call : callsites->getKnownPredecessors()) {
577  SmallVector<const AbstractSparseLattice *> callResultLattices =
578  getLatticeElementsFor(getProgramPointAfter(op), call->getResults());
579  for (auto [op, result] : llvm::zip(operandLattices, callResultLattices))
580  meet(op, *result);
581  }
582  } else {
583  // If we don't know all the callers, we can't know where the
584  // returned values go. Note that, in particular, this will trigger
585  // for the return ops of any public functions.
586  setAllToExitStates(operandLattices);
587  }
588  return success();
589 }
590 
591 void AbstractSparseBackwardDataFlowAnalysis::visitRegionSuccessors(
592  RegionBranchOpInterface branch,
593  ArrayRef<AbstractSparseLattice *> operandLattices) {
594  Operation *op = branch.getOperation();
595  SmallVector<RegionSuccessor> successors;
596  SmallVector<Attribute> operands(op->getNumOperands(), nullptr);
597  branch.getEntrySuccessorRegions(operands, successors);
598 
599  // All operands not forwarded to any successor. This set can be non-contiguous
600  // in the presence of multiple successors.
601  BitVector unaccounted(op->getNumOperands(), true);
602 
603  for (RegionSuccessor &successor : successors) {
604  OperandRange operands = branch.getEntrySuccessorOperands(successor);
605  MutableArrayRef<OpOperand> opoperands = operandsToOpOperands(operands);
606  ValueRange inputs = successor.getSuccessorInputs();
607  for (auto [operand, input] : llvm::zip(opoperands, inputs)) {
608  meet(getLatticeElement(operand.get()),
609  *getLatticeElementFor(getProgramPointAfter(op), input));
610  unaccounted.reset(operand.getOperandNumber());
611  }
612  }
613  // All operands not forwarded to regions are typically parameters of the
614  // branch operation itself (for example the boolean for if/else).
615  for (int index : unaccounted.set_bits()) {
616  visitBranchOperand(op->getOpOperand(index));
617  }
618 }
619 
620 void AbstractSparseBackwardDataFlowAnalysis::
621  visitRegionSuccessorsFromTerminator(
622  RegionBranchTerminatorOpInterface terminator,
623  RegionBranchOpInterface branch) {
624  assert(isa<RegionBranchTerminatorOpInterface>(terminator) &&
625  "expected a `RegionBranchTerminatorOpInterface` op");
626  assert(terminator->getParentOp() == branch.getOperation() &&
627  "expected `branch` to be the parent op of `terminator`");
628 
629  SmallVector<Attribute> operandAttributes(terminator->getNumOperands(),
630  nullptr);
631  SmallVector<RegionSuccessor> successors;
632  terminator.getSuccessorRegions(operandAttributes, successors);
633  // All operands not forwarded to any successor. This set can be
634  // non-contiguous in the presence of multiple successors.
635  BitVector unaccounted(terminator->getNumOperands(), true);
636 
637  for (const RegionSuccessor &successor : successors) {
638  ValueRange inputs = successor.getSuccessorInputs();
639  OperandRange operands = terminator.getSuccessorOperands(successor);
640  MutableArrayRef<OpOperand> opOperands = operandsToOpOperands(operands);
641  for (auto [opOperand, input] : llvm::zip(opOperands, inputs)) {
642  meet(getLatticeElement(opOperand.get()),
643  *getLatticeElementFor(getProgramPointAfter(terminator), input));
644  unaccounted.reset(const_cast<OpOperand &>(opOperand).getOperandNumber());
645  }
646  }
647  // Visit operands of the branch op not forwarded to the next region.
648  // (Like e.g. the boolean of `scf.conditional`)
649  for (int index : unaccounted.set_bits()) {
650  visitBranchOperand(terminator->getOpOperand(index));
651  }
652 }
653 
654 const AbstractSparseLattice *
655 AbstractSparseBackwardDataFlowAnalysis::getLatticeElementFor(
656  ProgramPoint *point, Value value) {
658  addDependency(state, point);
659  return state;
660 }
661 
664  for (AbstractSparseLattice *lattice : lattices)
665  setToExitState(lattice);
666 }
667 
669  AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs) {
670  propagateIfChanged(lhs, lhs->meet(rhs));
671 }
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.