From 34278eef421e19e0df84195aeaf28724b9fccead Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Thu, 26 Dec 2013 15:08:43 -0800 Subject: support for optional complete emulation in relooper --- src/relooper/Relooper.cpp | 38 ++++++++++++++++++++++++++++++-------- src/relooper/Relooper.h | 20 +++++++++++++++----- src/relooper/fuzzer.py | 6 ++++++ src/relooper/test.cpp | 28 ++++++++++++++++++++++++++++ src/relooper/test.txt | 44 ++++++++++++++++++++++++++++++++++++++++++++ tools/shared.py | 2 +- 6 files changed, 124 insertions(+), 14 deletions(-) diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp index d2a48f63..fc7b3ea7 100644 --- a/src/relooper/Relooper.cpp +++ b/src/relooper/Relooper.cpp @@ -142,6 +142,7 @@ void Block::Render(bool InLoop) { if (!ProcessedBranchesOut.size()) return; bool SetLabel = true; // in some cases it is clear we can avoid setting label, see later + bool ForceSetLabel = Shape::IsEmulated(Parent); // A setting of the label variable (label = x) is necessary if it can // cause an impact. The main case is where we set label to x, then elsewhere @@ -210,7 +211,7 @@ void Block::Render(bool InLoop) { Target = DefaultTarget; Details = ProcessedBranchesOut[DefaultTarget]; } - bool SetCurrLabel = SetLabel && Target->IsCheckedMultipleEntry; + bool SetCurrLabel = (SetLabel && Target->IsCheckedMultipleEntry) || ForceSetLabel; bool HasFusedContent = Fused && contains(Fused->InnerMap, Target); bool HasContent = SetCurrLabel || Details->Type != Branch::Direct || HasFusedContent || Details->Code; if (iter != ProcessedBranchesOut.end()) { @@ -330,16 +331,19 @@ void LoopShape::Render(bool InLoop) { if (Next) Next->Render(InLoop); }; -/* // EmulatedShape void EmulatedShape::Render(bool InLoop) { + PrintIndented("label = %d;\n", Entry->Id); + if (Labeled) { + PrintIndented("L%d: ", Id); + } PrintIndented("while(1) {\n"); Indenter::Indent(); - PrintIndented("switch(label) {\n"); + PrintIndented("switch(label|0) {\n"); Indenter::Indent(); - for (int i = 0; i < Blocks.size(); i++) { - Block *Curr = Blocks[i]; + for (BlockSet::iterator iter = Blocks.begin(); iter != Blocks.end(); iter++) { + Block *Curr = *iter; PrintIndented("case %d: {\n", Curr->Id); Indenter::Indent(); Curr->Render(InLoop); @@ -353,11 +357,10 @@ void EmulatedShape::Render(bool InLoop) { PrintIndented("}\n"); if (Next) Next->Render(InLoop); }; -*/ // Relooper -Relooper::Relooper() : Root(NULL) { +Relooper::Relooper() : Root(NULL), Emulate(false) { } Relooper::~Relooper() { @@ -461,7 +464,7 @@ void Relooper::Calculate(Block *Entry) { } } - Pre.SplitDeadEnds(); + if (!Emulate) Pre.SplitDeadEnds(); // Recursively process the graph @@ -526,6 +529,21 @@ void Relooper::Calculate(Block *Entry) { return Simple; } + Shape *MakeEmulated(BlockSet &Blocks, Block *Entry, BlockSet &NextEntries) { + PrintDebug("creating emulated block with entry #%d and everything it can reach, %d blocks\n", Entry->Id, Blocks.size()); + EmulatedShape *Emulated = new EmulatedShape; + Notice(Emulated); + Emulated->Entry = Entry; + for (BlockSet::iterator iter = Blocks.begin(); iter != Blocks.end(); iter++) { + Block *Curr = *iter; + Emulated->Blocks.insert(Curr); + Curr->Parent = Emulated; + Solipsize(Curr, Branch::Continue, Emulated, Blocks); + } + Blocks.clear(); + return Emulated; + } + Shape *MakeLoop(BlockSet &Blocks, BlockSet& Entries, BlockSet &NextEntries) { // Find the inner blocks in this loop. Proceed backwards from the entries until // you reach a seen block, collecting as you go. @@ -837,6 +855,9 @@ void Relooper::Calculate(Block *Entry) { if (Entries->size() == 0) return Ret; if (Entries->size() == 1) { Block *Curr = *(Entries->begin()); + if (Parent->Emulate) { + Make(MakeEmulated(Blocks, Curr, *NextEntries)); + } if (Curr->BranchesIn.size() == 0) { // One entry, no looping ==> Simple Make(MakeSimple(Blocks, Curr, *NextEntries)); @@ -844,6 +865,7 @@ void Relooper::Calculate(Block *Entry) { // One entry, looping ==> Loop Make(MakeLoop(Blocks, *Entries, *NextEntries)); } + // More than one entry, try to eliminate through a Multiple groups of // independent blocks from an entry/ies. It is important to remove through // multiples as opposed to looping since the former is more performant. diff --git a/src/relooper/Relooper.h b/src/relooper/Relooper.h index f3dedf8c..e78d18e7 100644 --- a/src/relooper/Relooper.h +++ b/src/relooper/Relooper.h @@ -96,6 +96,7 @@ class SimpleShape; class LabeledShape; class MultipleShape; class LoopShape; +class EmulatedShape; struct Shape { int Id; // A unique identifier. Used to identify loops, labels are Lx where x is the Id. @@ -105,7 +106,8 @@ struct Shape { enum ShapeType { Simple, Multiple, - Loop + Loop, + Emulated }; ShapeType Type; @@ -118,6 +120,7 @@ struct Shape { static MultipleShape *IsMultiple(Shape *It) { return It && It->Type == Multiple ? (MultipleShape*)It : NULL; } static LoopShape *IsLoop(Shape *It) { return It && It->Type == Loop ? (LoopShape*)It : NULL; } static LabeledShape *IsLabeled(Shape *It) { return IsMultiple(It) || IsLoop(It) ? (LabeledShape*)It : NULL; } + static EmulatedShape *IsEmulated(Shape *It) { return It && It->Type == Emulated ? (EmulatedShape*)It : NULL; } // INTERNAL static int IdCounter; @@ -162,12 +165,15 @@ struct LoopShape : public LabeledShape { void Render(bool InLoop); }; -/* -struct EmulatedShape : public Shape { - std::deque Blocks; +// TODO EmulatedShape is only partially functional. Currently it can be used for the +// entire set of blocks being relooped, but not subsets. +struct EmulatedShape : public LabeledShape { + Block *Entry; + BlockSet Blocks; + + EmulatedShape() : LabeledShape(Emulated) { Labeled = true; } void Render(bool InLoop); }; -*/ // Implements the relooper algorithm for a function's blocks. // @@ -184,6 +190,7 @@ struct Relooper { std::deque Blocks; std::deque Shapes; Shape *Root; + bool Emulate; Relooper(); ~Relooper(); @@ -204,6 +211,9 @@ struct Relooper { // Sets asm.js mode on or off (default is off) static void SetAsmJSMode(int On); + + // Sets whether we must emulate everything with switch-loop code + void SetEmulate(int E) { Emulate = E; } }; typedef std::map BlockBlockSetMap; diff --git a/src/relooper/fuzzer.py b/src/relooper/fuzzer.py index 50846d10..fa47583e 100644 --- a/src/relooper/fuzzer.py +++ b/src/relooper/fuzzer.py @@ -87,6 +87,12 @@ int main() { Relooper r; ''' + if random.random() < 0.1: + print 'emulate' + fast += ''' + r.SetEmulate(true); +''' + for i in range(num): fast += ''' r.AddBlock(b%d); ''' % i diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp index fbd9c7aa..773f6ee4 100644 --- a/src/relooper/test.cpp +++ b/src/relooper/test.cpp @@ -258,5 +258,33 @@ int main() { puts(buffer); } + + if (1) { + Relooper::SetOutputBuffer(buffer, sizeof(buffer)); + + printf("\n\n-- If pattern, emulated --\n\n", "the_var"); + + Block *b_a = new Block("// block A\n", NULL); + Block *b_b = new Block("// block B\n", "b_check()"); + Block *b_c = new Block("// block C\n", NULL); + + b_a->AddBranchTo(b_b, "check == 10", "atob();"); + b_a->AddBranchTo(b_c, NULL, "atoc();"); + + b_b->AddBranchTo(b_c, "case 17:", "btoc();"); + b_b->AddBranchTo(b_a, NULL, NULL); + + Relooper r; + r.SetEmulate(true); + r.AddBlock(b_a); + r.AddBlock(b_b); + r.AddBlock(b_c); + + r.Calculate(b_a); + printf("\n\n", "the_var"); + r.Render(); + + puts(buffer); + } } diff --git a/src/relooper/test.txt b/src/relooper/test.txt index 2c530567..9b537fd9 100644 --- a/src/relooper/test.txt +++ b/src/relooper/test.txt @@ -270,3 +270,47 @@ L46: do { } while(0); // block C + + +-- If pattern, emulated -- + + + +L50: while(1) { + switch(label) { + case 40: { + // block A + if (check == 10) { + atob(); + label = 41; + continue L50; + } else { + atoc(); + label = 42; + continue L50; + } + break; + } + case 41: { + // block B + switch (b_check()) { + case 17: { + btoc(); + label = 42; + continue L50; + break; + } + default: { + label = 40; + continue L50; + } + } + break; + } + case 42: { + // block C + break; + } + } +} + diff --git a/tools/shared.py b/tools/shared.py index b425c655..20951a12 100644 --- a/tools/shared.py +++ b/tools/shared.py @@ -322,7 +322,7 @@ def find_temp_directory(): # we re-check sanity when the settings are changed) # We also re-check sanity and clear the cache when the version changes -EMSCRIPTEN_VERSION = '1.7.8' +EMSCRIPTEN_VERSION = '1.7.9' def generate_sanity(): return EMSCRIPTEN_VERSION + '|' + get_llvm_target() + '|' + LLVM_ROOT -- cgit v1.2.3-18-g5258