1/*
2 * Copyright 2016 WebAssembly Community Group participants
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17//
18// WebAssembly AST visitor. Useful for anything that wants to do something
19// different for each AST node type, like printing, interpreting, etc.
20//
21// This class is specifically designed as a template to avoid virtual function
22// call overhead. To write a visitor, derive from this class as follows:
23//
24// struct MyVisitor : public WasmVisitor<MyVisitor> { .. }
25//
26
27#ifndef wasm_wasm_traversal_h
28#define wasm_wasm_traversal_h
29
30#include "support/small_vector.h"
31#include "support/threads.h"
32#include "wasm.h"
33
34namespace wasm {
35
36// A generic visitor, defaulting to doing nothing on each visit
37
38template<typename SubType, typename ReturnType = void> struct Visitor {
39 // Expression visitors
40#define DELEGATE(CLASS_TO_VISIT) \
41 ReturnType visit##CLASS_TO_VISIT(CLASS_TO_VISIT* curr) { \
42 return ReturnType(); \
43 }
44#include "wasm-delegations.def"
45
46 // Module-level visitors
47 ReturnType visitExport(Export* curr) { return ReturnType(); }
48 ReturnType visitGlobal(Global* curr) { return ReturnType(); }
49 ReturnType visitFunction(Function* curr) { return ReturnType(); }
50 ReturnType visitTable(Table* curr) { return ReturnType(); }
51 ReturnType visitElementSegment(ElementSegment* curr) { return ReturnType(); }
52 ReturnType visitMemory(Memory* curr) { return ReturnType(); }
53 ReturnType visitDataSegment(DataSegment* curr) { return ReturnType(); }
54 ReturnType visitTag(Tag* curr) { return ReturnType(); }
55 ReturnType visitModule(Module* curr) { return ReturnType(); }
56
57 ReturnType visit(Expression* curr) {
58 assert(curr);
59
60 switch (curr->_id) {
61#define DELEGATE(CLASS_TO_VISIT) \
62 case Expression::Id::CLASS_TO_VISIT##Id: \
63 return static_cast<SubType*>(this)->visit##CLASS_TO_VISIT( \
64 static_cast<CLASS_TO_VISIT*>(curr))
65
66#include "wasm-delegations.def"
67
68 default:
69 WASM_UNREACHABLE("unexpected expression type");
70 }
71 }
72};
73
74// A visitor which must be overridden for each visitor that is reached.
75
76template<typename SubType, typename ReturnType = void>
77struct OverriddenVisitor : public Visitor<SubType, ReturnType> {
78// Expression visitors, which must be overridden
79#define DELEGATE(CLASS_TO_VISIT) \
80 ReturnType visit##CLASS_TO_VISIT(CLASS_TO_VISIT* curr) { \
81 static_assert( \
82 &SubType::visit##CLASS_TO_VISIT != \
83 &OverriddenVisitor<SubType, ReturnType>::visit##CLASS_TO_VISIT, \
84 "Derived class must implement visit" #CLASS_TO_VISIT); \
85 WASM_UNREACHABLE("Derived class must implement visit" #CLASS_TO_VISIT); \
86 }
87
88#include "wasm-delegations.def"
89};
90
91// Visit with a single unified visitor, called on every node, instead of
92// separate visit* per node
93
94template<typename SubType, typename ReturnType = void>
95struct UnifiedExpressionVisitor : public Visitor<SubType, ReturnType> {
96 // called on each node
97 ReturnType visitExpression(Expression* curr) { return ReturnType(); }
98
99 // redirects
100#define DELEGATE(CLASS_TO_VISIT) \
101 ReturnType visit##CLASS_TO_VISIT(CLASS_TO_VISIT* curr) { \
102 return static_cast<SubType*>(this)->visitExpression(curr); \
103 }
104
105#include "wasm-delegations.def"
106};
107
108//
109// Base class for all WasmWalkers, which can traverse an AST
110// and provide the option to replace nodes while doing so.
111//
112// Subclass and implement the visit*()
113// calls to run code on different node types.
114//
115template<typename SubType, typename VisitorType>
116struct Walker : public VisitorType {
117 // Useful methods for visitor implementions
118
119 // Replace the current node. You can call this in your visit*() methods.
120 // Note that the visit*() for the result node is not called for you (i.e.,
121 // just one visit*() method is called by the traversal; if you replace a node,
122 // and you want to process the output, you must do that explicitly).
123 Expression* replaceCurrent(Expression* expression) {
124 // Copy debug info, if present.
125 if (currFunction) {
126 auto& debugLocations = currFunction->debugLocations;
127 if (!debugLocations.empty()) {
128 auto* curr = getCurrent();
129 auto iter = debugLocations.find(curr);
130 if (iter != debugLocations.end()) {
131 auto location = iter->second;
132 debugLocations.erase(iter);
133 debugLocations[expression] = location;
134 }
135 }
136 }
137 return *replacep = expression;
138 }
139
140 Expression* getCurrent() { return *replacep; }
141
142 Expression** getCurrentPointer() { return replacep; }
143
144 // Get the current module
145 Module* getModule() { return currModule; }
146
147 // Get the current function
148 Function* getFunction() { return currFunction; }
149
150 // Walk starting
151
152 void walkGlobal(Global* global) {
153 walk(root&: global->init);
154 static_cast<SubType*>(this)->visitGlobal(global);
155 }
156
157 void walkFunction(Function* func) {
158 setFunction(func);
159 static_cast<SubType*>(this)->doWalkFunction(func);
160 static_cast<SubType*>(this)->visitFunction(func);
161 setFunction(nullptr);
162 }
163
164 void walkTag(Tag* tag) { static_cast<SubType*>(this)->visitTag(tag); }
165
166 void walkFunctionInModule(Function* func, Module* module) {
167 setModule(module);
168 setFunction(func);
169 static_cast<SubType*>(this)->doWalkFunction(func);
170 static_cast<SubType*>(this)->visitFunction(func);
171 setFunction(nullptr);
172 setModule(nullptr);
173 }
174
175 // override this to provide custom functionality
176 void doWalkFunction(Function* func) { walk(root&: func->body); }
177
178 void walkElementSegment(ElementSegment* segment) {
179 if (segment->table.is()) {
180 walk(root&: segment->offset);
181 }
182 for (auto* expr : segment->data) {
183 walk(expr);
184 }
185 static_cast<SubType*>(this)->visitElementSegment(segment);
186 }
187
188 void walkTable(Table* table) {
189 static_cast<SubType*>(this)->visitTable(table);
190 }
191
192 void walkDataSegment(DataSegment* segment) {
193 if (!segment->isPassive) {
194 walk(root&: segment->offset);
195 }
196 static_cast<SubType*>(this)->visitDataSegment(segment);
197 }
198
199 void walkMemory(Memory* memory) {
200 // TODO: This method and walkTable should walk children too, or be renamed.
201 static_cast<SubType*>(this)->visitMemory(memory);
202 }
203
204 void walkModule(Module* module) {
205 setModule(module);
206 static_cast<SubType*>(this)->doWalkModule(module);
207 static_cast<SubType*>(this)->visitModule(module);
208 setModule(nullptr);
209 }
210
211 // override this to provide custom functionality
212 void doWalkModule(Module* module) {
213 // Dispatch statically through the SubType.
214 SubType* self = static_cast<SubType*>(this);
215 for (auto& curr : module->exports) {
216 self->visitExport(curr.get());
217 }
218 for (auto& curr : module->globals) {
219 if (curr->imported()) {
220 self->visitGlobal(curr.get());
221 } else {
222 self->walkGlobal(curr.get());
223 }
224 }
225 for (auto& curr : module->functions) {
226 if (curr->imported()) {
227 self->visitFunction(curr.get());
228 } else {
229 self->walkFunction(curr.get());
230 }
231 }
232 for (auto& curr : module->tags) {
233 if (curr->imported()) {
234 self->visitTag(curr.get());
235 } else {
236 self->walkTag(curr.get());
237 }
238 }
239 for (auto& curr : module->tables) {
240 self->walkTable(curr.get());
241 }
242 for (auto& curr : module->elementSegments) {
243 self->walkElementSegment(curr.get());
244 }
245 for (auto& curr : module->memories) {
246 self->walkMemory(curr.get());
247 }
248 for (auto& curr : module->dataSegments) {
249 self->walkDataSegment(curr.get());
250 }
251 }
252
253 // Walks module-level code, that is, code that is not in functions.
254 void walkModuleCode(Module* module) {
255 setModule(module);
256 // Dispatch statically through the SubType.
257 SubType* self = static_cast<SubType*>(this);
258 for (auto& curr : module->globals) {
259 if (!curr->imported()) {
260 self->walk(curr->init);
261 }
262 }
263 for (auto& curr : module->elementSegments) {
264 if (curr->offset) {
265 self->walk(curr->offset);
266 }
267 for (auto* item : curr->data) {
268 self->walk(item);
269 }
270 }
271 for (auto& curr : module->dataSegments) {
272 if (curr->offset) {
273 self->walk(curr->offset);
274 }
275 }
276 setModule(nullptr);
277 }
278
279 // Walk implementation. We don't use recursion as ASTs may be highly
280 // nested.
281
282 // Tasks receive the this pointer and a pointer to the pointer to operate on
283 using TaskFunc = void (*)(SubType*, Expression**);
284
285 struct Task {
286 TaskFunc func;
287 Expression** currp;
288 Task() {}
289 Task(TaskFunc func, Expression** currp) : func(func), currp(currp) {}
290 };
291
292 void pushTask(TaskFunc func, Expression** currp) {
293 assert(*currp);
294 stack.emplace_back(func, currp);
295 }
296 void maybePushTask(TaskFunc func, Expression** currp) {
297 if (*currp) {
298 stack.emplace_back(func, currp);
299 }
300 }
301 Task popTask() {
302 auto ret = stack.back();
303 stack.pop_back();
304 return ret;
305 }
306
307 void walk(Expression*& root) {
308 assert(stack.size() == 0);
309 pushTask(func: SubType::scan, currp: &root);
310 while (stack.size() > 0) {
311 auto task = popTask();
312 replacep = task.currp;
313 assert(*task.currp);
314 task.func(static_cast<SubType*>(this), task.currp);
315 }
316 }
317
318 // subclasses implement this to define the proper order of execution
319 static void scan(SubType* self, Expression** currp) { abort(); }
320
321 // task hooks to call visitors
322
323#define DELEGATE(CLASS_TO_VISIT) \
324 static void doVisit##CLASS_TO_VISIT(SubType* self, Expression** currp) { \
325 self->visit##CLASS_TO_VISIT((*currp)->cast<CLASS_TO_VISIT>()); \
326 }
327
328#include "wasm-delegations.def"
329
330 void setModule(Module* module) { currModule = module; }
331
332 void setFunction(Function* func) { currFunction = func; }
333
334private:
335 // the address of the current node, used to replace it
336 Expression** replacep = nullptr;
337 SmallVector<Task, 10> stack; // stack of tasks
338 Function* currFunction = nullptr; // current function being processed
339 Module* currModule = nullptr; // current module being processed
340};
341
342// Walks in post-order, i.e., children first. When there isn't an obvious
343// order to operands, we follow them in order of execution.
344
345template<typename SubType, typename VisitorType = Visitor<SubType>>
346struct PostWalker : public Walker<SubType, VisitorType> {
347
348 static void scan(SubType* self, Expression** currp) {
349 Expression* curr = *currp;
350
351#define DELEGATE_ID curr->_id
352
353#define DELEGATE_START(id) \
354 self->pushTask(SubType::doVisit##id, currp); \
355 [[maybe_unused]] auto* cast = curr->cast<id>();
356
357#define DELEGATE_GET_FIELD(id, field) cast->field
358
359#define DELEGATE_FIELD_CHILD(id, field) \
360 self->pushTask(SubType::scan, &cast->field);
361
362#define DELEGATE_FIELD_OPTIONAL_CHILD(id, field) \
363 self->maybePushTask(SubType::scan, &cast->field);
364
365#define DELEGATE_FIELD_INT(id, field)
366#define DELEGATE_FIELD_INT_ARRAY(id, field)
367#define DELEGATE_FIELD_LITERAL(id, field)
368#define DELEGATE_FIELD_NAME(id, field)
369#define DELEGATE_FIELD_NAME_VECTOR(id, field)
370#define DELEGATE_FIELD_SCOPE_NAME_DEF(id, field)
371#define DELEGATE_FIELD_SCOPE_NAME_USE(id, field)
372#define DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR(id, field)
373#define DELEGATE_FIELD_TYPE(id, field)
374#define DELEGATE_FIELD_HEAPTYPE(id, field)
375#define DELEGATE_FIELD_ADDRESS(id, field)
376
377#include "wasm-delegations-fields.def"
378 }
379};
380
381// Stacks of expressions tend to be limited in size (although, sometimes
382// super-nested blocks exist for br_table).
383using ExpressionStack = SmallVector<Expression*, 10>;
384
385// Traversal with a control-flow stack.
386
387template<typename SubType, typename VisitorType = Visitor<SubType>>
388struct ControlFlowWalker : public PostWalker<SubType, VisitorType> {
389 ControlFlowWalker() = default;
390
391 ExpressionStack controlFlowStack; // contains blocks, loops, and ifs
392
393 // Uses the control flow stack to find the target of a break to a name
394 Expression* findBreakTarget(Name name) {
395 assert(!controlFlowStack.empty());
396 Index i = controlFlowStack.size() - 1;
397 while (true) {
398 auto* curr = controlFlowStack[i];
399 if (Block* block = curr->template dynCast<Block>()) {
400 if (name == block->name) {
401 return curr;
402 }
403 } else if (Loop* loop = curr->template dynCast<Loop>()) {
404 if (name == loop->name) {
405 return curr;
406 }
407 } else {
408 // an if or try, ignorable
409 assert(curr->template is<If>() || curr->template is<Try>());
410 }
411 if (i == 0) {
412 return nullptr;
413 }
414 i--;
415 }
416 }
417
418 static void doPreVisitControlFlow(SubType* self, Expression** currp) {
419 self->controlFlowStack.push_back(*currp);
420 }
421
422 static void doPostVisitControlFlow(SubType* self, Expression** currp) {
423 // note that we might be popping something else, as we may have been
424 // replaced
425 self->controlFlowStack.pop_back();
426 }
427
428 static void scan(SubType* self, Expression** currp) {
429 auto* curr = *currp;
430
431 switch (curr->_id) {
432 case Expression::Id::BlockId:
433 case Expression::Id::IfId:
434 case Expression::Id::LoopId:
435 case Expression::Id::TryId: {
436 self->pushTask(SubType::doPostVisitControlFlow, currp);
437 break;
438 }
439 default: {
440 }
441 }
442
443 PostWalker<SubType, VisitorType>::scan(self, currp);
444
445 switch (curr->_id) {
446 case Expression::Id::BlockId:
447 case Expression::Id::IfId:
448 case Expression::Id::LoopId:
449 case Expression::Id::TryId: {
450 self->pushTask(SubType::doPreVisitControlFlow, currp);
451 break;
452 }
453 default: {
454 }
455 }
456 }
457};
458
459// Traversal with an expression stack.
460
461template<typename SubType, typename VisitorType = Visitor<SubType>>
462struct ExpressionStackWalker : public PostWalker<SubType, VisitorType> {
463 ExpressionStackWalker() = default;
464
465 ExpressionStack expressionStack;
466
467 // Uses the control flow stack to find the target of a break to a name
468 Expression* findBreakTarget(Name name) {
469 assert(!expressionStack.empty());
470 Index i = expressionStack.size() - 1;
471 while (true) {
472 auto* curr = expressionStack[i];
473 if (Block* block = curr->template dynCast<Block>()) {
474 if (name == block->name) {
475 return curr;
476 }
477 } else if (Loop* loop = curr->template dynCast<Loop>()) {
478 if (name == loop->name) {
479 return curr;
480 }
481 }
482 if (i == 0) {
483 return nullptr;
484 }
485 i--;
486 }
487 }
488
489 Expression* getParent() {
490 if (expressionStack.size() == 1) {
491 return nullptr;
492 }
493 assert(expressionStack.size() >= 2);
494 return expressionStack[expressionStack.size() - 2];
495 }
496
497 static void doPreVisit(SubType* self, Expression** currp) {
498 self->expressionStack.push_back(*currp);
499 }
500
501 static void doPostVisit(SubType* self, Expression** currp) {
502 self->expressionStack.pop_back();
503 }
504
505 static void scan(SubType* self, Expression** currp) {
506 self->pushTask(SubType::doPostVisit, currp);
507
508 PostWalker<SubType, VisitorType>::scan(self, currp);
509
510 self->pushTask(SubType::doPreVisit, currp);
511 }
512
513 Expression* replaceCurrent(Expression* expression) {
514 PostWalker<SubType, VisitorType>::replaceCurrent(expression);
515 // also update the stack
516 expressionStack.back() = expression;
517 return expression;
518 }
519};
520
521} // namespace wasm
522
523#endif // wasm_wasm_traversal_h
524

source code of dart_sdk/third_party/binaryen/src/src/wasm-traversal.h