Optimizing: Test for `HSelect` in irreducible loop.

Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Change-Id: I32e0ef7956cabb436a1759934e24a1c0f4b7ea2d

2 files changed, 90 insertions, 0 deletions

diff --git a/compiler/optimizing/code_flow_simplifier_test.cc b/compiler/optimizing/code_flow_simplifier_test.cc
index dc4268a0aa..a382f0f6f6 100644
--- a/compiler/optimizing/code_flow_simplifier_test.cc
+++ b/compiler/optimizing/code_flow_simplifier_test.cc
@@ -71,4 +71,44 @@ TEST_F(CodeFlowSimplifierTest, testSelectWithAdd) {
   EXPECT_TRUE(phi->GetBlock() == nullptr);
 }
 
+// Test `HSelect` optimization in an irreducible loop.
+TEST_F(CodeFlowSimplifierTest, testSelectInIrreducibleLoop) {
+  HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
+  auto [split, left_header, right_header, body] = CreateIrreducibleLoop(return_block);
+
+  HParameterValue* split_param = MakeParam(DataType::Type::kBool);
+  HParameterValue* bool_param = MakeParam(DataType::Type::kBool);
+  HParameterValue* n_param = MakeParam(DataType::Type::kInt32);
+
+  MakeIf(split, split_param);
+
+  HInstruction* const0 = graph_->GetIntConstant(0);
+  HInstruction* const1 = graph_->GetIntConstant(1);
+  HPhi* right_phi = MakePhi(right_header, {const0, /* placeholder */ const0});
+  HPhi* left_phi = MakePhi(left_header, {const1, right_phi});
+  HAdd* add = MakeBinOp<HAdd>(body, DataType::Type::kInt32, left_phi, const1);
+  right_phi->ReplaceInput(add, 1u);  // Update back-edge input.
+  HCondition* condition = MakeCondition(left_header, kCondGE, left_phi, n_param);
+  MakeIf(left_header, condition);
+
+  auto [if_block, then_block, else_block] = CreateDiamondPattern(body, bool_param);
+  HPhi* phi = MakePhi(body, {const1, const0});
+
+  EXPECT_TRUE(CheckGraphAndTryCodeFlowSimplifier());
+  HLoopInformation* loop_info = left_header->GetLoopInformation();
+  ASSERT_TRUE(loop_info != nullptr);
+  ASSERT_TRUE(loop_info->IsIrreducible());
+
+  EXPECT_TRUE(phi->GetBlock() == nullptr);
+  ASSERT_TRUE(if_block->GetFirstInstruction()->IsSelect());
+
+  ASSERT_EQ(if_block, add->GetBlock());  // Moved when merging blocks.
+
+  for (HBasicBlock* removed_block : {then_block, else_block, body}) {
+    uint32_t removed_block_id = removed_block->GetBlockId();
+    ASSERT_TRUE(removed_block->GetGraph() == nullptr) << removed_block_id;
+    ASSERT_FALSE(loop_info->GetBlocks().IsBitSet(removed_block_id)) << removed_block_id;
+  }
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index 018ffce196..8115ea035d 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -389,6 +389,56 @@ class OptimizingUnitTestHelper {
     return {pre_header, loop};
   }
 
+  // Insert blocks for an irreducible loop before the `loop_exit`:
+  //
+  //      <loop_exit's old predecessor>
+  //                    |
+  //                  split
+  //                 /     \
+  //   left_preheader       right_preheader
+  //         |                     |
+  //    left_header <------- right_header <-+
+  //     |  |                               |
+  //     |  +------------> body ------------+
+  //     |
+  //    loop_exit
+  //
+  // Note that `left_preheader`, `right_preheader` and `body` are needed to avoid critical edges.
+  //
+  // `HGoto` instructions are added to `left_preheader`, `right_preheader`, `body`
+  // and `right_header`. To complete the control flow, the caller should add `HIf`
+  // to `split` and `left_header`.
+  //
+  // Returns `{split, left_header, right_header, body}`.
+  std::tuple<HBasicBlock*, HBasicBlock*, HBasicBlock*, HBasicBlock*> CreateIrreducibleLoop(
+      HBasicBlock* loop_exit) {
+    HBasicBlock* split = AddNewBlock();
+    HBasicBlock* left_preheader = AddNewBlock();
+    HBasicBlock* right_preheader = AddNewBlock();
+    HBasicBlock* left_header = AddNewBlock();
+    HBasicBlock* right_header = AddNewBlock();
+    HBasicBlock* body = AddNewBlock();
+
+    HBasicBlock* predecessor = loop_exit->GetSinglePredecessor();
+    predecessor->ReplaceSuccessor(loop_exit, split);
+
+    split->AddSuccessor(left_preheader);  // true successor
+    split->AddSuccessor(right_preheader);  // false successor
+    left_preheader->AddSuccessor(left_header);
+    right_preheader->AddSuccessor(right_header);
+    left_header->AddSuccessor(loop_exit);  // true successor
+    left_header->AddSuccessor(body);  // false successor
+    body->AddSuccessor(right_header);
+    right_header->AddSuccessor(left_header);
+
+    MakeGoto(left_preheader);
+    MakeGoto(right_preheader);
+    MakeGoto(body);
+    MakeGoto(right_header);
+
+    return {split, left_header, right_header, body};
+  }
+
   HBasicBlock* AddNewBlock() {
     HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
     graph_->AddBlock(block);