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
|
#ifndef wasm_analysis_liveness_transfer_function_h
#define wasm_analysis_liveness_transfer_function_h
#include "lattice.h"
#include "monotone-analyzer.h"
namespace wasm::analysis {
class LivenessTransferFunction : public Visitor<LivenessTransferFunction> {
FinitePowersetLattice::Element* currState = nullptr;
public:
// Transfer function implementation. A local becomes live before a get
// and becomes dead before a set.
void visitLocalSet(LocalSet* curr) {
assert(currState);
currState->set(curr->index, false);
}
void visitLocalGet(LocalGet* curr) {
assert(currState);
currState->set(curr->index, true);
}
// 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,
FinitePowersetLattice::Element& inputState) {
// If the block is empty, we propagate the state by inputState =
// outputState.
currState = &inputState;
// This is a backward analysis, so we start from the end of the CFG
// and evaluate every expression until the beginning.
for (auto cfgIter = cfgBlock->rbegin(); cfgIter != cfgBlock->rend();
++cfgIter) {
// Run transfer function.
visit(*cfgIter);
}
currState = nullptr;
}
// Enqueues the worklist before the worklist algorithm is run. For
// liveness analysis, we are doing a backward analysis, so we want
// to enqueue the worklist backward so that later CFG blocks are
// run before earlier CFG blocks. This improves performance by
// reducing the number of state propagations needed, since we are
// naturally following the backward flow at the beginning.
void enqueueWorklist(CFG& cfg, std::queue<const BasicBlock*>& worklist) {
for (auto it = cfg.rbegin(); it != cfg.rend(); ++it) {
worklist.push(&(*it));
}
}
// Predecessors depend on current basic block for information.
BasicBlock::Predecessors getDependents(const BasicBlock* currBlock) {
return currBlock->preds();
}
// Prints the intermediate states of each BlockState currBlock by applying
// the transfer function on each expression of the CFG block. This data is
// not stored in the BlockState itself. Requires the cfgBlock, and a temp
// copy of the input state to be passed in, where the temp copy is modified
// in place to produce the intermediate states.
void print(std::ostream& os,
const BasicBlock* cfgBlock,
FinitePowersetLattice::Element& inputState) {
os << "Intermediate States (reverse order): " << std::endl;
currState = &inputState;
currState->print(os);
os << std::endl;
auto cfgIter = cfgBlock->rbegin();
// Since we don't store the intermediate states in the BlockState, we need
// to re-run the transfer function on all the CFG node expressions to
// reconstruct the intermediate states here.
while (cfgIter != cfgBlock->rend()) {
os << ShallowExpression{*cfgIter} << std::endl;
LivenessTransferFunction::visit(*cfgIter);
currState->print(os);
os << std::endl;
++cfgIter;
}
currState = nullptr;
}
};
} // namespace wasm::analysis
#endif // wasm_analysis_liveness_transfer_function_h
|
