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