Generate selects for nested ternary operators

After an R8 update, the generated dex instructions are different
which means that the structure of the graph is different and we
weren't recognizing a possibility of select generation.

We now recognize it and can update the graph on the fly,
generating the corresponding selects.

Bug: 239385201
Fixes: 239385201
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: I07644f0a69369e809994b4dd39bdd95c2cc7dc6c

1 files changed, 226 insertions, 116 deletions

diff --git a/compiler/optimizing/select_generator.cc b/compiler/optimizing/select_generator.cc
index 54053820ca..f3b2af7491 100644
--- a/compiler/optimizing/select_generator.cc
+++ b/compiler/optimizing/select_generator.cc
@@ -16,7 +16,7 @@
 
 #include "select_generator.h"
 
-#include "base/scoped_arena_containers.h"
+#include "optimizing/nodes.h"
 #include "reference_type_propagation.h"
 
 namespace art {
@@ -90,135 +90,245 @@ static HPhi* GetSingleChangedPhi(HBasicBlock* block, size_t index1, size_t index
   return select_phi;
 }
 
-bool HSelectGenerator::Run() {
-  bool didSelect = false;
-  // Select cache with local allocator.
-  ScopedArenaAllocator allocator(graph_->GetArenaStack());
-  ScopedArenaSafeMap<HInstruction*, HSelect*> cache(
-      std::less<HInstruction*>(), allocator.Adapter(kArenaAllocSelectGenerator));
+bool HSelectGenerator::TryGenerateSelectSimpleDiamondPattern(
+    HBasicBlock* block, ScopedArenaSafeMap<HInstruction*, HSelect*>* cache) {
+  DCHECK(block->GetLastInstruction()->IsIf());
+  HIf* if_instruction = block->GetLastInstruction()->AsIf();
+  HBasicBlock* true_block = if_instruction->IfTrueSuccessor();
+  HBasicBlock* false_block = if_instruction->IfFalseSuccessor();
+  DCHECK_NE(true_block, false_block);
 
-  // Iterate in post order in the unlikely case that removing one occurrence of
-  // the selection pattern empties a branch block of another occurrence.
-  for (HBasicBlock* block : graph_->GetPostOrder()) {
-    if (!block->EndsWithIf()) continue;
+  if (!IsSimpleBlock(true_block) ||
+      !IsSimpleBlock(false_block) ||
+      !BlocksMergeTogether(true_block, false_block)) {
+    return false;
+  }
+  HBasicBlock* merge_block = true_block->GetSingleSuccessor();
 
-    // Find elements of the diamond pattern.
-    HIf* if_instruction = block->GetLastInstruction()->AsIf();
-    HBasicBlock* true_block = if_instruction->IfTrueSuccessor();
-    HBasicBlock* false_block = if_instruction->IfFalseSuccessor();
-    DCHECK_NE(true_block, false_block);
+  // If the branches are not empty, move instructions in front of the If.
+  // TODO(dbrazdil): This puts an instruction between If and its condition.
+  //                 Implement moving of conditions to first users if possible.
+  while (!true_block->IsSingleGoto() && !true_block->IsSingleReturn()) {
+    HInstruction* instr = true_block->GetFirstInstruction();
+    DCHECK(!instr->CanThrow());
+    instr->MoveBefore(if_instruction);
+  }
+  while (!false_block->IsSingleGoto() && !false_block->IsSingleReturn()) {
+    HInstruction* instr = false_block->GetFirstInstruction();
+    DCHECK(!instr->CanThrow());
+    instr->MoveBefore(if_instruction);
+  }
+  DCHECK(true_block->IsSingleGoto() || true_block->IsSingleReturn());
+  DCHECK(false_block->IsSingleGoto() || false_block->IsSingleReturn());
 
-    if (!IsSimpleBlock(true_block) ||
-        !IsSimpleBlock(false_block) ||
-        !BlocksMergeTogether(true_block, false_block)) {
-      continue;
-    }
-    HBasicBlock* merge_block = true_block->GetSingleSuccessor();
-
-    // If the branches are not empty, move instructions in front of the If.
-    // TODO(dbrazdil): This puts an instruction between If and its condition.
-    //                 Implement moving of conditions to first users if possible.
-    while (!true_block->IsSingleGoto() && !true_block->IsSingleReturn()) {
-      HInstruction* instr = true_block->GetFirstInstruction();
-      DCHECK(!instr->CanThrow());
-      instr->MoveBefore(if_instruction);
-    }
-    while (!false_block->IsSingleGoto() && !false_block->IsSingleReturn()) {
-      HInstruction* instr = false_block->GetFirstInstruction();
-      DCHECK(!instr->CanThrow());
-      instr->MoveBefore(if_instruction);
-    }
-    DCHECK(true_block->IsSingleGoto() || true_block->IsSingleReturn());
-    DCHECK(false_block->IsSingleGoto() || false_block->IsSingleReturn());
-
-    // Find the resulting true/false values.
-    size_t predecessor_index_true = merge_block->GetPredecessorIndexOf(true_block);
-    size_t predecessor_index_false = merge_block->GetPredecessorIndexOf(false_block);
-    DCHECK_NE(predecessor_index_true, predecessor_index_false);
-
-    bool both_successors_return = true_block->IsSingleReturn() && false_block->IsSingleReturn();
-    HPhi* phi = GetSingleChangedPhi(merge_block, predecessor_index_true, predecessor_index_false);
-
-    HInstruction* true_value = nullptr;
-    HInstruction* false_value = nullptr;
-    if (both_successors_return) {
-      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 {
-      continue;
-    }
-    DCHECK(both_successors_return || phi != nullptr);
-
-    // 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::FixUpInstructionType(select, graph_->GetHandleCache());
-      }
-    } else if (phi->GetType() == DataType::Type::kReference) {
-      select->SetReferenceTypeInfo(phi->GetReferenceTypeInfo());
-    }
-    block->InsertInstructionBefore(select, if_instruction);
+  // Find the resulting true/false values.
+  size_t predecessor_index_true = merge_block->GetPredecessorIndexOf(true_block);
+  size_t predecessor_index_false = merge_block->GetPredecessorIndexOf(false_block);
+  DCHECK_NE(predecessor_index_true, predecessor_index_false);
 
-    // 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 both_successors_return = true_block->IsSingleReturn() && false_block->IsSingleReturn();
+  HPhi* phi = GetSingleChangedPhi(merge_block, predecessor_index_true, predecessor_index_false);
+
+  HInstruction* true_value = nullptr;
+  HInstruction* false_value = nullptr;
+  if (both_successors_return) {
+    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;
+  }
+  DCHECK(both_successors_return || phi != nullptr);
+
+  // 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::FixUpInstructionType(select, graph_->GetHandleCache());
     }
+  } else if (phi->GetType() == DataType::Type::kReference) {
+    select->SetReferenceTypeInfo(phi->GetReferenceTypeInfo());
+  }
+  block->InsertInstructionBefore(select, if_instruction);
 
-    bool only_two_predecessors = (merge_block->GetPredecessors().size() == 2u);
-    true_block->DisconnectAndDelete();
+  // 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);
+  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);
+    DCHECK_EQ(block->GetSingleSuccessor(), merge_block);
+    block->MergeWith(merge_block);
+  }
 
-    // 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);
-      DCHECK_EQ(block->GetSingleSuccessor(), merge_block);
-      block->MergeWith(merge_block);
+  MaybeRecordStat(stats_, MethodCompilationStat::kSelectGenerated);
+
+  // Very simple way of finding common subexpressions in the generated HSelect statements
+  // (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);
     }
+    it->second = select;  // always cache latest
+  }
+
+  // No need to update dominance information, as we are simplifying
+  // a simple diamond shape, where the join block is merged with the
+  // entry block. Any following blocks would have had the join block
+  // as a dominator, and `MergeWith` handles changing that to the
+  // entry block
+  return true;
+}
 
-    MaybeRecordStat(stats_, MethodCompilationStat::kSelectGenerated);
+HBasicBlock* HSelectGenerator::TryFixupDoubleDiamondPattern(HBasicBlock* block) {
+  DCHECK(block->GetLastInstruction()->IsIf());
+  HIf* if_instruction = block->GetLastInstruction()->AsIf();
+  HBasicBlock* true_block = if_instruction->IfTrueSuccessor();
+  HBasicBlock* false_block = if_instruction->IfFalseSuccessor();
+  DCHECK_NE(true_block, false_block);
 
-    // Very simple way of finding common subexpressions in the generated HSelect statements
-    // (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);
+  // One branch must be a single goto, and the other one the inner if.
+  if (true_block->IsSingleGoto() == false_block->IsSingleGoto()) {
+    return nullptr;
+  }
+
+  HBasicBlock* single_goto = true_block->IsSingleGoto() ? true_block : false_block;
+  HBasicBlock* inner_if_block = true_block->IsSingleGoto() ? false_block : true_block;
+
+  // The innner if branch has to be a block with just a comparison and an if.
+  if (!inner_if_block->EndsWithIf() ||
+      inner_if_block->GetLastInstruction()->AsIf()->InputAt(0) !=
+          inner_if_block->GetFirstInstruction() ||
+      inner_if_block->GetLastInstruction()->GetPrevious() !=
+          inner_if_block->GetFirstInstruction() ||
+      !inner_if_block->GetFirstInstruction()->IsCondition()) {
+    return nullptr;
+  }
+
+  HIf* inner_if_instruction = inner_if_block->GetLastInstruction()->AsIf();
+  HBasicBlock* inner_if_true_block = inner_if_instruction->IfTrueSuccessor();
+  HBasicBlock* inner_if_false_block = inner_if_instruction->IfFalseSuccessor();
+  if (!inner_if_true_block->IsSingleGoto() || !inner_if_false_block->IsSingleGoto()) {
+    return nullptr;
+  }
+
+  // One must merge into the outer condition and the other must not.
+  if (BlocksMergeTogether(single_goto, inner_if_true_block) ==
+      BlocksMergeTogether(single_goto, inner_if_false_block)) {
+    return nullptr;
+  }
+
+  // First merge merges the outer if with one of the inner if branches. The block must be a Phi and
+  // a Goto.
+  HBasicBlock* first_merge = single_goto->GetSingleSuccessor();
+  if (first_merge->GetNumberOfPredecessors() != 2 ||
+      first_merge->GetPhis().CountSize() != 1 ||
+      !first_merge->GetLastInstruction()->IsGoto() ||
+      first_merge->GetFirstInstruction() != first_merge->GetLastInstruction()) {
+    return nullptr;
+  }
+
+  HPhi* first_phi = first_merge->GetFirstPhi()->AsPhi();
+
+  // Second merge is first_merge and the remainder branch merging. It must be phi + goto, or phi +
+  // return. Depending on the first merge, we define the second merge.
+  HBasicBlock* merges_into_second_merge =
+    BlocksMergeTogether(single_goto, inner_if_true_block)
+      ? inner_if_false_block
+      : inner_if_true_block;
+  if (!BlocksMergeTogether(first_merge, merges_into_second_merge)) {
+    return nullptr;
+  }
+
+  HBasicBlock* second_merge = merges_into_second_merge->GetSingleSuccessor();
+  if (second_merge->GetNumberOfPredecessors() != 2 ||
+      second_merge->GetPhis().CountSize() != 1 ||
+      !(second_merge->GetLastInstruction()->IsGoto() ||
+        second_merge->GetLastInstruction()->IsReturn()) ||
+      second_merge->GetFirstInstruction() != second_merge->GetLastInstruction()) {
+    return nullptr;
+  }
+
+  size_t index = second_merge->GetPredecessorIndexOf(merges_into_second_merge);
+  HPhi* second_phi = second_merge->GetFirstPhi()->AsPhi();
+
+  // Merge the phis.
+  first_phi->AddInput(second_phi->InputAt(index));
+  merges_into_second_merge->ReplaceSuccessor(second_merge, first_merge);
+  second_phi->ReplaceWith(first_phi);
+  second_merge->RemovePhi(second_phi);
+
+  // Sort out the new domination before merging the blocks
+  DCHECK_EQ(second_merge->GetSinglePredecessor(), first_merge);
+  second_merge->GetDominator()->RemoveDominatedBlock(second_merge);
+  second_merge->SetDominator(first_merge);
+  first_merge->AddDominatedBlock(second_merge);
+  first_merge->MergeWith(second_merge);
+
+  return inner_if_block;
+}
+
+bool HSelectGenerator::Run() {
+  bool did_select = false;
+  // Select cache with local allocator.
+  ScopedArenaAllocator allocator(graph_->GetArenaStack());
+  ScopedArenaSafeMap<HInstruction*, HSelect*> cache(std::less<HInstruction*>(),
+                                                    allocator.Adapter(kArenaAllocSelectGenerator));
+
+  // Iterate in post order in the unlikely case that removing one occurrence of
+  // the selection pattern empties a branch block of another occurrence.
+  for (HBasicBlock* block : graph_->GetPostOrder()) {
+    if (!block->EndsWithIf()) {
+      continue;
+    }
+
+    if (TryGenerateSelectSimpleDiamondPattern(block, &cache)) {
+      did_select = true;
     } else {
-      // Found cached value. See if latest can replace cached in the HIR.
-      HSelect* cached = it->second;
-      DCHECK_EQ(cached->GetCondition(), select->GetCondition());
-      if (cached->GetTrueValue() == select->GetTrueValue() &&
-          cached->GetFalseValue() == select->GetFalseValue() &&
-          select->StrictlyDominates(cached)) {
-       cached->ReplaceWith(select);
-       cached->GetBlock()->RemoveInstruction(cached);
+      // Try to fix up the odd version of the double diamond pattern. If we could do it, it means
+      // that we can generate two selects.
+      HBasicBlock* inner_if_block = TryFixupDoubleDiamondPattern(block);
+      if (inner_if_block != nullptr) {
+        // Generate the selects now since `inner_if_block` should be after `block` in PostOrder.
+        bool result = TryGenerateSelectSimpleDiamondPattern(inner_if_block, &cache);
+        DCHECK(result);
+        result = TryGenerateSelectSimpleDiamondPattern(block, &cache);
+        DCHECK(result);
+        did_select = true;
       }
-      it->second = select;  // always cache latest
     }
-
-    // No need to update dominance information, as we are simplifying
-    // a simple diamond shape, where the join block is merged with the
-    // entry block. Any following blocks would have had the join block
-    // as a dominator, and `MergeWith` handles changing that to the
-    // entry block.
-    didSelect = true;
   }
-  return didSelect;
+
+  return did_select;
 }
 
 }  // namespace art