From 18c332220f655dbad552c369ccde5da6e5b7fde2 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Fri, 7 Oct 2016 21:14:20 -0700 Subject: clean up some unneeded processing in cfg-walker --- src/cfg/cfg-traversal.h | 3 --- 1 file changed, 3 deletions(-) (limited to 'src') diff --git a/src/cfg/cfg-traversal.h b/src/cfg/cfg-traversal.h index 5bc593691..3bd3289cc 100644 --- a/src/cfg/cfg-traversal.h +++ b/src/cfg/cfg-traversal.h @@ -175,9 +175,7 @@ struct CFGWalker : public ControlFlowWalker { break; } case Expression::Id::IfId: { - self->pushTask(SubType::doPostVisitControlFlow, currp); self->pushTask(SubType::doEndIf, currp); - self->pushTask(SubType::doVisitIf, currp); auto* ifFalse = curr->cast()->ifFalse; if (ifFalse) { self->pushTask(SubType::scan, &curr->cast()->ifFalse); @@ -186,7 +184,6 @@ struct CFGWalker : public ControlFlowWalker { self->pushTask(SubType::scan, &curr->cast()->ifTrue); self->pushTask(SubType::doStartIfTrue, currp); self->pushTask(SubType::scan, &curr->cast()->condition); - self->pushTask(SubType::doPreVisitControlFlow, currp); return; // don't do anything else } case Expression::Id::LoopId: { -- cgit v1.2.3 From 99e50f51ba9917ee45d336e204e1c8d59e9ccc9e Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Sat, 8 Oct 2016 10:51:19 -0700 Subject: remove unneeded param to doStartBasicBlock --- src/cfg/cfg-traversal.h | 26 +++++++++++++++----------- 1 file changed, 15 insertions(+), 11 deletions(-) (limited to 'src') diff --git a/src/cfg/cfg-traversal.h b/src/cfg/cfg-traversal.h index 3bd3289cc..668bdfef2 100644 --- a/src/cfg/cfg-traversal.h +++ b/src/cfg/cfg-traversal.h @@ -61,9 +61,13 @@ struct CFGWalker : public ControlFlowWalker { std::vector ifStack; std::vector loopStack; + void startBasicBlock() { + currBasicBlock = makeBasicBlock(); + basicBlocks.push_back(std::unique_ptr(currBasicBlock)); + } + static void doStartBasicBlock(SubType* self, Expression** currp) { - self->currBasicBlock = self->makeBasicBlock(); - self->basicBlocks.push_back(std::unique_ptr(self->currBasicBlock)); + self->startBasicBlock(); } void link(BasicBlock* from, BasicBlock* to) { @@ -80,7 +84,7 @@ struct CFGWalker : public ControlFlowWalker { if (origins.size() == 0) return; // we have branches to here, so we need a new block auto* last = self->currBasicBlock; - doStartBasicBlock(self, currp); + self->startBasicBlock(); self->link(last, self->currBasicBlock); // fallthrough // branches to the new one for (auto* origin : origins) { @@ -91,20 +95,20 @@ struct CFGWalker : public ControlFlowWalker { static void doStartIfTrue(SubType* self, Expression** currp) { auto* last = self->currBasicBlock; - doStartBasicBlock(self, currp); + self->startBasicBlock(); self->link(last, self->currBasicBlock); // ifTrue self->ifStack.push_back(last); // the block before the ifTrue } static void doStartIfFalse(SubType* self, Expression** currp) { self->ifStack.push_back(self->currBasicBlock); // the ifTrue fallthrough - doStartBasicBlock(self, currp); + self->startBasicBlock(); self->link(self->ifStack[self->ifStack.size() - 2], self->currBasicBlock); // before if -> ifFalse } static void doEndIf(SubType* self, Expression** currp) { auto* last = self->currBasicBlock; - doStartBasicBlock(self, currp); + self->startBasicBlock(); self->link(last, self->currBasicBlock); // last one is ifFalse's fallthrough if there was one, otherwise it's the ifTrue fallthrough if ((*currp)->cast()->ifFalse) { // we just linked ifFalse, need to link ifTrue to the end @@ -119,14 +123,14 @@ struct CFGWalker : public ControlFlowWalker { static void doStartLoop(SubType* self, Expression** currp) { auto* last = self->currBasicBlock; - doStartBasicBlock(self, currp); + self->startBasicBlock(); self->link(last, self->currBasicBlock); self->loopStack.push_back(self->currBasicBlock); } static void doEndLoop(SubType* self, Expression** currp) { auto* last = self->currBasicBlock; - doStartBasicBlock(self, currp); + self->startBasicBlock(); self->link(last, self->currBasicBlock); // fallthrough auto* curr = (*currp)->cast(); // branches to the top of the loop @@ -145,7 +149,7 @@ struct CFGWalker : public ControlFlowWalker { auto* curr = (*currp)->cast(); self->branches[self->findBreakTarget(curr->name)].push_back(self->currBasicBlock); // branch to the target auto* last = self->currBasicBlock; - doStartBasicBlock(self, currp); + self->startBasicBlock(); if (curr->condition) { self->link(last, self->currBasicBlock); // we might fall through } @@ -163,7 +167,7 @@ struct CFGWalker : public ControlFlowWalker { if (!seen.count(curr->default_)) { self->branches[self->findBreakTarget(curr->default_)].push_back(self->currBasicBlock); // branch to the target } - doStartBasicBlock(self, currp); + self->startBasicBlock(); } static void scan(SubType* self, Expression** currp) { @@ -223,7 +227,7 @@ struct CFGWalker : public ControlFlowWalker { void doWalkFunction(Function* func) { basicBlocks.clear(); - doStartBasicBlock(static_cast(this), nullptr); + startBasicBlock(); entry = currBasicBlock; ControlFlowWalker::doWalkFunction(func); -- cgit v1.2.3 From b211e9d70456b995996aa9c0d656650177590927 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Sat, 8 Oct 2016 12:09:53 -0700 Subject: track unreachable code in coalesce-locals, we know what is unreachable anyhow, and it just adds overhead to not ignore it --- src/cfg/cfg-traversal.h | 25 ++++++++----- src/passes/CoalesceLocals.cpp | 11 +++++- test/passes/coalesce-locals-learning.txt | 24 ++++++------- test/passes/coalesce-locals.txt | 61 ++++++++++++++++++++++++-------- test/passes/coalesce-locals.wast | 29 +++++++++++++++ 5 files changed, 113 insertions(+), 37 deletions(-) (limited to 'src') diff --git a/src/cfg/cfg-traversal.h b/src/cfg/cfg-traversal.h index 668bdfef2..004f23752 100644 --- a/src/cfg/cfg-traversal.h +++ b/src/cfg/cfg-traversal.h @@ -56,7 +56,9 @@ struct CFGWalker : public ControlFlowWalker { std::vector> basicBlocks; // all the blocks // traversal state - BasicBlock* currBasicBlock; // the current block in play during traversal + BasicBlock* currBasicBlock; // the current block in play during traversal. can be nullptr if unreachable, + // but note that we don't do a deep unreachability analysis - just enough + // to be useful, given that DCE has run before. std::map> branches; // a block or loop => its branches std::vector ifStack; std::vector loopStack; @@ -66,11 +68,16 @@ struct CFGWalker : public ControlFlowWalker { basicBlocks.push_back(std::unique_ptr(currBasicBlock)); } - static void doStartBasicBlock(SubType* self, Expression** currp) { - self->startBasicBlock(); + void startUnreachableBlock() { + currBasicBlock = nullptr; + } + + static void doStartUnreachableBlock(SubType* self, Expression** currp) { + self->startUnreachableBlock(); } void link(BasicBlock* from, BasicBlock* to) { + if (!from || !to) return; // if one of them is not reachable, ignore from->out.push_back(to); to->in.push_back(from); } @@ -148,10 +155,12 @@ struct CFGWalker : public ControlFlowWalker { static void doEndBreak(SubType* self, Expression** currp) { auto* curr = (*currp)->cast(); self->branches[self->findBreakTarget(curr->name)].push_back(self->currBasicBlock); // branch to the target - auto* last = self->currBasicBlock; - self->startBasicBlock(); if (curr->condition) { + auto* last = self->currBasicBlock; + self->startBasicBlock(); self->link(last, self->currBasicBlock); // we might fall through + } else { + self->startUnreachableBlock(); } } @@ -167,7 +176,7 @@ struct CFGWalker : public ControlFlowWalker { if (!seen.count(curr->default_)) { self->branches[self->findBreakTarget(curr->default_)].push_back(self->currBasicBlock); // branch to the target } - self->startBasicBlock(); + self->startUnreachableBlock(); } static void scan(SubType* self, Expression** currp) { @@ -203,11 +212,11 @@ struct CFGWalker : public ControlFlowWalker { break; } case Expression::Id::ReturnId: { - self->pushTask(SubType::doStartBasicBlock, currp); + self->pushTask(SubType::doStartUnreachableBlock, currp); break; } case Expression::Id::UnreachableId: { - self->pushTask(SubType::doStartBasicBlock, currp); + self->pushTask(SubType::doStartUnreachableBlock, currp); break; } default: {} diff --git a/src/passes/CoalesceLocals.cpp b/src/passes/CoalesceLocals.cpp index ba2c6dd81..2ff1dde37 100644 --- a/src/passes/CoalesceLocals.cpp +++ b/src/passes/CoalesceLocals.cpp @@ -169,13 +169,22 @@ struct CoalesceLocals : public WalkerPasscast(); + // if in unreachable code, ignore + if (!self->currBasicBlock) { + ExpressionManipulator::convert(curr); + return; + } self->currBasicBlock->contents.actions.emplace_back(Action::Get, curr->index, currp); } static void doVisitSetLocal(CoalesceLocals* self, Expression** currp) { auto* curr = (*currp)->cast(); + // if in unreachable code, ignore + if (!self->currBasicBlock) { + ExpressionManipulator::nop(curr); + return; + } self->currBasicBlock->contents.actions.emplace_back(Action::Set, curr->index, currp); - // if this is a copy, note it auto* get = curr->value->dynCast(); if (get) self->addCopy(curr->index, get->index); diff --git a/test/passes/coalesce-locals-learning.txt b/test/passes/coalesce-locals-learning.txt index 49afc98ec..ef8d31174 100644 --- a/test/passes/coalesce-locals-learning.txt +++ b/test/passes/coalesce-locals-learning.txt @@ -108,15 +108,11 @@ ) (block $block (br $block) + (nop) (drop - (i32.const 0) - ) - (drop - (get_local $0) - ) - (drop - (i32.const -1) + (unreachable) ) + (nop) ) (drop (get_local $0) @@ -395,10 +391,10 @@ (block $block (br $block) (drop - (get_local $0) + (unreachable) ) (drop - (get_local $0) + (unreachable) ) ) ) @@ -407,10 +403,10 @@ (block $block (unreachable) (drop - (get_local $0) + (unreachable) ) (drop - (get_local $0) + (unreachable) ) ) ) @@ -419,10 +415,10 @@ (block $block (return) (drop - (get_local $0) + (unreachable) ) (drop - (get_local $0) + (unreachable) ) ) ) @@ -466,7 +462,7 @@ (i32.const 100) ) (drop - (get_local $0) + (unreachable) ) ) (drop diff --git a/test/passes/coalesce-locals.txt b/test/passes/coalesce-locals.txt index 1f89b9fa7..08573a790 100644 --- a/test/passes/coalesce-locals.txt +++ b/test/passes/coalesce-locals.txt @@ -108,15 +108,11 @@ ) (block $block (br $block) + (nop) (drop - (i32.const 0) - ) - (drop - (get_local $0) - ) - (drop - (i32.const -1) + (unreachable) ) + (nop) ) (drop (get_local $0) @@ -393,10 +389,10 @@ (block $block (br $block) (drop - (get_local $0) + (unreachable) ) (drop - (get_local $0) + (unreachable) ) ) ) @@ -405,10 +401,10 @@ (block $block (unreachable) (drop - (get_local $0) + (unreachable) ) (drop - (get_local $0) + (unreachable) ) ) ) @@ -417,10 +413,10 @@ (block $block (return) (drop - (get_local $0) + (unreachable) ) (drop - (get_local $0) + (unreachable) ) ) ) @@ -464,7 +460,7 @@ (i32.const 100) ) (drop - (get_local $0) + (unreachable) ) ) (drop @@ -898,4 +894,41 @@ (get_local $0) ) ) + (func $in-unreachable (type $2) + (local $0 i32) + (block $x + (return) + (nop) + (drop + (unreachable) + ) + (nop) + ) + (block $y + (unreachable) + (nop) + (drop + (unreachable) + ) + (nop) + ) + (block $z + (br $z) + (nop) + (drop + (unreachable) + ) + (nop) + ) + (block $z14 + (br_table $z14 $z14 + (i32.const 100) + ) + (nop) + (drop + (unreachable) + ) + (nop) + ) + ) ) diff --git a/test/passes/coalesce-locals.wast b/test/passes/coalesce-locals.wast index da71b7665..26d90ff49 100644 --- a/test/passes/coalesce-locals.wast +++ b/test/passes/coalesce-locals.wast @@ -925,4 +925,33 @@ (get_local $z) ) ) + (func $in-unreachable + (local $a i32) + (block $x + (return) + (set_local $a (i32.const 1)) + (drop (get_local $a)) + (set_local $a (get_local $a)) + ) + (block $y + (unreachable) + (set_local $a (i32.const 1)) + (drop (get_local $a)) + (set_local $a (get_local $a)) + ) + (block $z + (br $z) + (set_local $a (i32.const 1)) + (drop (get_local $a)) + (set_local $a (get_local $a)) + ) + (block $z + (br_table $z $z + (i32.const 100) + ) + (set_local $a (i32.const 1)) + (drop (get_local $a)) + (set_local $a (get_local $a)) + ) + ) ) -- cgit v1.2.3 From 9cfbe71f45a1234737178eee514b003387ff35de Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Sat, 8 Oct 2016 12:22:04 -0700 Subject: improve comment --- src/cfg/cfg-traversal.h | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/cfg/cfg-traversal.h b/src/cfg/cfg-traversal.h index 004f23752..99bc25ea8 100644 --- a/src/cfg/cfg-traversal.h +++ b/src/cfg/cfg-traversal.h @@ -58,7 +58,8 @@ struct CFGWalker : public ControlFlowWalker { // traversal state BasicBlock* currBasicBlock; // the current block in play during traversal. can be nullptr if unreachable, // but note that we don't do a deep unreachability analysis - just enough - // to be useful, given that DCE has run before. + // to avoid constructing obviously-unreachable blocks (we do a full reachability + // analysis on the CFG once it is constructed). std::map> branches; // a block or loop => its branches std::vector ifStack; std::vector loopStack; -- cgit v1.2.3