diff options
| -rw-r--r-- | src/passes/RemoveUnusedBrs.cpp | 67 | ||||
| -rw-r--r-- | test/lit/passes/remove-unused-brs.wast | 256 | ||||
| -rw-r--r-- | test/passes/remove-unused-brs_enable-multivalue.txt | 19 | ||||
| -rw-r--r-- | test/passes/remove-unused-brs_enable-multivalue.wast | 2 |
4 files changed, 321 insertions, 23 deletions
diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp index cacd24402..88a87ba1f 100644 --- a/src/passes/RemoveUnusedBrs.cpp +++ b/src/passes/RemoveUnusedBrs.cpp @@ -915,7 +915,7 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> { // Restructuring of ifs: if we have // (block $x - // (br_if $x (cond)) + // (drop (br_if $x (cond))) // .., no other references to $x // ) // then we can turn that into (if (!cond) ..). @@ -925,7 +925,7 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> { // If the block has a return value, we can do something similar, removing // the drop from the br_if and putting the if on the outside, // (block $x - // (br_if $x (value) (cond)) + // (drop (br_if $x (value) (cond))) // .., no other references to $x // ..final element.. // ) @@ -956,30 +956,73 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> { // not have a value, depending on if it was dropped or not. If the // type is unreachable that means it is not actually reached, which we // can ignore. + Builder builder(*getModule()); if (br && br->condition && br->name == curr->name && br->type != Type::unreachable) { if (BranchUtils::BranchSeeker::count(curr, curr->name) == 1) { // no other breaks to that name, so we can do this if (!drop) { assert(!br->value); - Builder builder(*getModule()); replaceCurrent(builder.makeIf( builder.makeUnary(EqZInt32, br->condition), curr)); ExpressionManipulator::nop(br); curr->finalize(curr->type); } else { - // If the items we move around have side effects, we can't do - // this. - // TODO: we could use a select, in some cases..? + // To use an if, the value must have no side effects, as in the + // if it may not execute. FeatureSet features = getModule()->features; if (!EffectAnalyzer(passOptions, features, br->value) - .hasSideEffects() && - !EffectAnalyzer(passOptions, features, br->condition) .hasSideEffects()) { - ExpressionManipulator::nop(list[0]); - Builder builder(*getModule()); - replaceCurrent( - builder.makeIf(br->condition, br->value, curr)); + // We also need to reorder the condition and the value. + if (EffectAnalyzer::canReorder( + passOptions, features, br->condition, br->value)) { + ExpressionManipulator::nop(list[0]); + replaceCurrent( + builder.makeIf(br->condition, br->value, curr)); + } + } else { + // The value has side effects, so it must always execute. We + // may still be able to optimize this, however, by using a + // select: + // (block $x + // (drop (br_if $x (value) (cond))) + // ..., no other references to $x + // ..final element.. + // ) + // => + // (select + // (value) + // (block $x + // ..., no other references to $x + // ..final element.. + // ) + // (cond) + // ) + // To do this we must be able to reorder the condition with + // the rest of the block (but not the value), and we must be + // able to make the rest of the block always execute, so it + // must not have side effects. + // TODO: we can do this when there *are* other refs to $x, + // with a larger refactoring here. + + // Test for the conditions with a temporary nop instead of the + // br_if. + Expression* old = list[0]; + Nop nop; + // After this assignment, curr is what is left in the block + // after ignoring the br_if. + list[0] = &nop; + auto canReorder = EffectAnalyzer::canReorder( + passOptions, features, br->condition, curr); + auto hasSideEffects = + EffectAnalyzer(passOptions, features, curr) + .hasSideEffects(); + list[0] = old; + if (canReorder && !hasSideEffects) { + ExpressionManipulator::nop(list[0]); + replaceCurrent( + builder.makeSelect(br->condition, br->value, curr)); + } } } } diff --git a/test/lit/passes/remove-unused-brs.wast b/test/lit/passes/remove-unused-brs.wast index bd4d80bcd..a43601654 100644 --- a/test/lit/passes/remove-unused-brs.wast +++ b/test/lit/passes/remove-unused-brs.wast @@ -26,4 +26,260 @@ ) ) ) + + ;; CHECK: (func $restructure-br_if (param $x i32) (result i32) + ;; CHECK-NEXT: (if (result i32) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (i32.const 100) + ;; CHECK-NEXT: (block $x (result i32) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 200) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 300) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $restructure-br_if (param $x i32) (result i32) + ;; this block+br_if can be turned into an if. + (block $x (result i32) + (drop + (br_if $x + (i32.const 100) + (local.get $x) + ) + ) + (drop (i32.const 200)) + (i32.const 300) + ) + ) + + (func $nothing) + + ;; CHECK: (func $restructure-br_if-condition-reorderable (param $x i32) (result i32) + ;; CHECK-NEXT: (if (result i32) + ;; CHECK-NEXT: (block $block (result i32) + ;; CHECK-NEXT: (call $nothing) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 100) + ;; CHECK-NEXT: (block $x (result i32) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 200) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 300) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $restructure-br_if-condition-reorderable (param $x i32) (result i32) + (block $x (result i32) + (drop + (br_if $x + (i32.const 100) + ;; the condition has side effects, but can be reordered with the value + (block (result i32) + (call $nothing) + (local.get $x) + ) + ) + ) + (drop (i32.const 200)) + (i32.const 300) + ) + ) + + ;; CHECK: (func $restructure-br_if-value-effectful (param $x i32) (result i32) + ;; CHECK-NEXT: (select + ;; CHECK-NEXT: (block $block (result i32) + ;; CHECK-NEXT: (call $nothing) + ;; CHECK-NEXT: (i32.const 100) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block $x (result i32) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 200) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 300) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block $block0 (result i32) + ;; CHECK-NEXT: (call $nothing) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $restructure-br_if-value-effectful (param $x i32) (result i32) + (block $x (result i32) + (drop + (br_if $x + ;; the value has side effects, but we can use a select instead + ;; of an if, which keeps the value first + (block (result i32) + (call $nothing) + (i32.const 100) + ) + ;; the condition has side effects too, but can be be reordered + ;; to the end of the block + (block (result i32) + (call $nothing) + (local.get $x) + ) + ) + ) + (drop (i32.const 200)) + (i32.const 300) + ) + ) + + ;; CHECK: (func $restructure-br_if-value-effectful-corner-case-1 (param $x i32) (result i32) + ;; CHECK-NEXT: (block $x (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (br_if $x + ;; CHECK-NEXT: (block $block (result i32) + ;; CHECK-NEXT: (call $nothing) + ;; CHECK-NEXT: (i32.const 100) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block $block1 (result i32) + ;; CHECK-NEXT: (call $nothing) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $nothing) + ;; CHECK-NEXT: (i32.const 300) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $restructure-br_if-value-effectful-corner-case-1 (param $x i32) (result i32) + (block $x (result i32) + (drop + (br_if $x + (block (result i32) + (call $nothing) + (i32.const 100) + ) + (block (result i32) + (call $nothing) + (local.get $x) + ) + ) + ) + ;; the condition cannot be reordered with this + (call $nothing) + (i32.const 300) + ) + ) + + ;; CHECK: (func $get-i32 (result i32) + ;; CHECK-NEXT: (i32.const 400) + ;; CHECK-NEXT: ) + (func $get-i32 (result i32) + (i32.const 400) + ) + + ;; CHECK: (func $restructure-br_if-value-effectful-corner-case-2 (param $x i32) (result i32) + ;; CHECK-NEXT: (block $x (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (br_if $x + ;; CHECK-NEXT: (block $block (result i32) + ;; CHECK-NEXT: (call $nothing) + ;; CHECK-NEXT: (i32.const 100) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block $block2 (result i32) + ;; CHECK-NEXT: (call $nothing) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 300) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $get-i32) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $restructure-br_if-value-effectful-corner-case-2 (param $x i32) (result i32) + (block $x (result i32) + (drop + (br_if $x + (block (result i32) + (call $nothing) + (i32.const 100) + ) + (block (result i32) + (call $nothing) + (local.get $x) + ) + ) + ) + (drop (i32.const 300)) + ;; the condition cannot be reordered with this + (call $get-i32) + ) + ) + ;; CHECK: (func $restructure-br_if-value-effectful-corner-case-3 (param $x i32) (result i32) + ;; CHECK-NEXT: (block $x (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (br_if $x + ;; CHECK-NEXT: (block $block (result i32) + ;; CHECK-NEXT: (call $nothing) + ;; CHECK-NEXT: (i32.const 100) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $nothing) + ;; CHECK-NEXT: (i32.const 100) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $restructure-br_if-value-effectful-corner-case-3 (param $x i32) (result i32) + (block $x (result i32) + (drop + (br_if $x + ;; we can't do an if because of effects here + (block (result i32) + (call $nothing) + (i32.const 100) + ) + (local.get $x) + ) + ) + ;; and we can't do a select because of effects here + (call $nothing) + (i32.const 100) + ) + ) + + ;; CHECK: (func $restructure-br_if-value-effectful-corner-case-4 (param $x i32) (result i32) + ;; CHECK-NEXT: (block $x (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (br_if $x + ;; CHECK-NEXT: (block $block (result i32) + ;; CHECK-NEXT: (call $nothing) + ;; CHECK-NEXT: (i32.const 100) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 300) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $get-i32) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $restructure-br_if-value-effectful-corner-case-4 (param $x i32) (result i32) + (block $x (result i32) + (drop + (br_if $x + ;; we can't do an if because of effects here + (block (result i32) + (call $nothing) + (i32.const 100) + ) + (local.get $x) + ) + ) + (drop (i32.const 300)) + ;; and we can't do a select because of effects here + (call $get-i32) + ) + ) ) diff --git a/test/passes/remove-unused-brs_enable-multivalue.txt b/test/passes/remove-unused-brs_enable-multivalue.txt index f48f7b6af..45e6b4159 100644 --- a/test/passes/remove-unused-brs_enable-multivalue.txt +++ b/test/passes/remove-unused-brs_enable-multivalue.txt @@ -1988,17 +1988,16 @@ ) ) ) - (func $drop-restructure-if-bad (param $x i32) (param $y i32) (result i32) - (block $label$2 (result i32) - (drop - (br_if $label$2 - (local.tee $y - (local.get $x) - ) - (local.get $y) - ) + (func $drop-restructure-select (param $x i32) (param $y i32) (result i32) + (select + (local.tee $y + (local.get $x) ) - (i32.const 0) + (block $label$2 (result i32) + (nop) + (i32.const 0) + ) + (local.get $y) ) ) (func $drop-restructure-if-bad-2 (param $x i32) (param $y i32) (result i32) diff --git a/test/passes/remove-unused-brs_enable-multivalue.wast b/test/passes/remove-unused-brs_enable-multivalue.wast index 6b5b4b1a7..afc8c3836 100644 --- a/test/passes/remove-unused-brs_enable-multivalue.wast +++ b/test/passes/remove-unused-brs_enable-multivalue.wast @@ -1615,7 +1615,7 @@ (i32.const 0) ) ) - (func $drop-restructure-if-bad (param $x i32) (param $y i32) (result i32) + (func $drop-restructure-select (param $x i32) (param $y i32) (result i32) (block $label$2 (result i32) (drop (br_if $label$2 |