MLIR  19.0.0git
DenseAnalysis.cpp
Go to the documentation of this file.
1 //===- DenseAnalysis.cpp - Dense 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/Block.h"
13 #include "mlir/IR/OpDefinition.h"
14 #include "mlir/IR/Operation.h"
15 #include "mlir/IR/Region.h"
18 #include "mlir/Support/LLVM.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/Support/Casting.h"
22 #include <cassert>
23 #include <optional>
24 
25 using namespace mlir;
26 using namespace mlir::dataflow;
27 
28 //===----------------------------------------------------------------------===//
29 // AbstractDenseForwardDataFlowAnalysis
30 //===----------------------------------------------------------------------===//
31 
33  // Visit every operation and block.
34  processOperation(top);
35  for (Region &region : top->getRegions()) {
36  for (Block &block : region) {
37  visitBlock(&block);
38  for (Operation &op : block)
39  if (failed(initialize(&op)))
40  return failure();
41  }
42  }
43  return success();
44 }
45 
47  if (auto *op = llvm::dyn_cast_if_present<Operation *>(point))
48  processOperation(op);
49  else if (auto *block = llvm::dyn_cast_if_present<Block *>(point))
50  visitBlock(block);
51  else
52  return failure();
53  return success();
54 }
55 
56 void AbstractDenseForwardDataFlowAnalysis::visitCallOperation(
57  CallOpInterface call, const AbstractDenseLattice &before,
58  AbstractDenseLattice *after) {
59  // Allow for customizing the behavior of calls to external symbols, including
60  // when the analysis is explicitly marked as non-interprocedural.
61  auto callable =
62  dyn_cast_if_present<CallableOpInterface>(call.resolveCallable());
63  if (!getSolverConfig().isInterprocedural() ||
64  (callable && !callable.getCallableRegion())) {
66  call, CallControlFlowAction::ExternalCallee, before, after);
67  }
68 
69  const auto *predecessors =
70  getOrCreateFor<PredecessorState>(call.getOperation(), call);
71  // Otherwise, if not all return sites are known, then conservatively assume we
72  // can't reason about the data-flow.
73  if (!predecessors->allPredecessorsKnown())
74  return setToEntryState(after);
75 
76  for (Operation *predecessor : predecessors->getKnownPredecessors()) {
77  // Get the lattices at callee return:
78  //
79  // func.func @callee() {
80  // ...
81  // return // predecessor
82  // // latticeAtCalleeReturn
83  // }
84  // func.func @caller() {
85  // ...
86  // call @callee
87  // // latticeAfterCall
88  // ...
89  // }
90  AbstractDenseLattice *latticeAfterCall = after;
91  const AbstractDenseLattice *latticeAtCalleeReturn =
92  getLatticeFor(call.getOperation(), predecessor);
94  *latticeAtCalleeReturn, latticeAfterCall);
95  }
96 }
97 
99  // If the containing block is not executable, bail out.
100  if (!getOrCreateFor<Executable>(op, op->getBlock())->isLive())
101  return;
102 
103  // Get the dense lattice to update.
104  AbstractDenseLattice *after = getLattice(op);
105 
106  // Get the dense state before the execution of the op.
107  const AbstractDenseLattice *before;
108  if (Operation *prev = op->getPrevNode())
109  before = getLatticeFor(op, prev);
110  else
111  before = getLatticeFor(op, op->getBlock());
112 
113  // If this op implements region control-flow, then control-flow dictates its
114  // transfer function.
115  if (auto branch = dyn_cast<RegionBranchOpInterface>(op))
116  return visitRegionBranchOperation(op, branch, after);
117 
118  // If this is a call operation, then join its lattices across known return
119  // sites.
120  if (auto call = dyn_cast<CallOpInterface>(op))
121  return visitCallOperation(call, *before, after);
122 
123  // Invoke the operation transfer function.
124  visitOperationImpl(op, *before, after);
125 }
126 
127 void AbstractDenseForwardDataFlowAnalysis::visitBlock(Block *block) {
128  // If the block is not executable, bail out.
129  if (!getOrCreateFor<Executable>(block, block)->isLive())
130  return;
131 
132  // Get the dense lattice to update.
133  AbstractDenseLattice *after = getLattice(block);
134 
135  // The dense lattices of entry blocks are set by region control-flow or the
136  // callgraph.
137  if (block->isEntryBlock()) {
138  // Check if this block is the entry block of a callable region.
139  auto callable = dyn_cast<CallableOpInterface>(block->getParentOp());
140  if (callable && callable.getCallableRegion() == block->getParent()) {
141  const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
142  // If not all callsites are known, conservatively mark all lattices as
143  // having reached their pessimistic fixpoints. Do the same if
144  // interprocedural analysis is not enabled.
145  if (!callsites->allPredecessorsKnown() ||
146  !getSolverConfig().isInterprocedural())
147  return setToEntryState(after);
148  for (Operation *callsite : callsites->getKnownPredecessors()) {
149  // Get the dense lattice before the callsite.
150  const AbstractDenseLattice *before;
151  if (Operation *prev = callsite->getPrevNode())
152  before = getLatticeFor(block, prev);
153  else
154  before = getLatticeFor(block, callsite->getBlock());
155 
156  visitCallControlFlowTransfer(cast<CallOpInterface>(callsite),
158  *before, after);
159  }
160  return;
161  }
162 
163  // Check if we can reason about the control-flow.
164  if (auto branch = dyn_cast<RegionBranchOpInterface>(block->getParentOp()))
165  return visitRegionBranchOperation(block, branch, after);
166 
167  // Otherwise, we can't reason about the data-flow.
168  return setToEntryState(after);
169  }
170 
171  // Join the state with the state after the block's predecessors.
172  for (Block::pred_iterator it = block->pred_begin(), e = block->pred_end();
173  it != e; ++it) {
174  // Skip control edges that aren't executable.
175  Block *predecessor = *it;
176  if (!getOrCreateFor<Executable>(
177  block, getProgramPoint<CFGEdge>(predecessor, block))
178  ->isLive())
179  continue;
180 
181  // Merge in the state from the predecessor's terminator.
182  join(after, *getLatticeFor(block, predecessor->getTerminator()));
183  }
184 }
185 
187  ProgramPoint point, RegionBranchOpInterface branch,
188  AbstractDenseLattice *after) {
189  // Get the terminator predecessors.
190  const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
191  assert(predecessors->allPredecessorsKnown() &&
192  "unexpected unresolved region successors");
193 
194  for (Operation *op : predecessors->getKnownPredecessors()) {
195  const AbstractDenseLattice *before;
196  // If the predecessor is the parent, get the state before the parent.
197  if (op == branch) {
198  if (Operation *prev = op->getPrevNode())
199  before = getLatticeFor(point, prev);
200  else
201  before = getLatticeFor(point, op->getBlock());
202 
203  // Otherwise, get the state after the terminator.
204  } else {
205  before = getLatticeFor(point, op);
206  }
207 
208  // This function is called in two cases:
209  // 1. when visiting the block (point = block);
210  // 2. when visiting the parent operation (point = parent op).
211  // In both cases, we are looking for predecessor operations of the point,
212  // 1. predecessor may be the terminator of another block from another
213  // region (assuming that the block does belong to another region via an
214  // assertion) or the parent (when parent can transfer control to this
215  // region);
216  // 2. predecessor may be the terminator of a block that exits the
217  // region (when region transfers control to the parent) or the operation
218  // before the parent.
219  // In the latter case, just perform the join as it isn't the control flow
220  // affected by the region.
221  std::optional<unsigned> regionFrom =
222  op == branch ? std::optional<unsigned>()
223  : op->getBlock()->getParent()->getRegionNumber();
224  if (auto *toBlock = point.dyn_cast<Block *>()) {
225  unsigned regionTo = toBlock->getParent()->getRegionNumber();
226  visitRegionBranchControlFlowTransfer(branch, regionFrom, regionTo,
227  *before, after);
228  } else {
229  assert(point.get<Operation *>() == branch &&
230  "expected to be visiting the branch itself");
231  // Only need to call the arc transfer when the predecessor is the region
232  // or the op itself, not the previous op.
233  if (op->getParentOp() == branch || op == branch) {
235  branch, regionFrom, /*regionTo=*/std::nullopt, *before, after);
236  } else {
237  join(after, *before);
238  }
239  }
240  }
241 }
242 
243 const AbstractDenseLattice *
245  ProgramPoint point) {
246  AbstractDenseLattice *state = getLattice(point);
247  addDependency(state, dependent);
248  return state;
249 }
250 
251 //===----------------------------------------------------------------------===//
252 // AbstractDenseBackwardDataFlowAnalysis
253 //===----------------------------------------------------------------------===//
254 
257  // Visit every operation and block.
258  processOperation(top);
259  for (Region &region : top->getRegions()) {
260  for (Block &block : region) {
261  visitBlock(&block);
262  for (Operation &op : llvm::reverse(block)) {
263  if (failed(initialize(&op)))
264  return failure();
265  }
266  }
267  }
268  return success();
269 }
270 
272  if (auto *op = llvm::dyn_cast_if_present<Operation *>(point))
273  processOperation(op);
274  else if (auto *block = llvm::dyn_cast_if_present<Block *>(point))
275  visitBlock(block);
276  else
277  return failure();
278  return success();
279 }
280 
281 void AbstractDenseBackwardDataFlowAnalysis::visitCallOperation(
282  CallOpInterface call, const AbstractDenseLattice &after,
283  AbstractDenseLattice *before) {
284  // Find the callee.
285  Operation *callee = call.resolveCallable(&symbolTable);
286 
287  auto callable = dyn_cast_or_null<CallableOpInterface>(callee);
288  // No region means the callee is only declared in this module.
289  // If that is the case or if the solver is not interprocedural,
290  // let the hook handle it.
291  if (!getSolverConfig().isInterprocedural() ||
292  (callable && (!callable.getCallableRegion() ||
293  callable.getCallableRegion()->empty()))) {
295  call, CallControlFlowAction::ExternalCallee, after, before);
296  }
297 
298  if (!callable)
299  return setToExitState(before);
300 
301  Region *region = callable.getCallableRegion();
302 
303  // Call-level control flow specifies the data flow here.
304  //
305  // func.func @callee() {
306  // ^calleeEntryBlock:
307  // // latticeAtCalleeEntry
308  // ...
309  // }
310  // func.func @caller() {
311  // ...
312  // // latticeBeforeCall
313  // call @callee
314  // ...
315  // }
316  Block *calleeEntryBlock = &region->front();
317  ProgramPoint calleeEntry = calleeEntryBlock->empty()
318  ? ProgramPoint(calleeEntryBlock)
319  : &calleeEntryBlock->front();
320  const AbstractDenseLattice &latticeAtCalleeEntry =
321  *getLatticeFor(call.getOperation(), calleeEntry);
322  AbstractDenseLattice *latticeBeforeCall = before;
324  latticeAtCalleeEntry, latticeBeforeCall);
325 }
326 
328  // If the containing block is not executable, bail out.
329  if (!getOrCreateFor<Executable>(op, op->getBlock())->isLive())
330  return;
331 
332  // Get the dense lattice to update.
333  AbstractDenseLattice *before = getLattice(op);
334 
335  // Get the dense state after execution of this op.
336  const AbstractDenseLattice *after;
337  if (Operation *next = op->getNextNode())
338  after = getLatticeFor(op, next);
339  else
340  after = getLatticeFor(op, op->getBlock());
341 
342  // Special cases where control flow may dictate data flow.
343  if (auto branch = dyn_cast<RegionBranchOpInterface>(op))
344  return visitRegionBranchOperation(op, branch, RegionBranchPoint::parent(),
345  before);
346  if (auto call = dyn_cast<CallOpInterface>(op))
347  return visitCallOperation(call, *after, before);
348 
349  // Invoke the operation transfer function.
350  visitOperationImpl(op, *after, before);
351 }
352 
353 void AbstractDenseBackwardDataFlowAnalysis::visitBlock(Block *block) {
354  // If the block is not executable, bail out.
355  if (!getOrCreateFor<Executable>(block, block)->isLive())
356  return;
357 
358  AbstractDenseLattice *before = getLattice(block);
359 
360  // We need "exit" blocks, i.e. the blocks that may return control to the
361  // parent operation.
362  auto isExitBlock = [](Block *b) {
363  // Treat empty and terminator-less blocks as exit blocks.
364  if (b->empty() || !b->back().mightHaveTrait<OpTrait::IsTerminator>())
365  return true;
366 
367  // There may be a weird case where a terminator may be transferring control
368  // either to the parent or to another block, so exit blocks and successors
369  // are not mutually exclusive.
370  return isa_and_nonnull<RegionBranchTerminatorOpInterface>(
371  b->getTerminator());
372  };
373  if (isExitBlock(block)) {
374  // If this block is exiting from a callable, the successors of exiting from
375  // a callable are the successors of all call sites. And the call sites
376  // themselves are predecessors of the callable.
377  auto callable = dyn_cast<CallableOpInterface>(block->getParentOp());
378  if (callable && callable.getCallableRegion() == block->getParent()) {
379  const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
380  // If not all call sites are known, conservative mark all lattices as
381  // having reached their pessimistic fix points.
382  if (!callsites->allPredecessorsKnown() ||
383  !getSolverConfig().isInterprocedural()) {
384  return setToExitState(before);
385  }
386 
387  for (Operation *callsite : callsites->getKnownPredecessors()) {
388  const AbstractDenseLattice *after;
389  if (Operation *next = callsite->getNextNode())
390  after = getLatticeFor(block, next);
391  else
392  after = getLatticeFor(block, callsite->getBlock());
393  visitCallControlFlowTransfer(cast<CallOpInterface>(callsite),
395  before);
396  }
397  return;
398  }
399 
400  // If this block is exiting from an operation with region-based control
401  // flow, propagate the lattice back along the control flow edge.
402  if (auto branch = dyn_cast<RegionBranchOpInterface>(block->getParentOp())) {
403  visitRegionBranchOperation(block, branch, block->getParent(), before);
404  return;
405  }
406 
407  // Cannot reason about successors of an exit block, set the pessimistic
408  // fixpoint.
409  return setToExitState(before);
410  }
411 
412  // Meet the state with the state before block's successors.
413  for (Block *successor : block->getSuccessors()) {
414  if (!getOrCreateFor<Executable>(block,
415  getProgramPoint<CFGEdge>(block, successor))
416  ->isLive())
417  continue;
418 
419  // Merge in the state from the successor: either the first operation, or the
420  // block itself when empty.
421  if (successor->empty())
422  meet(before, *getLatticeFor(block, successor));
423  else
424  meet(before, *getLatticeFor(block, &successor->front()));
425  }
426 }
427 
428 void AbstractDenseBackwardDataFlowAnalysis::visitRegionBranchOperation(
429  ProgramPoint point, RegionBranchOpInterface branch,
430  RegionBranchPoint branchPoint, AbstractDenseLattice *before) {
431 
432  // The successors of the operation may be either the first operation of the
433  // entry block of each possible successor region, or the next operation when
434  // the branch is a successor of itself.
435  SmallVector<RegionSuccessor> successors;
436  branch.getSuccessorRegions(branchPoint, successors);
437  for (const RegionSuccessor &successor : successors) {
438  const AbstractDenseLattice *after;
439  if (successor.isParent() || successor.getSuccessor()->empty()) {
440  if (Operation *next = branch->getNextNode())
441  after = getLatticeFor(point, next);
442  else
443  after = getLatticeFor(point, branch->getBlock());
444  } else {
445  Region *successorRegion = successor.getSuccessor();
446  assert(!successorRegion->empty() && "unexpected empty successor region");
447  Block *successorBlock = &successorRegion->front();
448 
449  if (!getOrCreateFor<Executable>(point, successorBlock)->isLive())
450  continue;
451 
452  if (successorBlock->empty())
453  after = getLatticeFor(point, successorBlock);
454  else
455  after = getLatticeFor(point, &successorBlock->front());
456  }
457 
458  visitRegionBranchControlFlowTransfer(branch, branchPoint, successor, *after,
459  before);
460  }
461 }
462 
463 const AbstractDenseLattice *
465  ProgramPoint point) {
466  AbstractDenseLattice *state = getLattice(point);
467  addDependency(state, dependent);
468  return state;
469 }
Block represents an ordered list of Operations.
Definition: Block.h:31
bool empty()
Definition: Block.h:146
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
Definition: Block.cpp:26
pred_iterator pred_begin()
Definition: Block.h:231
SuccessorRange getSuccessors()
Definition: Block.h:265
Operation * getTerminator()
Get the terminator operation of this block.
Definition: Block.cpp:243
Operation & front()
Definition: Block.h:151
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:234
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Definition: Block.cpp:30
const DataFlowConfig & getSolverConfig() const
Return the configuration of the solver used for this analysis.
void addDependency(AnalysisState *state, ProgramPoint point)
Create a dependency between the given analysis state and program point on this analysis.
This class provides the API for ops that are known to be terminators.
Definition: OpDefinition.h:764
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
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:672
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
unsigned getRegionNumber()
Return the number of this region in the parent operation.
Definition: Region.cpp:62
bool empty()
Definition: Region.h:60
Block & front()
Definition: Region.h:65
virtual void setToExitState(AbstractDenseLattice *lattice)=0
Set the dense lattice before at the control flow exit point and propagate the update if it changed.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting every program point whose execution may modify the program state;...
virtual void visitCallControlFlowTransfer(CallOpInterface call, CallControlFlowAction action, const AbstractDenseLattice &after, AbstractDenseLattice *before)
Propagate the dense lattice backwards along the call control flow edge, which can be either entering ...
LogicalResult visit(ProgramPoint point) override
Visit a program point that modifies the state of the program.
virtual void visitOperationImpl(Operation *op, const AbstractDenseLattice &after, AbstractDenseLattice *before)=0
Propagate the dense lattice after the execution of an operation to the lattice before its execution.
void meet(AbstractDenseLattice *lhs, const AbstractDenseLattice &rhs)
Meet a lattice with another lattice and propagate an update if it changed.
virtual void processOperation(Operation *op)
Visit an operation.
const AbstractDenseLattice * getLatticeFor(ProgramPoint dependent, ProgramPoint point)
Get the dense lattice before the execution of the program point point and declare that the dependent ...
virtual AbstractDenseLattice * getLattice(ProgramPoint point)=0
Get the dense lattice before the execution of the program point.
virtual void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch, RegionBranchPoint regionFrom, RegionBranchPoint regionTo, const AbstractDenseLattice &after, AbstractDenseLattice *before)
Propagate the dense lattice backwards along the control flow edge from regionFrom to regionTo regions...
const AbstractDenseLattice * getLatticeFor(ProgramPoint dependent, ProgramPoint point)
Get the dense lattice after the execution of the given program point and add it as a dependency to a ...
virtual AbstractDenseLattice * getLattice(ProgramPoint point)=0
Get the dense lattice after the execution of the given program point.
void join(AbstractDenseLattice *lhs, const AbstractDenseLattice &rhs)
Join a lattice with another and propagate an update if it changed.
void visitRegionBranchOperation(ProgramPoint point, RegionBranchOpInterface branch, AbstractDenseLattice *after)
Visit a program point within a region branch operation with predecessors in it.
virtual void setToEntryState(AbstractDenseLattice *lattice)=0
Set the dense lattice at control flow entry point and propagate an update if it changed.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting every program point whose execution may modify the program state;...
virtual void visitCallControlFlowTransfer(CallOpInterface call, CallControlFlowAction action, const AbstractDenseLattice &before, AbstractDenseLattice *after)
Propagate the dense lattice forward along the call control flow edge, which can be either entering or...
LogicalResult visit(ProgramPoint point) override
Visit a program point that modifies the state of the program.
virtual void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch, std::optional< unsigned > regionFrom, std::optional< unsigned > regionTo, const AbstractDenseLattice &before, AbstractDenseLattice *after)
Propagate the dense lattice forward along the control flow edge from regionFrom to regionTo regions o...
virtual void processOperation(Operation *op)
Visit an operation.
virtual void visitOperationImpl(Operation *op, const AbstractDenseLattice &before, AbstractDenseLattice *after)=0
Propagate the dense lattice before the execution of an operation to the lattice after its execution.
This class represents a dense lattice.
Definition: DenseAnalysis.h:42
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
Fundamental IR components are supported as first-class program points.