From c7cb56099d6a3b8b1dfb540cc64f6572c1101ed4 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Sat, 29 Oct 2016 10:45:38 -0700 Subject: handle the case of a br_if whose value is used in merge-blocks --- src/passes/MergeBlocks.cpp | 52 +++++++++++++++++++++++++++++++++------------- 1 file changed, 38 insertions(+), 14 deletions(-) (limited to 'src') diff --git a/src/passes/MergeBlocks.cpp b/src/passes/MergeBlocks.cpp index bde9397a8..f7fac9594 100644 --- a/src/passes/MergeBlocks.cpp +++ b/src/passes/MergeBlocks.cpp @@ -68,29 +68,53 @@ namespace wasm { -struct SwitchFinder : public ControlFlowWalker> { - Expression* origin; - bool found = false; +// Looks for reasons we can't remove the values from breaks to an origin +// For example, if there is a switch targeting us, we can't do it - we can't remove the value from other targets +struct ProblemFinder : public ControlFlowWalker> { + Name origin; + bool foundSwitch = false; + // count br_ifs, and dropped br_ifs. if they don't match, then a br_if flow value is used, and we can't drop it + Index brIfs = 0; + Index droppedBrIfs = 0; + + void visitBreak(Break* curr) { + if (curr->name == origin && curr->condition) { + brIfs++; + } + } + + void visitDrop(Drop* curr) { + if (auto* br = curr->value->dynCast()) { + if (br->name == origin && br->condition) { + droppedBrIfs++; + } + } + } void visitSwitch(Switch* curr) { - if (findBreakTarget(curr->default_) == origin) { - found = true; + if (curr->default_ == origin) { + foundSwitch = true; return; } for (auto& target : curr->targets) { - if (findBreakTarget(target) == origin) { - found = true; + if (target == origin) { + foundSwitch = true; return; } } } + + bool found() { + assert(brIfs >= droppedBrIfs); + return foundSwitch || brIfs > droppedBrIfs; + } }; struct BreakValueDropper : public ControlFlowWalker> { - Expression* origin; + Name origin; void visitBreak(Break* curr) { - if (curr->value && findBreakTarget(curr->name) == origin) { + if (curr->value && curr->name == origin) { Builder builder(*getModule()); replaceCurrent(builder.makeSequence(builder.makeDrop(curr->value), curr)); curr->value = nullptr; @@ -118,16 +142,16 @@ struct MergeBlocks : public WalkerPassname.is()) { Expression* expression = child; - // if there is a switch targeting us, we can't do it - we can't remove the value from other targets too - SwitchFinder finder; - finder.origin = child; + // check if it's ok to remove the value from all breaks to us + ProblemFinder finder; + finder.origin = child->name; finder.walk(expression); - if (finder.found) { + if (finder.found()) { child = nullptr; } else { // fix up breaks BreakValueDropper fixer; - fixer.origin = child; + fixer.origin = child->name; fixer.setModule(getModule()); fixer.walk(expression); } -- cgit v1.2.3 From 68bf64141dc4d35e6ff174fb68ce5bc50ff27c79 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Sat, 29 Oct 2016 11:02:28 -0700 Subject: fix break value removal in merge-blocks: a br_if's type changes without a value, so finalize the node, and remove the drop --- src/passes/MergeBlocks.cpp | 11 ++++++++++- test/passes/merge-blocks.txt | 14 ++++++-------- 2 files changed, 16 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/passes/MergeBlocks.cpp b/src/passes/MergeBlocks.cpp index f7fac9594..edfa1336b 100644 --- a/src/passes/MergeBlocks.cpp +++ b/src/passes/MergeBlocks.cpp @@ -116,8 +116,17 @@ struct BreakValueDropper : public ControlFlowWalkervalue && curr->name == origin) { Builder builder(*getModule()); - replaceCurrent(builder.makeSequence(builder.makeDrop(curr->value), curr)); + auto* value = curr->value; curr->value = nullptr; + curr->finalize(); + replaceCurrent(builder.makeSequence(builder.makeDrop(value), curr)); + } + } + + void visitDrop(Drop* curr) { + // if we dropped a br_if whose value we removed, then we are now dropping a (block (drop value) (br_if)) with type none, which does not need a drop + if (curr->value->type == none) { + replaceCurrent(curr->value); } } }; diff --git a/test/passes/merge-blocks.txt b/test/passes/merge-blocks.txt index 152e6fbae..1116e0d28 100644 --- a/test/passes/merge-blocks.txt +++ b/test/passes/merge-blocks.txt @@ -29,14 +29,12 @@ (func $drop-block-br-if (type $0) (block $block (block $x - (drop - (block i32 - (drop - (i32.const 1) - ) - (br_if $x - (i32.const 2) - ) + (block + (drop + (i32.const 1) + ) + (br_if $x + (i32.const 2) ) ) (drop -- cgit v1.2.3 From 73a2bae85261757303deb9e3ff5be230483d5ba4 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Sat, 29 Oct 2016 12:25:57 -0700 Subject: optimize child blocks in merge-blocks when we drop values in them, they may have new subchild blocks --- src/passes/MergeBlocks.cpp | 133 +++++++++++++++++++++++------------------- test/passes/merge-blocks.txt | 41 +++++++++---- test/passes/merge-blocks.wast | 15 +++++ 3 files changed, 117 insertions(+), 72 deletions(-) (limited to 'src') diff --git a/src/passes/MergeBlocks.cpp b/src/passes/MergeBlocks.cpp index edfa1336b..95d680ec7 100644 --- a/src/passes/MergeBlocks.cpp +++ b/src/passes/MergeBlocks.cpp @@ -110,9 +110,13 @@ struct ProblemFinder : public ControlFlowWalker> { Name origin; + void visitBlock(Block* curr); + void visitBreak(Break* curr) { if (curr->value && curr->name == origin) { Builder builder(*getModule()); @@ -131,72 +135,81 @@ struct BreakValueDropper : public ControlFlowWalker>> { - bool isFunctionParallel() override { return true; } - - Pass* create() override { return new MergeBlocks; } - - void visitBlock(Block *curr) { - bool more = true; - bool changed = false; - while (more) { - more = false; - for (size_t i = 0; i < curr->list.size(); i++) { - Block* child = curr->list[i]->dynCast(); - if (!child) { - // if we have a child that is (drop (block ..)) then we can move the drop into the block, and remove br values. this allows more merging, - auto* drop = curr->list[i]->dynCast(); - if (drop) { - child = drop->value->dynCast(); - if (child) { - if (child->name.is()) { - Expression* expression = child; - // check if it's ok to remove the value from all breaks to us - ProblemFinder finder; - finder.origin = child->name; - finder.walk(expression); - if (finder.found()) { - child = nullptr; - } else { - // fix up breaks - BreakValueDropper fixer; - fixer.origin = child->name; - fixer.setModule(getModule()); - fixer.walk(expression); - } - } - if (child) { - // we can do it! - // reuse the drop - drop->value = child->list.back(); - child->list.back() = drop; - child->finalize(); - curr->list[i] = child; - more = true; - changed = true; +// core block optimizer routine +static void optimizeBlock(Block* curr, Module* module) { + bool more = true; + bool changed = false; + while (more) { + more = false; + for (size_t i = 0; i < curr->list.size(); i++) { + Block* child = curr->list[i]->dynCast(); + if (!child) { + // if we have a child that is (drop (block ..)) then we can move the drop into the block, and remove br values. this allows more merging, + auto* drop = curr->list[i]->dynCast(); + if (drop) { + child = drop->value->dynCast(); + if (child) { + if (child->name.is()) { + Expression* expression = child; + // check if it's ok to remove the value from all breaks to us + ProblemFinder finder; + finder.origin = child->name; + finder.walk(expression); + if (finder.found()) { + child = nullptr; + } else { + // fix up breaks + BreakValueDropper fixer; + fixer.origin = child->name; + fixer.setModule(module); + fixer.walk(expression); } } + if (child) { + // we can do it! + // reuse the drop + drop->value = child->list.back(); + child->list.back() = drop; + child->finalize(); + curr->list[i] = child; + more = true; + changed = true; + } } } - if (!child) continue; - if (child->name.is()) continue; // named blocks can have breaks to them (and certainly do, if we ran RemoveUnusedNames and RemoveUnusedBrs) - ExpressionList merged(getModule()->allocator); - for (size_t j = 0; j < i; j++) { - merged.push_back(curr->list[j]); - } - for (auto item : child->list) { - merged.push_back(item); - } - for (size_t j = i + 1; j < curr->list.size(); j++) { - merged.push_back(curr->list[j]); - } - curr->list = merged; - more = true; - changed = true; - break; } + if (!child) continue; + if (child->name.is()) continue; // named blocks can have breaks to them (and certainly do, if we ran RemoveUnusedNames and RemoveUnusedBrs) + ExpressionList merged(module->allocator); + for (size_t j = 0; j < i; j++) { + merged.push_back(curr->list[j]); + } + for (auto item : child->list) { + merged.push_back(item); + } + for (size_t j = i + 1; j < curr->list.size(); j++) { + merged.push_back(curr->list[j]); + } + curr->list = merged; + more = true; + changed = true; + break; } - if (changed) curr->finalize(); + } + if (changed) curr->finalize(); +} + +void BreakValueDropper::visitBlock(Block* curr) { + optimizeBlock(curr, getModule()); +} + +struct MergeBlocks : public WalkerPass>> { + bool isFunctionParallel() override { return true; } + + Pass* create() override { return new MergeBlocks; } + + void visitBlock(Block *curr) { + optimizeBlock(curr, getModule()); } Block* optimize(Expression* curr, Expression*& child, Block* outer = nullptr, Expression** dependency1 = nullptr, Expression** dependency2 = nullptr) { diff --git a/test/passes/merge-blocks.txt b/test/passes/merge-blocks.txt index 1116e0d28..ae34bea05 100644 --- a/test/passes/merge-blocks.txt +++ b/test/passes/merge-blocks.txt @@ -14,12 +14,10 @@ (func $drop-block-br (type $0) (block $block (block $x - (block - (drop - (i32.const 1) - ) - (br $x) + (drop + (i32.const 1) ) + (br $x) (drop (i32.const 0) ) @@ -29,13 +27,11 @@ (func $drop-block-br-if (type $0) (block $block (block $x - (block - (drop - (i32.const 1) - ) - (br_if $x - (i32.const 2) - ) + (drop + (i32.const 1) + ) + (br_if $x + (i32.const 2) ) (drop (i32.const 0) @@ -58,4 +54,25 @@ ) ) ) + (func $drop-block-nested-br-if (type $0) + (block $block + (block $x + (if + (i32.const 100) + (block $block0 + (drop + (i32.const 1) + ) + (br_if $x + (i32.const 2) + ) + (nop) + ) + ) + (drop + (i32.const 0) + ) + ) + ) + ) ) diff --git a/test/passes/merge-blocks.wast b/test/passes/merge-blocks.wast index 161f9d90f..e0da890a1 100644 --- a/test/passes/merge-blocks.wast +++ b/test/passes/merge-blocks.wast @@ -38,5 +38,20 @@ ) ) ) + (func $drop-block-nested-br-if + (block + (drop + (block $x i32 + (if (i32.const 100) + (block + (drop (br_if $x (i32.const 1) (i32.const 2))) + (nop) + ) + ) + (i32.const 0) + ) + ) + ) + ) ) -- cgit v1.2.3