MLIR  16.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 "llvm/Support/Debug.h"
11 
12 #define DEBUG_TYPE "dataflow"
13 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
14 #define DATAFLOW_DEBUG(X) LLVM_DEBUG(X)
15 #else
16 #define DATAFLOW_DEBUG(X)
17 #endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
18 
19 using namespace mlir;
20 
21 //===----------------------------------------------------------------------===//
22 // GenericProgramPoint
23 //===----------------------------------------------------------------------===//
24 
26 
27 //===----------------------------------------------------------------------===//
28 // AnalysisState
29 //===----------------------------------------------------------------------===//
30 
32 
33 //===----------------------------------------------------------------------===//
34 // ProgramPoint
35 //===----------------------------------------------------------------------===//
36 
37 void ProgramPoint::print(raw_ostream &os) const {
38  if (isNull()) {
39  os << "<NULL POINT>";
40  return;
41  }
42  if (auto *programPoint = dyn_cast<GenericProgramPoint *>())
43  return programPoint->print(os);
44  if (auto *op = dyn_cast<Operation *>())
45  return op->print(os);
46  if (auto value = dyn_cast<Value>())
47  return value.print(os);
48  return get<Block *>()->print(os);
49 }
50 
52  if (auto *programPoint = dyn_cast<GenericProgramPoint *>())
53  return programPoint->getLoc();
54  if (auto *op = dyn_cast<Operation *>())
55  return op->getLoc();
56  if (auto value = dyn_cast<Value>())
57  return value.getLoc();
58  return get<Block *>()->getParent()->getLoc();
59 }
60 
61 //===----------------------------------------------------------------------===//
62 // DataFlowSolver
63 //===----------------------------------------------------------------------===//
64 
66  // Initialize the analyses.
67  for (DataFlowAnalysis &analysis : llvm::make_pointee_range(childAnalyses)) {
68  DATAFLOW_DEBUG(llvm::dbgs()
69  << "Priming analysis: " << analysis.debugName << "\n");
70  if (failed(analysis.initialize(top)))
71  return failure();
72  }
73 
74  // Run the analysis until fixpoint.
75  do {
76  // Exhaust the worklist.
77  while (!worklist.empty()) {
78  auto [point, analysis] = worklist.front();
79  worklist.pop();
80 
81  DATAFLOW_DEBUG(llvm::dbgs() << "Invoking '" << analysis->debugName
82  << "' on: " << point << "\n");
83  if (failed(analysis->visit(point)))
84  return failure();
85  }
86 
87  // Iterate until all states are in some initialized state and the worklist
88  // is exhausted.
89  } while (!worklist.empty());
90 
91  return success();
92 }
93 
95  ChangeResult changed) {
96  if (changed == ChangeResult::Change) {
97  DATAFLOW_DEBUG(llvm::dbgs() << "Propagating update to " << state->debugName
98  << " of " << state->point << "\n"
99  << "Value: " << *state << "\n");
100  for (const WorkItem &item : state->dependents)
101  enqueue(item);
102  state->onUpdate(this);
103  }
104 }
105 
107  DataFlowAnalysis *analysis,
108  ProgramPoint point) {
109  auto inserted = state->dependents.insert({point, analysis});
110  (void)inserted;
112  if (inserted) {
113  llvm::dbgs() << "Creating dependency between " << state->debugName
114  << " of " << state->point << "\nand " << analysis->debugName
115  << " on " << point << "\n";
116  }
117  });
118 }
119 
120 //===----------------------------------------------------------------------===//
121 // DataFlowAnalysis
122 //===----------------------------------------------------------------------===//
123 
125 
127 
129  solver.addDependency(state, this, point);
130 }
131 
133  ChangeResult changed) {
134  solver.propagateIfChanged(state, changed);
135 }
Include the generated interface declarations.
virtual void onUpdate(DataFlowSolver *solver) const
This function is called by the solver when the analysis state is updated to optionally enqueue more w...
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:28
void print(raw_ostream &os) const
Print the program point.
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value...
Definition: LogicalResult.h:72
The general data-flow analysis solver.
void addDependency(AnalysisState *state, DataFlowAnalysis *analysis, ProgramPoint point)
Add a dependency to an analysis state on a child analysis and program point.
Fundamental IR components are supported as first-class program points.
#define DATAFLOW_DEBUG(X)
static constexpr const bool value
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition: Location.h:48
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
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...
std::pair< ProgramPoint, DataFlowAnalysis * > WorkItem
A work item on the solver queue is a program point, child analysis pair.
ProgramPoint point
The program point to which the state belongs.
Base class for all data-flow analyses.
virtual ~AnalysisState()
LogicalResult initializeAndRun(Operation *top)
Initialize the children analyses starting from the provided top-level operation and run the analysis ...
SetVector< DataFlowSolver::WorkItem > dependents
The dependency relations originating from this analysis state.
void addDependency(AnalysisState *state, ProgramPoint point)
Create a dependency between the given analysis state and program point on this analysis.
ChangeResult
A result type used to indicate if a change happened.
DataFlowAnalysis(DataFlowSolver &solver)
Create an analysis with a reference to the parent solver.
Location getLoc() const
Get the source location of the program point.
Base class for generic analysis states.