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
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 @@
"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 @@
" 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 @@
"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 @@
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 @@
" 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 @@
" 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,