summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/ir/linear-execution.h139
-rw-r--r--src/passes/Asyncify.cpp1
-rw-r--r--src/passes/LocalCSE.cpp1
-rw-r--r--src/passes/SimplifyGlobals.cpp1
-rw-r--r--src/passes/SimplifyLocals.cpp1
-rw-r--r--src/wasm-traversal.h113
6 files changed, 143 insertions, 113 deletions
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 <wasm-traversal.h>
+#include <wasm.h>
+
+namespace wasm {
+
+// Traversal in the order of execution. This is quick and simple, but
+// does not provide the same comprehensive information that a full
+// conversion to basic blocks would. What it does give is a quick
+// way to view straightline execution traces, i.e., that have no
+// branching. This can let optimizations get most of what they
+// want without the cost of creating another AST.
+//
+// When execution is no longer linear, this notifies via a call
+// to noteNonLinear().
+
+template<typename SubType, typename VisitorType = Visitor<SubType>>
+struct LinearExecutionWalker : public PostWalker<SubType, VisitorType> {
+ LinearExecutionWalker() = default;
+
+ // subclasses should implement this
+ void noteNonLinear(Expression* curr) { abort(); }
+
+ static void doNoteNonLinear(SubType* self, Expression** currp) {
+ self->noteNonLinear(*currp);
+ }
+
+ 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<Block>()->name.is()) {
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ }
+ auto& list = curr->cast<Block>()->list;
+ for (int i = int(list.size()) - 1; i >= 0; i--) {
+ self->pushTask(SubType::scan, &list[i]);
+ }
+ break;
+ }
+ case Expression::Id::IfId: {
+ self->pushTask(SubType::doVisitIf, currp);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ self->maybePushTask(SubType::scan, &curr->cast<If>()->ifFalse);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ self->pushTask(SubType::scan, &curr->cast<If>()->ifTrue);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ self->pushTask(SubType::scan, &curr->cast<If>()->condition);
+ break;
+ }
+ case Expression::Id::LoopId: {
+ self->pushTask(SubType::doVisitLoop, currp);
+ self->pushTask(SubType::scan, &curr->cast<Loop>()->body);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ break;
+ }
+ case Expression::Id::BreakId: {
+ self->pushTask(SubType::doVisitBreak, currp);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ self->maybePushTask(SubType::scan, &curr->cast<Break>()->condition);
+ self->maybePushTask(SubType::scan, &curr->cast<Break>()->value);
+ break;
+ }
+ case Expression::Id::SwitchId: {
+ self->pushTask(SubType::doVisitSwitch, currp);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ self->maybePushTask(SubType::scan, &curr->cast<Switch>()->value);
+ self->pushTask(SubType::scan, &curr->cast<Switch>()->condition);
+ break;
+ }
+ case Expression::Id::ReturnId: {
+ self->pushTask(SubType::doVisitReturn, currp);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ self->maybePushTask(SubType::scan, &curr->cast<Return>()->value);
+ break;
+ }
+ case Expression::Id::TryId: {
+ self->pushTask(SubType::doVisitTry, currp);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ auto& list = curr->cast<Try>()->catchBodies;
+ for (int i = int(list.size()) - 1; i >= 0; i--) {
+ self->pushTask(SubType::scan, &list[i]);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ }
+ self->pushTask(SubType::scan, &curr->cast<Try>()->body);
+ break;
+ }
+ case Expression::Id::ThrowId: {
+ self->pushTask(SubType::doVisitThrow, currp);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ auto& list = curr->cast<Throw>()->operands;
+ for (int i = int(list.size()) - 1; i >= 0; i--) {
+ self->pushTask(SubType::scan, &list[i]);
+ }
+ break;
+ }
+ case Expression::Id::RethrowId: {
+ self->pushTask(SubType::doVisitRethrow, currp);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ break;
+ }
+ case Expression::Id::UnreachableId: {
+ self->pushTask(SubType::doVisitUnreachable, currp);
+ self->pushTask(SubType::doNoteNonLinear, currp);
+ break;
+ }
+ default: {
+ // other node types do not have control flow, use regular post-order
+ PostWalker<SubType, VisitorType>::scan(self, currp);
+ }
+ }
+ }
+};
+
+} // namespace wasm
+
+#endif // wasm_ir_linear_execution_h
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 <ir/effects.h>
#include <ir/equivalent_sets.h>
#include <ir/hashed.h>
+#include <ir/linear-execution.h>
#include <pass.h>
#include <wasm-builder.h>
#include <wasm-traversal.h>
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 <atomic>
#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 <ir/branch-utils.h>
#include <ir/effects.h>
#include <ir/find_all.h>
+#include <ir/linear-execution.h>
#include <ir/local-utils.h>
#include <ir/manipulation.h>
#include <pass.h>
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<SubType, VisitorType> {
}
};
-// Traversal in the order of execution. This is quick and simple, but
-// does not provide the same comprehensive information that a full
-// conversion to basic blocks would. What it does give is a quick
-// way to view straightline execution traces, i.e., that have no
-// branching. This can let optimizations get most of what they
-// want without the cost of creating another AST.
-//
-// When execution is no longer linear, this notifies via a call
-// to noteNonLinear().
-
-template<typename SubType, typename VisitorType = Visitor<SubType>>
-struct LinearExecutionWalker : public PostWalker<SubType, VisitorType> {
- LinearExecutionWalker() = default;
-
- // subclasses should implement this
- void noteNonLinear(Expression* curr) { abort(); }
-
- static void doNoteNonLinear(SubType* self, Expression** currp) {
- self->noteNonLinear(*currp);
- }
-
- 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<Block>()->name.is()) {
- self->pushTask(SubType::doNoteNonLinear, currp);
- }
- auto& list = curr->cast<Block>()->list;
- for (int i = int(list.size()) - 1; i >= 0; i--) {
- self->pushTask(SubType::scan, &list[i]);
- }
- break;
- }
- case Expression::Id::IfId: {
- self->pushTask(SubType::doVisitIf, currp);
- self->pushTask(SubType::doNoteNonLinear, currp);
- self->maybePushTask(SubType::scan, &curr->cast<If>()->ifFalse);
- self->pushTask(SubType::doNoteNonLinear, currp);
- self->pushTask(SubType::scan, &curr->cast<If>()->ifTrue);
- self->pushTask(SubType::doNoteNonLinear, currp);
- self->pushTask(SubType::scan, &curr->cast<If>()->condition);
- break;
- }
- case Expression::Id::LoopId: {
- self->pushTask(SubType::doVisitLoop, currp);
- self->pushTask(SubType::scan, &curr->cast<Loop>()->body);
- self->pushTask(SubType::doNoteNonLinear, currp);
- break;
- }
- case Expression::Id::BreakId: {
- self->pushTask(SubType::doVisitBreak, currp);
- self->pushTask(SubType::doNoteNonLinear, currp);
- self->maybePushTask(SubType::scan, &curr->cast<Break>()->condition);
- self->maybePushTask(SubType::scan, &curr->cast<Break>()->value);
- break;
- }
- case Expression::Id::SwitchId: {
- self->pushTask(SubType::doVisitSwitch, currp);
- self->pushTask(SubType::doNoteNonLinear, currp);
- self->maybePushTask(SubType::scan, &curr->cast<Switch>()->value);
- self->pushTask(SubType::scan, &curr->cast<Switch>()->condition);
- break;
- }
- case Expression::Id::ReturnId: {
- self->pushTask(SubType::doVisitReturn, currp);
- self->pushTask(SubType::doNoteNonLinear, currp);
- self->maybePushTask(SubType::scan, &curr->cast<Return>()->value);
- break;
- }
- case Expression::Id::TryId: {
- self->pushTask(SubType::doVisitTry, currp);
- self->pushTask(SubType::doNoteNonLinear, currp);
- auto& list = curr->cast<Try>()->catchBodies;
- for (int i = int(list.size()) - 1; i >= 0; i--) {
- self->pushTask(SubType::scan, &list[i]);
- self->pushTask(SubType::doNoteNonLinear, currp);
- }
- self->pushTask(SubType::scan, &curr->cast<Try>()->body);
- break;
- }
- case Expression::Id::ThrowId: {
- self->pushTask(SubType::doVisitThrow, currp);
- self->pushTask(SubType::doNoteNonLinear, currp);
- auto& list = curr->cast<Throw>()->operands;
- for (int i = int(list.size()) - 1; i >= 0; i--) {
- self->pushTask(SubType::scan, &list[i]);
- }
- break;
- }
- case Expression::Id::RethrowId: {
- self->pushTask(SubType::doVisitRethrow, currp);
- self->pushTask(SubType::doNoteNonLinear, currp);
- break;
- }
- case Expression::Id::UnreachableId: {
- self->pushTask(SubType::doVisitUnreachable, currp);
- self->pushTask(SubType::doNoteNonLinear, currp);
- break;
- }
- default: {
- // other node types do not have control flow, use regular post-order
- PostWalker<SubType, VisitorType>::scan(self, currp);
- }
- }
- }
-};
-
} // namespace wasm
#endif // wasm_wasm_traversal_h
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-04 12:20:28 +0000