MLIR  22.0.0git
DataFlowFramework.cpp
Go to the documentation of this file.
1 //===- DataFlowFramework.cpp - A generic framework for 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 
10 #include "mlir/IR/Location.h"
11 #include "mlir/IR/Operation.h"
12 #include "mlir/IR/SymbolTable.h"
13 #include "mlir/IR/Value.h"
14 #include "llvm/ADT/ScopeExit.h"
15 #include "llvm/ADT/iterator.h"
16 #include "llvm/Config/abi-breaking.h"
17 #include "llvm/Support/Casting.h"
18 #include "llvm/Support/DebugLog.h"
19 #include "llvm/Support/raw_ostream.h"
20 
21 #define DEBUG_TYPE "dataflow"
22 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
23 #define DATAFLOW_DEBUG(X) LLVM_DEBUG(X)
24 #else
25 #define DATAFLOW_DEBUG(X)
26 #endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
27 
28 using namespace mlir;
29 
30 //===----------------------------------------------------------------------===//
31 // GenericLatticeAnchor
32 //===----------------------------------------------------------------------===//
33 
35 
36 //===----------------------------------------------------------------------===//
37 // AnalysisState
38 //===----------------------------------------------------------------------===//
39 
41 
44  auto inserted = dependents.insert({dependent, analysis});
45  (void)inserted;
47  if (inserted) {
48  LDBG() << "Creating dependency between " << debugName << " of " << anchor
49  << "\nand " << debugName << " on " << *dependent;
50  }
51  });
52 }
53 
54 void AnalysisState::dump() const { print(llvm::errs()); }
55 
56 //===----------------------------------------------------------------------===//
57 // ProgramPoint
58 //===----------------------------------------------------------------------===//
59 
60 void ProgramPoint::print(raw_ostream &os) const {
61  if (isNull()) {
62  os << "<NULL POINT>";
63  return;
64  }
65  if (!isBlockStart()) {
66  os << "<after operation>:"
67  << OpWithFlags(getPrevOp(), OpPrintingFlags().skipRegions());
68  return;
69  }
70  os << "<before operation>:"
71  << OpWithFlags(getNextOp(), OpPrintingFlags().skipRegions());
72 }
73 
74 //===----------------------------------------------------------------------===//
75 // LatticeAnchor
76 //===----------------------------------------------------------------------===//
77 
78 void LatticeAnchor::print(raw_ostream &os) const {
79  if (isNull()) {
80  os << "<NULL POINT>";
81  return;
82  }
83  if (auto *latticeAnchor = llvm::dyn_cast<GenericLatticeAnchor *>(*this))
84  return latticeAnchor->print(os);
85  if (auto value = llvm::dyn_cast<Value>(*this)) {
86  return value.print(os, OpPrintingFlags().skipRegions());
87  }
88 
89  return llvm::cast<ProgramPoint *>(*this)->print(os);
90 }
91 
93  if (auto *latticeAnchor = llvm::dyn_cast<GenericLatticeAnchor *>(*this))
94  return latticeAnchor->getLoc();
95  if (auto value = llvm::dyn_cast<Value>(*this))
96  return value.getLoc();
97 
98  ProgramPoint *pp = llvm::cast<ProgramPoint *>(*this);
99  if (!pp->isBlockStart())
100  return pp->getPrevOp()->getLoc();
101  return pp->getBlock()->getParent()->getLoc();
102 }
103 
104 //===----------------------------------------------------------------------===//
105 // DataFlowSolver
106 //===----------------------------------------------------------------------===//
107 
109  // Enable enqueue to the worklist.
110  isRunning = true;
111  auto guard = llvm::make_scope_exit([&]() { isRunning = false; });
112 
113  bool isInterprocedural = config.isInterprocedural();
114  auto restoreInterprocedural = llvm::make_scope_exit(
115  [&]() { config.setInterprocedural(isInterprocedural); });
116  if (isInterprocedural && !top->hasTrait<OpTrait::SymbolTable>())
117  config.setInterprocedural(false);
118 
119  // Initialize equivalent lattice anchors.
120  for (DataFlowAnalysis &analysis : llvm::make_pointee_range(childAnalyses)) {
121  analysis.initializeEquivalentLatticeAnchor(top);
122  }
123 
124  // Initialize the analyses.
125  for (DataFlowAnalysis &analysis : llvm::make_pointee_range(childAnalyses)) {
126  DATAFLOW_DEBUG(LDBG() << "Priming analysis: " << analysis.debugName);
127  if (failed(analysis.initialize(top)))
128  return failure();
129  }
130 
131  // Run the analysis until fixpoint.
132  // Iterate until all states are in some initialized state and the worklist
133  // is exhausted.
134  while (!worklist.empty()) {
135  auto [point, analysis] = worklist.front();
136  worklist.pop();
137 
138  DATAFLOW_DEBUG(LDBG() << "Invoking '" << analysis->debugName
139  << "' on: " << *point);
140  if (failed(analysis->visit(point)))
141  return failure();
142  }
143 
144  return success();
145 }
146 
149  assert(isRunning &&
150  "DataFlowSolver is not running, should not use propagateIfChanged");
151  if (changed == ChangeResult::Change) {
152  DATAFLOW_DEBUG(LDBG() << "Propagating update to " << state->debugName
153  << " of " << state->anchor << "\n"
154  << "Value: " << *state);
155  state->onUpdate(this);
156  }
157 }
158 
159 //===----------------------------------------------------------------------===//
160 // DataFlowAnalysis
161 //===----------------------------------------------------------------------===//
162 
164 
166 
168  ProgramPoint *point) {
169  state->addDependency(point, this);
170 }
171 
174  solver.propagateIfChanged(state, changed);
175 }
#define DATAFLOW_DEBUG(X)
Base class for generic analysis states.
LLVM_DUMP_METHOD void dump() const
void addDependency(ProgramPoint *point, DataFlowAnalysis *analysis)
Add a dependency to this analysis state on a lattice anchor and an analysis.
virtual void print(raw_ostream &os) const =0
Print the contents of the analysis state.
virtual ~AnalysisState()
LatticeAnchor anchor
The lattice anchor to which the state belongs.
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
Definition: Block.cpp:27
Base class for all data-flow analyses.
void addDependency(AnalysisState *state, ProgramPoint *point)
Create a dependency between the given analysis state and lattice anchor on this analysis.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
DataFlowAnalysis(DataFlowSolver &solver)
Create an analysis with a reference to the parent solver.
DataFlowConfig & setInterprocedural(bool enable)
Set whether the solver should operate interpocedurally, i.e.
bool isInterprocedural() const
Return true if the solver operates interprocedurally, false otherwise.
The general data-flow analysis solver.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to an analysis state if it changed by pushing dependent work items to the back of...
LogicalResult initializeAndRun(Operation *top)
Initialize the children analyses starting from the provided top-level operation and run the analysis ...
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition: Location.h:76
Set of flags used to control the behavior of the various IR print methods (e.g.
A trait used to provide symbol table functionalities to a region operation.
Definition: SymbolTable.h:452
A wrapper class that allows for printing an operation with a set of flags, useful to act as a "stream...
Definition: Operation.h:1111
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:749
Location getLoc()
The source location the operation was defined or derived from.
Definition: Operation.h:223
Location getLoc()
Return a location for this region.
Definition: Region.cpp:31
detail::InFlightRemark failed(Location loc, RemarkOpts opts)
Report an optimization remark that failed.
Definition: Remarks.h:491
detail::InFlightRemark analysis(Location loc, RemarkOpts opts)
Report an optimization analysis remark.
Definition: Remarks.h:497
Include the generated interface declarations.
const FrozenRewritePatternSet GreedyRewriteConfig bool * changed
ChangeResult
A result type used to indicate if a change happened.
Location getLoc() const
Get the source location of the lattice anchor.
void print(raw_ostream &os) const
Print the lattice anchor.
Program point represents a specific location in the execution of a program.
bool isNull() const
Returns true if this program point is set.
bool isBlockStart() const
Operation * getPrevOp() const
Get the previous operation of this program point.
void print(raw_ostream &os) const
Print the program point.
Operation * getNextOp() const
Get the next operation of this program point.
Block * getBlock() const
Get the block contains this program point.