Remove TypeUpdater in Vacuum and always ReFinalize (#5707)
TypeUpdater::remove must be called after removing a thing from the
tree. If not, then we can get confused by something like this:
(block $b
(br $b)
)
If we first call TypeUpdater::remove then we see that the block's only
br is going away, so it becomes unreachable. But when we then remove
the br then the block should have type none. Removing the br first
from the IR, and then calling TypeUpdater::remove, is the safe way to do it.
However, changing that order in Vacuum is not trivial. After looking into
this, I realized that it is just simpler to remove TypeUpdater entirely.
Instead, we can ReFinalize at the end unconditionally. This has the downside
that we do not propagate type updates "as we go", but that should be very
rare.
Another downside is that TypeUpdater tracks the number of brs, which
can help remove code like in the one test that regresses here (see comment
there). But I'm not sure that removal was valid - Vacuum should not really be
doing it, and it looks like its related to this bug actually. Instead, we have a
dedicated pass for removing unused brs - RemoveUnusedBrs - so leave
things for it.
This PR's benefit, aside from now handling the fuzz testcase, is that it makes
the code simpler and faster. I see a 10-25% speedup on the Vacuum pass on
various binaries I tested on. (Vacuum is one of our faster passes anyhow,
though, so the runtime of -O1 is not much improved.)
Another minor benefit might be that running ReFinalize more often can
propagate type info more quickly, thanks to #5704 etc. But that is probably
very minor.
diff --git a/src/passes/Vacuum.cpp b/src/passes/Vacuum.cpp
index 7c39490..8d89553 100644
--- a/src/passes/Vacuum.cpp
+++ b/src/passes/Vacuum.cpp
@@ -23,7 +23,6 @@
#include <ir/effects.h>
#include <ir/iteration.h>
#include <ir/literal-utils.h>
-#include <ir/type-updating.h>
#include <ir/utils.h>
#include <pass.h>
#include <wasm-builder.h>
@@ -36,32 +35,9 @@
std::unique_ptr<Pass> create() override { return std::make_unique<Vacuum>(); }
- TypeUpdater typeUpdater;
-
- // The TypeUpdater class handles efficient updating of unreachability as we
- // go, but we may also refine types, which requires refinalization.
- bool refinalize = false;
-
- Expression* replaceCurrent(Expression* expression) {
- auto* old = getCurrent();
- if (expression->type != old->type &&
- expression->type != Type::unreachable) {
- // We are changing this to a new type that is not unreachable, so it is a
- // refinement that we need to use refinalize to propagate up.
- refinalize = true;
- }
- super::replaceCurrent(expression);
- // also update the type updater
- typeUpdater.noteReplacement(old, expression);
- return expression;
- }
-
void doWalkFunction(Function* func) {
- typeUpdater.walk(func->body);
walk(func->body);
- if (refinalize) {
- ReFinalize().walkFunctionInModule(func, getModule());
- }
+ ReFinalize().walkFunctionInModule(func, getModule());
}
// Returns nullptr if curr is dead, curr if it must stay as is, or one of its
@@ -185,11 +161,9 @@
}
}
if (!optimized) {
- typeUpdater.noteRecursiveRemoval(child);
skip++;
} else {
if (optimized != child) {
- typeUpdater.noteReplacement(child, optimized);
list[z] = optimized;
}
if (skip > 0) {
@@ -198,14 +172,7 @@
}
// if this is unreachable, the rest is dead code
if (list[z - skip]->type == Type::unreachable && z < size - 1) {
- for (Index i = z - skip + 1; i < list.size(); i++) {
- auto* remove = list[i];
- if (remove) {
- typeUpdater.noteRecursiveRemoval(remove);
- }
- }
list.resize(z - skip + 1);
- typeUpdater.maybeUpdateTypeToUnreachable(curr);
skip = 0; // nothing more to do on the list
break;
}
@@ -213,7 +180,6 @@
}
if (skip > 0) {
list.resize(size - skip);
- typeUpdater.maybeUpdateTypeToUnreachable(curr);
}
// the block may now be a trivial one that we can get rid of and just leave
// its contents
@@ -227,15 +193,10 @@
Expression* child;
if (value->value.getInteger()) {
child = curr->ifTrue;
- if (curr->ifFalse) {
- typeUpdater.noteRecursiveRemoval(curr->ifFalse);
- }
} else {
if (curr->ifFalse) {
child = curr->ifFalse;
- typeUpdater.noteRecursiveRemoval(curr->ifTrue);
} else {
- typeUpdater.noteRecursiveRemoval(curr);
ExpressionManipulator::nop(curr);
return;
}
@@ -245,10 +206,6 @@
}
// if the condition is unreachable, just return it
if (curr->condition->type == Type::unreachable) {
- typeUpdater.noteRecursiveRemoval(curr->ifTrue);
- if (curr->ifFalse) {
- typeUpdater.noteRecursiveRemoval(curr->ifFalse);
- }
replaceCurrent(curr->condition);
return;
}
@@ -384,9 +341,6 @@
// the try's body.
if (!EffectAnalyzer(getPassOptions(), *getModule(), curr->body).throws()) {
replaceCurrent(curr->body);
- for (auto* catchBody : curr->catchBodies) {
- typeUpdater.noteRecursiveRemoval(catchBody);
- }
return;
}
@@ -398,7 +352,6 @@
if (curr->type == Type::none && curr->hasCatchAll() &&
!EffectAnalyzer(getPassOptions(), *getModule(), curr)
.hasUnremovableSideEffects()) {
- typeUpdater.noteRecursiveRemoval(curr);
ExpressionManipulator::nop(curr);
}
}
diff --git a/test/lit/passes/vacuum-global-effects.wast b/test/lit/passes/vacuum-global-effects.wast
new file mode 100644
index 0000000..1bd44ce
--- /dev/null
+++ b/test/lit/passes/vacuum-global-effects.wast
@@ -0,0 +1,45 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited.
+;; RUN: wasm-opt %s --generate-global-effects --vacuum -all -S -o - | filecheck %s
+
+(module
+ ;; CHECK: (func $nop (type $i32_=>_none) (param $0 i32)
+ ;; CHECK-NEXT: (nop)
+ ;; CHECK-NEXT: )
+ (func $nop (param $0 i32)
+ (nop)
+ )
+
+ ;; CHECK: (func $test (type $none_=>_none)
+ ;; CHECK-NEXT: (local $x i32)
+ ;; CHECK-NEXT: (nop)
+ ;; CHECK-NEXT: )
+ (func $test
+ (local $x i32)
+ (local.set $x
+ (i32.const 0)
+ )
+ ;; After we compute global effects, we see that this call has no effects. We
+ ;; can then remove it, and all of its contents have no effects as well. The
+ ;; rest of the function is also removable and the entire body can be a nop.
+ ;;
+ ;; This is a regression testcase for a crash in TypeUpdater, which involved
+ ;; the call being discovered as having no effects, and then when we started
+ ;; to remove its children we'd remove the br first; that removal would make
+ ;; the block seem to have no brs that reach it any more (since the only one
+ ;; was removed). But as the br was still in the tree, and had type
+ ;; unreachable, we thought the block should become unreachable, which then
+ ;; propagated out to the call and the toplevel block. (Users of TypeUpdater
+ ;; should first remove things from the tree, and then do the update.)
+ (call $nop
+ (block $block (result i32)
+ (br $block
+ (i32.const 4)
+ )
+ )
+ )
+ (drop
+ (local.get $x)
+ )
+ )
+)
+
diff --git a/test/lit/passes/vacuum_all-features.wast b/test/lit/passes/vacuum_all-features.wast
index 36074af..1a64521 100644
--- a/test/lit/passes/vacuum_all-features.wast
+++ b/test/lit/passes/vacuum_all-features.wast
@@ -627,7 +627,7 @@
;; CHECK: (func $drop-if-both-unreachable (type $1) (param $0 i32)
;; CHECK-NEXT: (block $out
;; CHECK-NEXT: (drop
- ;; CHECK-NEXT: (if (result i32)
+ ;; CHECK-NEXT: (if
;; CHECK-NEXT: (local.get $0)
;; CHECK-NEXT: (br $out)
;; CHECK-NEXT: (br $out)
@@ -635,7 +635,7 @@
;; CHECK-NEXT: )
;; CHECK-NEXT: )
;; CHECK-NEXT: (drop
- ;; CHECK-NEXT: (if (result i32)
+ ;; CHECK-NEXT: (if
;; CHECK-NEXT: (local.get $0)
;; CHECK-NEXT: (unreachable)
;; CHECK-NEXT: (unreachable)
@@ -701,6 +701,12 @@
;; CHECK-NEXT: )
;; CHECK-NEXT: (return)
;; CHECK-NEXT: )
+ ;; CHECK-NEXT: (block $out2
+ ;; CHECK-NEXT: (block $in2
+ ;; CHECK-NEXT: (br $in2)
+ ;; CHECK-NEXT: )
+ ;; CHECK-NEXT: (return)
+ ;; CHECK-NEXT: )
;; CHECK-NEXT: )
(func $block-resize-br-gone
(block $out
@@ -711,6 +717,8 @@
)
(return)
)
+ ;; The second br will be removed. (The entire expression after us can also
+ ;; be removed, which will be done by --remove-unused-brs --vacuum.)
(block $out2
(block $in2
(br $in2)
@@ -758,14 +766,16 @@
)
)
;; CHECK: (func $leave-block-even-if-br-not-taken (type $none_=>_f64) (result f64)
- ;; CHECK-NEXT: (block $label$0 (result f64)
+ ;; CHECK-NEXT: (block $label$0
;; CHECK-NEXT: (f64.store align=1
;; CHECK-NEXT: (i32.const 879179022)
- ;; CHECK-NEXT: (br_if $label$0
+ ;; CHECK-NEXT: (block
;; CHECK-NEXT: (loop $label$9
;; CHECK-NEXT: (br $label$9)
;; CHECK-NEXT: )
- ;; CHECK-NEXT: (i32.const 677803374)
+ ;; CHECK-NEXT: (drop
+ ;; CHECK-NEXT: (i32.const 677803374)
+ ;; CHECK-NEXT: )
;; CHECK-NEXT: )
;; CHECK-NEXT: )
;; CHECK-NEXT: )
@@ -775,6 +785,9 @@
(f64.store align=1
(i32.const 879179022)
(br_if $label$0
+ ;; This loop never exits, so it is unreachable. We don't have much to
+ ;; optimize here, but we can remove the br_if and leave an unreachable
+ ;; block with the other contents for dce to clean up.
(loop $label$9
(br $label$9)
)
