remove break labels more aggresively, with a refined natural flow analysis1.4.9

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()