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