From 395b071ae9b09f0b4fe3ce0f3a43f16ba74f01a5 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Mon, 28 Jun 2021 14:25:40 -0700 Subject: Refactor LinearExecutionWalker to a separate file. NFC (#3956) --- src/ir/linear-execution.h | 139 +++++++++++++++++++++++++++++++++++++++++ src/passes/Asyncify.cpp | 1 + src/passes/LocalCSE.cpp | 1 + src/passes/SimplifyGlobals.cpp | 1 + src/passes/SimplifyLocals.cpp | 1 + src/wasm-traversal.h | 113 --------------------------------- 6 files changed, 143 insertions(+), 113 deletions(-) create mode 100644 src/ir/linear-execution.h (limited to 'src') diff --git a/src/ir/linear-execution.h b/src/ir/linear-execution.h new file mode 100644 index 000000000..b1d0b96c3 --- /dev/null +++ b/src/ir/linear-execution.h @@ -0,0 +1,139 @@ +/* + * Copyright 2021 WebAssembly Community Group participants + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef wasm_ir_linear_execution_h +#define wasm_ir_linear_execution_h + +#include +#include + +namespace wasm { + +// Traversal in the order of execution. This is quick and simple, but +// does not provide the same comprehensive information that a full +// conversion to basic blocks would. What it does give is a quick +// way to view straightline execution traces, i.e., that have no +// branching. This can let optimizations get most of what they +// want without the cost of creating another AST. +// +// When execution is no longer linear, this notifies via a call +// to noteNonLinear(). + +template> +struct LinearExecutionWalker : public PostWalker { + LinearExecutionWalker() = default; + + // subclasses should implement this + void noteNonLinear(Expression* curr) { abort(); } + + static void doNoteNonLinear(SubType* self, Expression** currp) { + self->noteNonLinear(*currp); + } + + static void scan(SubType* self, Expression** currp) { + Expression* curr = *currp; + + switch (curr->_id) { + case Expression::Id::InvalidId: + abort(); + case Expression::Id::BlockId: { + self->pushTask(SubType::doVisitBlock, currp); + if (curr->cast()->name.is()) { + self->pushTask(SubType::doNoteNonLinear, currp); + } + auto& list = curr->cast()->list; + for (int i = int(list.size()) - 1; i >= 0; i--) { + self->pushTask(SubType::scan, &list[i]); + } + break; + } + case Expression::Id::IfId: { + self->pushTask(SubType::doVisitIf, currp); + self->pushTask(SubType::doNoteNonLinear, currp); + self->maybePushTask(SubType::scan, &curr->cast()->ifFalse); + self->pushTask(SubType::doNoteNonLinear, currp); + self->pushTask(SubType::scan, &curr->cast()->ifTrue); + self->pushTask(SubType::doNoteNonLinear, currp); + self->pushTask(SubType::scan, &curr->cast()->condition); + break; + } + case Expression::Id::LoopId: { + self->pushTask(SubType::doVisitLoop, currp); + self->pushTask(SubType::scan, &curr->cast()->body); + self->pushTask(SubType::doNoteNonLinear, currp); + break; + } + case Expression::Id::BreakId: { + self->pushTask(SubType::doVisitBreak, currp); + self->pushTask(SubType::doNoteNonLinear, currp); + self->maybePushTask(SubType::scan, &curr->cast()->condition); + self->maybePushTask(SubType::scan, &curr->cast()->value); + break; + } + case Expression::Id::SwitchId: { + self->pushTask(SubType::doVisitSwitch, currp); + self->pushTask(SubType::doNoteNonLinear, currp); + self->maybePushTask(SubType::scan, &curr->cast()->value); + self->pushTask(SubType::scan, &curr->cast()->condition); + break; + } + case Expression::Id::ReturnId: { + self->pushTask(SubType::doVisitReturn, currp); + self->pushTask(SubType::doNoteNonLinear, currp); + self->maybePushTask(SubType::scan, &curr->cast()->value); + break; + } + case Expression::Id::TryId: { + self->pushTask(SubType::doVisitTry, currp); + self->pushTask(SubType::doNoteNonLinear, currp); + auto& list = curr->cast()->catchBodies; + for (int i = int(list.size()) - 1; i >= 0; i--) { + self->pushTask(SubType::scan, &list[i]); + self->pushTask(SubType::doNoteNonLinear, currp); + } + self->pushTask(SubType::scan, &curr->cast()->body); + break; + } + case Expression::Id::ThrowId: { + self->pushTask(SubType::doVisitThrow, currp); + self->pushTask(SubType::doNoteNonLinear, currp); + auto& list = curr->cast()->operands; + for (int i = int(list.size()) - 1; i >= 0; i--) { + self->pushTask(SubType::scan, &list[i]); + } + break; + } + case Expression::Id::RethrowId: { + self->pushTask(SubType::doVisitRethrow, currp); + self->pushTask(SubType::doNoteNonLinear, currp); + break; + } + case Expression::Id::UnreachableId: { + self->pushTask(SubType::doVisitUnreachable, currp); + self->pushTask(SubType::doNoteNonLinear, currp); + break; + } + default: { + // other node types do not have control flow, use regular post-order + PostWalker::scan(self, currp); + } + } + } +}; + +} // namespace wasm + +#endif // wasm_ir_linear_execution_h diff --git a/src/passes/Asyncify.cpp b/src/passes/Asyncify.cpp index 7ad3fab5d..4bd9dee61 100644 --- a/src/passes/Asyncify.cpp +++ b/src/passes/Asyncify.cpp @@ -299,6 +299,7 @@ #include "cfg/liveness-traversal.h" #include "ir/effects.h" #include "ir/find_all.h" +#include "ir/linear-execution.h" #include "ir/literal-utils.h" #include "ir/memory-utils.h" #include "ir/module-utils.h" diff --git a/src/passes/LocalCSE.cpp b/src/passes/LocalCSE.cpp index 7435687ae..7e6d9cb41 100644 --- a/src/passes/LocalCSE.cpp +++ b/src/passes/LocalCSE.cpp @@ -42,6 +42,7 @@ #include #include #include +#include #include #include #include diff --git a/src/passes/SimplifyGlobals.cpp b/src/passes/SimplifyGlobals.cpp index 361e0bb61..243e9a0d6 100644 --- a/src/passes/SimplifyGlobals.cpp +++ b/src/passes/SimplifyGlobals.cpp @@ -37,6 +37,7 @@ #include #include "ir/effects.h" +#include "ir/linear-execution.h" #include "ir/properties.h" #include "ir/utils.h" #include "pass.h" diff --git a/src/passes/SimplifyLocals.cpp b/src/passes/SimplifyLocals.cpp index 0649b39c4..02be1ceec 100644 --- a/src/passes/SimplifyLocals.cpp +++ b/src/passes/SimplifyLocals.cpp @@ -50,6 +50,7 @@ #include #include #include +#include #include #include #include diff --git a/src/wasm-traversal.h b/src/wasm-traversal.h index 5678d2f77..d3e2a19da 100644 --- a/src/wasm-traversal.h +++ b/src/wasm-traversal.h @@ -519,119 +519,6 @@ struct ExpressionStackWalker : public PostWalker { } }; -// Traversal in the order of execution. This is quick and simple, but -// does not provide the same comprehensive information that a full -// conversion to basic blocks would. What it does give is a quick -// way to view straightline execution traces, i.e., that have no -// branching. This can let optimizations get most of what they -// want without the cost of creating another AST. -// -// When execution is no longer linear, this notifies via a call -// to noteNonLinear(). - -template> -struct LinearExecutionWalker : public PostWalker { - LinearExecutionWalker() = default; - - // subclasses should implement this - void noteNonLinear(Expression* curr) { abort(); } - - static void doNoteNonLinear(SubType* self, Expression** currp) { - self->noteNonLinear(*currp); - } - - static void scan(SubType* self, Expression** currp) { - - Expression* curr = *currp; - - switch (curr->_id) { - case Expression::Id::InvalidId: - abort(); - case Expression::Id::BlockId: { - self->pushTask(SubType::doVisitBlock, currp); - if (curr->cast()->name.is()) { - self->pushTask(SubType::doNoteNonLinear, currp); - } - auto& list = curr->cast()->list; - for (int i = int(list.size()) - 1; i >= 0; i--) { - self->pushTask(SubType::scan, &list[i]); - } - break; - } - case Expression::Id::IfId: { - self->pushTask(SubType::doVisitIf, currp); - self->pushTask(SubType::doNoteNonLinear, currp); - self->maybePushTask(SubType::scan, &curr->cast()->ifFalse); - self->pushTask(SubType::doNoteNonLinear, currp); - self->pushTask(SubType::scan, &curr->cast()->ifTrue); - self->pushTask(SubType::doNoteNonLinear, currp); - self->pushTask(SubType::scan, &curr->cast()->condition); - break; - } - case Expression::Id::LoopId: { - self->pushTask(SubType::doVisitLoop, currp); - self->pushTask(SubType::scan, &curr->cast()->body); - self->pushTask(SubType::doNoteNonLinear, currp); - break; - } - case Expression::Id::BreakId: { - self->pushTask(SubType::doVisitBreak, currp); - self->pushTask(SubType::doNoteNonLinear, currp); - self->maybePushTask(SubType::scan, &curr->cast()->condition); - self->maybePushTask(SubType::scan, &curr->cast()->value); - break; - } - case Expression::Id::SwitchId: { - self->pushTask(SubType::doVisitSwitch, currp); - self->pushTask(SubType::doNoteNonLinear, currp); - self->maybePushTask(SubType::scan, &curr->cast()->value); - self->pushTask(SubType::scan, &curr->cast()->condition); - break; - } - case Expression::Id::ReturnId: { - self->pushTask(SubType::doVisitReturn, currp); - self->pushTask(SubType::doNoteNonLinear, currp); - self->maybePushTask(SubType::scan, &curr->cast()->value); - break; - } - case Expression::Id::TryId: { - self->pushTask(SubType::doVisitTry, currp); - self->pushTask(SubType::doNoteNonLinear, currp); - auto& list = curr->cast()->catchBodies; - for (int i = int(list.size()) - 1; i >= 0; i--) { - self->pushTask(SubType::scan, &list[i]); - self->pushTask(SubType::doNoteNonLinear, currp); - } - self->pushTask(SubType::scan, &curr->cast()->body); - break; - } - case Expression::Id::ThrowId: { - self->pushTask(SubType::doVisitThrow, currp); - self->pushTask(SubType::doNoteNonLinear, currp); - auto& list = curr->cast()->operands; - for (int i = int(list.size()) - 1; i >= 0; i--) { - self->pushTask(SubType::scan, &list[i]); - } - break; - } - case Expression::Id::RethrowId: { - self->pushTask(SubType::doVisitRethrow, currp); - self->pushTask(SubType::doNoteNonLinear, currp); - break; - } - case Expression::Id::UnreachableId: { - self->pushTask(SubType::doVisitUnreachable, currp); - self->pushTask(SubType::doNoteNonLinear, currp); - break; - } - default: { - // other node types do not have control flow, use regular post-order - PostWalker::scan(self, currp); - } - } - } -}; - } // namespace wasm #endif // wasm_wasm_traversal_h -- cgit v1.2.3