Optimizing: Generate `HSelect` if there are more phis...

... as long as they have identical inputs at the relevant
indexes.

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

5 files changed, 123 insertions, 54 deletions

diff --git a/compiler/optimizing/code_flow_simplifier.cc b/compiler/optimizing/code_flow_simplifier.cc
index b32a4a5c4c..855da3e959 100644
--- a/compiler/optimizing/code_flow_simplifier.cc
+++ b/compiler/optimizing/code_flow_simplifier.cc
@@ -68,23 +68,31 @@ static bool BlocksMergeTogether(HBasicBlock* block1, HBasicBlock* block2) {
   return block1->GetSingleSuccessor() == block2->GetSingleSuccessor();
 }
 
-// Returns nullptr if `block` has either no phis or there is more than one phi. Otherwise returns
-// that phi.
-static HPhi* GetSinglePhi(HBasicBlock* block, size_t index1, size_t index2) {
+// Search `block` for phis that have different inputs at `index1` and `index2`.
+// If none is found, returns `{true, nullptr}`.
+// If exactly one such `phi` is found, returns `{true, phi}`.
+// Otherwise (if more than one such phi is found), returns `{false, nullptr}`.
+static std::pair<bool, HPhi*> HasAtMostOnePhiWithDifferentInputs(HBasicBlock* block,
+                                                                 size_t index1,
+                                                                 size_t index2) {
   DCHECK_NE(index1, index2);
 
   HPhi* select_phi = nullptr;
   for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
     HPhi* phi = it.Current()->AsPhi();
+    auto&& inputs = phi->GetInputs();
+    if (inputs[index1] == inputs[index2]) {
+      continue;
+    }
     if (select_phi == nullptr) {
       // First phi found.
       select_phi = phi;
     } else {
       // More than one phi found, return null.
-      return nullptr;
+      return {false, nullptr};
     }
   }
-  return select_phi;
+  return {true, select_phi};
 }
 
 bool HCodeFlowSimplifier::TryGenerateSelectSimpleDiamondPattern(
@@ -132,54 +140,60 @@ bool HCodeFlowSimplifier::TryGenerateSelectSimpleDiamondPattern(
   //     a = 1; b = 2;
   //   }
   //   // use a and b
-  HPhi* phi = GetSinglePhi(merge_block, predecessor_index_true, predecessor_index_false);
-
+  bool at_most_one_phi_with_different_inputs = false;
+  HPhi* phi = nullptr;
   HInstruction* true_value = nullptr;
   HInstruction* false_value = nullptr;
   if (both_successors_return) {
+    // Note: This can create a select with the same then-value and else-value.
     true_value = true_block->GetFirstInstruction()->InputAt(0);
     false_value = false_block->GetFirstInstruction()->InputAt(0);
-  } else if (phi != nullptr) {
-    true_value = phi->InputAt(predecessor_index_true);
-    false_value = phi->InputAt(predecessor_index_false);
   } else {
-    return false;
+    std::tie(at_most_one_phi_with_different_inputs, phi) = HasAtMostOnePhiWithDifferentInputs(
+        merge_block, predecessor_index_true, predecessor_index_false);
+    if (!at_most_one_phi_with_different_inputs) {
+      return false;
+    }
+    if (phi != nullptr) {
+      true_value = phi->InputAt(predecessor_index_true);
+      false_value = phi->InputAt(predecessor_index_false);
+    }  // else we don't need to create a `HSelect` at all.
   }
-  DCHECK(both_successors_return || phi != nullptr);
+  DCHECK(both_successors_return || at_most_one_phi_with_different_inputs);
 
   // Create the Select instruction and insert it in front of the If.
   HInstruction* condition = if_instruction->InputAt(0);
-  HSelect* select = new (graph_->GetAllocator()) HSelect(condition,
-                                                          true_value,
-                                                          false_value,
-                                                          if_instruction->GetDexPc());
-  if (both_successors_return) {
-    if (true_value->GetType() == DataType::Type::kReference) {
-      DCHECK(false_value->GetType() == DataType::Type::kReference);
-      ReferenceTypePropagation::FixUpSelectType(select, graph_->GetHandleCache());
+  HSelect* select = nullptr;
+  if (both_successors_return || phi != nullptr) {
+    select = new (graph_->GetAllocator()) HSelect(condition,
+                                                  true_value,
+                                                  false_value,
+                                                  if_instruction->GetDexPc());
+    block->InsertInstructionBefore(select, if_instruction);
+    if (both_successors_return) {
+      if (true_value->GetType() == DataType::Type::kReference) {
+        DCHECK(false_value->GetType() == DataType::Type::kReference);
+        ReferenceTypePropagation::FixUpSelectType(select, graph_->GetHandleCache());
+      }
+      false_block->GetFirstInstruction()->ReplaceInput(select, 0);
+    } else {
+      if (phi->GetType() == DataType::Type::kReference) {
+        select->SetReferenceTypeInfoIfValid(phi->GetReferenceTypeInfo());
+      }
+      phi->ReplaceInput(select, predecessor_index_false);  // We'll remove the true branch below.
     }
-  } else if (phi->GetType() == DataType::Type::kReference) {
-    select->SetReferenceTypeInfoIfValid(phi->GetReferenceTypeInfo());
-  }
-  block->InsertInstructionBefore(select, if_instruction);
-
-  // Remove the true branch which removes the corresponding Phi
-  // input if needed. If left only with the false branch, the Phi is
-  // automatically removed.
-  if (both_successors_return) {
-    false_block->GetFirstInstruction()->ReplaceInput(select, 0);
-  } else {
-    phi->ReplaceInput(select, predecessor_index_false);
   }
 
-  bool only_two_predecessors = (merge_block->GetPredecessors().size() == 2u);
+  // Remove the true branch which removes the corresponding Phi input if needed.
+  // If left only with the false branch, the Phi is automatically removed.
   true_block->DisconnectAndDelete();
 
   // Merge remaining blocks which are now connected with Goto.
   DCHECK_EQ(block->GetSingleSuccessor(), false_block);
   block->MergeWith(false_block);
-  if (!both_successors_return && only_two_predecessors) {
-    DCHECK_EQ(only_two_predecessors, phi->GetBlock() == nullptr);
+  if (!both_successors_return && merge_block->GetPredecessors().size() == 1u) {
+    DCHECK_IMPLIES(phi != nullptr, phi->GetBlock() == nullptr);
+    DCHECK(merge_block->GetPhis().IsEmpty());
     DCHECK_EQ(block->GetSingleSuccessor(), merge_block);
     block->MergeWith(merge_block);
   }
@@ -190,20 +204,22 @@ bool HCodeFlowSimplifier::TryGenerateSelectSimpleDiamondPattern(
   // (since this runs after GVN). Lookup by condition, and reuse latest one if possible
   // (due to post order, latest select is most likely replacement). If needed, we could
   // improve this by e.g. using the operands in the map as well.
-  auto it = cache->find(condition);
-  if (it == cache->end()) {
-    cache->Put(condition, select);
-  } else {
-    // Found cached value. See if latest can replace cached in the HIR.
-    HSelect* cached_select = it->second;
-    DCHECK_EQ(cached_select->GetCondition(), select->GetCondition());
-    if (cached_select->GetTrueValue() == select->GetTrueValue() &&
-        cached_select->GetFalseValue() == select->GetFalseValue() &&
-        select->StrictlyDominates(cached_select)) {
-      cached_select->ReplaceWith(select);
-      cached_select->GetBlock()->RemoveInstruction(cached_select);
+  if (select != nullptr) {
+    auto it = cache->find(condition);
+    if (it == cache->end()) {
+      cache->Put(condition, select);
+    } else {
+      // Found cached value. See if latest can replace cached in the HIR.
+      HSelect* cached_select = it->second;
+      DCHECK_EQ(cached_select->GetCondition(), select->GetCondition());
+      if (cached_select->GetTrueValue() == select->GetTrueValue() &&
+          cached_select->GetFalseValue() == select->GetFalseValue() &&
+          select->StrictlyDominates(cached_select)) {
+        cached_select->ReplaceWith(select);
+        cached_select->GetBlock()->RemoveInstruction(cached_select);
+      }
+      it->second = select;  // always cache latest
     }
-    it->second = select;  // always cache latest
   }
 
   // No need to update dominance information, as we are simplifying
diff --git a/compiler/optimizing/code_flow_simplifier_test.cc b/compiler/optimizing/code_flow_simplifier_test.cc
index 1abd9f8fa6..8945e03619 100644
--- a/compiler/optimizing/code_flow_simplifier_test.cc
+++ b/compiler/optimizing/code_flow_simplifier_test.cc
@@ -71,6 +71,44 @@ TEST_F(CodeFlowSimplifierTest, testSelectWithAdd) {
   EXPECT_INS_REMOVED(phi);
 }
 
+// Test that CodeFlowSimplifier succeeds if there is an additional `HPhi` with identical inputs.
+TEST_F(CodeFlowSimplifierTest, testSelectWithAddAndExtraPhi) {
+  // Create a graph with three blocks merging to the `return_block`.
+  HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
+  HParameterValue* bool_param1 = MakeParam(DataType::Type::kBool);
+  HParameterValue* bool_param2 = MakeParam(DataType::Type::kBool);
+  HParameterValue* param = MakeParam(DataType::Type::kInt32);
+  HInstruction* const0 = graph_->GetIntConstant(0);
+  auto [if_block1, left, mid] = CreateDiamondPattern(return_block, bool_param1);
+  HBasicBlock* if_block2 = AddNewBlock();
+  if_block1->ReplaceSuccessor(mid, if_block2);
+  HBasicBlock* right = AddNewBlock();
+  if_block2->AddSuccessor(mid);
+  if_block2->AddSuccessor(right);
+  HIf* if2 = MakeIf(if_block2, bool_param2);
+  right->AddSuccessor(return_block);
+  MakeGoto(right);
+  ASSERT_TRUE(PredecessorsEqual(return_block, {left, mid, right}));
+  HAdd* add = MakeBinOp<HAdd>(right, DataType::Type::kInt32, param, param);
+  HPhi* phi1 = MakePhi(return_block, {param, param, add});
+  HPhi* phi2 = MakePhi(return_block, {param, const0, const0});
+
+  // Prevent second `HSelect` match. Do not rely on the "instructions per branch" limit.
+  MakeInvokeStatic(left, DataType::Type::kVoid, {}, {});
+
+  EXPECT_TRUE(CheckGraphAndTryCodeFlowSimplifier());
+
+  ASSERT_BLOCK_RETAINED(left);
+  ASSERT_BLOCK_REMOVED(mid);
+  ASSERT_BLOCK_REMOVED(right);
+  HInstruction* select = if2->GetPrevious();  // `HSelect` is inserted before `HIf`.
+  ASSERT_TRUE(select->IsSelect());
+  ASSERT_INS_RETAINED(phi1);
+  ASSERT_TRUE(InputsEqual(phi1, {param, select}));
+  ASSERT_INS_RETAINED(phi2);
+  ASSERT_TRUE(InputsEqual(phi2, {param, const0}));
+}
+
 // Test `HSelect` optimization in an irreducible loop.
 TEST_F(CodeFlowSimplifierTest, testSelectInIrreducibleLoop) {
   HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index 21998b19da..d81f3804dc 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -957,6 +957,16 @@ class OptimizingUnitTestHelper {
     return val;
   }
 
+  static bool PredecessorsEqual(HBasicBlock* block,
+                                std::initializer_list<HBasicBlock*> expected) {
+    return RangeEquals(block->GetPredecessors(), expected);
+  }
+
+  static bool InputsEqual(HInstruction* instruction,
+                          std::initializer_list<HInstruction*> expected) {
+    return RangeEquals(instruction->GetInputs(), expected);
+  }
+
   // Returns if the `instruction` is removed from the graph.
   static inline bool IsRemoved(HInstruction* instruction) {
     return instruction->GetBlock() == nullptr;
@@ -975,6 +985,12 @@ class OptimizingUnitTestHelper {
     return checker.IsValid();
   }
 
+  template <typename Range, typename ElementType>
+  static bool RangeEquals(Range&& range, std::initializer_list<ElementType> expected) {
+    return std::distance(range.begin(), range.end()) == expected.size() &&
+           std::equal(range.begin(), range.end(), expected.begin());
+  }
+
   std::vector<std::unique_ptr<const StandardDexFile>> dex_files_;
   std::unique_ptr<ArenaPoolAndAllocator> pool_and_allocator_;
 
diff --git a/test/463-checker-boolean-simplifier/smali/Main2.smali b/test/463-checker-boolean-simplifier/smali/Main2.smali
index b10e61022c..9bf0bc1b13 100644
--- a/test/463-checker-boolean-simplifier/smali/Main2.smali
+++ b/test/463-checker-boolean-simplifier/smali/Main2.smali
@@ -231,11 +231,11 @@
 ## CHECK-DAG:     <<Const1:i\d+>>   IntConstant 1
 ## CHECK-DAG:     <<Const13:i\d+>>  IntConstant 13
 ## CHECK-DAG:     <<Const42:i\d+>>  IntConstant 42
-## CHECK-DAG:     <<PhiX:i\d+>>     Phi [<<Const0>>,<<Const13>>,<<Const42>>]
-## CHECK-DAG:     <<PhiY:i\d+>>     Phi [<<Const1>>,<<Add:i\d+>>,<<Add>>]
+## CHECK-DAG:     <<PhiX:i\d+>>     Phi [<<Const0>>,<<Select:i\d+>>]
+## CHECK-DAG:     <<PhiY:i\d+>>     Phi [<<Const1>>,<<Add:i\d+>>]
 ## CHECK-DAG:     <<Add>>           Add [<<PhiY>>,<<Const1>>]
 ## CHECK-DAG:     <<Cond:z\d+>>     LessThanOrEqual [<<Add>>,<<Const1>>]
-## CHECK-DAG:                       If [<<Cond>>]
+## CHECK-DAG:     <<Select>>        Select [<<Const13>>,<<Const42>>,<<Cond>>]
 ## CHECK-DAG:                       Return [<<PhiX>>]
 
 # The original java source of this method:
diff --git a/test/663-checker-select-generator/src/Main.java b/test/663-checker-select-generator/src/Main.java
index 6a5564b1c1..631210c9bc 100644
--- a/test/663-checker-select-generator/src/Main.java
+++ b/test/663-checker-select-generator/src/Main.java
@@ -106,9 +106,8 @@ public class Main {
   /// CHECK-DAG:   <<Bool2:z\d+>>   ParameterValue
   /// CHECK-DAG:   <<Const10:i\d+>> IntConstant 10
   /// CHECK-DAG:   <<Const20:i\d+>> IntConstant 20
-  /// CHECK-DAG:   <<Select:i\d+>>  Select [<<Const20>>,<<Const20>>,<<Bool2>>]
-  /// CHECK-DAG:   <<Select2:i\d+>> Select [<<Select>>,<<Const10>>,<<Bool1>>]
-  /// CHECK-DAG:                    Return [<<Select2>>]
+  /// CHECK-DAG:   <<Select:i\d+>>  Select [<<Const20>>,<<Const10>>,<<Bool1>>]
+  /// CHECK-DAG:                    Return [<<Select>>]
   private static int $noinline$testDoubleDiamondSameValueButNotAllOuter(boolean bool_param_1, boolean bool_param_2) {
       int return_value;
     if (bool_param_1) {