From 5c03805d684cb541ba5a40138457bb598642de20 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Fri, 14 Mar 2014 15:09:59 -0700 Subject: add a Nested branch type in relooper, to represent a path we must make sure is nested so that parallel paths do not get intertwined. this allows us to emit a more canonical form of nested ifs as a result of short-circuit operators; 1.13.2 --- emscripten-version.txt | 2 +- src/relooper/Relooper.cpp | 51 ++++++++++++++++++++++++--- src/relooper/Relooper.h | 8 +++-- src/relooper/test.cpp | 90 +++++++++++++++++++++++++++++++++++++++++++++++ src/relooper/test.txt | 39 ++++++++++++++++++++ 5 files changed, 181 insertions(+), 9 deletions(-) diff --git a/emscripten-version.txt b/emscripten-version.txt index 87684ab8..2e46fa6f 100644 --- a/emscripten-version.txt +++ b/emscripten-version.txt @@ -1,2 +1,2 @@ -1.13.1 +1.13.2 diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp index c11de099..c6830158 100644 --- a/src/relooper/Relooper.cpp +++ b/src/relooper/Relooper.cpp @@ -122,7 +122,7 @@ void Branch::Render(Block *Target, bool SetLabel) { if (Code) PrintIndented("%s\n", Code); if (SetLabel) PrintIndented("label = %d;\n", Target->Id); if (Ancestor) { - if (Type != Direct) { + if (Type == Break || Type == Continue) { if (Labeled) { PrintIndented("%s L%d;\n", Type == Break ? "break" : "continue", Ancestor->Id); } else { @@ -287,6 +287,11 @@ void Block::Render(bool InLoop) { Details->Render(Target, SetCurrLabel); if (HasFusedContent) { Fused->InnerMap.find(Target)->second->Render(InLoop); + } else if (Details->Type == Branch::Nested) { + // Nest the parent content here, and remove it from showing up afterwards as Next + assert(Parent->Next); + Parent->Next->Render(InLoop); + Parent->Next = NULL; } if (useSwitch && iter != ProcessedBranchesOut.end()) { PrintIndented("break;\n"); @@ -1077,12 +1082,48 @@ void Relooper::Calculate(Block *Entry) { SHAPE_SWITCH(Root, { if (Simple->Inner->BranchVar) LastLoop = NULL; // a switch clears out the loop (TODO: only for breaks, not continue) - // If there is a next block, we already know at Simple creation time to make direct branches, - // and we can do nothing more. If there is no next however, then Natural is where we will - // go to by doing nothing, so we can potentially optimize some branches to direct. if (Simple->Next) { + if (!Simple->Inner->BranchVar && Simple->Inner->ProcessedBranchesOut.size() == 2) { + // If there is a next block, we already know at Simple creation time to make direct branches, + // and we can do nothing more in general. But, we try to optimize the case of a break and + // a direct: This would normally be if (break?) { break; } .. but if we + // make sure to nest the else, we can save the break, if (!break?) { .. } . This is also + // better because the more canonical nested form is easier to further optimize later. The + // downside is more nesting, which adds to size in builds with whitespace. + // Note that we avoid switches, as it complicates control flow and is not relevant + // for the common case we optimize here. + bool Found = false; + bool Abort = false; + for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) { + Block *Target = iter->first; + Branch *Details = iter->second; + if (Details->Type == Branch::Break) { + Found = true; + if (!contains(NaturalBlocks, Target)) Abort = true; + } else if (Details->Type != Branch::Direct) { + Abort = true; + } + } + if (Found && !Abort) { + for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) { + Block *Target = iter->first; + Branch *Details = iter->second; + if (Details->Type == Branch::Break) { + Details->Type = Branch::Direct; + if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) { + Multiple->NeedLoop--; + } + } else { + assert(Details->Type == Branch::Direct); + Details->Type = Branch::Nested; + } + } + } + } Next = Simple->Next; } else { + // If there is no next then Natural is where we will + // go to by doing nothing, so we can potentially optimize some branches to direct. for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) { Block *Target = iter->first; Branch *Details = iter->second; @@ -1140,7 +1181,7 @@ void Relooper::Calculate(Block *Entry) { for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) { Block *Target = iter->first; Branch *Details = iter->second; - if (Details->Type != Branch::Direct) { + if (Details->Type == Branch::Break || Details->Type == Branch::Continue) { assert(LoopStack.size() > 0); if (Details->Ancestor != LoopStack.top() && Details->Labeled) { LabeledShape *Labeled = Shape::IsLabeled(Details->Ancestor); diff --git a/src/relooper/Relooper.h b/src/relooper/Relooper.h index 85adf359..152bae0e 100644 --- a/src/relooper/Relooper.h +++ b/src/relooper/Relooper.h @@ -24,9 +24,11 @@ struct Shape; // Info about a branching from one block to another struct Branch { enum FlowType { - Direct = 0, // We will directly reach the right location through other means, no need for continue or break + Direct = 0, // We will directly reach the right location through other means, no need for continue or break Break = 1, - Continue = 2 + Continue = 2, + Nested = 3 // This code is directly reached, but we must be careful to ensure it is nested in an if - it is not reached + // unconditionally, other code paths exist alongside it that we need to make sure do not intertwine }; Shape *Ancestor; // If not NULL, this shape is the relevant one for purposes of getting to the target block. We break or continue on it Branch::FlowType Type; // If Ancestor is not NULL, this says whether to break or continue @@ -59,7 +61,7 @@ struct Block { Shape *Parent; // The shape we are directly inside int Id; // A unique identifier, defined when added to relooper. Note that this uniquely identifies a *logical* block - if we split it, the two instances have the same content *and* the same Id const char *Code; // The string representation of the code in this block. Owning pointer (we copy the input) - const char *BranchVar; // If we have more than one branch out, the variable whose value determines where we go + const char *BranchVar; // A variable whose value determines where we go; if this is not NULL, emit a switch on that variable bool IsCheckedMultipleEntry; // If true, we are a multiple entry, so reaching us requires setting the label variable Block(const char *CodeInit, const char *BranchVarInit); diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp index b4ce669c..2b25001b 100644 --- a/src/relooper/test.cpp +++ b/src/relooper/test.cpp @@ -314,5 +314,95 @@ int main() { puts(buffer); } + + if (1) { + Relooper::MakeOutputBuffer(10); + + printf("\n\n-- If chain (optimized) --\n\n"); + + Block *b_a = new Block("// block A\n", NULL); + Block *b_b = new Block("// block B\n", NULL); + Block *b_c = new Block("// block C\n", NULL); + + b_a->AddBranchTo(b_b, "a == 10", NULL); + b_a->AddBranchTo(b_c, NULL, NULL); + + b_b->AddBranchTo(b_c, NULL, NULL); + + Relooper r; + r.AddBlock(b_a); + r.AddBlock(b_b); + r.AddBlock(b_c); + + r.Calculate(b_a); + r.Render(); + + puts(r.GetOutputBuffer()); + } + + if (1) { + Relooper::MakeOutputBuffer(10); + + printf("\n\n-- If chain (optimized) --\n\n"); + + Block *b_a = new Block("// block A\n", NULL); + Block *b_b = new Block("// block B\n", NULL); + Block *b_c = new Block("// block C\n", NULL); + Block *b_d = new Block("// block D\n", NULL); + + b_a->AddBranchTo(b_b, "a == 10", NULL); + b_a->AddBranchTo(b_d, NULL, NULL); + + b_b->AddBranchTo(b_c, "b == 10", NULL); + b_b->AddBranchTo(b_d, NULL, NULL); + + b_c->AddBranchTo(b_d, NULL, NULL); + + Relooper r; + r.AddBlock(b_a); + r.AddBlock(b_b); + r.AddBlock(b_c); + r.AddBlock(b_d); + + r.Calculate(b_a); + r.Render(); + + puts(r.GetOutputBuffer()); + } + + if (1) { + Relooper::MakeOutputBuffer(10); + + printf("\n\n-- If chain (optimized, long) --\n\n"); + + Block *b_a = new Block("// block A\n", NULL); + Block *b_b = new Block("// block B\n", NULL); + Block *b_c = new Block("// block C\n", NULL); + Block *b_d = new Block("// block D\n", NULL); + Block *b_e = new Block("// block E\n", NULL); + + b_a->AddBranchTo(b_b, "a == 10", NULL); + b_a->AddBranchTo(b_e, NULL, NULL); + + b_b->AddBranchTo(b_c, "b == 10", NULL); + b_b->AddBranchTo(b_e, NULL, NULL); + + b_c->AddBranchTo(b_d, "c == 10", NULL); + b_c->AddBranchTo(b_e, NULL, NULL); + + b_d->AddBranchTo(b_e, NULL, NULL); + + Relooper r; + r.AddBlock(b_a); + r.AddBlock(b_b); + r.AddBlock(b_c); + r.AddBlock(b_d); + r.AddBlock(b_e); + + r.Calculate(b_a); + r.Render(); + + puts(r.GetOutputBuffer()); + } } diff --git a/src/relooper/test.txt b/src/relooper/test.txt index 82b02ad7..1fa205ba 100644 --- a/src/relooper/test.txt +++ b/src/relooper/test.txt @@ -360,3 +360,42 @@ } } + + +-- If chain (optimized) -- + + // block A + if (a == 10) { + // block B + } + // block C + + + +-- If chain (optimized) -- + + // block A + if (a == 10) { + // block B + if (b == 10) { + // block C + } + } + // block D + + + +-- If chain (optimized, long) -- + + // block A + if (a == 10) { + // block B + if (b == 10) { + // block C + if (c == 10) { + // block D + } + } + } + // block E + -- cgit v1.2.3-18-g5258