From 507d73ae7b6964031c3090e9330fb50c009df7c1 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Fri, 7 Jun 2013 14:00:12 -0700 Subject: remove break labels more aggresively, with a refined natural flow analysis --- src/relooper/Relooper.cpp | 39 ++- src/relooper/Relooper.h | 1 + src/relooper/test.cpp | 27 ++ src/relooper/test.txt | 17 ++ src/relooper/test3.txt | 4 +- src/relooper/test_inf.txt | 648 +++++++++++++++++++++++----------------------- tools/shared.py | 2 +- 7 files changed, 403 insertions(+), 335 deletions(-) diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp index 19398310..8a6e18b8 100644 --- a/src/relooper/Relooper.cpp +++ b/src/relooper/Relooper.cpp @@ -70,7 +70,7 @@ int Indenter::CurrIndent = 0; // Branch -Branch::Branch(const char *ConditionInit, const char *CodeInit) : Ancestor(NULL), Labeled(false) { +Branch::Branch(const char *ConditionInit, const char *CodeInit) : Ancestor(NULL), Labeled(true) { Condition = ConditionInit ? strdup(ConditionInit) : NULL; Code = CodeInit ? strdup(CodeInit) : NULL; } @@ -951,10 +951,28 @@ void Relooper::Calculate(Block *Entry) { }); } + void FindNaturals(Shape *Root, Shape *Otherwise=NULL) { + if (Root->Next) { + Root->Natural = Root->Next; + FindNaturals(Root->Next, Otherwise); + } else { + Root->Natural = Otherwise; + } + + SHAPE_SWITCH(Root, { + }, { + for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) { + FindNaturals(iter->second, Root->Natural); + } + }, { + FindNaturals(Loop->Inner, Loop->Inner); + }); + } + // Remove unneeded breaks and continues. // A flow operation is trivially unneeded if the shape we naturally get to by normal code // execution is the same as the flow forces us to. - void RemoveUnneededFlows(Shape *Root, Shape *Natural=NULL) { + void RemoveUnneededFlows(Shape *Root, Shape *Natural=NULL, LoopShape *LastLoop=NULL) { BlockSet NaturalBlocks; FollowNaturalFlow(Natural, NaturalBlocks); Shape *Next = Root; @@ -976,16 +994,22 @@ void Relooper::Calculate(Block *Entry) { if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) { Multiple->NeedLoop--; } + } else if (Details->Type == Branch::Break && LastLoop && LastLoop->Natural == Details->Ancestor->Natural) { + // it is important to simplify breaks, as simpler breaks enable other optimizations + Details->Labeled = false; + if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) { + Multiple->NeedLoop--; + } } } } }, { for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) { - RemoveUnneededFlows(iter->second, Multiple->Next); + RemoveUnneededFlows(iter->second, Multiple->Next, Multiple->NeedLoop ? NULL : LastLoop); } Next = Multiple->Next; }, { - RemoveUnneededFlows(Loop->Inner, Loop->Inner); + RemoveUnneededFlows(Loop->Inner, Loop->Inner, Loop); Next = Loop->Next; }); } @@ -1016,7 +1040,7 @@ void Relooper::Calculate(Block *Entry) { Branch *Details = iter->second; if (Details->Type != Branch::Direct) { assert(LoopStack.size() > 0); - if (Details->Ancestor != LoopStack.top()) { + if (Details->Ancestor != LoopStack.top() && Details->Labeled) { LabeledShape *Labeled = Shape::IsLabeled(Details->Ancestor); Labeled->Labeled = true; Details->Labeled = true; @@ -1054,6 +1078,7 @@ void Relooper::Calculate(Block *Entry) { } void Process(Shape *Root) { + FindNaturals(Root); RemoveUnneededFlows(Root); FindLabeledLoops(Root); } @@ -1101,6 +1126,10 @@ void Debugging::Dump(BlockSet &Blocks, const char *prefix) { void Debugging::Dump(Shape *S, const char *prefix) { if (prefix) printf("%s ", prefix); + if (!S) { + printf(" (null)\n"); + return; + } printf(" %d ", S->Id); SHAPE_SWITCH(S, { printf("<< Simple with block %d\n", Simple->Inner->Id); diff --git a/src/relooper/Relooper.h b/src/relooper/Relooper.h index 34b6db08..fe56a133 100644 --- a/src/relooper/Relooper.h +++ b/src/relooper/Relooper.h @@ -101,6 +101,7 @@ class LoopShape; struct Shape { int Id; // A unique identifier. Used to identify loops, labels are Lx where x is the Id. 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, diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp index 7da990b5..b2d500d7 100644 --- a/src/relooper/test.cpp +++ b/src/relooper/test.cpp @@ -231,5 +231,32 @@ int main() { puts(buffer); } + + if (1) { + Relooper::SetOutputBuffer(buffer, sizeof(buffer)); + + printf("\n\n-- conditional loop --\n\n"); + + Block *b_a = new Block("// block A\n"); + Block *b_b = new Block("// block B\n"); + Block *b_c = new Block("// block C\n"); + + b_a->AddBranchTo(b_b, "shouldLoop()"); + b_a->AddBranchTo(b_c, NULL); + + b_b->AddBranchTo(b_b, "moarLoop()"); + b_b->AddBranchTo(b_c, NULL); + + Relooper r; + r.AddBlock(b_a); + r.AddBlock(b_b); + r.AddBlock(b_c); + + r.Calculate(b_a); + printf("\n\n"); + r.Render(); + + puts(buffer); + } } diff --git a/src/relooper/test.txt b/src/relooper/test.txt index d657c6af..b3535592 100644 --- a/src/relooper/test.txt +++ b/src/relooper/test.txt @@ -136,3 +136,20 @@ while(1) { // block F } + + +-- conditional loop -- + + + +// block A +if (shouldLoop()) { + while(1) { + // block B + if (!(moarLoop())) { + break; + } + } +} +// block C + diff --git a/src/relooper/test3.txt b/src/relooper/test3.txt index 696542ef..6049ee48 100644 --- a/src/relooper/test3.txt +++ b/src/relooper/test3.txt @@ -9,7 +9,7 @@ do { } } while(0); LBB3 -L5: do { +do { if (LBB3 -> LBB4) { LBB4 if (!(LBB4 -> LBB5)) { @@ -18,7 +18,7 @@ L5: do { while(1) { LBB5 if (LBB5 -> LBB6) { - break L5; + break; } } } diff --git a/src/relooper/test_inf.txt b/src/relooper/test_inf.txt index 379d2083..1dff59bb 100644 --- a/src/relooper/test_inf.txt +++ b/src/relooper/test_inf.txt @@ -5,35 +5,33 @@ if (uint(i4) >= uint(i5)) { code 1 } code 3 -L5: do { - if (!(i2 == 0)) { - code 4 - while(1) { - code 5 - if (uint(i6) >= uint(i7)) { - code 7 - } else { - code 6 - } - code 8 - if (uint(i6) >= uint(i7)) { - code 10 - } else { - code 9 - } - code 11 - if (uint(i5) >= uint(i6)) { - code 13 - } else { - code 12 - } - code 14 - if (!(i2 != 0)) { - break L5; - } +if (!(i2 == 0)) { + code 4 + while(1) { + code 5 + if (uint(i6) >= uint(i7)) { + code 7 + } else { + code 6 + } + code 8 + if (uint(i6) >= uint(i7)) { + code 10 + } else { + code 9 + } + code 11 + if (uint(i5) >= uint(i6)) { + code 13 + } else { + code 12 + } + code 14 + if (!(i2 != 0)) { + break; } } -} while(0); +} code 15 if (uint(i4) >= uint(i5)) { code 17 @@ -41,179 +39,177 @@ if (uint(i4) >= uint(i5)) { code 16 } code 18 -L26: do { - if (!(i2 == 0)) { - code 19 - while(1) { - code 20 - if (uint(i5) >= uint(i6)) { - code 22 - } else { - code 21 - } - code 23 - if (uint(i5) >= uint(i6)) { - code 25 - } else { - code 24 - } - code 26 - if (uint(i5) >= uint(i6)) { - code 28 - } else { - code 27 - } - code 29 - if (uint(i5) >= uint(i6)) { - code 31 - } else { - code 30 - } - code 32 - if (uint(i5) >= uint(i6)) { - code 34 - } else { - code 33 - } - code 35 - if (uint(i5) >= uint(i6)) { - code 37 - } else { - code 36 - } - code 38 - if (uint(i5) >= uint(i6)) { - code 40 - } else { - code 39 - } - code 41 - if (uint(i5) >= uint(i6)) { - code 43 - } else { - code 42 - } - code 44 - if (uint(i5) >= uint(i6)) { - code 46 - } else { - code 45 - } - code 47 - if (uint(i5) >= uint(i6)) { - code 49 - } else { - code 48 - } - code 50 - if (uint(i5) >= uint(i6)) { - code 52 - } else { - code 51 - } - code 53 - if (uint(i5) >= uint(i6)) { - code 55 - } else { - code 54 - } - code 56 - if (uint(i5) >= uint(i6)) { - code 58 - } else { - code 57 - } - code 59 - if (uint(i5) >= uint(i6)) { - code 61 - } else { - code 60 - } - code 62 - if (uint(i5) >= uint(i6)) { - code 64 - } else { - code 63 - } - code 65 - if (uint(i5) >= uint(i6)) { - code 67 - } else { - code 66 - } - code 68 - if (uint(i5) >= uint(i6)) { - code 70 - } else { - code 69 - } - code 71 - if (uint(i5) >= uint(i6)) { - code 73 - } else { - code 72 - } - code 74 - if (uint(i5) >= uint(i6)) { - code 76 - } else { - code 75 - } - code 77 - if (uint(i5) >= uint(i6)) { - code 79 - } else { - code 78 - } - code 80 - if (uint(i5) >= uint(i6)) { - code 82 - } else { - code 81 - } - code 83 - if (uint(i5) >= uint(i6)) { - code 85 - } else { - code 84 - } - code 86 - if (uint(i5) >= uint(i6)) { - code 88 - } else { - code 87 - } - code 89 - if (uint(i5) >= uint(i6)) { - code 91 - } else { - code 90 - } - code 92 - if (uint(i5) >= uint(i6)) { - code 94 - } else { - code 93 - } - code 95 - if (uint(i5) >= uint(i6)) { - code 97 - } else { - code 96 - } - code 98 - if (uint(i5) >= uint(i6)) { - code 100 - } else { - code 99 - } - code 101 - if (!(i2 != 0)) { - break L26; - } +if (!(i2 == 0)) { + code 19 + while(1) { + code 20 + if (uint(i5) >= uint(i6)) { + code 22 + } else { + code 21 + } + code 23 + if (uint(i5) >= uint(i6)) { + code 25 + } else { + code 24 + } + code 26 + if (uint(i5) >= uint(i6)) { + code 28 + } else { + code 27 + } + code 29 + if (uint(i5) >= uint(i6)) { + code 31 + } else { + code 30 + } + code 32 + if (uint(i5) >= uint(i6)) { + code 34 + } else { + code 33 + } + code 35 + if (uint(i5) >= uint(i6)) { + code 37 + } else { + code 36 + } + code 38 + if (uint(i5) >= uint(i6)) { + code 40 + } else { + code 39 + } + code 41 + if (uint(i5) >= uint(i6)) { + code 43 + } else { + code 42 + } + code 44 + if (uint(i5) >= uint(i6)) { + code 46 + } else { + code 45 + } + code 47 + if (uint(i5) >= uint(i6)) { + code 49 + } else { + code 48 + } + code 50 + if (uint(i5) >= uint(i6)) { + code 52 + } else { + code 51 + } + code 53 + if (uint(i5) >= uint(i6)) { + code 55 + } else { + code 54 + } + code 56 + if (uint(i5) >= uint(i6)) { + code 58 + } else { + code 57 + } + code 59 + if (uint(i5) >= uint(i6)) { + code 61 + } else { + code 60 + } + code 62 + if (uint(i5) >= uint(i6)) { + code 64 + } else { + code 63 + } + code 65 + if (uint(i5) >= uint(i6)) { + code 67 + } else { + code 66 + } + code 68 + if (uint(i5) >= uint(i6)) { + code 70 + } else { + code 69 + } + code 71 + if (uint(i5) >= uint(i6)) { + code 73 + } else { + code 72 + } + code 74 + if (uint(i5) >= uint(i6)) { + code 76 + } else { + code 75 + } + code 77 + if (uint(i5) >= uint(i6)) { + code 79 + } else { + code 78 + } + code 80 + if (uint(i5) >= uint(i6)) { + code 82 + } else { + code 81 + } + code 83 + if (uint(i5) >= uint(i6)) { + code 85 + } else { + code 84 + } + code 86 + if (uint(i5) >= uint(i6)) { + code 88 + } else { + code 87 + } + code 89 + if (uint(i5) >= uint(i6)) { + code 91 + } else { + code 90 + } + code 92 + if (uint(i5) >= uint(i6)) { + code 94 + } else { + code 93 + } + code 95 + if (uint(i5) >= uint(i6)) { + code 97 + } else { + code 96 + } + code 98 + if (uint(i5) >= uint(i6)) { + code 100 + } else { + code 99 + } + code 101 + if (!(i2 != 0)) { + break; } } -} while(0); +} code 102 if (uint(i4) >= uint(i5)) { code 104 @@ -221,137 +217,135 @@ if (uint(i4) >= uint(i5)) { code 103 } code 105 -L143: do { - if (!(i2 == 0)) { - code 106 - while(1) { - code 107 - if (uint(i5) >= uint(i6)) { - code 109 - } else { - code 108 - } - code 110 - if (uint(i5) >= uint(i6)) { - code 112 - } else { - code 111 - } - code 113 - if (uint(i5) >= uint(i6)) { - code 115 - } else { - code 114 - } - code 116 - if (uint(i5) >= uint(i6)) { - code 118 - } else { - code 117 - } - code 119 - if (uint(i5) >= uint(i6)) { - code 121 - } else { - code 120 - } - code 122 - if (uint(i5) >= uint(i6)) { - code 124 - } else { - code 123 - } - code 125 - if (uint(i5) >= uint(i6)) { - code 127 - } else { - code 126 - } - code 128 - if (uint(i5) >= uint(i6)) { - code 130 - } else { - code 129 - } - code 131 - if (uint(i5) >= uint(i6)) { - code 133 - } else { - code 132 - } - code 134 - if (uint(i5) >= uint(i6)) { - code 136 - } else { - code 135 - } - code 137 - if (uint(i5) >= uint(i6)) { - code 139 - } else { - code 138 - } - code 140 - if (uint(i5) >= uint(i6)) { - code 142 - } else { - code 141 - } - code 143 - if (uint(i5) >= uint(i6)) { - code 145 - } else { - code 144 - } - code 146 - if (uint(i5) >= uint(i6)) { - code 148 - } else { - code 147 - } - code 149 - if (uint(i5) >= uint(i6)) { - code 151 - } else { - code 150 - } - code 152 - if (uint(i5) >= uint(i6)) { - code 154 - } else { - code 153 - } - code 155 - if (uint(i5) >= uint(i6)) { - code 157 - } else { - code 156 - } - code 158 - if (uint(i5) >= uint(i6)) { - code 160 - } else { - code 159 - } - code 161 - if (uint(i5) >= uint(i6)) { - code 163 - } else { - code 162 - } - code 164 - if (uint(i5) >= uint(i6)) { - code 166 - } else { - code 165 - } - code 167 - if (!(i2 != 0)) { - break L143; - } +if (!(i2 == 0)) { + code 106 + while(1) { + code 107 + if (uint(i5) >= uint(i6)) { + code 109 + } else { + code 108 + } + code 110 + if (uint(i5) >= uint(i6)) { + code 112 + } else { + code 111 + } + code 113 + if (uint(i5) >= uint(i6)) { + code 115 + } else { + code 114 + } + code 116 + if (uint(i5) >= uint(i6)) { + code 118 + } else { + code 117 + } + code 119 + if (uint(i5) >= uint(i6)) { + code 121 + } else { + code 120 + } + code 122 + if (uint(i5) >= uint(i6)) { + code 124 + } else { + code 123 + } + code 125 + if (uint(i5) >= uint(i6)) { + code 127 + } else { + code 126 + } + code 128 + if (uint(i5) >= uint(i6)) { + code 130 + } else { + code 129 + } + code 131 + if (uint(i5) >= uint(i6)) { + code 133 + } else { + code 132 + } + code 134 + if (uint(i5) >= uint(i6)) { + code 136 + } else { + code 135 + } + code 137 + if (uint(i5) >= uint(i6)) { + code 139 + } else { + code 138 + } + code 140 + if (uint(i5) >= uint(i6)) { + code 142 + } else { + code 141 + } + code 143 + if (uint(i5) >= uint(i6)) { + code 145 + } else { + code 144 + } + code 146 + if (uint(i5) >= uint(i6)) { + code 148 + } else { + code 147 + } + code 149 + if (uint(i5) >= uint(i6)) { + code 151 + } else { + code 150 + } + code 152 + if (uint(i5) >= uint(i6)) { + code 154 + } else { + code 153 + } + code 155 + if (uint(i5) >= uint(i6)) { + code 157 + } else { + code 156 + } + code 158 + if (uint(i5) >= uint(i6)) { + code 160 + } else { + code 159 + } + code 161 + if (uint(i5) >= uint(i6)) { + code 163 + } else { + code 162 + } + code 164 + if (uint(i5) >= uint(i6)) { + code 166 + } else { + code 165 + } + code 167 + if (!(i2 != 0)) { + break; } } -} while(0); +} code 168 if (uint(i4) >= uint(i5)) { code 170 diff --git a/tools/shared.py b/tools/shared.py index 4225be26..8a172d9c 100644 --- a/tools/shared.py +++ b/tools/shared.py @@ -295,7 +295,7 @@ def check_node_version(): # 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.4.8' +EMSCRIPTEN_VERSION = '1.4.9' def generate_sanity(): return EMSCRIPTEN_VERSION + '|' + get_llvm_target() -- cgit v1.2.3-18-g5258