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