add a Nested branch type in relooper, to represent a path we must make sure is nested so that parallel paths do not get intertwined. this allows us to emit a more canonical form of nested ifs as a result of short-circuit operators; 1.13.21.13.2

4 files changed, 180 insertions, 8 deletions

diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp
index c11de099..c6830158 100644
--- a/src/relooper/Relooper.cpp
+++ b/src/relooper/Relooper.cpp
@@ -122,7 +122,7 @@ void Branch::Render(Block *Target, bool SetLabel) {
   if (Code) PrintIndented("%s\n", Code);
   if (SetLabel) PrintIndented("label = %d;\n", Target->Id);
   if (Ancestor) {
-    if (Type != Direct) {
+    if (Type == Break || Type == Continue) {
       if (Labeled) {
         PrintIndented("%s L%d;\n", Type == Break ? "break" : "continue", Ancestor->Id);
       } else {
@@ -287,6 +287,11 @@ void Block::Render(bool InLoop) {
     Details->Render(Target, SetCurrLabel);
     if (HasFusedContent) {
       Fused->InnerMap.find(Target)->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);
+      Parent->Next->Render(InLoop);
+      Parent->Next = NULL;
     }
     if (useSwitch && iter != ProcessedBranchesOut.end()) {
       PrintIndented("break;\n");
@@ -1077,12 +1082,48 @@ void Relooper::Calculate(Block *Entry) {
         SHAPE_SWITCH(Root, {
           if (Simple->Inner->BranchVar) LastLoop = NULL; // a switch clears out the loop (TODO: only for breaks, not continue)
 
-          // If there is a next block, we already know at Simple creation time to make direct branches,
-          // and we can do nothing more. If there is no next however, then Natural is where we will
-          // go to by doing nothing, so we can potentially optimize some branches to direct.
           if (Simple->Next) {
+            if (!Simple->Inner->BranchVar && Simple->Inner->ProcessedBranchesOut.size() == 2) {
+              // If there is a next block, we already know at Simple creation time to make direct branches,
+              // and we can do nothing more in general. But, we try to optimize the case of a break and
+              // a direct: This would normally be  if (break?) { break; } ..  but if we
+              // make sure to nest the else, we can save the break,  if (!break?) { .. }  . This is also
+              // better because the more canonical nested form is easier to further optimize later. The
+              // downside is more nesting, which adds to size in builds with whitespace.
+              // Note that we avoid switches, as it complicates control flow and is not relevant
+              // for the common case we optimize here.
+              bool Found = false;
+              bool Abort = false;
+              for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {
+                Block *Target = iter->first;
+                Branch *Details = iter->second;
+                if (Details->Type == Branch::Break) {
+                  Found = true;
+                  if (!contains(NaturalBlocks, Target)) Abort = true;
+                } else if (Details->Type != Branch::Direct) {
+                  Abort = true;
+                }
+              }
+              if (Found && !Abort) {
+                for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {
+                  Block *Target = iter->first;
+                  Branch *Details = iter->second;
+                  if (Details->Type == Branch::Break) {
+                    Details->Type = Branch::Direct;
+                    if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) {
+                      Multiple->NeedLoop--;
+                    }
+                  } else {
+                    assert(Details->Type == Branch::Direct);
+                    Details->Type = Branch::Nested;
+                  }
+                }
+              }
+            }
             Next = Simple->Next;
           } else {
+            // If there is no next then Natural is where we will
+            // go to by doing nothing, so we can potentially optimize some branches to direct.
             for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {
               Block *Target = iter->first;
               Branch *Details = iter->second;
@@ -1140,7 +1181,7 @@ void Relooper::Calculate(Block *Entry) {
           for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {
             Block *Target = iter->first;
             Branch *Details = iter->second;
-            if (Details->Type != Branch::Direct) {
+            if (Details->Type == Branch::Break || Details->Type == Branch::Continue) {
               assert(LoopStack.size() > 0);
               if (Details->Ancestor != LoopStack.top() && Details->Labeled) {
                 LabeledShape *Labeled = Shape::IsLabeled(Details->Ancestor);
diff --git a/src/relooper/Relooper.h b/src/relooper/Relooper.h
index 85adf359..152bae0e 100644
--- a/src/relooper/Relooper.h
+++ b/src/relooper/Relooper.h
@@ -24,9 +24,11 @@ struct Shape;
 // Info about a branching from one block to another
 struct Branch {
   enum FlowType {
-    Direct = 0, // We will directly reach the right location through other means, no need for continue or break
+    Direct = 0,   // We will directly reach the right location through other means, no need for continue or break
     Break = 1,
-    Continue = 2
+    Continue = 2,
+    Nested = 3    // This code is directly reached, but we must be careful to ensure it is nested in an if - it is not reached
+                  // unconditionally, other code paths exist alongside it that we need to make sure do not intertwine
   };
   Shape *Ancestor; // If not NULL, this shape is the relevant one for purposes of getting to the target block. We break or continue on it
   Branch::FlowType Type; // If Ancestor is not NULL, this says whether to break or continue
@@ -59,7 +61,7 @@ struct Block {
   Shape *Parent; // The shape we are directly inside
   int Id; // A unique identifier, defined when added to relooper. Note that this uniquely identifies a *logical* block - if we split it, the two instances have the same content *and* the same Id
   const char *Code; // The string representation of the code in this block. Owning pointer (we copy the input)
-  const char *BranchVar; // If we have more than one branch out, the variable whose value determines where we go
+  const char *BranchVar; // A variable whose value determines where we go; if this is not NULL, emit a switch on that variable
   bool IsCheckedMultipleEntry; // If true, we are a multiple entry, so reaching us requires setting the label variable
 
   Block(const char *CodeInit, const char *BranchVarInit);
diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp
index b4ce669c..2b25001b 100644
--- a/src/relooper/test.cpp
+++ b/src/relooper/test.cpp
@@ -314,5 +314,95 @@ int main() {
 
     puts(buffer);
   }
+
+  if (1) {
+    Relooper::MakeOutputBuffer(10);
+
+    printf("\n\n-- If chain (optimized) --\n\n");
+
+    Block *b_a = new Block("// block A\n", NULL);
+    Block *b_b = new Block("// block B\n", NULL);
+    Block *b_c = new Block("// block C\n", NULL);
+
+    b_a->AddBranchTo(b_b, "a == 10", NULL);
+    b_a->AddBranchTo(b_c, NULL, NULL);
+
+    b_b->AddBranchTo(b_c, NULL, NULL);
+
+    Relooper r;
+    r.AddBlock(b_a);
+    r.AddBlock(b_b);
+    r.AddBlock(b_c);
+
+    r.Calculate(b_a);
+    r.Render();
+
+    puts(r.GetOutputBuffer());
+  }
+
+  if (1) {
+    Relooper::MakeOutputBuffer(10);
+
+    printf("\n\n-- If chain (optimized) --\n\n");
+
+    Block *b_a = new Block("// block A\n", NULL);
+    Block *b_b = new Block("// block B\n", NULL);
+    Block *b_c = new Block("// block C\n", NULL);
+    Block *b_d = new Block("// block D\n", NULL);
+
+    b_a->AddBranchTo(b_b, "a == 10", NULL);
+    b_a->AddBranchTo(b_d, NULL, NULL);
+
+    b_b->AddBranchTo(b_c, "b == 10", NULL);
+    b_b->AddBranchTo(b_d, NULL, NULL);
+
+    b_c->AddBranchTo(b_d, NULL, NULL);
+
+    Relooper r;
+    r.AddBlock(b_a);
+    r.AddBlock(b_b);
+    r.AddBlock(b_c);
+    r.AddBlock(b_d);
+
+    r.Calculate(b_a);
+    r.Render();
+
+    puts(r.GetOutputBuffer());
+  }
+
+  if (1) {
+    Relooper::MakeOutputBuffer(10);
+
+    printf("\n\n-- If chain (optimized, long) --\n\n");
+
+    Block *b_a = new Block("// block A\n", NULL);
+    Block *b_b = new Block("// block B\n", NULL);
+    Block *b_c = new Block("// block C\n", NULL);
+    Block *b_d = new Block("// block D\n", NULL);
+    Block *b_e = new Block("// block E\n", NULL);
+
+    b_a->AddBranchTo(b_b, "a == 10", NULL);
+    b_a->AddBranchTo(b_e, NULL, NULL);
+
+    b_b->AddBranchTo(b_c, "b == 10", NULL);
+    b_b->AddBranchTo(b_e, NULL, NULL);
+
+    b_c->AddBranchTo(b_d, "c == 10", NULL);
+    b_c->AddBranchTo(b_e, NULL, NULL);
+
+    b_d->AddBranchTo(b_e, NULL, NULL);
+
+    Relooper r;
+    r.AddBlock(b_a);
+    r.AddBlock(b_b);
+    r.AddBlock(b_c);
+    r.AddBlock(b_d);
+    r.AddBlock(b_e);
+
+    r.Calculate(b_a);
+    r.Render();
+
+    puts(r.GetOutputBuffer());
+  }
 }
 
diff --git a/src/relooper/test.txt b/src/relooper/test.txt
index 82b02ad7..1fa205ba 100644
--- a/src/relooper/test.txt
+++ b/src/relooper/test.txt
@@ -360,3 +360,42 @@
   }
  }
 
+
+
+-- If chain (optimized) --
+
+ // block A
+ if (a == 10) {
+  // block B
+ }
+ // block C
+
+
+
+-- If chain (optimized) --
+
+ // block A
+ if (a == 10) {
+  // block B
+  if (b == 10) {
+   // block C
+  }
+ }
+ // block D
+
+
+
+-- If chain (optimized, long) --
+
+ // block A
+ if (a == 10) {
+  // block B
+  if (b == 10) {
+   // block C
+   if (c == 10) {
+    // block D
+   }
+  }
+ }
+ // block E
+