Add loop recognition and CFG simplifications in new compiler.

We do three simplifications:
- Split critical edges, for code generation from SSA (new).
- Ensure one back edge per loop, to simplify loop recognition (new).
- Ensure only one pre header for a loop, to simplify SSA creation (existing).

Change-Id: I9bfccd4b236a00486a261078627b091c8a68be33

1 files changed, 41 insertions, 24 deletions

diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
index e4aafb7..9be2197 100644
--- a/compiler/optimizing/ssa_test.cc
+++ b/compiler/optimizing/ssa_test.cc
@@ -98,15 +98,18 @@ TEST(SsaTest, CFG1) {
     "BasicBlock 0, succ: 1\n"
     "  0: IntConstant 0 [2, 2]\n"
     "  1: Goto\n"
-    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "BasicBlock 1, pred: 0, succ: 2, 5\n"
     "  2: Equal(0, 0) [3]\n"
     "  3: If(2)\n"
     "BasicBlock 2, pred: 1, succ: 3\n"
     "  4: Goto\n"
-    "BasicBlock 3, pred: 1, 2, succ: 4\n"
+    "BasicBlock 3, pred: 2, 5, succ: 4\n"
     "  5: ReturnVoid\n"
     "BasicBlock 4, pred: 3\n"
-    "  6: Exit\n";
+    "  6: Exit\n"
+    // Synthesized block to avoid critical edge.
+    "BasicBlock 5, pred: 1, succ: 3\n"
+    "  7: Goto\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -125,16 +128,19 @@ TEST(SsaTest, CFG2) {
     "  0: IntConstant 0 [6, 3, 3]\n"
     "  1: IntConstant 4 [6]\n"
     "  2: Goto\n"
-    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "BasicBlock 1, pred: 0, succ: 2, 5\n"
     "  3: Equal(0, 0) [4]\n"
     "  4: If(3)\n"
     "BasicBlock 2, pred: 1, succ: 3\n"
     "  5: Goto\n"
-    "BasicBlock 3, pred: 1, 2, succ: 4\n"
-    "  6: Phi(0, 1) [7]\n"
+    "BasicBlock 3, pred: 2, 5, succ: 4\n"
+    "  6: Phi(1, 0) [7]\n"
     "  7: Return(6)\n"
     "BasicBlock 4, pred: 3\n"
-    "  8: Exit\n";
+    "  8: Exit\n"
+    // Synthesized block to avoid critical edge.
+    "BasicBlock 5, pred: 1, succ: 3\n"
+    "  9: Goto\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -184,16 +190,21 @@ TEST(SsaTest, Loop1) {
     "BasicBlock 0, succ: 1\n"
     "  0: IntConstant 0 [6, 4, 2, 2]\n"
     "  1: Goto\n"
-    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "BasicBlock 1, pred: 0, succ: 5, 6\n"
     "  2: Equal(0, 0) [3]\n"
     "  3: If(2)\n"
-    "BasicBlock 2, pred: 1, 3, succ: 3\n"
-    "  4: Phi(0, 6) [6]\n"
+    "BasicBlock 2, pred: 3, 6, succ: 3\n"
+    "  4: Phi(6, 0) [6]\n"
     "  5: Goto\n"
-    "BasicBlock 3, pred: 1, 2, succ: 2\n"
-    "  6: Phi(0, 4) [4]\n"
+    "BasicBlock 3, pred: 2, 5, succ: 2\n"
+    "  6: Phi(4, 0) [4]\n"
     "  7: Goto\n"
-    "BasicBlock 4\n";
+    "BasicBlock 4\n"
+    // Synthesized blocks to avoid critical edge.
+    "BasicBlock 5, pred: 1, succ: 3\n"
+    "  8: Goto\n"
+    "BasicBlock 6, pred: 1, succ: 2\n"
+    "  9: Goto\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -349,26 +360,30 @@ TEST(SsaTest, Loop6) {
   const char* expected =
     "BasicBlock 0, succ: 1\n"
     "  0: IntConstant 0 [5]\n"
-    "  1: IntConstant 4 [5, 8, 8]\n"
-    "  2: IntConstant 5 [5]\n"
+    "  1: IntConstant 4 [14, 8, 8]\n"
+    "  2: IntConstant 5 [14]\n"
     "  3: Goto\n"
     "BasicBlock 1, pred: 0, succ: 2\n"
     "  4: Goto\n"
-    "BasicBlock 2, pred: 1, 4, 5, succ: 6, 3\n"
-    "  5: Phi(0, 2, 1) [12, 6, 6]\n"
+    "BasicBlock 2, pred: 1, 8, succ: 6, 3\n"
+    "  5: Phi(0, 14) [12, 6, 6]\n"
     "  6: Equal(5, 5) [7]\n"
     "  7: If(6)\n"
     "BasicBlock 3, pred: 2, succ: 5, 4\n"
     "  8: Equal(1, 1) [9]\n"
     "  9: If(8)\n"
-    "BasicBlock 4, pred: 3, succ: 2\n"
+    "BasicBlock 4, pred: 3, succ: 8\n"
     "  10: Goto\n"
-    "BasicBlock 5, pred: 3, succ: 2\n"
+    "BasicBlock 5, pred: 3, succ: 8\n"
     "  11: Goto\n"
     "BasicBlock 6, pred: 2, succ: 7\n"
     "  12: Return(5)\n"
     "BasicBlock 7, pred: 6\n"
-    "  13: Exit\n";
+    "  13: Exit\n"
+    // Synthesized single back edge of loop.
+    "BasicBlock 8, pred: 5, 4, succ: 2\n"
+    "  14: Phi(1, 2) [5]\n"
+    "  15: Goto\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -393,7 +408,7 @@ TEST(SsaTest, Loop7) {
     "  3: Goto\n"
     "BasicBlock 1, pred: 0, succ: 2\n"
     "  4: Goto\n"
-    "BasicBlock 2, pred: 1, 5, succ: 6, 3\n"
+    "BasicBlock 2, pred: 1, 5, succ: 3, 8\n"
     "  5: Phi(0, 1) [12, 6, 6]\n"
     "  6: Equal(5, 5) [7]\n"
     "  7: If(6)\n"
@@ -404,11 +419,13 @@ TEST(SsaTest, Loop7) {
     "  10: Goto\n"
     "BasicBlock 5, pred: 3, succ: 2\n"
     "  11: Goto\n"
-    "BasicBlock 6, pred: 2, 4, succ: 7\n"
-    "  12: Phi(5, 2) [13]\n"
+    "BasicBlock 6, pred: 4, 8, succ: 7\n"
+    "  12: Phi(2, 5) [13]\n"
     "  13: Return(12)\n"
     "BasicBlock 7, pred: 6\n"
-    "  14: Exit\n";
+    "  14: Exit\n"
+    "BasicBlock 8, pred: 2, succ: 6\n"
+    "  15: Goto\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,