diff options
Diffstat (limited to 'src/relooper')
-rw-r--r-- | src/relooper/Relooper.cpp | 12 | ||||
-rw-r--r-- | src/relooper/Relooper.h | 14 | ||||
-rw-r--r-- | src/relooper/test.txt | 401 | ||||
-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 |
17 files changed, 1560 insertions, 1567 deletions
diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp index fc7b3ea7..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; } @@ -273,10 +271,6 @@ void Block::Render(bool InLoop) { } } -// Shape - -int Shape::IdCounter = 0; - // MultipleShape void MultipleShape::RenderLoopPrefix() { @@ -360,7 +354,7 @@ void EmulatedShape::Render(bool InLoop) { // Relooper -Relooper::Relooper() : Root(NULL), Emulate(false) { +Relooper::Relooper() : Root(NULL), Emulate(false), BlockIdCounter(1), ShapeIdCounter(0) { // block ID 0 is reserved for clearings } Relooper::~Relooper() { @@ -369,6 +363,7 @@ Relooper::~Relooper() { } void Relooper::AddBlock(Block *New) { + New->Id = BlockIdCounter++; Blocks.push_back(New); } @@ -473,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); } diff --git a/src/relooper/Relooper.h b/src/relooper/Relooper.h index e78d18e7..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 @@ -99,7 +96,7 @@ 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) @@ -111,7 +108,7 @@ struct Shape { }; 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; @@ -121,9 +118,6 @@ struct Shape { 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; }; struct SimpleShape : public Shape { @@ -191,6 +185,8 @@ struct Relooper { std::deque<Shape*> Shapes; Shape *Root; bool Emulate; + int BlockIdCounter; + int ShapeIdCounter; Relooper(); ~Relooper(); diff --git a/src/relooper/test.txt b/src/relooper/test.txt index 9b537fd9..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,49 +167,18 @@ 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; } } -} - - - --- if (expensive || expensive2) X else Y; Z -- - - - -// block A -L37: do { - switch (the_var) { - expensive() { - label = 33; - break; - } - default: { + while(1) { // block B switch (the_var) { - expensive2() { - label = 33; - break L37; - break; - } default: { } } @@ -219,98 +188,130 @@ L37: do { } } } - } -} 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: { - } - } -} --- conditional loop -- +-- if (expensive || expensive2) X else Y; Z -- -// block A -L46: do { - switch (the_var) { - shouldLoop() { - while(1) { + // block A + L1: do { + switch (the_var) { + expensive() { + label = 3; + break; + } + default: { // block B switch (the_var) { - moarLoop() { + expensive2() { + label = 3; + break L1; break; } default: { - break L46; + } + } + // block D + switch (the_var) { + default: { } } } - break; - } - default: { + } + } 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); -// block C --- If pattern, emulated -- +-- conditional loop -- -L50: while(1) { - switch(label) { - case 40: { - // block A - if (check == 10) { - atob(); - label = 41; - continue L50; - } else { - atoc(); - label = 42; - continue L50; + // block A + L1: do { + switch (the_var) { + shouldLoop() { + while(1) { + // block B + switch (the_var) { + moarLoop() { + break; + } + default: { + break L1; + } + } } break; } - case 41: { - // block B - switch (b_check()) { - case 17: { - btoc(); - label = 42; - continue L50; + default: { + } + } + } while(0); + // block C + + + +-- If pattern, emulated -- + + + + label = 1; + L0: while(1) { + switch(label|0) { + case 3: { + // block C break; } - default: { - label = 40; - continue L50; + 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; - } - case 42: { - // block C - break; } } -} 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"); - block_map[2] = b2; - rl_relooper_add_block(rl, block_map[2]); - void *b3 = rl_new_block("// code 3"); - block_map[3] = b3; - rl_relooper_add_block(rl, block_map[3]); - void *b4 = rl_new_block("// code 4"); - block_map[4] = b4; - rl_relooper_add_block(rl, block_map[4]); + void *b-1 = rl_new_block("// code -1"); + block_map[-1] = b-1; + rl_relooper_add_block(rl, block_map[-1]); + void *b-1 = rl_new_block("// code -1"); + block_map[-1] = b-1; + rl_relooper_add_block(rl, block_map[-1]); + void *b-1 = rl_new_block("// code -1"); + block_map[-1] = b-1; + rl_relooper_add_block(rl, block_map[-1]); + void *b-1 = rl_new_block("// code -1"); + block_map[-1] = b-1; + rl_relooper_add_block(rl, block_map[-1]); rl_block_add_branch_to(block_map[1], block_map[2], "ep -> LBB1", NULL); rl_block_add_branch_to(block_map[1], block_map[4], NULL, NULL); rl_block_add_branch_to(block_map[2], block_map[3], "LBB1 -> LBB2", NULL); @@ -114,29 +114,29 @@ int main() { // Process() returning // === Optimizing shapes === // Fusing Multiple to Simple -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 + } while(0); + LBB3 diff --git a/src/relooper/test_fuzz1.txt b/src/relooper/test_fuzz1.txt index d887f5b8..ccd38934 100644 --- a/src/relooper/test_fuzz1.txt +++ b/src/relooper/test_fuzz1.txt @@ -1,72 +1,72 @@ -print('entry'); var label; var state; var decisions = [4, 1, 7, 2, 6, 6, 8]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } -switch (the_var) { -default: { -} -} -print(5); state = check(); -switch (the_var) { -default: { -} -} -print(6); state = check(); -switch (the_var) { -state == 7 { - print(7); state = check(); + print('entry'); var label; var state; var decisions = [4, 1, 7, 2, 6, 6, 8]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } switch (the_var) { default: { - label = 3; } } - break; -} -default: { -} -} -L5: while(1) { - if (label == 3) { - label = 0; - print(2); state = check(); + print(5); state = check(); + switch (the_var) { + default: { + } + } + print(6); state = check(); + switch (the_var) { + state == 7 { + print(7); state = check(); switch (the_var) { default: { + label = 3; } } + break; } - print(1); state = check(); - switch (the_var) { default: { } } - while(1) { - print(3); state = check(); - switch (the_var) { - state == 8 { - break; + L5: while(1) { + if (label == 3) { + label = 0; + print(2); state = check(); + switch (the_var) { + default: { + } + } } - default: { - continue L5; - } - } - print(8); state = check(); + print(1); state = check(); switch (the_var) { - state == 4 { - break; - } default: { - label = 3; - continue L5; } } - print(4); state = check(); - switch (the_var) { - state == 3 { - break; - } - default: { - continue L5; - } + while(1) { + print(3); state = check(); + switch (the_var) { + state == 8 { + break; + } + default: { + continue L5; + } + } + print(8); state = check(); + switch (the_var) { + state == 4 { + break; + } + default: { + label = 3; + continue L5; + } + } + print(4); state = check(); + switch (the_var) { + state == 3 { + break; + } + default: { + continue L5; + } + } } } -} diff --git a/src/relooper/test_fuzz2.txt b/src/relooper/test_fuzz2.txt index 69f4350c..a94908a1 100644 --- a/src/relooper/test_fuzz2.txt +++ b/src/relooper/test_fuzz2.txt @@ -1,30 +1,30 @@ -print('entry'); var label; var state; var decisions = [4, 1, 4, 3, 4, 1, 2, 5, 1, 3, 5, 5, 1, 5, 2, 4, 4, 3]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } -switch (the_var) { -state == 1 { - while(1) { - print(1); state = check(); - switch (the_var) { - default: { - } + print('entry'); var label; var state; var decisions = [4, 1, 4, 3, 4, 1, 2, 5, 1, 3, 5, 5, 1, 5, 2, 4, 4, 3]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } + switch (the_var) { + state == 1 { + while(1) { + print(1); state = check(); + switch (the_var) { + default: { + } + } } + break; } - break; -} -default: { -} -} -while(1) { - print(3); state = check(); - switch (the_var) { default: { } } - print(2); state = check(); - switch (the_var) { - default: { - } + while(1) { + print(3); state = check(); + switch (the_var) { + default: { + } + } + print(2); state = check(); + switch (the_var) { + default: { + } + } } -} diff --git a/src/relooper/test_fuzz3.txt b/src/relooper/test_fuzz3.txt index 398b4803..15037eec 100644 --- a/src/relooper/test_fuzz3.txt +++ b/src/relooper/test_fuzz3.txt @@ -1,25 +1,25 @@ -print('entry'); var label; var state; var decisions = [3, 3, 4, 1, 2, 1, 2, 4, 4, 4, 2, 3, 3, 1, 2]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } -switch (the_var) { -default: { -} -} -print(1); state = check(); -switch (the_var) { -default: { -} -} -print(3); state = check(); -switch (the_var) { -default: { -} -} -while(1) { - print(4); state = check(); + print('entry'); var label; var state; var decisions = [3, 3, 4, 1, 2, 1, 2, 4, 4, 4, 2, 3, 3, 1, 2]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } switch (the_var) { default: { } } -} + print(1); state = check(); + switch (the_var) { + default: { + } + } + print(3); state = check |