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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
/*
* Copyright 2021 WebAssembly Community Group participants
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef wasm_ir_linear_execution_h
#define wasm_ir_linear_execution_h
#include "ir/properties.h"
#include "wasm-traversal.h"
#include "wasm.h"
namespace wasm {
// Traversal in the order of execution. This is quick and simple, but
// does not provide the same comprehensive information that a full
// conversion to basic blocks would. What it does give is a quick
// way to view straightline execution traces, i.e., that have no
// branching. This can let optimizations get most of what they
// want without the cost of creating another AST.
//
// When execution is no longer linear, this notifies via a call
// to noteNonLinear().
template<typename SubType, typename VisitorType = Visitor<SubType>>
struct LinearExecutionWalker : public PostWalker<SubType, VisitorType> {
LinearExecutionWalker() = default;
// subclasses should implement this
void noteNonLinear(Expression* curr) { abort(); }
static void doNoteNonLinear(SubType* self, Expression** currp) {
self->noteNonLinear(*currp);
}
// Optionally, we can connect adjacent basic blocks. "Adjacent" here means
// that the first branches to the second, and that there is no other code in
// between them. As a result, the first dominates the second, but it might not
// reach it.
//
// For example, a call may branch if exceptions are enabled, but if this
// option is flipped on then we will *not* call doNoteNonLinear on the call:
//
// ..A..
// call();
// ..B..
//
// As a result, we'd consider A and B to be together. Another example is an
// if:
//
// ..A..
// if
// ..B..
// else
// ..C..
// end
//
// Here we will connect A and B, but *not* A and C (there is code in between)
// or B and C (they do not branch to each other).
//
// As the if case shows, this can be useful for cases where we want to look at
// dominated blocks with their dominator, but it only handles the trivial
// adjacent cases of such dominance. Passes should generally uses a full CFG
// and dominator tree for this, but this option does help some very common
// cases (calls, if without an else) and it has very low overhead (we still
// only do a simple postorder walk on the IR, no CFG is constructed, etc.).
bool connectAdjacentBlocks = false;
static void scan(SubType* self, Expression** currp) {
Expression* curr = *currp;
auto handleCall = [&](bool isReturn) {
if (!self->connectAdjacentBlocks) {
// Control is nonlinear if we return, or if EH is enabled or may be.
if (isReturn || !self->getModule() ||
self->getModule()->features.hasExceptionHandling()) {
self->pushTask(SubType::doNoteNonLinear, currp);
}
}
// Scan the children normally.
PostWalker<SubType, VisitorType>::scan(self, currp);
};
switch (curr->_id) {
case Expression::Id::InvalidId:
WASM_UNREACHABLE("bad id");
case Expression::Id::BlockId: {
self->pushTask(SubType::doVisitBlock, currp);
if (curr->cast<Block>()->name.is()) {
self->pushTask(SubType::doNoteNonLinear, currp);
}
auto& list = curr->cast<Block>()->list;
for (int i = int(list.size()) - 1; i >= 0; i--) {
self->pushTask(SubType::scan, &list[i]);
}
break;
}
case Expression::Id::IfId: {
self->pushTask(SubType::doVisitIf, currp);
self->pushTask(SubType::doNoteNonLinear, currp);
self->maybePushTask(SubType::scan, &curr->cast<If>()->ifFalse);
self->pushTask(SubType::doNoteNonLinear, currp);
self->pushTask(SubType::scan, &curr->cast<If>()->ifTrue);
if (!self->connectAdjacentBlocks) {
self->pushTask(SubType::doNoteNonLinear, currp);
}
self->pushTask(SubType::scan, &curr->cast<If>()->condition);
break;
}
case Expression::Id::LoopId: {
self->pushTask(SubType::doVisitLoop, currp);
self->pushTask(SubType::scan, &curr->cast<Loop>()->body);
self->pushTask(SubType::doNoteNonLinear, currp);
break;
}
case Expression::Id::BreakId: {
self->pushTask(SubType::doVisitBreak, currp);
auto* br = curr->cast<Break>();
// If there is no condition then we note non-linearity as the code after
// us is unreachable anyhow (we do the same for Switch, Return, etc.).
// If there is a condition, then we note or do not note depending on
// whether we allow adjacent blocks.
if (!br->condition || !self->connectAdjacentBlocks) {
self->pushTask(SubType::doNoteNonLinear, currp);
}
self->maybePushTask(SubType::scan, &br->condition);
self->maybePushTask(SubType::scan, &br->value);
break;
}
case Expression::Id::SwitchId: {
self->pushTask(SubType::doVisitSwitch, currp);
self->pushTask(SubType::doNoteNonLinear, currp);
self->pushTask(SubType::scan, &curr->cast<Switch>()->condition);
self->maybePushTask(SubType::scan, &curr->cast<Switch>()->value);
break;
}
case Expression::Id::ReturnId: {
self->pushTask(SubType::doVisitReturn, currp);
self->pushTask(SubType::doNoteNonLinear, currp);
self->maybePushTask(SubType::scan, &curr->cast<Return>()->value);
break;
}
case Expression::Id::CallId: {
handleCall(curr->cast<Call>()->isReturn);
return;
}
case Expression::Id::CallRefId: {
handleCall(curr->cast<CallRef>()->isReturn);
return;
}
case Expression::Id::TryId: {
self->pushTask(SubType::doVisitTry, currp);
self->pushTask(SubType::doNoteNonLinear, currp);
auto& list = curr->cast<Try>()->catchBodies;
for (int i = int(list.size()) - 1; i >= 0; i--) {
self->pushTask(SubType::scan, &list[i]);
self->pushTask(SubType::doNoteNonLinear, currp);
}
self->pushTask(SubType::scan, &curr->cast<Try>()->body);
break;
}
case Expression::Id::ThrowId: {
self->pushTask(SubType::doVisitThrow, currp);
self->pushTask(SubType::doNoteNonLinear, currp);
auto& list = curr->cast<Throw>()->operands;
for (int i = int(list.size()) - 1; i >= 0; i--) {
self->pushTask(SubType::scan, &list[i]);
}
break;
}
case Expression::Id::RethrowId: {
self->pushTask(SubType::doVisitRethrow, currp);
self->pushTask(SubType::doNoteNonLinear, currp);
break;
}
case Expression::Id::UnreachableId: {
self->pushTask(SubType::doVisitUnreachable, currp);
self->pushTask(SubType::doNoteNonLinear, currp);
break;
}
case Expression::Id::BrOnId: {
self->pushTask(SubType::doVisitBrOn, currp);
if (!self->connectAdjacentBlocks) {
self->pushTask(SubType::doNoteNonLinear, currp);
}
self->pushTask(SubType::scan, &curr->cast<BrOn>()->ref);
break;
}
default: {
// All relevant things should have been handled.
assert(!Properties::isControlFlowStructure(curr));
assert(!Properties::isBranch(curr));
// other node types do not have control flow, use regular post-order
PostWalker<SubType, VisitorType>::scan(self, currp);
}
}
}
};
} // namespace wasm
#endif // wasm_ir_linear_execution_h