diff options
Diffstat (limited to 'src/relooper')
-rw-r--r-- | src/relooper/Relooper.cpp | 48 | ||||
-rw-r--r-- | src/relooper/Relooper.h | 34 | ||||
-rw-r--r-- | src/relooper/fuzzer.py | 6 | ||||
-rw-r--r-- | src/relooper/test.cpp | 28 | ||||
-rw-r--r-- | src/relooper/test.txt | 377 | ||||
-rw-r--r-- | src/relooper/test2.txt | 40 | ||||
-rw-r--r-- | src/relooper/test3.txt | 82 | ||||
-rw-r--r-- | src/relooper/test4.txt | 52 | ||||
-rw-r--r-- | src/relooper/test5.txt | 104 | ||||
-rw-r--r-- | src/relooper/test6.txt | 38 | ||||
-rw-r--r-- | src/relooper/test_dead.txt | 2 | ||||
-rw-r--r-- | src/relooper/test_debug.txt | 62 | ||||
-rw-r--r-- | src/relooper/test_fuzz1.txt | 100 | ||||
-rw-r--r-- | src/relooper/test_fuzz2.txt | 42 | ||||
-rw-r--r-- | src/relooper/test_fuzz3.txt | 36 | ||||
-rw-r--r-- | src/relooper/test_fuzz4.txt | 56 | ||||
-rw-r--r-- | src/relooper/test_fuzz5.txt | 122 | ||||
-rw-r--r-- | src/relooper/test_fuzz6.txt | 358 | ||||
-rw-r--r-- | src/relooper/test_inf.txt | 1606 | ||||
-rwxr-xr-x | src/relooper/testit.sh | 30 |
20 files changed, 1663 insertions, 1560 deletions
diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp index d2a48f63..70cf844b 100644 --- a/src/relooper/Relooper.cpp +++ b/src/relooper/Relooper.cpp @@ -101,9 +101,7 @@ void Branch::Render(Block *Target, bool SetLabel) { // Block -int Block::IdCounter = 1; // 0 is reserved for clearings - -Block::Block(const char *CodeInit, const char *BranchVarInit) : Parent(NULL), Id(Block::IdCounter++), IsCheckedMultipleEntry(false) { +Block::Block(const char *CodeInit, const char *BranchVarInit) : Parent(NULL), Id(-1), IsCheckedMultipleEntry(false) { Code = strdup(CodeInit); BranchVar = BranchVarInit ? strdup(BranchVarInit) : NULL; } @@ -142,6 +140,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 +209,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()) { @@ -272,10 +271,6 @@ void Block::Render(bool InLoop) { } } -// Shape - -int Shape::IdCounter = 0; - // MultipleShape void MultipleShape::RenderLoopPrefix() { @@ -330,16 +325,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 +351,10 @@ void EmulatedShape::Render(bool InLoop) { PrintIndented("}\n"); if (Next) Next->Render(InLoop); }; -*/ // Relooper -Relooper::Relooper() : Root(NULL) { +Relooper::Relooper() : Root(NULL), Emulate(false), BlockIdCounter(1), ShapeIdCounter(0) { // block ID 0 is reserved for clearings } Relooper::~Relooper() { @@ -366,6 +363,7 @@ Relooper::~Relooper() { } void Relooper::AddBlock(Block *New) { + New->Id = BlockIdCounter++; Blocks.push_back(New); } @@ -461,7 +459,7 @@ void Relooper::Calculate(Block *Entry) { } } - Pre.SplitDeadEnds(); + if (!Emulate) Pre.SplitDeadEnds(); // Recursively process the graph @@ -470,6 +468,7 @@ void Relooper::Calculate(Block *Entry) { // Add a shape to the list of shapes in this Relooper calculation void Notice(Shape *New) { + New->Id = Parent->ShapeIdCounter++; Parent->Shapes.push_back(New); } @@ -526,6 +525,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 +851,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 +861,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..04f2ffc3 100644 --- a/src/relooper/Relooper.h +++ b/src/relooper/Relooper.h @@ -57,7 +57,7 @@ struct Block { BlockBranchMap ProcessedBranchesOut; BlockSet ProcessedBranchesIn; Shape *Parent; // The shape we are directly inside - int Id; // A unique identifier + int Id; // A unique identifier, defined when added to relooper 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 bool IsCheckedMultipleEntry; // If true, we are a multiple entry, so reaching us requires setting the label variable @@ -69,9 +69,6 @@ struct Block { // Prints out the instructions code and branchings void Render(bool InLoop); - - // INTERNAL - static int IdCounter; }; // Represents a structured control flow shape, one of @@ -96,20 +93,22 @@ 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. + int Id; // A unique identifier. Used to identify loops, labels are Lx where x is the Id. Defined when added to relooper Shape *Next; // The shape that will appear in the code right after this one Shape *Natural; // The shape that control flow gets to naturally (if there is Next, then this is Next) enum ShapeType { Simple, Multiple, - Loop + Loop, + Emulated }; ShapeType Type; - Shape(ShapeType TypeInit) : Id(Shape::IdCounter++), Next(NULL), Type(TypeInit) {} + Shape(ShapeType TypeInit) : Id(-1), Next(NULL), Type(TypeInit) {} virtual ~Shape() {} virtual void Render(bool InLoop) = 0; @@ -118,9 +117,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; } - - // INTERNAL - static int IdCounter; + static EmulatedShape *IsEmulated(Shape *It) { return It && It->Type == Emulated ? (EmulatedShape*)It : NULL; } }; struct SimpleShape : public Shape { @@ -162,12 +159,15 @@ struct LoopShape : public LabeledShape { void Render(bool InLoop); }; -/* -struct EmulatedShape : public Shape { - std::deque<Block*> 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 +184,9 @@ struct Relooper { std::deque<Block*> Blocks; std::deque<Shape*> Shapes; Shape *Root; + bool Emulate; + int BlockIdCounter; + int ShapeIdCounter; Relooper(); ~Relooper(); @@ -204,6 +207,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<Block*, BlockSet> 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..540f7bdb 100644 --- a/src/relooper/test.txt +++ b/src/relooper/test.txt @@ -4,23 +4,23 @@ -// block A -switch (the_var) { -check == 10 { - atob(); - // block B + // block A switch (the_var) { + check == 10 { + atob(); + // block B + switch (the_var) { + default: { + btoc(); + } + } + break; + } default: { - btoc(); + atoc(); } } - break; -} -default: { - atoc(); -} -} -// block C + // block C @@ -28,25 +28,25 @@ default: { -// block A -switch (the_var) { -check == 15 { - // block B + // block A switch (the_var) { - default: { - } + check == 15 { + // block B + switch (the_var) { + default: { + } + } + break; } - break; -} -default: { - // block C - switch (the_var) { default: { + // block C + switch (the_var) { + default: { + } + } } } -} -} -// block D + // block D @@ -54,81 +54,81 @@ default: { -L9: while(1) { - // block A - var check = maybe(); - switch (the_var) { - default: { - } - } - // block B - switch (the_var) { - check == 41 { - break; - } - default: { - break L9; - } + L0: while(1) { + // block A + var check = maybe(); + switch (the_var) { + default: { + } + } + // block B + switch (the_var) { + check == 41 { + break; + } + default: { + break L0; + } + } } -} -// block C + // block C -- Loop with phi to head -// code 1 -switch (the_var) { -default: { - var $i_0 = 0;var $x_0 = 5; -} -} -L14: while(1) { - // code 2 + // code 1 switch (the_var) { - $2 { - break; - } default: { - var $x_1 = $x_0; - label = 18; - break L14; + var $i_0 = 0;var $x_0 = 5; + } + } + L1: while(1) { + // code 2 + switch (the_var) { + $2 { + break; + } + default: { + var $x_1 = $x_0; + label = -1; + break L1; + } + } + // code 3 + switch (the_var) { + $6 { + break L1; + break; + } + default: { + var $i_0 = $7;var $x_0 = $5; + } + } } + if (label == -1) { + // code 7 } - // code 3 + // code 4 switch (the_var) { - $6 { - break L14; + $10 { + // code 5 + switch (the_var) { + default: { + } + } break; } default: { - var $i_0 = $7;var $x_0 = $5; } } -} -if (label == 18) { - // code 7 -} -// code 4 -switch (the_var) { -$10 { - // code 5 + // code 6 switch (the_var) { default: { + var $x_1 = $13; } } - break; -} -default: { -} -} -// code 6 -switch (the_var) { -default: { - var $x_1 = $13; -} -} -// code 7 + // code 7 @@ -136,30 +136,30 @@ default: { -// block A................................................................................................... -switch (the_var) { -chak() { - atob(); - // block B................................................................................................... + // block A................................................................................................... switch (the_var) { - default: { - btod(); - } + chak() { + atob(); + // block B................................................................................................... + switch (the_var) { + default: { + btod(); + } + } + // block D + break; } - // block D - break; -} -default: { - atoc(); - // block C................................................................................................... - switch (the_var) { default: { - ctod2(); + atoc(); + // block C................................................................................................... + switch (the_var) { + default: { + ctod2(); + } + } + // block D } } - // block D -} -} @@ -167,27 +167,27 @@ default: { -// block A -switch (the_var) { -check == 10 { - break; -} -default: { - return C; -} -} -while(1) { - // block B + // block A switch (the_var) { - default: { - } + check == 10 { + break; } - // block D - switch (the_var) { default: { + return C; } } -} + while(1) { + // block B + switch (the_var) { + default: { + } + } + // block D + switch (the_var) { + default: { + } + } + } @@ -195,51 +195,51 @@ while(1) { -// block A -L37: do { - switch (the_var) { - expensive() { - label = 33; - break; - } - default: { - // block B + // block A + L1: do { switch (the_var) { - expensive2() { - label = 33; - break L37; + expensive() { + label = 3; break; } default: { + // block B + switch (the_var) { + expensive2() { + label = 3; + break L1; + break; + } + default: { + } + } + // block D + switch (the_var) { + default: { + } + } } } - // block D + } while(0); + if (label == 3) { + // block C; switch (the_var) { default: { } } } + while(1) { + // block E + switch (the_var) { + default: { + } + } + // block F + switch (the_var) { + default: { + } + } } -} while(0); -if (label == 33) { - // block C; - switch (the_var) { - default: { - } - } -} -while(1) { - // block E - switch (the_var) { - default: { - } - } - // block F - switch (the_var) { - default: { - } - } -} @@ -247,26 +247,71 @@ while(1) { -// block A -L46: do { - switch (the_var) { - shouldLoop() { - while(1) { - // block B - switch (the_var) { - moarLoop() { + // block A + L1: do { + switch (the_var) { + shouldLoop() { + while(1) { + // block B + switch (the_var) { + moarLoop() { + break; + } + default: { + break L1; + } + } + } + break; + } + default: { + } + } + } while(0); + // block C + + + +-- If pattern, emulated -- + + + + label = 1; + L0: while(1) { + switch(label|0) { + case 3: { + // block C break; } - default: { - break L46; + case 1: { + // block A + if (check == 10) { + atob(); + label = 2; + continue L0; + } else { + atoc(); + label = 3; + continue L0; + } + break; } + case 2: { + // block B + switch (b_check()) { + case 17: { + btoc(); + label = 3; + continue L0; + break; + } + default: { + label = 1; + continue L0; + } + } + break; } } - break; - } - default: { - } } -} while(0); -// block C diff --git a/src/relooper/test2.txt b/src/relooper/test2.txt index a558a8b7..aba9ec1f 100644 --- a/src/relooper/test2.txt +++ b/src/relooper/test2.txt @@ -1,26 +1,26 @@ -ep -L1: do { - switch (var) { - ep -> LBB1 { - LBB1 - switch (the_var) { - LBB1 -> LBB2 { + ep + L1: do { + switch (var) { + ep -> LBB1 { + LBB1 + switch (the_var) { + LBB1 -> LBB2 { + break; + } + default: { + break L1; + } + } + LBB2 + switch (the_var) { + default: { + } + } break; } default: { - break L1; } } - LBB2 - switch (the_var) { - default: { - } - } - break; - } - default: { - } - } -} while(0); -LBB3 + } while(0); + LBB3 diff --git a/src/relooper/test3.txt b/src/relooper/test3.txt index f77e2618..33f85a7e 100644 --- a/src/relooper/test3.txt +++ b/src/relooper/test3.txt @@ -1,56 +1,56 @@ -ep -L1: do { - switch (the_var) { - ep -> LBB1 { - LBB1 + ep + L1: do { switch (the_var) { - LBB1 -> LBB2 { + ep -> LBB1 { + LBB1 + switch (the_var) { + LBB1 -> LBB2 { + break; + } + default: { + break L1; + } + } + LBB2 + switch (the_var) { + default: { + } + } break; } default: { - break L1; - } - } - LBB2 - switch (the_var) { - default: { } } - break; - } - default: { - } - } -} while(0); -LBB3 -L5: do { - switch (the_var) { - LBB3 -> LBB4 { - LBB4 + } while(0); + LBB3 + L5: do { switch (the_var) { - LBB4 -> LBB5 { - break; - } - default: { - break L5; - } - } - while(1) { - LBB5 + LBB3 -> LBB4 { + LBB4 switch (the_var) { - LBB5 -> LBB6 { - break L5; + LBB4 -> LBB5 { break; } default: { + break L5; + } } + while(1) { + LBB5 + switch (the_var) { + LBB5 -> LBB6 { + break L5; + break; + } + default: { + } + } } + break; + } + default: { + } } - break; - } - default: { - } - } -} while(0); -LBB6 + } while(0); + LBB6 diff --git a/src/relooper/test4.txt b/src/relooper/test4.txt index 1829e523..7e3fe8e1 100644 --- a/src/relooper/test4.txt +++ b/src/relooper/test4.txt @@ -1,44 +1,44 @@ -//19 -L1: do { - switch (the_var) { - 1 { - //20 + //19 + L1: do { switch (the_var) { 1 { + //20 + switch (the_var) { + 1 { + break; + } + default: { + label = 4; + break L1; + } + } + //21 + switch (the_var) { + default: { + } + } break; } default: { label = 4; - break L1; } } - //21 + } while(0); + if (label == 4) { + //22 switch (the_var) { default: { } } - break; - } - default: { - label = 4; } - } -} while(0); -if (label == 4) { - //22 + //23 switch (the_var) { + 1 { + //24 + break; + } default: { + //28 } } -} -//23 -switch (the_var) { - 1 { - //24 - break; -} -default: { - //28 -} -} diff --git a/src/relooper/test5.txt b/src/relooper/test5.txt index 82ef5edf..e3c204f6 100644 --- a/src/relooper/test5.txt +++ b/src/relooper/test5.txt @@ -1,56 +1,56 @@ -//0 -switch (the_var) { -check(0) { - L2: while(1) { - //1 - switch (the_var) { - check(1) { - break; - } - default: { - break L2; - } - } + //0 + switch (the_var) { + check(0) { + L2: while(1) { + //1 + switch (the_var) { + check(1) { + break; + } + default: { + break L2; + } + } + } + L4: while(1) { + //2 + switch (the_var) { + check(2) { + break; + } + default: { + break L4; + } + } + } + //3 + break; } - L4: while(1) { - //2 - switch (the_var) { - check(2) { - break; - } - default: { - break L4; - } - } + default: { + goingFrom0to4(); + L7: while(1) { + //4 + switch (the_var) { + check(4) { + break; + } + default: { + break L7; + } + } + } + L9: while(1) { + //5 + switch (the_var) { + check(5) { + break L9; + break; + } + default: { + } + } + } + //3 } - //3 - break; -} -default: { - goingFrom0to4(); - L7: while(1) { - //4 - switch (the_var) { - check(4) { - break; - } - default: { - break L7; - } - } - } - L9: while(1) { - //5 - switch (the_var) { - check(5) { - break L9; - break; - } - default: { - } - } } - //3 -} -} diff --git a/src/relooper/test6.txt b/src/relooper/test6.txt index f9d6e93a..837fc243 100644 --- a/src/relooper/test6.txt +++ b/src/relooper/test6.txt @@ -1,26 +1,26 @@ -//0 -L1: do { - switch (the_var) { - check(0) { - //1 + //0 + L1: do { switch (the_var) { - check(1) { + check(0) { + //1 + switch (the_var) { + check(1) { + break; + } + default: { + break L1; + } + } + //2 + switch (the_var) { + default: { + } + } break; } default: { - break L1; } } - //2 - switch (the_var) { - default: { - } - } - break; - } - default: { - } - } -} while(0); -//3 + } while(0); + //3 diff --git a/src/relooper/test_dead.txt b/src/relooper/test_dead.txt index ae54e2cd..43d557ae 100644 --- a/src/relooper/test_dead.txt +++ b/src/relooper/test_dead.txt @@ -4,6 +4,6 @@ -// block A + // block A I did not crash even though I have dead code with a branch! diff --git a/src/relooper/test_debug.txt b/src/relooper/test_debug.txt index eb33fdbc..498dee39 100644 --- a/src/relooper/test_debug.txt +++ b/src/relooper/test_debug.txt @@ -4,18 +4,18 @@ int main() { rl_set_output_buffer(buffer); void *block_map[10000]; void *rl = rl_new_relooper(); - void *b1 = rl_new_block("// code 1"); - block_map[1] = b1; - rl_relooper_add_block(rl, block_map[1]); - void *b2 = rl_new_block("// code 2"); |