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 
34 namespace wasm {
35 
36 // A generic visitor, defaulting to doing nothing on each visit
37 
38 template<typename SubType, typename ReturnType = void> struct Visitor {
39   // Expression visitors
visitBlockVisitor40   ReturnType visitBlock(Block* curr) { return ReturnType(); }
visitIfVisitor41   ReturnType visitIf(If* curr) { return ReturnType(); }
visitLoopVisitor42   ReturnType visitLoop(Loop* curr) { return ReturnType(); }
visitBreakVisitor43   ReturnType visitBreak(Break* curr) { return ReturnType(); }
visitSwitchVisitor44   ReturnType visitSwitch(Switch* curr) { return ReturnType(); }
visitCallVisitor45   ReturnType visitCall(Call* curr) { return ReturnType(); }
visitCallIndirectVisitor46   ReturnType visitCallIndirect(CallIndirect* curr) { return ReturnType(); }
visitLocalGetVisitor47   ReturnType visitLocalGet(LocalGet* curr) { return ReturnType(); }
visitLocalSetVisitor48   ReturnType visitLocalSet(LocalSet* curr) { return ReturnType(); }
visitGlobalGetVisitor49   ReturnType visitGlobalGet(GlobalGet* curr) { return ReturnType(); }
visitGlobalSetVisitor50   ReturnType visitGlobalSet(GlobalSet* curr) { return ReturnType(); }
visitLoadVisitor51   ReturnType visitLoad(Load* curr) { return ReturnType(); }
visitStoreVisitor52   ReturnType visitStore(Store* curr) { return ReturnType(); }
visitAtomicRMWVisitor53   ReturnType visitAtomicRMW(AtomicRMW* curr) { return ReturnType(); }
visitAtomicCmpxchgVisitor54   ReturnType visitAtomicCmpxchg(AtomicCmpxchg* curr) { return ReturnType(); }
visitAtomicWaitVisitor55   ReturnType visitAtomicWait(AtomicWait* curr) { return ReturnType(); }
visitAtomicNotifyVisitor56   ReturnType visitAtomicNotify(AtomicNotify* curr) { return ReturnType(); }
visitAtomicFenceVisitor57   ReturnType visitAtomicFence(AtomicFence* curr) { return ReturnType(); }
visitSIMDExtractVisitor58   ReturnType visitSIMDExtract(SIMDExtract* curr) { return ReturnType(); }
visitSIMDReplaceVisitor59   ReturnType visitSIMDReplace(SIMDReplace* curr) { return ReturnType(); }
visitSIMDShuffleVisitor60   ReturnType visitSIMDShuffle(SIMDShuffle* curr) { return ReturnType(); }
visitSIMDTernaryVisitor61   ReturnType visitSIMDTernary(SIMDTernary* curr) { return ReturnType(); }
visitSIMDShiftVisitor62   ReturnType visitSIMDShift(SIMDShift* curr) { return ReturnType(); }
visitSIMDLoadVisitor63   ReturnType visitSIMDLoad(SIMDLoad* curr) { return ReturnType(); }
visitMemoryInitVisitor64   ReturnType visitMemoryInit(MemoryInit* curr) { return ReturnType(); }
visitDataDropVisitor65   ReturnType visitDataDrop(DataDrop* curr) { return ReturnType(); }
visitMemoryCopyVisitor66   ReturnType visitMemoryCopy(MemoryCopy* curr) { return ReturnType(); }
visitMemoryFillVisitor67   ReturnType visitMemoryFill(MemoryFill* curr) { return ReturnType(); }
visitConstVisitor68   ReturnType visitConst(Const* curr) { return ReturnType(); }
visitUnaryVisitor69   ReturnType visitUnary(Unary* curr) { return ReturnType(); }
visitBinaryVisitor70   ReturnType visitBinary(Binary* curr) { return ReturnType(); }
visitSelectVisitor71   ReturnType visitSelect(Select* curr) { return ReturnType(); }
visitDropVisitor72   ReturnType visitDrop(Drop* curr) { return ReturnType(); }
visitReturnVisitor73   ReturnType visitReturn(Return* curr) { return ReturnType(); }
visitMemorySizeVisitor74   ReturnType visitMemorySize(MemorySize* curr) { return ReturnType(); }
visitMemoryGrowVisitor75   ReturnType visitMemoryGrow(MemoryGrow* curr) { return ReturnType(); }
visitRefNullVisitor76   ReturnType visitRefNull(RefNull* curr) { return ReturnType(); }
visitRefIsNullVisitor77   ReturnType visitRefIsNull(RefIsNull* curr) { return ReturnType(); }
visitRefFuncVisitor78   ReturnType visitRefFunc(RefFunc* curr) { return ReturnType(); }
visitRefEqVisitor79   ReturnType visitRefEq(RefEq* curr) { return ReturnType(); }
visitTryVisitor80   ReturnType visitTry(Try* curr) { return ReturnType(); }
visitThrowVisitor81   ReturnType visitThrow(Throw* curr) { return ReturnType(); }
visitRethrowVisitor82   ReturnType visitRethrow(Rethrow* curr) { return ReturnType(); }
visitBrOnExnVisitor83   ReturnType visitBrOnExn(BrOnExn* curr) { return ReturnType(); }
visitNopVisitor84   ReturnType visitNop(Nop* curr) { return ReturnType(); }
visitUnreachableVisitor85   ReturnType visitUnreachable(Unreachable* curr) { return ReturnType(); }
visitPopVisitor86   ReturnType visitPop(Pop* curr) { return ReturnType(); }
visitTupleMakeVisitor87   ReturnType visitTupleMake(TupleMake* curr) { return ReturnType(); }
visitTupleExtractVisitor88   ReturnType visitTupleExtract(TupleExtract* curr) { return ReturnType(); }
visitI31NewVisitor89   ReturnType visitI31New(I31New* curr) { return ReturnType(); }
visitI31GetVisitor90   ReturnType visitI31Get(I31Get* curr) { return ReturnType(); }
visitRefTestVisitor91   ReturnType visitRefTest(RefTest* curr) { return ReturnType(); }
visitRefCastVisitor92   ReturnType visitRefCast(RefCast* curr) { return ReturnType(); }
visitBrOnCastVisitor93   ReturnType visitBrOnCast(BrOnCast* curr) { return ReturnType(); }
visitRttCanonVisitor94   ReturnType visitRttCanon(RttCanon* curr) { return ReturnType(); }
visitRttSubVisitor95   ReturnType visitRttSub(RttSub* curr) { return ReturnType(); }
visitStructNewVisitor96   ReturnType visitStructNew(StructNew* curr) { return ReturnType(); }
visitStructGetVisitor97   ReturnType visitStructGet(StructGet* curr) { return ReturnType(); }
visitStructSetVisitor98   ReturnType visitStructSet(StructSet* curr) { return ReturnType(); }
visitArrayNewVisitor99   ReturnType visitArrayNew(ArrayNew* curr) { return ReturnType(); }
visitArrayGetVisitor100   ReturnType visitArrayGet(ArrayGet* curr) { return ReturnType(); }
visitArraySetVisitor101   ReturnType visitArraySet(ArraySet* curr) { return ReturnType(); }
visitArrayLenVisitor102   ReturnType visitArrayLen(ArrayLen* curr) { return ReturnType(); }
103   // Module-level visitors
visitExportVisitor104   ReturnType visitExport(Export* curr) { return ReturnType(); }
visitGlobalVisitor105   ReturnType visitGlobal(Global* curr) { return ReturnType(); }
visitFunctionVisitor106   ReturnType visitFunction(Function* curr) { return ReturnType(); }
visitTableVisitor107   ReturnType visitTable(Table* curr) { return ReturnType(); }
visitMemoryVisitor108   ReturnType visitMemory(Memory* curr) { return ReturnType(); }
visitEventVisitor109   ReturnType visitEvent(Event* curr) { return ReturnType(); }
visitModuleVisitor110   ReturnType visitModule(Module* curr) { return ReturnType(); }
111 
visitVisitor112   ReturnType visit(Expression* curr) {
113     assert(curr);
114 
115 #define DELEGATE(CLASS_TO_VISIT)                                               \
116   return static_cast<SubType*>(this)->visit##CLASS_TO_VISIT(                   \
117     static_cast<CLASS_TO_VISIT*>(curr))
118 
119     switch (curr->_id) {
120       case Expression::Id::BlockId:
121         DELEGATE(Block);
122       case Expression::Id::IfId:
123         DELEGATE(If);
124       case Expression::Id::LoopId:
125         DELEGATE(Loop);
126       case Expression::Id::BreakId:
127         DELEGATE(Break);
128       case Expression::Id::SwitchId:
129         DELEGATE(Switch);
130       case Expression::Id::CallId:
131         DELEGATE(Call);
132       case Expression::Id::CallIndirectId:
133         DELEGATE(CallIndirect);
134       case Expression::Id::LocalGetId:
135         DELEGATE(LocalGet);
136       case Expression::Id::LocalSetId:
137         DELEGATE(LocalSet);
138       case Expression::Id::GlobalGetId:
139         DELEGATE(GlobalGet);
140       case Expression::Id::GlobalSetId:
141         DELEGATE(GlobalSet);
142       case Expression::Id::LoadId:
143         DELEGATE(Load);
144       case Expression::Id::StoreId:
145         DELEGATE(Store);
146       case Expression::Id::AtomicRMWId:
147         DELEGATE(AtomicRMW);
148       case Expression::Id::AtomicCmpxchgId:
149         DELEGATE(AtomicCmpxchg);
150       case Expression::Id::AtomicWaitId:
151         DELEGATE(AtomicWait);
152       case Expression::Id::AtomicNotifyId:
153         DELEGATE(AtomicNotify);
154       case Expression::Id::AtomicFenceId:
155         DELEGATE(AtomicFence);
156       case Expression::Id::SIMDExtractId:
157         DELEGATE(SIMDExtract);
158       case Expression::Id::SIMDReplaceId:
159         DELEGATE(SIMDReplace);
160       case Expression::Id::SIMDShuffleId:
161         DELEGATE(SIMDShuffle);
162       case Expression::Id::SIMDTernaryId:
163         DELEGATE(SIMDTernary);
164       case Expression::Id::SIMDShiftId:
165         DELEGATE(SIMDShift);
166       case Expression::Id::SIMDLoadId:
167         DELEGATE(SIMDLoad);
168       case Expression::Id::MemoryInitId:
169         DELEGATE(MemoryInit);
170       case Expression::Id::DataDropId:
171         DELEGATE(DataDrop);
172       case Expression::Id::MemoryCopyId:
173         DELEGATE(MemoryCopy);
174       case Expression::Id::MemoryFillId:
175         DELEGATE(MemoryFill);
176       case Expression::Id::ConstId:
177         DELEGATE(Const);
178       case Expression::Id::UnaryId:
179         DELEGATE(Unary);
180       case Expression::Id::BinaryId:
181         DELEGATE(Binary);
182       case Expression::Id::SelectId:
183         DELEGATE(Select);
184       case Expression::Id::DropId:
185         DELEGATE(Drop);
186       case Expression::Id::ReturnId:
187         DELEGATE(Return);
188       case Expression::Id::MemorySizeId:
189         DELEGATE(MemorySize);
190       case Expression::Id::MemoryGrowId:
191         DELEGATE(MemoryGrow);
192       case Expression::Id::RefNullId:
193         DELEGATE(RefNull);
194       case Expression::Id::RefIsNullId:
195         DELEGATE(RefIsNull);
196       case Expression::Id::RefFuncId:
197         DELEGATE(RefFunc);
198       case Expression::Id::RefEqId:
199         DELEGATE(RefEq);
200       case Expression::Id::TryId:
201         DELEGATE(Try);
202       case Expression::Id::ThrowId:
203         DELEGATE(Throw);
204       case Expression::Id::RethrowId:
205         DELEGATE(Rethrow);
206       case Expression::Id::BrOnExnId:
207         DELEGATE(BrOnExn);
208       case Expression::Id::NopId:
209         DELEGATE(Nop);
210       case Expression::Id::UnreachableId:
211         DELEGATE(Unreachable);
212       case Expression::Id::PopId:
213         DELEGATE(Pop);
214       case Expression::Id::TupleMakeId:
215         DELEGATE(TupleMake);
216       case Expression::Id::TupleExtractId:
217         DELEGATE(TupleExtract);
218       case Expression::Id::I31NewId:
219         DELEGATE(I31New);
220       case Expression::Id::I31GetId:
221         DELEGATE(I31Get);
222       case Expression::Id::RefTestId:
223         DELEGATE(RefTest);
224       case Expression::Id::RefCastId:
225         DELEGATE(RefCast);
226       case Expression::Id::BrOnCastId:
227         DELEGATE(BrOnCast);
228       case Expression::Id::RttCanonId:
229         DELEGATE(RttCanon);
230       case Expression::Id::RttSubId:
231         DELEGATE(RttSub);
232       case Expression::Id::StructNewId:
233         DELEGATE(StructNew);
234       case Expression::Id::StructGetId:
235         DELEGATE(StructGet);
236       case Expression::Id::StructSetId:
237         DELEGATE(StructSet);
238       case Expression::Id::ArrayNewId:
239         DELEGATE(ArrayNew);
240       case Expression::Id::ArrayGetId:
241         DELEGATE(ArrayGet);
242       case Expression::Id::ArraySetId:
243         DELEGATE(ArraySet);
244       case Expression::Id::ArrayLenId:
245         DELEGATE(ArrayLen);
246       case Expression::Id::InvalidId:
247       default:
248         WASM_UNREACHABLE("unexpected expression type");
249     }
250 
251 #undef DELEGATE
252   }
253 };
254 
255 // A visitor which must be overridden for each visitor that is reached.
256 
257 template<typename SubType, typename ReturnType = void>
258 struct OverriddenVisitor {
259 // Expression visitors, which must be overridden
260 #define UNIMPLEMENTED(CLASS_TO_VISIT)                                          \
261   ReturnType visit##CLASS_TO_VISIT(CLASS_TO_VISIT* curr) {                     \
262     static_assert(                                                             \
263       &SubType::visit##CLASS_TO_VISIT !=                                       \
264         &OverriddenVisitor<SubType, ReturnType>::visit##CLASS_TO_VISIT,        \
265       "Derived class must implement visit" #CLASS_TO_VISIT);                   \
266     WASM_UNREACHABLE("Derived class must implement visit" #CLASS_TO_VISIT);    \
267   }
268 
269   UNIMPLEMENTED(Block);
270   UNIMPLEMENTED(If);
271   UNIMPLEMENTED(Loop);
272   UNIMPLEMENTED(Break);
273   UNIMPLEMENTED(Switch);
274   UNIMPLEMENTED(Call);
275   UNIMPLEMENTED(CallIndirect);
276   UNIMPLEMENTED(LocalGet);
277   UNIMPLEMENTED(LocalSet);
278   UNIMPLEMENTED(GlobalGet);
279   UNIMPLEMENTED(GlobalSet);
280   UNIMPLEMENTED(Load);
281   UNIMPLEMENTED(Store);
282   UNIMPLEMENTED(AtomicRMW);
283   UNIMPLEMENTED(AtomicCmpxchg);
284   UNIMPLEMENTED(AtomicWait);
285   UNIMPLEMENTED(AtomicNotify);
286   UNIMPLEMENTED(AtomicFence);
287   UNIMPLEMENTED(SIMDExtract);
288   UNIMPLEMENTED(SIMDReplace);
289   UNIMPLEMENTED(SIMDShuffle);
290   UNIMPLEMENTED(SIMDTernary);
291   UNIMPLEMENTED(SIMDShift);
292   UNIMPLEMENTED(SIMDLoad);
293   UNIMPLEMENTED(MemoryInit);
294   UNIMPLEMENTED(DataDrop);
295   UNIMPLEMENTED(MemoryCopy);
296   UNIMPLEMENTED(MemoryFill);
297   UNIMPLEMENTED(Const);
298   UNIMPLEMENTED(Unary);
299   UNIMPLEMENTED(Binary);
300   UNIMPLEMENTED(Select);
301   UNIMPLEMENTED(Drop);
302   UNIMPLEMENTED(Return);
303   UNIMPLEMENTED(MemorySize);
304   UNIMPLEMENTED(MemoryGrow);
305   UNIMPLEMENTED(RefNull);
306   UNIMPLEMENTED(RefIsNull);
307   UNIMPLEMENTED(RefFunc);
308   UNIMPLEMENTED(RefEq);
309   UNIMPLEMENTED(Try);
310   UNIMPLEMENTED(Throw);
311   UNIMPLEMENTED(Rethrow);
312   UNIMPLEMENTED(BrOnExn);
313   UNIMPLEMENTED(Nop);
314   UNIMPLEMENTED(Unreachable);
315   UNIMPLEMENTED(Pop);
316   UNIMPLEMENTED(TupleMake);
317   UNIMPLEMENTED(TupleExtract);
318   UNIMPLEMENTED(I31New);
319   UNIMPLEMENTED(I31Get);
320   UNIMPLEMENTED(RefTest);
321   UNIMPLEMENTED(RefCast);
322   UNIMPLEMENTED(BrOnCast);
323   UNIMPLEMENTED(RttCanon);
324   UNIMPLEMENTED(RttSub);
325   UNIMPLEMENTED(StructNew);
326   UNIMPLEMENTED(StructGet);
327   UNIMPLEMENTED(StructSet);
328   UNIMPLEMENTED(ArrayNew);
329   UNIMPLEMENTED(ArrayGet);
330   UNIMPLEMENTED(ArraySet);
331   UNIMPLEMENTED(ArrayLen);
332   UNIMPLEMENTED(Export);
333   UNIMPLEMENTED(Global);
334   UNIMPLEMENTED(Function);
335   UNIMPLEMENTED(Table);
336   UNIMPLEMENTED(Memory);
337   UNIMPLEMENTED(Event);
338   UNIMPLEMENTED(Module);
339 
340 #undef UNIMPLEMENTED
341 
visitOverriddenVisitor342   ReturnType visit(Expression* curr) {
343     assert(curr);
344 
345 #define DELEGATE(CLASS_TO_VISIT)                                               \
346   return static_cast<SubType*>(this)->visit##CLASS_TO_VISIT(                   \
347     static_cast<CLASS_TO_VISIT*>(curr))
348 
349     switch (curr->_id) {
350       case Expression::Id::BlockId:
351         DELEGATE(Block);
352       case Expression::Id::IfId:
353         DELEGATE(If);
354       case Expression::Id::LoopId:
355         DELEGATE(Loop);
356       case Expression::Id::BreakId:
357         DELEGATE(Break);
358       case Expression::Id::SwitchId:
359         DELEGATE(Switch);
360       case Expression::Id::CallId:
361         DELEGATE(Call);
362       case Expression::Id::CallIndirectId:
363         DELEGATE(CallIndirect);
364       case Expression::Id::LocalGetId:
365         DELEGATE(LocalGet);
366       case Expression::Id::LocalSetId:
367         DELEGATE(LocalSet);
368       case Expression::Id::GlobalGetId:
369         DELEGATE(GlobalGet);
370       case Expression::Id::GlobalSetId:
371         DELEGATE(GlobalSet);
372       case Expression::Id::LoadId:
373         DELEGATE(Load);
374       case Expression::Id::StoreId:
375         DELEGATE(Store);
376       case Expression::Id::AtomicRMWId:
377         DELEGATE(AtomicRMW);
378       case Expression::Id::AtomicCmpxchgId:
379         DELEGATE(AtomicCmpxchg);
380       case Expression::Id::AtomicWaitId:
381         DELEGATE(AtomicWait);
382       case Expression::Id::AtomicNotifyId:
383         DELEGATE(AtomicNotify);
384       case Expression::Id::AtomicFenceId:
385         DELEGATE(AtomicFence);
386       case Expression::Id::SIMDExtractId:
387         DELEGATE(SIMDExtract);
388       case Expression::Id::SIMDReplaceId:
389         DELEGATE(SIMDReplace);
390       case Expression::Id::SIMDShuffleId:
391         DELEGATE(SIMDShuffle);
392       case Expression::Id::SIMDTernaryId:
393         DELEGATE(SIMDTernary);
394       case Expression::Id::SIMDShiftId:
395         DELEGATE(SIMDShift);
396       case Expression::Id::SIMDLoadId:
397         DELEGATE(SIMDLoad);
398       case Expression::Id::MemoryInitId:
399         DELEGATE(MemoryInit);
400       case Expression::Id::DataDropId:
401         DELEGATE(DataDrop);
402       case Expression::Id::MemoryCopyId:
403         DELEGATE(MemoryCopy);
404       case Expression::Id::MemoryFillId:
405         DELEGATE(MemoryFill);
406       case Expression::Id::ConstId:
407         DELEGATE(Const);
408       case Expression::Id::UnaryId:
409         DELEGATE(Unary);
410       case Expression::Id::BinaryId:
411         DELEGATE(Binary);
412       case Expression::Id::SelectId:
413         DELEGATE(Select);
414       case Expression::Id::DropId:
415         DELEGATE(Drop);
416       case Expression::Id::ReturnId:
417         DELEGATE(Return);
418       case Expression::Id::MemorySizeId:
419         DELEGATE(MemorySize);
420       case Expression::Id::MemoryGrowId:
421         DELEGATE(MemoryGrow);
422       case Expression::Id::RefNullId:
423         DELEGATE(RefNull);
424       case Expression::Id::RefIsNullId:
425         DELEGATE(RefIsNull);
426       case Expression::Id::RefFuncId:
427         DELEGATE(RefFunc);
428       case Expression::Id::RefEqId:
429         DELEGATE(RefEq);
430       case Expression::Id::TryId:
431         DELEGATE(Try);
432       case Expression::Id::ThrowId:
433         DELEGATE(Throw);
434       case Expression::Id::RethrowId:
435         DELEGATE(Rethrow);
436       case Expression::Id::BrOnExnId:
437         DELEGATE(BrOnExn);
438       case Expression::Id::NopId:
439         DELEGATE(Nop);
440       case Expression::Id::UnreachableId:
441         DELEGATE(Unreachable);
442       case Expression::Id::PopId:
443         DELEGATE(Pop);
444       case Expression::Id::TupleMakeId:
445         DELEGATE(TupleMake);
446       case Expression::Id::TupleExtractId:
447         DELEGATE(TupleExtract);
448       case Expression::Id::I31NewId:
449         DELEGATE(I31New);
450       case Expression::Id::I31GetId:
451         DELEGATE(I31Get);
452       case Expression::Id::RefTestId:
453         DELEGATE(RefTest);
454       case Expression::Id::RefCastId:
455         DELEGATE(RefCast);
456       case Expression::Id::BrOnCastId:
457         DELEGATE(BrOnCast);
458       case Expression::Id::RttCanonId:
459         DELEGATE(RttCanon);
460       case Expression::Id::RttSubId:
461         DELEGATE(RttSub);
462       case Expression::Id::StructNewId:
463         DELEGATE(StructNew);
464       case Expression::Id::StructGetId:
465         DELEGATE(StructGet);
466       case Expression::Id::StructSetId:
467         DELEGATE(StructSet);
468       case Expression::Id::ArrayNewId:
469         DELEGATE(ArrayNew);
470       case Expression::Id::ArrayGetId:
471         DELEGATE(ArrayGet);
472       case Expression::Id::ArraySetId:
473         DELEGATE(ArraySet);
474       case Expression::Id::ArrayLenId:
475         DELEGATE(ArrayLen);
476       case Expression::Id::InvalidId:
477       default:
478         WASM_UNREACHABLE("unexpected expression type");
479     }
480 
481 #undef DELEGATE
482   }
483 };
484 
485 // Visit with a single unified visitor, called on every node, instead of
486 // separate visit* per node
487 
488 template<typename SubType, typename ReturnType = void>
489 struct UnifiedExpressionVisitor : public Visitor<SubType, ReturnType> {
490   // called on each node
visitExpressionUnifiedExpressionVisitor491   ReturnType visitExpression(Expression* curr) { return ReturnType(); }
492 
493   // redirects
visitBlockUnifiedExpressionVisitor494   ReturnType visitBlock(Block* curr) {
495     return static_cast<SubType*>(this)->visitExpression(curr);
496   }
visitIfUnifiedExpressionVisitor497   ReturnType visitIf(If* curr) {
498     return static_cast<SubType*>(this)->visitExpression(curr);
499   }
visitLoopUnifiedExpressionVisitor500   ReturnType visitLoop(Loop* curr) {
501     return static_cast<SubType*>(this)->visitExpression(curr);
502   }
visitBreakUnifiedExpressionVisitor503   ReturnType visitBreak(Break* curr) {
504     return static_cast<SubType*>(this)->visitExpression(curr);
505   }
visitSwitchUnifiedExpressionVisitor506   ReturnType visitSwitch(Switch* curr) {
507     return static_cast<SubType*>(this)->visitExpression(curr);
508   }
visitCallUnifiedExpressionVisitor509   ReturnType visitCall(Call* curr) {
510     return static_cast<SubType*>(this)->visitExpression(curr);
511   }
visitCallIndirectUnifiedExpressionVisitor512   ReturnType visitCallIndirect(CallIndirect* curr) {
513     return static_cast<SubType*>(this)->visitExpression(curr);
514   }
visitLocalGetUnifiedExpressionVisitor515   ReturnType visitLocalGet(LocalGet* curr) {
516     return static_cast<SubType*>(this)->visitExpression(curr);
517   }
visitLocalSetUnifiedExpressionVisitor518   ReturnType visitLocalSet(LocalSet* curr) {
519     return static_cast<SubType*>(this)->visitExpression(curr);
520   }
visitGlobalGetUnifiedExpressionVisitor521   ReturnType visitGlobalGet(GlobalGet* curr) {
522     return static_cast<SubType*>(this)->visitExpression(curr);
523   }
visitGlobalSetUnifiedExpressionVisitor524   ReturnType visitGlobalSet(GlobalSet* curr) {
525     return static_cast<SubType*>(this)->visitExpression(curr);
526   }
visitLoadUnifiedExpressionVisitor527   ReturnType visitLoad(Load* curr) {
528     return static_cast<SubType*>(this)->visitExpression(curr);
529   }
visitStoreUnifiedExpressionVisitor530   ReturnType visitStore(Store* curr) {
531     return static_cast<SubType*>(this)->visitExpression(curr);
532   }
visitAtomicRMWUnifiedExpressionVisitor533   ReturnType visitAtomicRMW(AtomicRMW* curr) {
534     return static_cast<SubType*>(this)->visitExpression(curr);
535   }
visitAtomicCmpxchgUnifiedExpressionVisitor536   ReturnType visitAtomicCmpxchg(AtomicCmpxchg* curr) {
537     return static_cast<SubType*>(this)->visitExpression(curr);
538   }
visitAtomicWaitUnifiedExpressionVisitor539   ReturnType visitAtomicWait(AtomicWait* curr) {
540     return static_cast<SubType*>(this)->visitExpression(curr);
541   }
visitAtomicNotifyUnifiedExpressionVisitor542   ReturnType visitAtomicNotify(AtomicNotify* curr) {
543     return static_cast<SubType*>(this)->visitExpression(curr);
544   }
visitAtomicFenceUnifiedExpressionVisitor545   ReturnType visitAtomicFence(AtomicFence* curr) {
546     return static_cast<SubType*>(this)->visitExpression(curr);
547   }
visitSIMDExtractUnifiedExpressionVisitor548   ReturnType visitSIMDExtract(SIMDExtract* curr) {
549     return static_cast<SubType*>(this)->visitExpression(curr);
550   }
visitSIMDReplaceUnifiedExpressionVisitor551   ReturnType visitSIMDReplace(SIMDReplace* curr) {
552     return static_cast<SubType*>(this)->visitExpression(curr);
553   }
visitSIMDShuffleUnifiedExpressionVisitor554   ReturnType visitSIMDShuffle(SIMDShuffle* curr) {
555     return static_cast<SubType*>(this)->visitExpression(curr);
556   }
visitSIMDTernaryUnifiedExpressionVisitor557   ReturnType visitSIMDTernary(SIMDTernary* curr) {
558     return static_cast<SubType*>(this)->visitExpression(curr);
559   }
visitSIMDShiftUnifiedExpressionVisitor560   ReturnType visitSIMDShift(SIMDShift* curr) {
561     return static_cast<SubType*>(this)->visitExpression(curr);
562   }
visitSIMDLoadUnifiedExpressionVisitor563   ReturnType visitSIMDLoad(SIMDLoad* curr) {
564     return static_cast<SubType*>(this)->visitExpression(curr);
565   }
visitMemoryInitUnifiedExpressionVisitor566   ReturnType visitMemoryInit(MemoryInit* curr) {
567     return static_cast<SubType*>(this)->visitExpression(curr);
568   }
visitDataDropUnifiedExpressionVisitor569   ReturnType visitDataDrop(DataDrop* curr) {
570     return static_cast<SubType*>(this)->visitExpression(curr);
571   }
visitMemoryCopyUnifiedExpressionVisitor572   ReturnType visitMemoryCopy(MemoryCopy* curr) {
573     return static_cast<SubType*>(this)->visitExpression(curr);
574   }
visitMemoryFillUnifiedExpressionVisitor575   ReturnType visitMemoryFill(MemoryFill* curr) {
576     return static_cast<SubType*>(this)->visitExpression(curr);
577   }
visitConstUnifiedExpressionVisitor578   ReturnType visitConst(Const* curr) {
579     return static_cast<SubType*>(this)->visitExpression(curr);
580   }
visitUnaryUnifiedExpressionVisitor581   ReturnType visitUnary(Unary* curr) {
582     return static_cast<SubType*>(this)->visitExpression(curr);
583   }
visitBinaryUnifiedExpressionVisitor584   ReturnType visitBinary(Binary* curr) {
585     return static_cast<SubType*>(this)->visitExpression(curr);
586   }
visitSelectUnifiedExpressionVisitor587   ReturnType visitSelect(Select* curr) {
588     return static_cast<SubType*>(this)->visitExpression(curr);
589   }
visitDropUnifiedExpressionVisitor590   ReturnType visitDrop(Drop* curr) {
591     return static_cast<SubType*>(this)->visitExpression(curr);
592   }
visitReturnUnifiedExpressionVisitor593   ReturnType visitReturn(Return* curr) {
594     return static_cast<SubType*>(this)->visitExpression(curr);
595   }
visitMemorySizeUnifiedExpressionVisitor596   ReturnType visitMemorySize(MemorySize* curr) {
597     return static_cast<SubType*>(this)->visitExpression(curr);
598   }
visitMemoryGrowUnifiedExpressionVisitor599   ReturnType visitMemoryGrow(MemoryGrow* curr) {
600     return static_cast<SubType*>(this)->visitExpression(curr);
601   }
visitRefNullUnifiedExpressionVisitor602   ReturnType visitRefNull(RefNull* curr) {
603     return static_cast<SubType*>(this)->visitExpression(curr);
604   }
visitRefIsNullUnifiedExpressionVisitor605   ReturnType visitRefIsNull(RefIsNull* curr) {
606     return static_cast<SubType*>(this)->visitExpression(curr);
607   }
visitRefFuncUnifiedExpressionVisitor608   ReturnType visitRefFunc(RefFunc* curr) {
609     return static_cast<SubType*>(this)->visitExpression(curr);
610   }
visitRefEqUnifiedExpressionVisitor611   ReturnType visitRefEq(RefEq* curr) {
612     return static_cast<SubType*>(this)->visitExpression(curr);
613   }
visitTryUnifiedExpressionVisitor614   ReturnType visitTry(Try* curr) {
615     return static_cast<SubType*>(this)->visitExpression(curr);
616   }
visitThrowUnifiedExpressionVisitor617   ReturnType visitThrow(Throw* curr) {
618     return static_cast<SubType*>(this)->visitExpression(curr);
619   }
visitRethrowUnifiedExpressionVisitor620   ReturnType visitRethrow(Rethrow* curr) {
621     return static_cast<SubType*>(this)->visitExpression(curr);
622   }
visitBrOnExnUnifiedExpressionVisitor623   ReturnType visitBrOnExn(BrOnExn* curr) {
624     return static_cast<SubType*>(this)->visitExpression(curr);
625   }
visitNopUnifiedExpressionVisitor626   ReturnType visitNop(Nop* curr) {
627     return static_cast<SubType*>(this)->visitExpression(curr);
628   }
visitUnreachableUnifiedExpressionVisitor629   ReturnType visitUnreachable(Unreachable* curr) {
630     return static_cast<SubType*>(this)->visitExpression(curr);
631   }
visitPopUnifiedExpressionVisitor632   ReturnType visitPop(Pop* curr) {
633     return static_cast<SubType*>(this)->visitExpression(curr);
634   }
visitTupleMakeUnifiedExpressionVisitor635   ReturnType visitTupleMake(TupleMake* curr) {
636     return static_cast<SubType*>(this)->visitExpression(curr);
637   }
visitTupleExtractUnifiedExpressionVisitor638   ReturnType visitTupleExtract(TupleExtract* curr) {
639     return static_cast<SubType*>(this)->visitExpression(curr);
640   }
visitI31NewUnifiedExpressionVisitor641   ReturnType visitI31New(I31New* curr) {
642     return static_cast<SubType*>(this)->visitExpression(curr);
643   }
visitI31GetUnifiedExpressionVisitor644   ReturnType visitI31Get(I31Get* curr) {
645     return static_cast<SubType*>(this)->visitExpression(curr);
646   }
visitRefTestUnifiedExpressionVisitor647   ReturnType visitRefTest(RefTest* curr) {
648     return static_cast<SubType*>(this)->visitExpression(curr);
649   }
visitRefCastUnifiedExpressionVisitor650   ReturnType visitRefCast(RefCast* curr) {
651     return static_cast<SubType*>(this)->visitExpression(curr);
652   }
visitBrOnCastUnifiedExpressionVisitor653   ReturnType visitBrOnCast(BrOnCast* curr) {
654     return static_cast<SubType*>(this)->visitExpression(curr);
655   }
visitRttCanonUnifiedExpressionVisitor656   ReturnType visitRttCanon(RttCanon* curr) {
657     return static_cast<SubType*>(this)->visitExpression(curr);
658   }
visitRttSubUnifiedExpressionVisitor659   ReturnType visitRttSub(RttSub* curr) {
660     return static_cast<SubType*>(this)->visitExpression(curr);
661   }
visitStructNewUnifiedExpressionVisitor662   ReturnType visitStructNew(StructNew* curr) {
663     return static_cast<SubType*>(this)->visitExpression(curr);
664   }
visitStructGetUnifiedExpressionVisitor665   ReturnType visitStructGet(StructGet* curr) {
666     return static_cast<SubType*>(this)->visitExpression(curr);
667   }
visitStructSetUnifiedExpressionVisitor668   ReturnType visitStructSet(StructSet* curr) {
669     return static_cast<SubType*>(this)->visitExpression(curr);
670   }
visitArrayNewUnifiedExpressionVisitor671   ReturnType visitArrayNew(ArrayNew* curr) {
672     return static_cast<SubType*>(this)->visitExpression(curr);
673   }
visitArrayGetUnifiedExpressionVisitor674   ReturnType visitArrayGet(ArrayGet* curr) {
675     return static_cast<SubType*>(this)->visitExpression(curr);
676   }
visitArraySetUnifiedExpressionVisitor677   ReturnType visitArraySet(ArraySet* curr) {
678     return static_cast<SubType*>(this)->visitExpression(curr);
679   }
visitArrayLenUnifiedExpressionVisitor680   ReturnType visitArrayLen(ArrayLen* curr) {
681     return static_cast<SubType*>(this)->visitExpression(curr);
682   }
683 };
684 
685 //
686 // Base class for all WasmWalkers, which can traverse an AST
687 // and provide the option to replace nodes while doing so.
688 //
689 // Subclass and implement the visit*()
690 // calls to run code on different node types.
691 //
692 template<typename SubType, typename VisitorType>
693 struct Walker : public VisitorType {
694   // Useful methods for visitor implementions
695 
696   // Replace the current node. You can call this in your visit*() methods.
697   // Note that the visit*() for the result node is not called for you (i.e.,
698   // just one visit*() method is called by the traversal; if you replace a node,
699   // and you want to process the output, you must do that explicitly).
replaceCurrentWalker700   Expression* replaceCurrent(Expression* expression) {
701     // Copy debug info, if present.
702     if (currFunction) {
703       auto& debugLocations = currFunction->debugLocations;
704       if (!debugLocations.empty()) {
705         auto* curr = getCurrent();
706         auto iter = debugLocations.find(curr);
707         if (iter != debugLocations.end()) {
708           auto location = iter->second;
709           debugLocations.erase(iter);
710           debugLocations[expression] = location;
711         }
712       }
713     }
714     return *replacep = expression;
715   }
716 
getCurrentWalker717   Expression* getCurrent() { return *replacep; }
718 
getCurrentPointerWalker719   Expression** getCurrentPointer() { return replacep; }
720 
721   // Get the current module
getModuleWalker722   Module* getModule() { return currModule; }
723 
724   // Get the current function
getFunctionWalker725   Function* getFunction() { return currFunction; }
726 
727   // Walk starting
728 
walkGlobalWalker729   void walkGlobal(Global* global) {
730     walk(global->init);
731     static_cast<SubType*>(this)->visitGlobal(global);
732   }
733 
walkFunctionWalker734   void walkFunction(Function* func) {
735     setFunction(func);
736     static_cast<SubType*>(this)->doWalkFunction(func);
737     static_cast<SubType*>(this)->visitFunction(func);
738     setFunction(nullptr);
739   }
740 
walkEventWalker741   void walkEvent(Event* event) {
742     static_cast<SubType*>(this)->visitEvent(event);
743   }
744 
walkFunctionInModuleWalker745   void walkFunctionInModule(Function* func, Module* module) {
746     setModule(module);
747     setFunction(func);
748     static_cast<SubType*>(this)->doWalkFunction(func);
749     static_cast<SubType*>(this)->visitFunction(func);
750     setFunction(nullptr);
751     setModule(nullptr);
752   }
753 
754   // override this to provide custom functionality
doWalkFunctionWalker755   void doWalkFunction(Function* func) { walk(func->body); }
756 
walkTableWalker757   void walkTable(Table* table) {
758     for (auto& segment : table->segments) {
759       walk(segment.offset);
760     }
761     static_cast<SubType*>(this)->visitTable(table);
762   }
763 
walkMemoryWalker764   void walkMemory(Memory* memory) {
765     for (auto& segment : memory->segments) {
766       if (!segment.isPassive) {
767         walk(segment.offset);
768       }
769     }
770     static_cast<SubType*>(this)->visitMemory(memory);
771   }
772 
walkModuleWalker773   void walkModule(Module* module) {
774     setModule(module);
775     static_cast<SubType*>(this)->doWalkModule(module);
776     static_cast<SubType*>(this)->visitModule(module);
777     setModule(nullptr);
778   }
779 
780   // override this to provide custom functionality
doWalkModuleWalker781   void doWalkModule(Module* module) {
782     // Dispatch statically through the SubType.
783     SubType* self = static_cast<SubType*>(this);
784     for (auto& curr : module->exports) {
785       self->visitExport(curr.get());
786     }
787     for (auto& curr : module->globals) {
788       if (curr->imported()) {
789         self->visitGlobal(curr.get());
790       } else {
791         self->walkGlobal(curr.get());
792       }
793     }
794     for (auto& curr : module->functions) {
795       if (curr->imported()) {
796         self->visitFunction(curr.get());
797       } else {
798         self->walkFunction(curr.get());
799       }
800     }
801     for (auto& curr : module->events) {
802       if (curr->imported()) {
803         self->visitEvent(curr.get());
804       } else {
805         self->walkEvent(curr.get());
806       }
807     }
808     self->walkTable(&module->table);
809     self->walkMemory(&module->memory);
810   }
811 
812   // Walk implementation. We don't use recursion as ASTs may be highly
813   // nested.
814 
815   // Tasks receive the this pointer and a pointer to the pointer to operate on
816   typedef void (*TaskFunc)(SubType*, Expression**);
817 
818   struct Task {
819     TaskFunc func;
820     Expression** currp;
TaskWalker::Task821     Task() {}
TaskWalker::Task822     Task(TaskFunc func, Expression** currp) : func(func), currp(currp) {}
823   };
824 
pushTaskWalker825   void pushTask(TaskFunc func, Expression** currp) {
826     assert(*currp);
827     stack.emplace_back(func, currp);
828   }
maybePushTaskWalker829   void maybePushTask(TaskFunc func, Expression** currp) {
830     if (*currp) {
831       stack.emplace_back(func, currp);
832     }
833   }
popTaskWalker834   Task popTask() {
835     auto ret = stack.back();
836     stack.pop_back();
837     return ret;
838   }
839 
walkWalker840   void walk(Expression*& root) {
841     assert(stack.size() == 0);
842     pushTask(SubType::scan, &root);
843     while (stack.size() > 0) {
844       auto task = popTask();
845       replacep = task.currp;
846       assert(*task.currp);
847       task.func(static_cast<SubType*>(this), task.currp);
848     }
849   }
850 
851   // subclasses implement this to define the proper order of execution
scanWalker852   static void scan(SubType* self, Expression** currp) { abort(); }
853 
854   // task hooks to call visitors
855 
doVisitBlockWalker856   static void doVisitBlock(SubType* self, Expression** currp) {
857     self->visitBlock((*currp)->cast<Block>());
858   }
doVisitIfWalker859   static void doVisitIf(SubType* self, Expression** currp) {
860     self->visitIf((*currp)->cast<If>());
861   }
doVisitLoopWalker862   static void doVisitLoop(SubType* self, Expression** currp) {
863     self->visitLoop((*currp)->cast<Loop>());
864   }
doVisitBreakWalker865   static void doVisitBreak(SubType* self, Expression** currp) {
866     self->visitBreak((*currp)->cast<Break>());
867   }
doVisitSwitchWalker868   static void doVisitSwitch(SubType* self, Expression** currp) {
869     self->visitSwitch((*currp)->cast<Switch>());
870   }
doVisitCallWalker871   static void doVisitCall(SubType* self, Expression** currp) {
872     self->visitCall((*currp)->cast<Call>());
873   }
doVisitCallIndirectWalker874   static void doVisitCallIndirect(SubType* self, Expression** currp) {
875     self->visitCallIndirect((*currp)->cast<CallIndirect>());
876   }
doVisitLocalGetWalker877   static void doVisitLocalGet(SubType* self, Expression** currp) {
878     self->visitLocalGet((*currp)->cast<LocalGet>());
879   }
doVisitLocalSetWalker880   static void doVisitLocalSet(SubType* self, Expression** currp) {
881     self->visitLocalSet((*currp)->cast<LocalSet>());
882   }
doVisitGlobalGetWalker883   static void doVisitGlobalGet(SubType* self, Expression** currp) {
884     self->visitGlobalGet((*currp)->cast<GlobalGet>());
885   }
doVisitGlobalSetWalker886   static void doVisitGlobalSet(SubType* self, Expression** currp) {
887     self->visitGlobalSet((*currp)->cast<GlobalSet>());
888   }
doVisitLoadWalker889   static void doVisitLoad(SubType* self, Expression** currp) {
890     self->visitLoad((*currp)->cast<Load>());
891   }
doVisitStoreWalker892   static void doVisitStore(SubType* self, Expression** currp) {
893     self->visitStore((*currp)->cast<Store>());
894   }
doVisitAtomicRMWWalker895   static void doVisitAtomicRMW(SubType* self, Expression** currp) {
896     self->visitAtomicRMW((*currp)->cast<AtomicRMW>());
897   }
doVisitAtomicCmpxchgWalker898   static void doVisitAtomicCmpxchg(SubType* self, Expression** currp) {
899     self->visitAtomicCmpxchg((*currp)->cast<AtomicCmpxchg>());
900   }
doVisitAtomicWaitWalker901   static void doVisitAtomicWait(SubType* self, Expression** currp) {
902     self->visitAtomicWait((*currp)->cast<AtomicWait>());
903   }
doVisitAtomicNotifyWalker904   static void doVisitAtomicNotify(SubType* self, Expression** currp) {
905     self->visitAtomicNotify((*currp)->cast<AtomicNotify>());
906   }
doVisitAtomicFenceWalker907   static void doVisitAtomicFence(SubType* self, Expression** currp) {
908     self->visitAtomicFence((*currp)->cast<AtomicFence>());
909   }
doVisitSIMDExtractWalker910   static void doVisitSIMDExtract(SubType* self, Expression** currp) {
911     self->visitSIMDExtract((*currp)->cast<SIMDExtract>());
912   }
doVisitSIMDReplaceWalker913   static void doVisitSIMDReplace(SubType* self, Expression** currp) {
914     self->visitSIMDReplace((*currp)->cast<SIMDReplace>());
915   }
doVisitSIMDShuffleWalker916   static void doVisitSIMDShuffle(SubType* self, Expression** currp) {
917     self->visitSIMDShuffle((*currp)->cast<SIMDShuffle>());
918   }
doVisitSIMDTernaryWalker919   static void doVisitSIMDTernary(SubType* self, Expression** currp) {
920     self->visitSIMDTernary((*currp)->cast<SIMDTernary>());
921   }
doVisitSIMDShiftWalker922   static void doVisitSIMDShift(SubType* self, Expression** currp) {
923     self->visitSIMDShift((*currp)->cast<SIMDShift>());
924   }
doVisitSIMDLoadWalker925   static void doVisitSIMDLoad(SubType* self, Expression** currp) {
926     self->visitSIMDLoad((*currp)->cast<SIMDLoad>());
927   }
doVisitMemoryInitWalker928   static void doVisitMemoryInit(SubType* self, Expression** currp) {
929     self->visitMemoryInit((*currp)->cast<MemoryInit>());
930   }
doVisitDataDropWalker931   static void doVisitDataDrop(SubType* self, Expression** currp) {
932     self->visitDataDrop((*currp)->cast<DataDrop>());
933   }
doVisitMemoryCopyWalker934   static void doVisitMemoryCopy(SubType* self, Expression** currp) {
935     self->visitMemoryCopy((*currp)->cast<MemoryCopy>());
936   }
doVisitMemoryFillWalker937   static void doVisitMemoryFill(SubType* self, Expression** currp) {
938     self->visitMemoryFill((*currp)->cast<MemoryFill>());
939   }
doVisitConstWalker940   static void doVisitConst(SubType* self, Expression** currp) {
941     self->visitConst((*currp)->cast<Const>());
942   }
doVisitUnaryWalker943   static void doVisitUnary(SubType* self, Expression** currp) {
944     self->visitUnary((*currp)->cast<Unary>());
945   }
doVisitBinaryWalker946   static void doVisitBinary(SubType* self, Expression** currp) {
947     self->visitBinary((*currp)->cast<Binary>());
948   }
doVisitSelectWalker949   static void doVisitSelect(SubType* self, Expression** currp) {
950     self->visitSelect((*currp)->cast<Select>());
951   }
doVisitDropWalker952   static void doVisitDrop(SubType* self, Expression** currp) {
953     self->visitDrop((*currp)->cast<Drop>());
954   }
doVisitReturnWalker955   static void doVisitReturn(SubType* self, Expression** currp) {
956     self->visitReturn((*currp)->cast<Return>());
957   }
doVisitMemorySizeWalker958   static void doVisitMemorySize(SubType* self, Expression** currp) {
959     self->visitMemorySize((*currp)->cast<MemorySize>());
960   }
doVisitMemoryGrowWalker961   static void doVisitMemoryGrow(SubType* self, Expression** currp) {
962     self->visitMemoryGrow((*currp)->cast<MemoryGrow>());
963   }
doVisitRefNullWalker964   static void doVisitRefNull(SubType* self, Expression** currp) {
965     self->visitRefNull((*currp)->cast<RefNull>());
966   }
doVisitRefIsNullWalker967   static void doVisitRefIsNull(SubType* self, Expression** currp) {
968     self->visitRefIsNull((*currp)->cast<RefIsNull>());
969   }
doVisitRefFuncWalker970   static void doVisitRefFunc(SubType* self, Expression** currp) {
971     self->visitRefFunc((*currp)->cast<RefFunc>());
972   }
doVisitRefEqWalker973   static void doVisitRefEq(SubType* self, Expression** currp) {
974     self->visitRefEq((*currp)->cast<RefEq>());
975   }
doVisitTryWalker976   static void doVisitTry(SubType* self, Expression** currp) {
977     self->visitTry((*currp)->cast<Try>());
978   }
doVisitThrowWalker979   static void doVisitThrow(SubType* self, Expression** currp) {
980     self->visitThrow((*currp)->cast<Throw>());
981   }
doVisitRethrowWalker982   static void doVisitRethrow(SubType* self, Expression** currp) {
983     self->visitRethrow((*currp)->cast<Rethrow>());
984   }
doVisitBrOnExnWalker985   static void doVisitBrOnExn(SubType* self, Expression** currp) {
986     self->visitBrOnExn((*currp)->cast<BrOnExn>());
987   }
doVisitNopWalker988   static void doVisitNop(SubType* self, Expression** currp) {
989     self->visitNop((*currp)->cast<Nop>());
990   }
doVisitUnreachableWalker991   static void doVisitUnreachable(SubType* self, Expression** currp) {
992     self->visitUnreachable((*currp)->cast<Unreachable>());
993   }
doVisitPopWalker994   static void doVisitPop(SubType* self, Expression** currp) {
995     self->visitPop((*currp)->cast<Pop>());
996   }
doVisitTupleMakeWalker997   static void doVisitTupleMake(SubType* self, Expression** currp) {
998     self->visitTupleMake((*currp)->cast<TupleMake>());
999   }
doVisitTupleExtractWalker1000   static void doVisitTupleExtract(SubType* self, Expression** currp) {
1001     self->visitTupleExtract((*currp)->cast<TupleExtract>());
1002   }
doVisitI31NewWalker1003   static void doVisitI31New(SubType* self, Expression** currp) {
1004     self->visitI31New((*currp)->cast<I31New>());
1005   }
doVisitI31GetWalker1006   static void doVisitI31Get(SubType* self, Expression** currp) {
1007     self->visitI31Get((*currp)->cast<I31Get>());
1008   }
doVisitRefTestWalker1009   static void doVisitRefTest(SubType* self, Expression** currp) {
1010     self->visitRefTest((*currp)->cast<RefTest>());
1011   }
doVisitRefCastWalker1012   static void doVisitRefCast(SubType* self, Expression** currp) {
1013     self->visitRefCast((*currp)->cast<RefCast>());
1014   }
doVisitBrOnCastWalker1015   static void doVisitBrOnCast(SubType* self, Expression** currp) {
1016     self->visitBrOnCast((*currp)->cast<BrOnCast>());
1017   }
doVisitRttCanonWalker1018   static void doVisitRttCanon(SubType* self, Expression** currp) {
1019     self->visitRttCanon((*currp)->cast<RttCanon>());
1020   }
doVisitRttSubWalker1021   static void doVisitRttSub(SubType* self, Expression** currp) {
1022     self->visitRttSub((*currp)->cast<RttSub>());
1023   }
doVisitStructNewWalker1024   static void doVisitStructNew(SubType* self, Expression** currp) {
1025     self->visitStructNew((*currp)->cast<StructNew>());
1026   }
doVisitStructGetWalker1027   static void doVisitStructGet(SubType* self, Expression** currp) {
1028     self->visitStructGet((*currp)->cast<StructGet>());
1029   }
doVisitStructSetWalker1030   static void doVisitStructSet(SubType* self, Expression** currp) {
1031     self->visitStructSet((*currp)->cast<StructSet>());
1032   }
doVisitArrayNewWalker1033   static void doVisitArrayNew(SubType* self, Expression** currp) {
1034     self->visitArrayNew((*currp)->cast<ArrayNew>());
1035   }
doVisitArrayGetWalker1036   static void doVisitArrayGet(SubType* self, Expression** currp) {
1037     self->visitArrayGet((*currp)->cast<ArrayGet>());
1038   }
doVisitArraySetWalker1039   static void doVisitArraySet(SubType* self, Expression** currp) {
1040     self->visitArraySet((*currp)->cast<ArraySet>());
1041   }
doVisitArrayLenWalker1042   static void doVisitArrayLen(SubType* self, Expression** currp) {
1043     self->visitArrayLen((*currp)->cast<ArrayLen>());
1044   }
1045 
setModuleWalker1046   void setModule(Module* module) { currModule = module; }
1047 
setFunctionWalker1048   void setFunction(Function* func) { currFunction = func; }
1049 
1050 private:
1051   // the address of the current node, used to replace it
1052   Expression** replacep = nullptr;
1053   SmallVector<Task, 10> stack;      // stack of tasks
1054   Function* currFunction = nullptr; // current function being processed
1055   Module* currModule = nullptr;     // current module being processed
1056 };
1057 
1058 // Walks in post-order, i.e., children first. When there isn't an obvious
1059 // order to operands, we follow them in order of execution.
1060 
1061 template<typename SubType, typename VisitorType = Visitor<SubType>>
1062 struct PostWalker : public Walker<SubType, VisitorType> {
1063 
scanPostWalker1064   static void scan(SubType* self, Expression** currp) {
1065     Expression* curr = *currp;
1066     switch (curr->_id) {
1067       case Expression::Id::InvalidId:
1068         abort();
1069       case Expression::Id::BlockId: {
1070         self->pushTask(SubType::doVisitBlock, currp);
1071         auto& list = curr->cast<Block>()->list;
1072         for (int i = int(list.size()) - 1; i >= 0; i--) {
1073           self->pushTask(SubType::scan, &list[i]);
1074         }
1075         break;
1076       }
1077       case Expression::Id::IfId: {
1078         self->pushTask(SubType::doVisitIf, currp);
1079         self->maybePushTask(SubType::scan, &curr->cast<If>()->ifFalse);
1080         self->pushTask(SubType::scan, &curr->cast<If>()->ifTrue);
1081         self->pushTask(SubType::scan, &curr->cast<If>()->condition);
1082         break;
1083       }
1084       case Expression::Id::LoopId: {
1085         self->pushTask(SubType::doVisitLoop, currp);
1086         self->pushTask(SubType::scan, &curr->cast<Loop>()->body);
1087         break;
1088       }
1089       case Expression::Id::BreakId: {
1090         self->pushTask(SubType::doVisitBreak, currp);
1091         self->maybePushTask(SubType::scan, &curr->cast<Break>()->condition);
1092         self->maybePushTask(SubType::scan, &curr->cast<Break>()->value);
1093         break;
1094       }
1095       case Expression::Id::SwitchId: {
1096         self->pushTask(SubType::doVisitSwitch, currp);
1097         self->pushTask(SubType::scan, &curr->cast<Switch>()->condition);
1098         self->maybePushTask(SubType::scan, &curr->cast<Switch>()->value);
1099         break;
1100       }
1101       case Expression::Id::CallId: {
1102         self->pushTask(SubType::doVisitCall, currp);
1103         auto& list = curr->cast<Call>()->operands;
1104         for (int i = int(list.size()) - 1; i >= 0; i--) {
1105           self->pushTask(SubType::scan, &list[i]);
1106         }
1107         break;
1108       }
1109       case Expression::Id::CallIndirectId: {
1110         self->pushTask(SubType::doVisitCallIndirect, currp);
1111         auto& list = curr->cast<CallIndirect>()->operands;
1112         self->pushTask(SubType::scan, &curr->cast<CallIndirect>()->target);
1113         for (int i = int(list.size()) - 1; i >= 0; i--) {
1114           self->pushTask(SubType::scan, &list[i]);
1115         }
1116         break;
1117       }
1118       case Expression::Id::LocalGetId: {
1119         // TODO: optimize leaves with a direct call?
1120         self->pushTask(SubType::doVisitLocalGet, currp);
1121         break;
1122       }
1123       case Expression::Id::LocalSetId: {
1124         self->pushTask(SubType::doVisitLocalSet, currp);
1125         self->pushTask(SubType::scan, &curr->cast<LocalSet>()->value);
1126         break;
1127       }
1128       case Expression::Id::GlobalGetId: {
1129         self->pushTask(SubType::doVisitGlobalGet, currp);
1130         break;
1131       }
1132       case Expression::Id::GlobalSetId: {
1133         self->pushTask(SubType::doVisitGlobalSet, currp);
1134         self->pushTask(SubType::scan, &curr->cast<GlobalSet>()->value);
1135         break;
1136       }
1137       case Expression::Id::LoadId: {
1138         self->pushTask(SubType::doVisitLoad, currp);
1139         self->pushTask(SubType::scan, &curr->cast<Load>()->ptr);
1140         break;
1141       }
1142       case Expression::Id::StoreId: {
1143         self->pushTask(SubType::doVisitStore, currp);
1144         self->pushTask(SubType::scan, &curr->cast<Store>()->value);
1145         self->pushTask(SubType::scan, &curr->cast<Store>()->ptr);
1146         break;
1147       }
1148       case Expression::Id::AtomicRMWId: {
1149         self->pushTask(SubType::doVisitAtomicRMW, currp);
1150         self->pushTask(SubType::scan, &curr->cast<AtomicRMW>()->value);
1151         self->pushTask(SubType::scan, &curr->cast<AtomicRMW>()->ptr);
1152         break;
1153       }
1154       case Expression::Id::AtomicCmpxchgId: {
1155         self->pushTask(SubType::doVisitAtomicCmpxchg, currp);
1156         self->pushTask(SubType::scan,
1157                        &curr->cast<AtomicCmpxchg>()->replacement);
1158         self->pushTask(SubType::scan, &curr->cast<AtomicCmpxchg>()->expected);
1159         self->pushTask(SubType::scan, &curr->cast<AtomicCmpxchg>()->ptr);
1160         break;
1161       }
1162       case Expression::Id::AtomicWaitId: {
1163         self->pushTask(SubType::doVisitAtomicWait, currp);
1164         self->pushTask(SubType::scan, &curr->cast<AtomicWait>()->timeout);
1165         self->pushTask(SubType::scan, &curr->cast<AtomicWait>()->expected);
1166         self->pushTask(SubType::scan, &curr->cast<AtomicWait>()->ptr);
1167         break;
1168       }
1169       case Expression::Id::AtomicNotifyId: {
1170         self->pushTask(SubType::doVisitAtomicNotify, currp);
1171         self->pushTask(SubType::scan, &curr->cast<AtomicNotify>()->notifyCount);
1172         self->pushTask(SubType::scan, &curr->cast<AtomicNotify>()->ptr);
1173         break;
1174       }
1175       case Expression::Id::AtomicFenceId: {
1176         self->pushTask(SubType::doVisitAtomicFence, currp);
1177         break;
1178       }
1179       case Expression::Id::SIMDExtractId: {
1180         self->pushTask(SubType::doVisitSIMDExtract, currp);
1181         self->pushTask(SubType::scan, &curr->cast<SIMDExtract>()->vec);
1182         break;
1183       }
1184       case Expression::Id::SIMDReplaceId: {
1185         self->pushTask(SubType::doVisitSIMDReplace, currp);
1186         self->pushTask(SubType::scan, &curr->cast<SIMDReplace>()->value);
1187         self->pushTask(SubType::scan, &curr->cast<SIMDReplace>()->vec);
1188         break;
1189       }
1190       case Expression::Id::SIMDShuffleId: {
1191         self->pushTask(SubType::doVisitSIMDShuffle, currp);
1192         self->pushTask(SubType::scan, &curr->cast<SIMDShuffle>()->right);
1193         self->pushTask(SubType::scan, &curr->cast<SIMDShuffle>()->left);
1194         break;
1195       }
1196       case Expression::Id::SIMDTernaryId: {
1197         self->pushTask(SubType::doVisitSIMDTernary, currp);
1198         self->pushTask(SubType::scan, &curr->cast<SIMDTernary>()->c);
1199         self->pushTask(SubType::scan, &curr->cast<SIMDTernary>()->b);
1200         self->pushTask(SubType::scan, &curr->cast<SIMDTernary>()->a);
1201         break;
1202       }
1203       case Expression::Id::SIMDShiftId: {
1204         self->pushTask(SubType::doVisitSIMDShift, currp);
1205         self->pushTask(SubType::scan, &curr->cast<SIMDShift>()->shift);
1206         self->pushTask(SubType::scan, &curr->cast<SIMDShift>()->vec);
1207         break;
1208       }
1209       case Expression::Id::SIMDLoadId: {
1210         self->pushTask(SubType::doVisitSIMDLoad, currp);
1211         self->pushTask(SubType::scan, &curr->cast<SIMDLoad>()->ptr);
1212         break;
1213       }
1214       case Expression::Id::MemoryInitId: {
1215         self->pushTask(SubType::doVisitMemoryInit, currp);
1216         self->pushTask(SubType::scan, &curr->cast<MemoryInit>()->size);
1217         self->pushTask(SubType::scan, &curr->cast<MemoryInit>()->offset);
1218         self->pushTask(SubType::scan, &curr->cast<MemoryInit>()->dest);
1219         break;
1220       }
1221       case Expression::Id::DataDropId: {
1222         self->pushTask(SubType::doVisitDataDrop, currp);
1223         break;
1224       }
1225       case Expression::Id::MemoryCopyId: {
1226         self->pushTask(SubType::doVisitMemoryCopy, currp);
1227         self->pushTask(SubType::scan, &curr->cast<MemoryCopy>()->size);
1228         self->pushTask(SubType::scan, &curr->cast<MemoryCopy>()->source);
1229         self->pushTask(SubType::scan, &curr->cast<MemoryCopy>()->dest);
1230         break;
1231       }
1232       case Expression::Id::MemoryFillId: {
1233         self->pushTask(SubType::doVisitMemoryFill, currp);
1234         self->pushTask(SubType::scan, &curr->cast<MemoryFill>()->size);
1235         self->pushTask(SubType::scan, &curr->cast<MemoryFill>()->value);
1236         self->pushTask(SubType::scan, &curr->cast<MemoryFill>()->dest);
1237         break;
1238       }
1239       case Expression::Id::ConstId: {
1240         self->pushTask(SubType::doVisitConst, currp);
1241         break;
1242       }
1243       case Expression::Id::UnaryId: {
1244         self->pushTask(SubType::doVisitUnary, currp);
1245         self->pushTask(SubType::scan, &curr->cast<Unary>()->value);
1246         break;
1247       }
1248       case Expression::Id::BinaryId: {
1249         self->pushTask(SubType::doVisitBinary, currp);
1250         self->pushTask(SubType::scan, &curr->cast<Binary>()->right);
1251         self->pushTask(SubType::scan, &curr->cast<Binary>()->left);
1252         break;
1253       }
1254       case Expression::Id::SelectId: {
1255         self->pushTask(SubType::doVisitSelect, currp);
1256         self->pushTask(SubType::scan, &curr->cast<Select>()->condition);
1257         self->pushTask(SubType::scan, &curr->cast<Select>()->ifFalse);
1258         self->pushTask(SubType::scan, &curr->cast<Select>()->ifTrue);
1259         break;
1260       }
1261       case Expression::Id::DropId: {
1262         self->pushTask(SubType::doVisitDrop, currp);
1263         self->pushTask(SubType::scan, &curr->cast<Drop>()->value);
1264         break;
1265       }
1266       case Expression::Id::ReturnId: {
1267         self->pushTask(SubType::doVisitReturn, currp);
1268         self->maybePushTask(SubType::scan, &curr->cast<Return>()->value);
1269         break;
1270       }
1271       case Expression::Id::MemorySizeId:
1272         self->pushTask(SubType::doVisitMemorySize, currp);
1273         break;
1274       case Expression::Id::MemoryGrowId:
1275         self->pushTask(SubType::doVisitMemoryGrow, currp);
1276         self->pushTask(SubType::scan, &curr->cast<MemoryGrow>()->delta);
1277         break;
1278       case Expression::Id::RefNullId: {
1279         self->pushTask(SubType::doVisitRefNull, currp);
1280         break;
1281       }
1282       case Expression::Id::RefIsNullId: {
1283         self->pushTask(SubType::doVisitRefIsNull, currp);
1284         self->pushTask(SubType::scan, &curr->cast<RefIsNull>()->value);
1285         break;
1286       }
1287       case Expression::Id::RefFuncId: {
1288         self->pushTask(SubType::doVisitRefFunc, currp);
1289         break;
1290       }
1291       case Expression::Id::RefEqId: {
1292         self->pushTask(SubType::doVisitRefEq, currp);
1293         self->pushTask(SubType::scan, &curr->cast<RefEq>()->right);
1294         self->pushTask(SubType::scan, &curr->cast<RefEq>()->left);
1295         break;
1296       }
1297       case Expression::Id::TryId: {
1298         self->pushTask(SubType::doVisitTry, currp);
1299         self->pushTask(SubType::scan, &curr->cast<Try>()->catchBody);
1300         self->pushTask(SubType::scan, &curr->cast<Try>()->body);
1301         break;
1302       }
1303       case Expression::Id::ThrowId: {
1304         self->pushTask(SubType::doVisitThrow, currp);
1305         auto& list = curr->cast<Throw>()->operands;
1306         for (int i = int(list.size()) - 1; i >= 0; i--) {
1307           self->pushTask(SubType::scan, &list[i]);
1308         }
1309         break;
1310       }
1311       case Expression::Id::RethrowId: {
1312         self->pushTask(SubType::doVisitRethrow, currp);
1313         self->pushTask(SubType::scan, &curr->cast<Rethrow>()->exnref);
1314         break;
1315       }
1316       case Expression::Id::BrOnExnId: {
1317         self->pushTask(SubType::doVisitBrOnExn, currp);
1318         self->pushTask(SubType::scan, &curr->cast<BrOnExn>()->exnref);
1319         break;
1320       }
1321       case Expression::Id::NopId: {
1322         self->pushTask(SubType::doVisitNop, currp);
1323         break;
1324       }
1325       case Expression::Id::UnreachableId: {
1326         self->pushTask(SubType::doVisitUnreachable, currp);
1327         break;
1328       }
1329       case Expression::Id::PopId: {
1330         self->pushTask(SubType::doVisitPop, currp);
1331         break;
1332       }
1333       case Expression::Id::TupleMakeId: {
1334         self->pushTask(SubType::doVisitTupleMake, currp);
1335         auto& operands = curr->cast<TupleMake>()->operands;
1336         for (int i = int(operands.size()) - 1; i >= 0; --i) {
1337           self->pushTask(SubType::scan, &operands[i]);
1338         }
1339         break;
1340       }
1341       case Expression::Id::TupleExtractId: {
1342         self->pushTask(SubType::doVisitTupleExtract, currp);
1343         self->pushTask(SubType::scan, &curr->cast<TupleExtract>()->tuple);
1344         break;
1345       }
1346       case Expression::Id::I31NewId: {
1347         self->pushTask(SubType::doVisitI31New, currp);
1348         self->pushTask(SubType::scan, &curr->cast<I31New>()->value);
1349         break;
1350       }
1351       case Expression::Id::I31GetId: {
1352         self->pushTask(SubType::doVisitI31Get, currp);
1353         self->pushTask(SubType::scan, &curr->cast<I31Get>()->i31);
1354         break;
1355       }
1356       case Expression::Id::RefTestId:
1357         self->pushTask(SubType::doVisitRefTest, currp);
1358         WASM_UNREACHABLE("TODO (gc): ref.test");
1359         break;
1360       case Expression::Id::RefCastId:
1361         self->pushTask(SubType::doVisitRefCast, currp);
1362         WASM_UNREACHABLE("TODO (gc): ref.cast");
1363         break;
1364       case Expression::Id::BrOnCastId:
1365         self->pushTask(SubType::doVisitBrOnCast, currp);
1366         WASM_UNREACHABLE("TODO (gc): br_on_cast");
1367         break;
1368       case Expression::Id::RttCanonId:
1369         self->pushTask(SubType::doVisitRttCanon, currp);
1370         WASM_UNREACHABLE("TODO (gc): rtt.canon");
1371         break;
1372       case Expression::Id::RttSubId:
1373         self->pushTask(SubType::doVisitRttSub, currp);
1374         WASM_UNREACHABLE("TODO (gc): rtt.sub");
1375         break;
1376       case Expression::Id::StructNewId:
1377         self->pushTask(SubType::doVisitStructNew, currp);
1378         WASM_UNREACHABLE("TODO (gc): struct.new");
1379         break;
1380       case Expression::Id::StructGetId:
1381         self->pushTask(SubType::doVisitStructGet, currp);
1382         WASM_UNREACHABLE("TODO (gc): struct.get");
1383         break;
1384       case Expression::Id::StructSetId:
1385         self->pushTask(SubType::doVisitStructSet, currp);
1386         WASM_UNREACHABLE("TODO (gc): struct.set");
1387         break;
1388       case Expression::Id::ArrayNewId:
1389         self->pushTask(SubType::doVisitArrayNew, currp);
1390         WASM_UNREACHABLE("TODO (gc): array.new");
1391         break;
1392       case Expression::Id::ArrayGetId:
1393         self->pushTask(SubType::doVisitArrayGet, currp);
1394         WASM_UNREACHABLE("TODO (gc): array.get");
1395         break;
1396       case Expression::Id::ArraySetId:
1397         self->pushTask(SubType::doVisitArraySet, currp);
1398         WASM_UNREACHABLE("TODO (gc): array.set");
1399         break;
1400       case Expression::Id::ArrayLenId:
1401         self->pushTask(SubType::doVisitArrayLen, currp);
1402         WASM_UNREACHABLE("TODO (gc): array.len");
1403         break;
1404       case Expression::Id::NumExpressionIds:
1405         WASM_UNREACHABLE("unexpected expression type");
1406     }
1407   }
1408 };
1409 
1410 // Stacks of expressions tend to be limited in size (although, sometimes
1411 // super-nested blocks exist for br_table).
1412 typedef SmallVector<Expression*, 10> ExpressionStack;
1413 
1414 // Traversal with a control-flow stack.
1415 
1416 template<typename SubType, typename VisitorType = Visitor<SubType>>
1417 struct ControlFlowWalker : public PostWalker<SubType, VisitorType> {
1418   ControlFlowWalker() = default;
1419 
1420   ExpressionStack controlFlowStack; // contains blocks, loops, and ifs
1421 
1422   // Uses the control flow stack to find the target of a break to a name
findBreakTargetControlFlowWalker1423   Expression* findBreakTarget(Name name) {
1424     assert(!controlFlowStack.empty());
1425     Index i = controlFlowStack.size() - 1;
1426     while (true) {
1427       auto* curr = controlFlowStack[i];
1428       if (Block* block = curr->template dynCast<Block>()) {
1429         if (name == block->name) {
1430           return curr;
1431         }
1432       } else if (Loop* loop = curr->template dynCast<Loop>()) {
1433         if (name == loop->name) {
1434           return curr;
1435         }
1436       } else {
1437         // an if or try, ignorable
1438         assert(curr->template is<If>() || curr->template is<Try>());
1439       }
1440       if (i == 0) {
1441         return nullptr;
1442       }
1443       i--;
1444     }
1445   }
1446 
doPreVisitControlFlowControlFlowWalker1447   static void doPreVisitControlFlow(SubType* self, Expression** currp) {
1448     self->controlFlowStack.push_back(*currp);
1449   }
1450 
doPostVisitControlFlowControlFlowWalker1451   static void doPostVisitControlFlow(SubType* self, Expression** currp) {
1452     // note that we might be popping something else, as we may have been
1453     // replaced
1454     self->controlFlowStack.pop_back();
1455   }
1456 
scanControlFlowWalker1457   static void scan(SubType* self, Expression** currp) {
1458     auto* curr = *currp;
1459 
1460     switch (curr->_id) {
1461       case Expression::Id::BlockId:
1462       case Expression::Id::IfId:
1463       case Expression::Id::LoopId:
1464       case Expression::Id::TryId: {
1465         self->pushTask(SubType::doPostVisitControlFlow, currp);
1466         break;
1467       }
1468       default: {
1469       }
1470     }
1471 
1472     PostWalker<SubType, VisitorType>::scan(self, currp);
1473 
1474     switch (curr->_id) {
1475       case Expression::Id::BlockId:
1476       case Expression::Id::IfId:
1477       case Expression::Id::LoopId:
1478       case Expression::Id::TryId: {
1479         self->pushTask(SubType::doPreVisitControlFlow, currp);
1480         break;
1481       }
1482       default: {
1483       }
1484     }
1485   }
1486 };
1487 
1488 // Traversal with an expression stack.
1489 
1490 template<typename SubType, typename VisitorType = Visitor<SubType>>
1491 struct ExpressionStackWalker : public PostWalker<SubType, VisitorType> {
1492   ExpressionStackWalker() = default;
1493 
1494   ExpressionStack expressionStack;
1495 
1496   // Uses the control flow stack to find the target of a break to a name
findBreakTargetExpressionStackWalker1497   Expression* findBreakTarget(Name name) {
1498     assert(!expressionStack.empty());
1499     Index i = expressionStack.size() - 1;
1500     while (true) {
1501       auto* curr = expressionStack[i];
1502       if (Block* block = curr->template dynCast<Block>()) {
1503         if (name == block->name) {
1504           return curr;
1505         }
1506       } else if (Loop* loop = curr->template dynCast<Loop>()) {
1507         if (name == loop->name) {
1508           return curr;
1509         }
1510       }
1511       if (i == 0) {
1512         return nullptr;
1513       }
1514       i--;
1515     }
1516   }
1517 
getParentExpressionStackWalker1518   Expression* getParent() {
1519     if (expressionStack.size() == 1) {
1520       return nullptr;
1521     }
1522     assert(expressionStack.size() >= 2);
1523     return expressionStack[expressionStack.size() - 2];
1524   }
1525 
doPreVisitExpressionStackWalker1526   static void doPreVisit(SubType* self, Expression** currp) {
1527     self->expressionStack.push_back(*currp);
1528   }
1529 
doPostVisitExpressionStackWalker1530   static void doPostVisit(SubType* self, Expression** currp) {
1531     self->expressionStack.pop_back();
1532   }
1533 
scanExpressionStackWalker1534   static void scan(SubType* self, Expression** currp) {
1535     self->pushTask(SubType::doPostVisit, currp);
1536 
1537     PostWalker<SubType, VisitorType>::scan(self, currp);
1538 
1539     self->pushTask(SubType::doPreVisit, currp);
1540   }
1541 
replaceCurrentExpressionStackWalker1542   Expression* replaceCurrent(Expression* expression) {
1543     PostWalker<SubType, VisitorType>::replaceCurrent(expression);
1544     // also update the stack
1545     expressionStack.back() = expression;
1546     return expression;
1547   }
1548 };
1549 
1550 // Traversal in the order of execution. This is quick and simple, but
1551 // does not provide the same comprehensive information that a full
1552 // conversion to basic blocks would. What it does give is a quick
1553 // way to view straightline execution traces, i.e., that have no
1554 // branching. This can let optimizations get most of what they
1555 // want without the cost of creating another AST.
1556 //
1557 // When execution is no longer linear, this notifies via a call
1558 // to noteNonLinear().
1559 
1560 template<typename SubType, typename VisitorType = Visitor<SubType>>
1561 struct LinearExecutionWalker : public PostWalker<SubType, VisitorType> {
1562   LinearExecutionWalker() = default;
1563 
1564   // subclasses should implement this
noteNonLinearLinearExecutionWalker1565   void noteNonLinear(Expression* curr) { abort(); }
1566 
doNoteNonLinearLinearExecutionWalker1567   static void doNoteNonLinear(SubType* self, Expression** currp) {
1568     self->noteNonLinear(*currp);
1569   }
1570 
scanLinearExecutionWalker1571   static void scan(SubType* self, Expression** currp) {
1572 
1573     Expression* curr = *currp;
1574 
1575     switch (curr->_id) {
1576       case Expression::Id::InvalidId:
1577         abort();
1578       case Expression::Id::BlockId: {
1579         self->pushTask(SubType::doVisitBlock, currp);
1580         if (curr->cast<Block>()->name.is()) {
1581           self->pushTask(SubType::doNoteNonLinear, currp);
1582         }
1583         auto& list = curr->cast<Block>()->list;
1584         for (int i = int(list.size()) - 1; i >= 0; i--) {
1585           self->pushTask(SubType::scan, &list[i]);
1586         }
1587         break;
1588       }
1589       case Expression::Id::IfId: {
1590         self->pushTask(SubType::doVisitIf, currp);
1591         self->pushTask(SubType::doNoteNonLinear, currp);
1592         self->maybePushTask(SubType::scan, &curr->cast<If>()->ifFalse);
1593         self->pushTask(SubType::doNoteNonLinear, currp);
1594         self->pushTask(SubType::scan, &curr->cast<If>()->ifTrue);
1595         self->pushTask(SubType::doNoteNonLinear, currp);
1596         self->pushTask(SubType::scan, &curr->cast<If>()->condition);
1597         break;
1598       }
1599       case Expression::Id::LoopId: {
1600         self->pushTask(SubType::doVisitLoop, currp);
1601         self->pushTask(SubType::scan, &curr->cast<Loop>()->body);
1602         self->pushTask(SubType::doNoteNonLinear, currp);
1603         break;
1604       }
1605       case Expression::Id::BreakId: {
1606         self->pushTask(SubType::doVisitBreak, currp);
1607         self->pushTask(SubType::doNoteNonLinear, currp);
1608         self->maybePushTask(SubType::scan, &curr->cast<Break>()->condition);
1609         self->maybePushTask(SubType::scan, &curr->cast<Break>()->value);
1610         break;
1611       }
1612       case Expression::Id::SwitchId: {
1613         self->pushTask(SubType::doVisitSwitch, currp);
1614         self->pushTask(SubType::doNoteNonLinear, currp);
1615         self->maybePushTask(SubType::scan, &curr->cast<Switch>()->value);
1616         self->pushTask(SubType::scan, &curr->cast<Switch>()->condition);
1617         break;
1618       }
1619       case Expression::Id::ReturnId: {
1620         self->pushTask(SubType::doVisitReturn, currp);
1621         self->pushTask(SubType::doNoteNonLinear, currp);
1622         self->maybePushTask(SubType::scan, &curr->cast<Return>()->value);
1623         break;
1624       }
1625       case Expression::Id::TryId: {
1626         self->pushTask(SubType::doVisitTry, currp);
1627         self->pushTask(SubType::doNoteNonLinear, currp);
1628         self->pushTask(SubType::scan, &curr->cast<Try>()->catchBody);
1629         self->pushTask(SubType::doNoteNonLinear, currp);
1630         self->pushTask(SubType::scan, &curr->cast<Try>()->body);
1631         break;
1632       }
1633       case Expression::Id::ThrowId: {
1634         self->pushTask(SubType::doVisitThrow, currp);
1635         self->pushTask(SubType::doNoteNonLinear, currp);
1636         auto& list = curr->cast<Throw>()->operands;
1637         for (int i = int(list.size()) - 1; i >= 0; i--) {
1638           self->pushTask(SubType::scan, &list[i]);
1639         }
1640         break;
1641       }
1642       case Expression::Id::RethrowId: {
1643         self->pushTask(SubType::doVisitRethrow, currp);
1644         self->pushTask(SubType::doNoteNonLinear, currp);
1645         self->pushTask(SubType::scan, &curr->cast<Rethrow>()->exnref);
1646         break;
1647       }
1648       case Expression::Id::BrOnExnId: {
1649         self->pushTask(SubType::doVisitBrOnExn, currp);
1650         self->pushTask(SubType::doNoteNonLinear, currp);
1651         self->pushTask(SubType::scan, &curr->cast<BrOnExn>()->exnref);
1652         break;
1653       }
1654       case Expression::Id::UnreachableId: {
1655         self->pushTask(SubType::doVisitUnreachable, currp);
1656         self->pushTask(SubType::doNoteNonLinear, currp);
1657         break;
1658       }
1659       default: {
1660         // other node types do not have control flow, use regular post-order
1661         PostWalker<SubType, VisitorType>::scan(self, currp);
1662       }
1663     }
1664   }
1665 };
1666 
1667 } // namespace wasm
1668 
1669 #endif // wasm_wasm_traversal_h
1670