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