relooper update

2 files changed, 80 insertions, 48 deletions

diff --git a/lib/Target/JSBackend/Relooper.cpp b/lib/Target/JSBackend/Relooper.cpp
index 780a6d5930..ce9232d994 100644
--- a/lib/Target/JSBackend/Relooper.cpp
+++ b/lib/Target/JSBackend/Relooper.cpp
@@ -243,7 +243,7 @@ void Block::Render(bool InLoop) {
       Details = ProcessedBranchesOut[DefaultTarget];
     }
     bool SetCurrLabel = (SetLabel && Target->IsCheckedMultipleEntry) || ForceSetLabel;
-    bool HasFusedContent = Fused && contains(Fused->InnerMap, Target);
+    bool HasFusedContent = Fused && contains(Fused->InnerMap, Target->Id);
     bool HasContent = SetCurrLabel || Details->Type != Branch::Direct || HasFusedContent || Details->Code;
     if (iter != ProcessedBranchesOut.end()) {
       // If there is nothing to show in this branch, omit the condition
@@ -286,7 +286,7 @@ void Block::Render(bool InLoop) {
     if (!First) Indenter::Indent();
     Details->Render(Target, SetCurrLabel);
     if (HasFusedContent) {
-      Fused->InnerMap.find(Target)->second->Render(InLoop);
+      Fused->InnerMap.find(Target->Id)->second->Render(InLoop);
     } else if (Details->Type == Branch::Nested) {
       // Nest the parent content here, and remove it from showing up afterwards as Next
       assert(Parent->Next);
@@ -312,18 +312,28 @@ void Block::Render(bool InLoop) {
 // MultipleShape
 
 void MultipleShape::RenderLoopPrefix() {
-  if (NeedLoop) {
-    if (Labeled) {
-      PrintIndented("L%d: do {\n", Id);
+  if (Breaks) {
+    if (UseSwitch) {
+      if (Labeled) {
+        PrintIndented("L%d: ", Id);
+      }
     } else {
-      PrintIndented("do {\n");
+      if (Labeled) {
+        if (UseSwitch) {
+          PrintIndented("L%d: ", Id);
+        } else {
+          PrintIndented("L%d: do {\n", Id);
+        }
+      } else {
+        PrintIndented("do {\n");
+      }
+      Indenter::Indent();
     }
-    Indenter::Indent();
   }
 }
 
 void MultipleShape::RenderLoopPostfix() {
-  if (NeedLoop) {
+  if (Breaks && !UseSwitch) {
     Indenter::Unindent();
     PrintIndented("} while(0);\n");
   }
@@ -332,32 +342,41 @@ void MultipleShape::RenderLoopPostfix() {
 void MultipleShape::Render(bool InLoop) {
   RenderLoopPrefix();
 
-  // We know that blocks with the same Id were split from the same source, so their contents are identical and they are logically the same, so re-merge them here
-  typedef std::map<int, Shape*> IdShapeMap;
-  IdShapeMap IdMap;
-  for (BlockShapeMap::iterator iter = InnerMap.begin(); iter != InnerMap.end(); iter++) {
-    int Id = iter->first->Id;
-    IdShapeMap::iterator Test = IdMap.find(Id);
-    if (Test != IdMap.end()) {
-      assert(Shape::IsSimple(iter->second) && Shape::IsSimple(Test->second)); // we can only merge simple blocks, something horrible has gone wrong if we see anything else
-      continue;
+  if (!UseSwitch) {
+    // emit an if-else chain
+    bool First = true;
+    for (IdShapeMap::iterator iter = InnerMap.begin(); iter != InnerMap.end(); iter++) {
+      if (AsmJS) {
+        PrintIndented("%sif ((label|0) == %d) {\n", First ? "" : "else ", iter->first);
+      } else {
+        PrintIndented("%sif (label == %d) {\n", First ? "" : "else ", iter->first);
+      }
+      First = false;
+      Indenter::Indent();
+      iter->second->Render(InLoop);
+      Indenter::Unindent();
+      PrintIndented("}\n");
     }
-    IdMap[iter->first->Id] = iter->second;
-  }
-
-  bool First = true;
-  for (IdShapeMap::iterator iter = IdMap.begin(); iter != IdMap.end(); iter++) {
+  } else {
+    // emit a switch
     if (AsmJS) {
-      PrintIndented("%sif ((label|0) == %d) {\n", First ? "" : "else ", iter->first);
+      PrintIndented("switch (label|0) {\n");
     } else {
-      PrintIndented("%sif (label == %d) {\n", First ? "" : "else ", iter->first);
+      PrintIndented("switch (label) {\n");
     }
-    First = false;
     Indenter::Indent();
-    iter->second->Render(InLoop);
+    for (IdShapeMap::iterator iter = InnerMap.begin(); iter != InnerMap.end(); iter++) {
+      PrintIndented("case %d: {\n", iter->first);
+      Indenter::Indent();
+      iter->second->Render(InLoop);
+      PrintIndented("break;\n");
+      Indenter::Unindent();
+      PrintIndented("}\n");
+    }
     Indenter::Unindent();
     PrintIndented("}\n");
   }
+
   RenderLoopPostfix();
   if (Next) Next->Render(InLoop);
 }
@@ -547,7 +566,7 @@ void Relooper::Calculate(Block *Entry) {
         PriorOut->Ancestor = Ancestor;
         PriorOut->Type = Type;
         if (MultipleShape *Multiple = Shape::IsMultiple(Ancestor)) {
-          Multiple->NeedLoop++; // We are breaking out of this Multiple, so need a loop
+          Multiple->Breaks++; // We are breaking out of this Multiple, so need a loop
         }
         iter++; // carefully increment iter before erasing
         Target->BranchesIn.erase(Prior);
@@ -853,7 +872,7 @@ void Relooper::Calculate(Block *Entry) {
             iter = Next; // increment carefully because Solipsize can remove us
           }
         }
-        Multiple->InnerMap[CurrEntry] = Process(CurrBlocks, CurrEntries, NULL);
+        Multiple->InnerMap[CurrEntry->Id] = Process(CurrBlocks, CurrEntries, NULL);
         // If we are not fused, then our entries will actually be checked
         if (!Fused) {
           CurrEntry->IsCheckedMultipleEntry = true;
@@ -867,6 +886,11 @@ void Relooper::Calculate(Block *Entry) {
           NextEntries.insert(Entry);
         }
       }
+      // The multiple has been created, we can decide how to implement it
+      if (Multiple->InnerMap.size() >= 10) {
+        Multiple->UseSwitch = true;
+        Multiple->Breaks++; // switch captures breaks
+      }
       return Multiple;
     }
 
@@ -1021,7 +1045,7 @@ void Relooper::Calculate(Block *Entry) {
     PostOptimizer(Relooper *ParentInit) : Parent(ParentInit), Closure(NULL) {}
 
     #define RECURSE_Multiple(shape, func) \
-      for (BlockShapeMap::iterator iter = shape->InnerMap.begin(); iter != shape->InnerMap.end(); iter++) { \
+      for (IdShapeMap::iterator iter = shape->InnerMap.begin(); iter != shape->InnerMap.end(); iter++) { \
         func(iter->second); \
       }
     #define RECURSE_Loop(shape, func) \
@@ -1042,7 +1066,7 @@ void Relooper::Calculate(Block *Entry) {
       SHAPE_SWITCH(S, {
         Out.insert(Simple->Inner);
       }, {
-        for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
+        for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
           FollowNaturalFlow(iter->second, Out);
         }
         FollowNaturalFlow(Multiple->Next, Out);
@@ -1061,7 +1085,7 @@ void Relooper::Calculate(Block *Entry) {
 
       SHAPE_SWITCH(Root, {
       }, {
-        for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
+        for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
           FindNaturals(iter->second, Root->Natural);
         }
       }, {
@@ -1111,7 +1135,7 @@ void Relooper::Calculate(Block *Entry) {
                   if (Details->Type == Branch::Break) {
                     Details->Type = Branch::Direct;
                     if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) {
-                      Multiple->NeedLoop--;
+                      Multiple->Breaks--;
                     }
                   } else {
                     assert(Details->Type == Branch::Direct);
@@ -1130,20 +1154,20 @@ void Relooper::Calculate(Block *Entry) {
               if (Details->Type != Branch::Direct && contains(NaturalBlocks, Target)) { // note: cannot handle split blocks
                 Details->Type = Branch::Direct;
                 if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) {
-                  Multiple->NeedLoop--;
+                  Multiple->Breaks--;
                 }
               } 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--;
+                  Multiple->Breaks--;
                 }
               }
             }
           }
         }, {
-          for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
-            RemoveUnneededFlows(iter->second, Multiple->Next, Multiple->NeedLoop ? NULL : LastLoop);
+          for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
+            RemoveUnneededFlows(iter->second, Multiple->Next, Multiple->Breaks ? NULL : LastLoop);
           }
           Next = Multiple->Next;
         }, {
@@ -1169,13 +1193,16 @@ void Relooper::Calculate(Block *Entry) {
         SHAPE_SWITCH(Root, {
           MultipleShape *Fused = Shape::IsMultiple(Root->Next);
           // If we are fusing a Multiple with a loop into this Simple, then visit it now
-          if (Fused && Fused->NeedLoop) {
+          if (Fused && Fused->Breaks) {
             LoopStack.push(Fused);
           }
           if (Simple->Inner->BranchVar) {
             LoopStack.push(NULL); // a switch means breaks are now useless, push a dummy
           }
           if (Fused) {
+            if (Fused->UseSwitch) {
+              LoopStack.push(NULL); // a switch means breaks are now useless, push a dummy
+            }
             RECURSE_Multiple(Fused, FindLabeledLoops);
           }
           for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {
@@ -1191,10 +1218,13 @@ void Relooper::Calculate(Block *Entry) {
               }
             }
           }
+          if (Fused && Fused->UseSwitch) {
+            LoopStack.pop();
+          }
           if (Simple->Inner->BranchVar) {
             LoopStack.pop();
           }
-          if (Fused && Fused->NeedLoop) {
+          if (Fused && Fused->Breaks) {
             LoopStack.pop();
           }
           if (Fused) {
@@ -1203,11 +1233,11 @@ void Relooper::Calculate(Block *Entry) {
             Next = Root->Next;
           }
         }, {
-          if (Multiple->NeedLoop) {
+          if (Multiple->Breaks) {
             LoopStack.push(Multiple);
           }
           RECURSE(Multiple, FindLabeledLoops);
-          if (Multiple->NeedLoop) {
+          if (Multiple->Breaks) {
             LoopStack.pop();
           }
           Next = Root->Next;
@@ -1290,8 +1320,8 @@ void Debugging::Dump(Shape *S, const char *prefix) {
     printf("<< Simple with block %d\n", Simple->Inner->Id);
   }, {
     printf("<< Multiple\n");
-    for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
-      printf("     with entry %d\n", iter->first->Id);
+    for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
+      printf("     with entry %d\n", iter->first);
     }
   }, {
     printf("<< Loop\n");
diff --git a/lib/Target/JSBackend/Relooper.h b/lib/Target/JSBackend/Relooper.h
index 152bae0e6e..c86e63ac1f 100644
--- a/lib/Target/JSBackend/Relooper.h
+++ b/lib/Target/JSBackend/Relooper.h
@@ -132,8 +132,6 @@ struct SimpleShape : public Shape {
   }
 };
 
-typedef std::map<Block*, Shape*> BlockShapeMap;
-
 // A shape that may be implemented with a labeled loop.
 struct LabeledShape : public Shape {
   bool Labeled; // If we have a loop, whether it needs to be labeled
@@ -141,12 +139,16 @@ struct LabeledShape : public Shape {
   LabeledShape(ShapeType TypeInit) : Shape(TypeInit), Labeled(false) {}
 };
 
+// Blocks with the same id were split and are identical, so we just care about ids in Multiple entries
+typedef std::map<int, Shape*> IdShapeMap;
+
 struct MultipleShape : public LabeledShape {
-  BlockShapeMap InnerMap; // entry block -> shape
-  int NeedLoop; // If we have branches, we need a loop. This is a counter of loop requirements,
-                // if we optimize it to 0, the loop is unneeded
+  IdShapeMap InnerMap; // entry block ID -> shape
+  int Breaks; // If we have branches on us, we need a loop (or a switch). This is a counter of requirements,
+                     // if we optimize it to 0, the loop is unneeded
+  bool UseSwitch; // Whether to switch on label as opposed to an if-else chain
 
-  MultipleShape() : LabeledShape(Multiple), NeedLoop(0) {}
+  MultipleShape() : LabeledShape(Multiple), Breaks(0), UseSwitch(false) {}
 
   void RenderLoopPrefix();
   void RenderLoopPostfix();