support for optional complete emulation in relooper1.7.9

6 files changed, 124 insertions, 14 deletions

diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp
index d2a48f63..fc7b3ea7 100644
--- a/src/relooper/Relooper.cpp
+++ b/src/relooper/Relooper.cpp
@@ -142,6 +142,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 +211,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()) {
@@ -330,16 +331,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 +357,10 @@ void EmulatedShape::Render(bool InLoop) {
   PrintIndented("}\n");
   if (Next) Next->Render(InLoop);
 };
-*/
 
 // Relooper
 
-Relooper::Relooper() : Root(NULL) {
+Relooper::Relooper() : Root(NULL), Emulate(false) {
 }
 
 Relooper::~Relooper() {
@@ -461,7 +464,7 @@ void Relooper::Calculate(Block *Entry) {
     }
   }
 
-  Pre.SplitDeadEnds();
+  if (!Emulate) Pre.SplitDeadEnds();
 
   // Recursively process the graph
 
@@ -526,6 +529,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 +855,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 +865,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..e78d18e7 100644
--- a/src/relooper/Relooper.h
+++ b/src/relooper/Relooper.h
@@ -96,6 +96,7 @@ 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.
@@ -105,7 +106,8 @@ struct Shape {
   enum ShapeType {
     Simple,
     Multiple,
-    Loop
+    Loop,
+    Emulated
   };
   ShapeType Type;
 
@@ -118,6 +120,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; }
+  static EmulatedShape *IsEmulated(Shape *It) { return It && It->Type == Emulated ? (EmulatedShape*)It : NULL; }
 
   // INTERNAL
   static int IdCounter;
@@ -162,12 +165,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 +190,7 @@ struct Relooper {
   std::deque<Block*> Blocks;
   std::deque<Shape*> Shapes;
   Shape *Root;
+  bool Emulate;
 
   Relooper();
   ~Relooper();
@@ -204,6 +211,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..9b537fd9 100644
--- a/src/relooper/test.txt
+++ b/src/relooper/test.txt
@@ -270,3 +270,47 @@ L46: do {
 } while(0);
 // block C
 
+
+
+-- If pattern, emulated --
+
+
+
+L50:  while(1) {
+ switch(label) {
+  case 40: {
+   // block A
+   if (check == 10) {
+    atob();
+    label = 41;
+    continue L50;
+   } else {
+    atoc();
+    label = 42;
+    continue L50;
+   }
+   break;
+  }
+  case 41: {
+   // block B
+   switch (b_check()) {
+   case 17: {
+    btoc();
+    label = 42;
+    continue L50;
+    break;
+   }
+   default: {
+    label = 40;
+    continue L50;
+   }
+   }
+   break;
+  }
+  case 42: {
+   // block C
+   break;
+  }
+ }
+}
+
diff --git a/tools/shared.py b/tools/shared.py
index b425c655..20951a12 100644
--- a/tools/shared.py
+++ b/tools/shared.py
@@ -322,7 +322,7 @@ def find_temp_directory():
 # 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.7.8'
+EMSCRIPTEN_VERSION = '1.7.9'
 
 def generate_sanity():
   return EMSCRIPTEN_VERSION + '|' + get_llvm_target() + '|' + LLVM_ROOT