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