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/Value.h"
13 #include "llvm/ADT/ScopeExit.h"
14 #include "llvm/ADT/iterator.h"
15 #include "llvm/Config/abi-breaking.h"
16 #include "llvm/Support/Casting.h"
17 #include "llvm/Support/DebugLog.h"
18 #include "llvm/Support/raw_ostream.h"
19 
20 #define DEBUG_TYPE "dataflow"
21 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
22 #define DATAFLOW_DEBUG(X) LLVM_DEBUG(X)
23 #else
24 #define DATAFLOW_DEBUG(X)
25 #endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
26 
27 using namespace mlir;
28 
29 //===----------------------------------------------------------------------===//
30 // GenericLatticeAnchor
31 //===----------------------------------------------------------------------===//
32 
34 
35 //===----------------------------------------------------------------------===//
36 // AnalysisState
37 //===----------------------------------------------------------------------===//
38 
40 
43  auto inserted = dependents.insert({dependent, analysis});
44  (void)inserted;
46  if (inserted) {
47  LDBG() << "Creating dependency between " << debugName << " of " << anchor
48  << "\nand " << debugName << " on " << *dependent;
49  }
50  });
51 }
52 
53 void AnalysisState::dump() const { print(llvm::errs()); }
54 
55 //===----------------------------------------------------------------------===//
56 // ProgramPoint
57 //===----------------------------------------------------------------------===//
58 
59 void ProgramPoint::print(raw_ostream &os) const {
60  if (isNull()) {
61  os << "<NULL POINT>";
62  return;
63  }
64  if (!isBlockStart()) {
65  os << "<after operation>:"
66  << OpWithFlags(getPrevOp(), OpPrintingFlags().skipRegions());
67  return;
68  }
69  os << "<before operation>:"
70  << OpWithFlags(getNextOp(), OpPrintingFlags().skipRegions());
71 }
72 
73 //===----------------------------------------------------------------------===//
74 // LatticeAnchor
75 //===----------------------------------------------------------------------===//
76 
77 void LatticeAnchor::print(raw_ostream &os) const {
78  if (isNull()) {
79  os << "<NULL POINT>";
80  return;
81  }
82  if (auto *latticeAnchor = llvm::dyn_cast<GenericLatticeAnchor *>(*this))
83  return latticeAnchor->print(os);
84  if (auto value = llvm::dyn_cast<Value>(*this)) {
85  return value.print(os, OpPrintingFlags().skipRegions());
86  }
87 
88  return llvm::cast<ProgramPoint *>(*this)->print(os);
89 }
90 
92  if (auto *latticeAnchor = llvm::dyn_cast<GenericLatticeAnchor *>(*this))
93  return latticeAnchor->getLoc();
94  if (auto value = llvm::dyn_cast<Value>(*this))
95  return value.getLoc();
96 
97  ProgramPoint *pp = llvm::cast<ProgramPoint *>(*this);
98  if (!pp->isBlockStart())
99  return pp->getPrevOp()->getLoc();
100  return pp->getBlock()->getParent()->getLoc();
101 }
102 
103 //===----------------------------------------------------------------------===//
104 // DataFlowSolver
105 //===----------------------------------------------------------------------===//
106 
108  // Enable enqueue to the worklist.
109  isRunning = true;
110  auto guard = llvm::make_scope_exit([&]() { isRunning = false; });
111 
112  // Initialize equivalent lattice anchors.
113  for (DataFlowAnalysis &analysis : llvm::make_pointee_range(childAnalyses)) {
114  analysis.initializeEquivalentLatticeAnchor(top);
115  }
116 
117  // Initialize the analyses.
118  for (DataFlowAnalysis &analysis : llvm::make_pointee_range(childAnalyses)) {
119  DATAFLOW_DEBUG(LDBG() << "Priming analysis: " << analysis.debugName);
120  if (failed(analysis.initialize(top)))
121  return failure();
122  }
123 
124  // Run the analysis until fixpoint.
125  // Iterate until all states are in some initialized state and the worklist
126  // is exhausted.
127  while (!worklist.empty()) {
128  auto [point, analysis] = worklist.front();
129  worklist.pop();
130 
131  DATAFLOW_DEBUG(LDBG() << "Invoking '" << analysis->debugName
132  << "' on: " << *point);
133  if (failed(analysis->visit(point)))
134  return failure();
135  }
136 
137  return success();
138 }
139 
142  assert(isRunning &&
143  "DataFlowSolver is not running, should not use propagateIfChanged");
144  if (changed == ChangeResult::Change) {
145  DATAFLOW_DEBUG(LDBG() << "Propagating update to " << state->debugName
146  << " of " << state->anchor << "\n"
147  << "Value: " << *state);
148  state->onUpdate(this);
149  }
150 }
151 
152 //===----------------------------------------------------------------------===//
153 // DataFlowAnalysis
154 //===----------------------------------------------------------------------===//
155 
157 
159 
161  ProgramPoint *point) {
162  state->addDependency(point, this);
163 }
164 
167  solver.propagateIfChanged(state, changed);
168 }
#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.
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 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
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.