Merge "Quick: Redefine the notion of back-egdes."

1 files changed, 292 insertions, 2 deletions

diff --git a/compiler/dex/mir_optimization_test.cc b/compiler/dex/mir_optimization_test.cc
index c794cc6..6c2e9c0 100644
--- a/compiler/dex/mir_optimization_test.cc
+++ b/compiler/dex/mir_optimization_test.cc
@@ -88,6 +88,8 @@ class MirOptimizationTest : public testing::Test {
     { bb, opcode, 0u, vA, vB, vC }
 #define DEF_INVOKE(bb, opcode, vC, method_info) \
     { bb, opcode, method_info, 0u, 0u, vC }
+#define DEF_OTHER0(bb, opcode) \
+    { bb, opcode, 0u, 0u, 0u, 0u }
 #define DEF_OTHER1(bb, opcode, vA) \
     { bb, opcode, 0u, vA, 0u, 0u }
 #define DEF_OTHER2(bb, opcode, vA, vB) \
@@ -175,6 +177,56 @@ class MirOptimizationTest : public testing::Test {
     PrepareBasicBlocks(bbs);
   }
 
+  void PrepareNestedLoopsWhile_While() {
+    static const BBDef bbs[] = {
+        DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+        DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+        DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(8)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 8), DEF_PRED2(3, 7)),  // Outer while loop head.
+        DEF_BB(kDalvikByteCode, DEF_SUCC2(6, 7), DEF_PRED2(4, 6)),  // Inner while loop head.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(5)),        // "taken" loops to inner head.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(5)),        // "taken" loops to outer head.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)),
+    };
+    PrepareBasicBlocks(bbs);
+  }
+
+  void PrepareNestedLoopsWhile_WhileWhile() {
+    static const BBDef bbs[] = {
+        DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+        DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+        DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(10)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 10), DEF_PRED2(3, 9)),   // Outer while loop head.
+        DEF_BB(kDalvikByteCode, DEF_SUCC2(6, 7), DEF_PRED2(4, 6)),    // Inner while loop head 1.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(5)),          // Loops to inner head 1.
+        DEF_BB(kDalvikByteCode, DEF_SUCC2(8, 9), DEF_PRED2(5, 8)),    // Inner while loop head 2.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED1(7)),          // loops to inner head 2.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(7)),          // loops to outer head.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)),
+    };
+    PrepareBasicBlocks(bbs);
+  }
+
+  void PrepareNestedLoopsWhile_WhileWhile_WithExtraEdge() {
+    // Extra edge from the first inner loop body to second inner loop body (6u->8u).
+    static const BBDef bbs[] = {
+        DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+        DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+        DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(10)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 10), DEF_PRED2(3, 9)),   // Outer while loop head.
+        DEF_BB(kDalvikByteCode, DEF_SUCC2(6, 7), DEF_PRED2(4, 6)),    // Inner while loop head 1.
+        DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 8), DEF_PRED1(5)),       // Loops to inner head 1.
+        DEF_BB(kDalvikByteCode, DEF_SUCC2(8, 9), DEF_PRED2(5, 8)),    // Inner while loop head 2.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED2(7, 6)),       // loops to inner head 2.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(7)),          // loops to outer head.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)),
+    };
+    PrepareBasicBlocks(bbs);
+  }
+
   void PrepareCatch() {
     static const BBDef bbs[] = {
         DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
@@ -397,6 +449,43 @@ class NullCheckEliminationTest : public MirOptimizationTest {
   }
 };
 
+class SuspendCheckEliminationTest : public MirOptimizationTest {
+ protected:
+  bool IsBackEdge(BasicBlockId branch_bb, BasicBlockId target_bb) {
+    BasicBlock* branch = cu_.mir_graph->GetBasicBlock(branch_bb);
+    return target_bb != NullBasicBlockId && cu_.mir_graph->IsBackEdge(branch, target_bb);
+  }
+
+  bool IsSuspendCheckEdge(BasicBlockId branch_bb, BasicBlockId target_bb) {
+    BasicBlock* branch = cu_.mir_graph->GetBasicBlock(branch_bb);
+    return cu_.mir_graph->IsSuspendCheckEdge(branch, target_bb);
+  }
+
+  void PerformSuspendCheckElimination() {
+    cu_.mir_graph->SSATransformationStart();
+    cu_.mir_graph->ComputeDFSOrders();
+    cu_.mir_graph->ComputeDominators();
+    cu_.mir_graph->ComputeTopologicalSortOrder();
+    cu_.mir_graph->SSATransformationEnd();
+    bool gate_result = cu_.mir_graph->EliminateSuspendChecksGate();
+    ASSERT_TRUE(gate_result);
+    TopologicalSortIterator iterator(cu_.mir_graph.get());
+    bool change = false;
+    for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) {
+      change = cu_.mir_graph->EliminateSuspendChecks(bb);
+    }
+    cu_.mir_graph->EliminateSuspendChecksEnd();
+  }
+
+  SuspendCheckEliminationTest()
+      : MirOptimizationTest() {
+    static const MethodDef methods[] = {
+        { 0u, 1u, 0u, 0u, kDirect, kDirect, false, false },  // Dummy.
+    };
+    PrepareMethods(methods);
+  }
+};
+
 TEST_F(ClassInitCheckEliminationTest, SingleBlock) {
   static const SFieldDef sfields[] = {
       { 0u, 1u, 0u, 0u, kDexMemAccessWord },
@@ -882,7 +971,208 @@ TEST_F(NullCheckEliminationTest, Catch) {
   }
 }
 
-// Undefine MIR_DEF for null check elimination.
-#undef MIR_DEF
+TEST_F(SuspendCheckEliminationTest, LoopNoElimination) {
+  static const MIRDef mirs[] = {
+    DEF_INVOKE(3u, Instruction::INVOKE_STATIC, 0u, 0u),  // Force the pass to run.
+    DEF_OTHER1(4u, Instruction::IF_NEZ, 1u),             // Edge back.
+  };
+
+  PrepareLoop();
+  PrepareMIRs(mirs);
+  PerformSuspendCheckElimination();
+  ASSERT_TRUE(IsBackEdge(4u, 4u));
+  EXPECT_TRUE(IsSuspendCheckEdge(4u, 4u));  // Suspend point on loop to self.
+}
+
+TEST_F(SuspendCheckEliminationTest, LoopElimination) {
+  static const MIRDef mirs[] = {
+    DEF_INVOKE(4u, Instruction::INVOKE_STATIC, 0u, 0u),  // Invoke in the loop.
+    DEF_OTHER1(4u, Instruction::IF_NEZ, 1u),             // Edge back.
+  };
+
+  PrepareLoop();
+  PrepareMIRs(mirs);
+  PerformSuspendCheckElimination();
+  ASSERT_TRUE(IsBackEdge(4u, 4u));
+  EXPECT_FALSE(IsSuspendCheckEdge(4u, 4u));  // No suspend point on loop to self.
+}
+
+TEST_F(SuspendCheckEliminationTest, While_While_NoElimination) {
+  static const MIRDef mirs[] = {
+    DEF_INVOKE(3u, Instruction::INVOKE_STATIC, 0u, 0u),  // Force the pass to run.
+    DEF_OTHER1(4u, Instruction::IF_NEZ, 1u),             // Edge out of outer loop.
+    DEF_OTHER1(5u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop.
+    DEF_OTHER0(6u, Instruction::GOTO),                   // Edge back to inner loop head.
+    DEF_OTHER0(7u, Instruction::GOTO),                   // Edge back to outer loop head.
+  };
+
+  PrepareNestedLoopsWhile_While();
+  PrepareMIRs(mirs);
+  PerformSuspendCheckElimination();
+  ASSERT_TRUE(IsBackEdge(6u, 5u));
+  EXPECT_TRUE(IsSuspendCheckEdge(6u, 5u));
+  ASSERT_TRUE(IsBackEdge(7u, 4u));
+  EXPECT_TRUE(IsSuspendCheckEdge(7u, 4u));
+}
+
+TEST_F(SuspendCheckEliminationTest, While_While_InvokeInOuterLoopHead) {
+  static const MIRDef mirs[] = {
+    DEF_INVOKE(4u, Instruction::INVOKE_STATIC, 0u, 0u),  // Invoke in outer loop head.
+    DEF_OTHER1(4u, Instruction::IF_NEZ, 1u),             // Edge out of outer loop.
+    DEF_OTHER1(5u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop.
+    DEF_OTHER0(6u, Instruction::GOTO),                   // Edge back to inner loop head.
+    DEF_OTHER0(7u, Instruction::GOTO),                   // Edge back to outer loop head.
+  };
+
+  PrepareNestedLoopsWhile_While();
+  PrepareMIRs(mirs);
+  PerformSuspendCheckElimination();
+  ASSERT_TRUE(IsBackEdge(6u, 5u));
+  EXPECT_TRUE(IsSuspendCheckEdge(6u, 5u));
+  ASSERT_TRUE(IsBackEdge(7u, 4u));
+  EXPECT_FALSE(IsSuspendCheckEdge(7u, 4u));
+}
+
+TEST_F(SuspendCheckEliminationTest, While_While_InvokeInOuterLoopBody) {
+  static const MIRDef mirs[] = {
+    DEF_OTHER1(4u, Instruction::IF_NEZ, 1u),             // Edge out of outer loop.
+    DEF_OTHER1(5u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop.
+    DEF_OTHER0(6u, Instruction::GOTO),                   // Edge back to inner loop head.
+    DEF_INVOKE(7u, Instruction::INVOKE_STATIC, 0u, 0u),  // Invoke in outer loop body.
+    DEF_OTHER0(7u, Instruction::GOTO),                   // Edge back to outer loop head.
+  };
+
+  PrepareNestedLoopsWhile_While();
+  PrepareMIRs(mirs);
+  PerformSuspendCheckElimination();
+  ASSERT_TRUE(IsBackEdge(6u, 5u));
+  EXPECT_TRUE(IsSuspendCheckEdge(6u, 5u));
+  ASSERT_TRUE(IsBackEdge(7u, 4u));
+  EXPECT_FALSE(IsSuspendCheckEdge(7u, 4u));
+}
+
+TEST_F(SuspendCheckEliminationTest, While_While_InvokeInInnerLoopHead) {
+  static const MIRDef mirs[] = {
+    DEF_OTHER1(4u, Instruction::IF_NEZ, 1u),             // Edge out of outer loop.
+    DEF_INVOKE(5u, Instruction::INVOKE_STATIC, 0u, 0u),  // Invoke in inner loop head.
+    DEF_OTHER1(5u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop.
+    DEF_OTHER0(6u, Instruction::GOTO),                   // Edge back to inner loop head.
+    DEF_OTHER0(7u, Instruction::GOTO),                   // Edge back to outer loop head.
+  };
+
+  PrepareNestedLoopsWhile_While();
+  PrepareMIRs(mirs);
+  PerformSuspendCheckElimination();
+  ASSERT_TRUE(IsBackEdge(6u, 5u));
+  EXPECT_FALSE(IsSuspendCheckEdge(6u, 5u));
+  ASSERT_TRUE(IsBackEdge(7u, 4u));
+  EXPECT_FALSE(IsSuspendCheckEdge(7u, 4u));
+}
+
+TEST_F(SuspendCheckEliminationTest, While_While_InvokeInInnerLoopBody) {
+  static const MIRDef mirs[] = {
+    DEF_OTHER1(4u, Instruction::IF_NEZ, 1u),             // Edge out of outer loop.
+    DEF_OTHER1(5u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop.
+    DEF_INVOKE(6u, Instruction::INVOKE_STATIC, 0u, 0u),  // Invoke in inner loop body.
+    DEF_OTHER0(6u, Instruction::GOTO),                   // Edge back to inner loop head.
+    DEF_OTHER0(7u, Instruction::GOTO),                   // Edge back to outer loop head.
+  };
+
+  PrepareNestedLoopsWhile_While();
+  PrepareMIRs(mirs);
+  PerformSuspendCheckElimination();
+  ASSERT_TRUE(IsBackEdge(6u, 5u));
+  EXPECT_FALSE(IsSuspendCheckEdge(6u, 5u));
+  ASSERT_TRUE(IsBackEdge(7u, 4u));
+  EXPECT_TRUE(IsSuspendCheckEdge(7u, 4u));
+}
+
+TEST_F(SuspendCheckEliminationTest, While_WhileWhile_InvokeInFirstInnerLoopHead) {
+  static const MIRDef mirs[] = {
+    DEF_OTHER1(4u, Instruction::IF_NEZ, 1u),             // Edge out of outer loop.
+    DEF_INVOKE(5u, Instruction::INVOKE_STATIC, 0u, 0u),  // Invoke in first inner loop head.
+    DEF_OTHER1(5u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop 1.
+    DEF_OTHER0(6u, Instruction::GOTO),                   // Edge back to inner loop head.
+    DEF_OTHER1(7u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop 2.
+    DEF_OTHER0(8u, Instruction::GOTO),                   // Edge back to inner loop 2 head.
+    DEF_OTHER0(9u, Instruction::GOTO),                   // Edge back to outer loop head.
+  };
+
+  PrepareNestedLoopsWhile_WhileWhile();
+  PrepareMIRs(mirs);
+  PerformSuspendCheckElimination();
+  ASSERT_TRUE(IsBackEdge(6u, 5u));
+  EXPECT_FALSE(IsSuspendCheckEdge(6u, 5u));
+  ASSERT_TRUE(IsBackEdge(8u, 7u));
+  EXPECT_TRUE(IsSuspendCheckEdge(8u, 7u));
+  ASSERT_TRUE(IsBackEdge(9u, 4u));
+  EXPECT_FALSE(IsSuspendCheckEdge(9u, 4u));
+}
+
+TEST_F(SuspendCheckEliminationTest, While_WhileWhile_InvokeInFirstInnerLoopBody) {
+  static const MIRDef mirs[] = {
+    DEF_OTHER1(4u, Instruction::IF_NEZ, 1u),             // Edge out of outer loop.
+    DEF_OTHER1(5u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop 1.
+    DEF_INVOKE(6u, Instruction::INVOKE_STATIC, 0u, 0u),  // Invoke in first inner loop body.
+    DEF_OTHER0(6u, Instruction::GOTO),                   // Edge back to inner loop head.
+    DEF_OTHER1(7u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop 2.
+    DEF_OTHER0(8u, Instruction::GOTO),                   // Edge back to inner loop 2 head.
+    DEF_OTHER0(9u, Instruction::GOTO),                   // Edge back to outer loop head.
+  };
+
+  PrepareNestedLoopsWhile_WhileWhile();
+  PrepareMIRs(mirs);
+  PerformSuspendCheckElimination();
+  ASSERT_TRUE(IsBackEdge(6u, 5u));
+  EXPECT_FALSE(IsSuspendCheckEdge(6u, 5u));
+  ASSERT_TRUE(IsBackEdge(8u, 7u));
+  EXPECT_TRUE(IsSuspendCheckEdge(8u, 7u));
+  ASSERT_TRUE(IsBackEdge(9u, 4u));
+  EXPECT_TRUE(IsSuspendCheckEdge(9u, 4u));
+}
+
+TEST_F(SuspendCheckEliminationTest, While_WhileWhile_WithExtraEdge_InvokeInFirstInnerLoopBody) {
+  static const MIRDef mirs[] = {
+    DEF_OTHER1(4u, Instruction::IF_NEZ, 1u),             // Edge out of outer loop.
+    DEF_OTHER1(5u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop 1.
+    DEF_INVOKE(6u, Instruction::INVOKE_STATIC, 0u, 0u),  // Invoke in first inner loop body.
+    DEF_OTHER0(6u, Instruction::GOTO),                   // Edge back to inner loop head.
+    DEF_OTHER1(7u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop 2.
+    DEF_OTHER0(8u, Instruction::GOTO),                   // Edge back to inner loop 2 head.
+    DEF_OTHER0(9u, Instruction::GOTO),                   // Edge back to outer loop head.
+  };
+
+  PrepareNestedLoopsWhile_WhileWhile_WithExtraEdge();
+  PrepareMIRs(mirs);
+  PerformSuspendCheckElimination();
+  ASSERT_TRUE(IsBackEdge(6u, 5u));
+  EXPECT_FALSE(IsSuspendCheckEdge(6u, 5u));
+  ASSERT_TRUE(IsBackEdge(8u, 7u));
+  EXPECT_TRUE(IsSuspendCheckEdge(8u, 7u));  // Unaffected by the extra edge.
+  ASSERT_TRUE(IsBackEdge(9u, 4u));
+  EXPECT_TRUE(IsSuspendCheckEdge(9u, 4u));
+}
+
+TEST_F(SuspendCheckEliminationTest, While_WhileWhile_WithExtraEdge_InvokeInSecondInnerLoopHead) {
+  static const MIRDef mirs[] = {
+    DEF_OTHER1(4u, Instruction::IF_NEZ, 1u),             // Edge out of outer loop.
+    DEF_OTHER1(5u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop 1.
+    DEF_OTHER0(6u, Instruction::GOTO),                   // Edge back to inner loop head.
+    DEF_INVOKE(7u, Instruction::INVOKE_STATIC, 0u, 0u),  // Invoke in second inner loop head.
+    DEF_OTHER1(7u, Instruction::IF_NEZ, 2u),             // Edge out of inner loop 2.
+    DEF_OTHER0(8u, Instruction::GOTO),                   // Edge back to inner loop 2 head.
+    DEF_OTHER0(9u, Instruction::GOTO),                   // Edge back to outer loop head.
+  };
+
+  PrepareNestedLoopsWhile_WhileWhile_WithExtraEdge();
+  PrepareMIRs(mirs);
+  PerformSuspendCheckElimination();
+  ASSERT_TRUE(IsBackEdge(6u, 5u));
+  EXPECT_TRUE(IsSuspendCheckEdge(6u, 5u));
+  ASSERT_TRUE(IsBackEdge(8u, 7u));
+  EXPECT_FALSE(IsSuspendCheckEdge(8u, 7u));  // Unaffected by the extra edge.
+  ASSERT_TRUE(IsBackEdge(9u, 4u));
+  EXPECT_FALSE(IsSuspendCheckEdge(9u, 4u));
+}
 
 }  // namespace art