optimize unbalanced 2-multiple shapes in relooper, prevent unnecessary nesting when the smaller is a dead end

8 files changed, 146 insertions, 111 deletions

diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp
index f16055c0..933fda96 100644
--- a/src/relooper/Relooper.cpp
+++ b/src/relooper/Relooper.cpp
@@ -750,6 +750,49 @@ void Relooper::Calculate(Block *Entry) {
             }
           }
 
+          // As an optimization, if we have 2 independent groups, and one is a small dead end, we can handle only that dead end.
+          // The other then becomes a Next - without nesting in the code and recursion in the analysis.
+          // TODO: if the larger is the only dead end, handle that too
+          // TODO: handle >2 groups
+          // TODO: handle not just dead ends, but also that do not branch to the NextEntries. However, must be careful
+          //       there since we create a Next, and that Next can prevent eliminating a break (since we no longer
+          //       naturally reach the same place), which may necessitate a one-time loop, which makes the unnesting
+          //       pointless.
+          if (IndependentGroups.size() == 2) {
+            // Find the smaller one
+            BlockBlockSetMap::iterator iter = IndependentGroups.begin();
+            Block *SmallEntry = iter->first;
+            int SmallSize = iter->second.size();
+            iter++;
+            Block *LargeEntry = iter->first;
+            int LargeSize = iter->second.size();
+            if (SmallSize != LargeSize) { // ignore the case where they are identical - keep things symmetrical there
+              if (SmallSize > LargeSize) {
+                Block *Temp = SmallEntry;
+                SmallEntry = LargeEntry;
+                LargeEntry = Temp; // Note: we did not flip the Sizes too, they are now invalid. TODO: use the smaller size as a limit?
+              }
+              // Check if dead end
+              bool DeadEnd = true;
+              BlockSet &SmallGroup = IndependentGroups[SmallEntry];
+              for (BlockSet::iterator iter = SmallGroup.begin(); iter != SmallGroup.end(); iter++) {
+                Block *Curr = *iter;
+                for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) {
+                  Block *Target = iter->first;
+                  if (SmallGroup.find(Target) == SmallGroup.end()) {
+                    DeadEnd = false;
+                    break;
+                  }
+                }
+                if (!DeadEnd) break;
+              }
+              if (DeadEnd) {
+                PrintDebug("Removing nesting by not handling large group because small group is dead end\n");
+                IndependentGroups.erase(LargeEntry);
+              }
+            }
+          }
+
           PrintDebug("Handleable independent groups: %d\n", IndependentGroups.size());
 
           if (IndependentGroups.size() > 0) {
diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp
index 0d029216..4275941b 100644
--- a/src/relooper/test.cpp
+++ b/src/relooper/test.cpp
@@ -160,7 +160,7 @@ int main() {
 
     puts(buffer);
   }
-/*
+
   if (1) {
     Relooper::SetOutputBuffer(buffer, sizeof(buffer));
 
@@ -168,11 +168,11 @@ int main() {
 
     Block *b_a = new Block("// block A\n");
     Block *b_b = new Block("// block B\n");
-    Block *b_c = new Block("// block C\n");
+    Block *b_c = new Block("return C;\n");
     Block *b_d = new Block("// block D\n");
 
     b_a->AddBranchTo(b_b, "check == 10");
-    b_a->AddBranchTo(b_c, NULL);
+    b_a->AddBranchTo(b_c, NULL); // c is a dead end
 
     b_b->AddBranchTo(b_d, NULL);
 
@@ -190,6 +190,5 @@ int main() {
 
     puts(buffer);
   }
-*/
 }
 
diff --git a/src/relooper/test.txt b/src/relooper/test.txt
index ff4ada24..12d0ef39 100644
--- a/src/relooper/test.txt
+++ b/src/relooper/test.txt
@@ -59,24 +59,21 @@ while(1) {
   }
   // code 3
   if ($6) {
-    label = 14;
     break;
   } else {
     var $i_0 = $7;var $x_0 = $5; 
   }
 }
-if (label == 14) {
-  // code 4
-  if ($10) {
-    // code 5
-  }
-  // code 6
-  var $x_1 = $13; 
+if (label == 18) {
   // code 7
 }
-else if (label == 18) {
-  // code 7
+// code 4
+if ($10) {
+  // code 5
 }
+// code 6
+var $x_1 = $13; 
+// code 7
 
 
 
@@ -97,3 +94,18 @@ if (chak()) {
   // block D
 }
 
+
+
+-- Unbalanced with a dead end --
+
+
+
+// block A
+if (!(check == 10)) {
+  return C;
+}
+while(1) {
+  // block B
+  // block D
+}
+
diff --git a/src/relooper/test_fuzz1.txt b/src/relooper/test_fuzz1.txt
index 63bbee0c..5122257e 100644
--- a/src/relooper/test_fuzz1.txt
+++ b/src/relooper/test_fuzz1.txt
@@ -8,37 +8,28 @@ do {
     print(7); state = check();
     label = 3;
     break;
-  } else {
-    label = 2;
   }
 } while(0);
 L5: while(1) {
-  if (label == 2) {
-    label = 0;
-    print(1); state = check();
-    while(1) {
-      print(3); state = check();
-      if (!(state == 8)) {
-        label = 2;
-        continue L5;
-      }
-      print(8); state = check();
-      if (!(state == 4)) {
-        label = 3;
-        continue L5;
-      }
-      print(4); state = check();
-      if (!(state == 3)) {
-        label = 2;
-        continue L5;
-      }
-    }
-  }
-  else if (label == 3) {
+  if (label == 3) {
     label = 0;
     print(2); state = check();
-    label = 2;
-    continue;
+  }
+  print(1); state = check();
+  while(1) {
+    print(3); state = check();
+    if (!(state == 8)) {
+      continue L5;
+    }
+    print(8); state = check();
+    if (!(state == 4)) {
+      label = 3;
+      continue L5;
+    }
+    print(4); state = check();
+    if (!(state == 3)) {
+      continue L5;
+    }
   }
 }
 
diff --git a/src/relooper/test_fuzz2.txt b/src/relooper/test_fuzz2.txt
index c48c6b6c..572e819d 100644
--- a/src/relooper/test_fuzz2.txt
+++ b/src/relooper/test_fuzz2.txt
@@ -5,10 +5,9 @@ if (state == 1) {
   while(1) {
     print(1); state = check();
   }
-} else {
-  while(1) {
-    print(3); state = check();
-    print(2); state = check();
-  }
+}
+while(1) {
+  print(3); state = check();
+  print(2); state = check();
 }
 
diff --git a/src/relooper/test_fuzz4.txt b/src/relooper/test_fuzz4.txt
index 5bb219f4..05a70582 100644
--- a/src/relooper/test_fuzz4.txt
+++ b/src/relooper/test_fuzz4.txt
@@ -5,16 +5,15 @@ if (state == 2) {
   while(1) {
     print(2); state = check();
   }
-} else {
-  while(1) {
-    print(4); state = check();
-    if (!(state == 4)) {
-      break;
-    }
-  }
-  print(3); state = check();
-  while(1) {
-    print(1); state = check();
+}
+while(1) {
+  print(4); state = check();
+  if (!(state == 4)) {
+    break;
   }
 }
+print(3); state = check();
+while(1) {
+  print(1); state = check();
+}
 
diff --git a/src/relooper/test_fuzz6.txt b/src/relooper/test_fuzz6.txt
index af188ab1..bd45e8fd 100644
--- a/src/relooper/test_fuzz6.txt
+++ b/src/relooper/test_fuzz6.txt
@@ -40,39 +40,14 @@ while(1) {
         print(16); state = check();// ................................................................................................................................................................................................................................................................................................................................................................
         print(57); state = check();// ...........................................................................................................................................................................................................................................................................................................................
         print(39); state = check();// ................
-        if (state % 3 == 0) {
-          label = 73;
-        } else if (state % 3 == 1) {
+        if (state % 3 == 1) {
           label = 74;
-        } else {
+        } else if (!(state % 3 == 0)) {
           label = 32;
           break;
         }
         while(1) {
-          if (label == 73) {
-            label = 0;
-            print(72); state = check();// ..........................................................................................................
-            if (state % 2 == 0) {
-              label = 92;
-              break L20;
-            }
-            print(80); state = check();// ....................................
-            if (state % 2 == 0) {
-              continue L18;
-            }
-            print(50); state = check();// ........................................
-            print(29); state = check();// ...............
-            print(8); state = check();// ....................................................................................................................................................................................................................................................
-            if (state % 2 == 0) {
-              continue L10;
-            }
-            print(19); state = check();// ......................................................................................................................................................................................................................
-            print(56); state = check();// ....................................................................................................................................................................................................................
-            print(34); state = check();// ..........................................................................................................................................
-            label = 74;
-            continue;
-          }
-          else if (label == 74) {
+          if (label == 74) {
             label = 0;
             print(73); state = check();// .
             if (state % 3 == 1) {
@@ -87,9 +62,27 @@ while(1) {
             print(77); state = check();// ...........................................................................................................................................................................................................................................................................................
             print(76); state = check();// ..............................................................................................................................................................................................................................................................................................................................................................................................................................
             print(22); state = check();// .........................................................................................................
-            label = 73;
-            continue;
           }
+          print(72); state = check();// ..........................................................................................................
+          if (state % 2 == 0) {
+            label = 92;
+            break L20;
+          }
+          print(80); state = check();// ....................................
+          if (state % 2 == 0) {
+            continue L18;
+          }
+          print(50); state = check();// ........................................
+          print(29); state = check();// ...............
+          print(8); state = check();// ....................................................................................................................................................................................................................................................
+          if (state % 2 == 0) {
+            continue L10;
+          }
+          print(19); state = check();// ......................................................................................................................................................................................................................
+          print(56); state = check();// ....................................................................................................................................................................................................................
+          print(34); state = check();// ..........................................................................................................................................
+          label = 74;
+          continue;
         }
         print(62); state = check();// .......................................................................................
       }
diff --git a/src/relooper/test_inf.txt b/src/relooper/test_inf.txt
index 2edfc760..379d2083 100644
--- a/src/relooper/test_inf.txt
+++ b/src/relooper/test_inf.txt
@@ -361,32 +361,31 @@ if (uint(i4) >= uint(i5)) {
 code 171
 if (i2 == 0) {
   code 183
-} else {
-  code 172
-  while(1) {
-    code 173
-    if (uint(i5) >= uint(i6)) {
-      code 175
-    } else {
-      code 174
-    }
-    code 176
-    if (uint(i5) >= uint(i6)) {
-      code 178
-    } else {
-      code 177
-    }
-    code 179
-    if (uint(i4) >= uint(i5)) {
-      code 181
-    } else {
-      code 180
-    }
-    code 182
-    if (!(i2 != 0)) {
-      break;
-    }
+}
+code 172
+while(1) {
+  code 173
+  if (uint(i5) >= uint(i6)) {
+    code 175
+  } else {
+    code 174
+  }
+  code 176
+  if (uint(i5) >= uint(i6)) {
+    code 178
+  } else {
+    code 177
+  }
+  code 179
+  if (uint(i4) >= uint(i5)) {
+    code 181
+  } else {
+    code 180
+  }
+  code 182
+  if (!(i2 != 0)) {
+    break;
   }
-  code 183
 }
+code 183