1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
#ifndef wasm_analysis_visitor_transfer_function_h
#define wasm_analysis_visitor_transfer_function_h
#include <queue>
#include "cfg.h"
#include "lattice.h"
#include "wasm-traversal.h"
namespace wasm::analysis {
enum class AnalysisDirection { Forward, Backward };
// Utility for visitor-based transfer functions for forward and backward
// analysis. Forward analysis is chosen by default unless the template parameter
// Backward is true.
template<typename SubType, typename Lattice, AnalysisDirection Direction>
struct VisitorTransferFunc : public Visitor<SubType> {
protected:
typename Lattice::Element* currState = nullptr;
// There are two distinct phases in the execution of the analyzer. First,
// the worklist algorithm will be run to obtain a solution, calling
// transfer() for each block. Then, to collect the final states, the analyzer
// will iterate over every block, calling collectResults().
// As there is only one set of visitor functions, they are used both to
// mutate intermediate states as the transfer function, and also to
// collect results from the final states. Therefore, we have the variable
// collectingResults to signal whether we are collecting results from the
// solved analysis, as opposed to solving the analysis to the visitor
// functions.
bool collectingResults = false;
public:
// Returns an iterable to all the BasicBlocks which depend on currBlock for
// information.
BasicBlock::BasicBlockIterable getDependents(const BasicBlock* currBlock) {
if constexpr (Direction == AnalysisDirection::Backward) {
return currBlock->preds();
} else {
return currBlock->succs();
}
}
// Executes the transfer function on all the expressions of the corresponding
// CFG node, starting with the node's input state, and changes the input state
// to the final output state of the node in place.
void transfer(const BasicBlock* cfgBlock,
typename Lattice::Element& inputState) {
// If the block is empty, we propagate the state by inputState =
// outputState.
currState = &inputState;
if constexpr (Direction == AnalysisDirection::Backward) {
for (auto cfgIter = cfgBlock->rbegin(); cfgIter != cfgBlock->rend();
++cfgIter) {
static_cast<SubType*>(this)->visit(*cfgIter);
}
} else {
for (auto cfgIter = cfgBlock->begin(); cfgIter != cfgBlock->end();
++cfgIter) {
static_cast<SubType*>(this)->visit(*cfgIter);
}
}
currState = nullptr;
}
// Enqueues the worklist before the worklist algorithm is run. We want to
// evaluate the blocks in an order matching the "flow" of the analysis to
// reduce the number of state propagations needed. Thus, for a forward
// analysis, we push all the blocks in order, while for backward analysis, we
// push them in reverse order, so that later blocks are evaluated before
// earlier ones.
void enqueueWorklist(CFG& cfg, std::queue<const BasicBlock*>& worklist) {
if constexpr (Direction == AnalysisDirection::Backward) {
for (auto it = cfg.rbegin(); it != cfg.rend(); ++it) {
worklist.push(&(*it));
}
} else {
for (auto it = cfg.begin(); it != cfg.end(); ++it) {
worklist.push(&(*it));
}
}
}
// This is for collecting results after solving an analysis. Implemented in
// the same way as transfer(), but we also set the collectingResults flag.
void collectResults(const BasicBlock* cfgBlock,
typename Lattice::Element& inputState) {
collectingResults = true;
currState = &inputState;
if constexpr (Direction == AnalysisDirection::Backward) {
for (auto cfgIter = cfgBlock->rbegin(); cfgIter != cfgBlock->rend();
++cfgIter) {
static_cast<SubType*>(this)->visit(*cfgIter);
}
} else {
for (auto cfgIter = cfgBlock->begin(); cfgIter != cfgBlock->end();
++cfgIter) {
static_cast<SubType*>(this)->visit(*cfgIter);
}
}
currState = nullptr;
collectingResults = false;
}
};
} // namespace wasm::analysis
#endif // wasm_analysis_visitor_transfer_function_h
|
