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 
9 #include "mlir/Analysis/DataFlowFramework.h"
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 
25 GenericProgramPoint::~GenericProgramPoint() = default;
26 
27 //===----------------------------------------------------------------------===//
28 // AnalysisState
29 //===----------------------------------------------------------------------===//
30 
31 AnalysisState::~AnalysisState() = default;
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   if (auto *block = dyn_cast<Block *>())
49     return block->print(os);
50   auto *region = get<Region *>();
51   os << "{\n";
52   for (Block &block : *region) {
53     block.print(os);
54     os << "\n";
55   }
56   os << "}";
57 }
58 
59 Location ProgramPoint::getLoc() const {
60   if (auto *programPoint = dyn_cast<GenericProgramPoint *>())
61     return programPoint->getLoc();
62   if (auto *op = dyn_cast<Operation *>())
63     return op->getLoc();
64   if (auto value = dyn_cast<Value>())
65     return value.getLoc();
66   if (auto *block = dyn_cast<Block *>())
67     return block->getParent()->getLoc();
68   return get<Region *>()->getLoc();
69 }
70 
71 //===----------------------------------------------------------------------===//
72 // DataFlowSolver
73 //===----------------------------------------------------------------------===//
74 
75 LogicalResult DataFlowSolver::initializeAndRun(Operation *top) {
76   // Initialize the analyses.
77   for (DataFlowAnalysis &analysis : llvm::make_pointee_range(childAnalyses)) {
78     DATAFLOW_DEBUG(llvm::dbgs()
79                    << "Priming analysis: " << analysis.debugName << "\n");
80     if (failed(analysis.initialize(top)))
81       return failure();
82   }
83 
84   // Run the analysis until fixpoint.
85   ProgramPoint point;
86   DataFlowAnalysis *analysis;
87 
88   do {
89     // Exhaust the worklist.
90     while (!worklist.empty()) {
91       std::tie(point, analysis) = worklist.front();
92       worklist.pop();
93 
94       DATAFLOW_DEBUG(llvm::dbgs() << "Invoking '" << analysis->debugName
95                                   << "' on: " << point << "\n");
96       if (failed(analysis->visit(point)))
97         return failure();
98     }
99 
100     // "Nudge" the state of the analysis by forcefully initializing states that
101     // are still uninitialized. All uninitialized states in the graph can be
102     // initialized in any order because the analysis reached fixpoint, meaning
103     // that there are no work items that would have further nudged the analysis.
104     for (AnalysisState &state :
105          llvm::make_pointee_range(llvm::make_second_range(analysisStates))) {
106       if (!state.isUninitialized())
107         continue;
108       DATAFLOW_DEBUG(llvm::dbgs() << "Default initializing " << state.debugName
109                                   << " of " << state.point << "\n");
110       propagateIfChanged(&state, state.defaultInitialize());
111     }
112 
113     // Iterate until all states are in some initialized state and the worklist
114     // is exhausted.
115   } while (!worklist.empty());
116 
117   return success();
118 }
119 
120 void DataFlowSolver::propagateIfChanged(AnalysisState *state,
121                                         ChangeResult changed) {
122   if (changed == ChangeResult::Change) {
123     DATAFLOW_DEBUG(llvm::dbgs() << "Propagating update to " << state->debugName
124                                 << " of " << state->point << "\n"
125                                 << "Value: " << *state << "\n");
126     for (const WorkItem &item : state->dependents)
127       enqueue(item);
128     state->onUpdate(this);
129   }
130 }
131 
132 void DataFlowSolver::addDependency(AnalysisState *state,
133                                    DataFlowAnalysis *analysis,
134                                    ProgramPoint point) {
135   auto inserted = state->dependents.insert({point, analysis});
136   (void)inserted;
137   DATAFLOW_DEBUG({
138     if (inserted) {
139       llvm::dbgs() << "Creating dependency between " << state->debugName
140                    << " of " << state->point << "\nand " << analysis->debugName
141                    << " on " << point << "\n";
142     }
143   });
144 }
145 
146 //===----------------------------------------------------------------------===//
147 // DataFlowAnalysis
148 //===----------------------------------------------------------------------===//
149 
150 DataFlowAnalysis::~DataFlowAnalysis() = default;
151 
152 DataFlowAnalysis::DataFlowAnalysis(DataFlowSolver &solver) : solver(solver) {}
153 
154 void DataFlowAnalysis::addDependency(AnalysisState *state, ProgramPoint point) {
155   solver.addDependency(state, this, point);
156 }
157 
158 void DataFlowAnalysis::propagateIfChanged(AnalysisState *state,
159                                           ChangeResult changed) {
160   solver.propagateIfChanged(state, changed);
161 }
162