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
diff --git a/compiler/optimizing/select_generator.cc b/compiler/optimizing/select_generator.cc
index 5405382..f3b2af7 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 @@
return select_phi;
}
+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);
+
+ if (!IsSimpleBlock(true_block) ||
+ !IsSimpleBlock(false_block) ||
+ !BlocksMergeTogether(true_block, false_block)) {
+ return false;
+ }
+ 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 {
+ 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);
+
+ // 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);
+ }
+
+ 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;
+}
+
+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);
+
+ // 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 didSelect = false;
+ bool did_select = false;
// Select cache with local allocator.
ScopedArenaAllocator allocator(graph_->GetArenaStack());
- ScopedArenaSafeMap<HInstruction*, HSelect*> cache(
- std::less<HInstruction*>(), allocator.Adapter(kArenaAllocSelectGenerator));
+ 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;
-
- // 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 (!IsSimpleBlock(true_block) ||
- !IsSimpleBlock(false_block) ||
- !BlocksMergeTogether(true_block, false_block)) {
+ if (!block->EndsWithIf()) {
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);
+ if (TryGenerateSelectSimpleDiamondPattern(block, &cache)) {
+ did_select = true;
} 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());
+ // 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;
}
- } else if (phi->GetType() == DataType::Type::kReference) {
- select->SetReferenceTypeInfo(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);
- 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);
- }
-
- 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 = 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);
- }
- 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
diff --git a/compiler/optimizing/select_generator.h b/compiler/optimizing/select_generator.h
index 30ac8a8..4f13917 100644
--- a/compiler/optimizing/select_generator.h
+++ b/compiler/optimizing/select_generator.h
@@ -57,7 +57,9 @@
#ifndef ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
#define ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
+#include "base/scoped_arena_containers.h"
#include "optimization.h"
+#include "optimizing/nodes.h"
namespace art {
@@ -72,6 +74,43 @@
static constexpr const char* kSelectGeneratorPassName = "select_generator";
private:
+ bool TryGenerateSelectSimpleDiamondPattern(HBasicBlock* block,
+ ScopedArenaSafeMap<HInstruction*, HSelect*>* cache);
+
+ // When generating code for nested ternary operators (e.g. `return (x > 100) ? 100 : ((x < -100) ?
+ // -100 : x);`), a dexer can generate a double diamond pattern but it is not a clear cut one due
+ // to the merging of the blocks. `TryFixupDoubleDiamondPattern` recognizes that pattern and fixes
+ // up the graph to have a clean double diamond that `TryGenerateSelectSimpleDiamondPattern` can
+ // use to generate selects.
+ //
+ // In ASCII, it turns:
+ //
+ // 1 (outer if)
+ // / \
+ // 2 3 (inner if)
+ // | / \
+ // | 4 5
+ // \/ |
+ // 6 |
+ // \ |
+ // 7
+ // |
+ // 8
+ // into:
+ // 1 (outer if)
+ // / \
+ // 2 3 (inner if)
+ // | / \
+ // | 4 5
+ // \/ /
+ // 6
+ // |
+ // 8
+ //
+ // In short, block 7 disappears and we merge 6 and 7. Now we have a diamond with {3,4,5,6}, and
+ // when that gets resolved we get another one with the outer if.
+ HBasicBlock* TryFixupDoubleDiamondPattern(HBasicBlock* block);
+
DISALLOW_COPY_AND_ASSIGN(HSelectGenerator);
};
diff --git a/test/567-checker-builder-intrinsics/src/TestMinMax.java b/test/567-checker-builder-intrinsics/src/TestMinMax.java
index 2bedf57..7207006 100644
--- a/test/567-checker-builder-intrinsics/src/TestMinMax.java
+++ b/test/567-checker-builder-intrinsics/src/TestMinMax.java
@@ -564,14 +564,23 @@
return x;
}
- // b/239385201: Disable checks for Min and Max
+ /// CHECK-START: int TestMinMax.minmax3(int) select_generator (after)
+ /// CHECK-DAG: <<Par:i\d+>> ParameterValue
+ /// CHECK-DAG: <<P100:i\d+>> IntConstant 100
+ /// CHECK-DAG: <<M100:i\d+>> IntConstant -100
+ /// CHECK-DAG: <<Cnd1:z\d+>> LessThanOrEqual [<<Par>>,<<P100>>]
+ /// CHECK-DAG: <<Cnd2:z\d+>> GreaterThanOrEqual [<<Par>>,<<M100>>]
+ /// CHECK-DAG: <<Sel1:i\d+>> Select [<<M100>>,<<Par>>,<<Cnd2>>]
+ /// CHECK-DAG: <<Sel2:i\d+>> Select [<<P100>>,<<Sel1>>,<<Cnd1>>]
+ /// CHECK-DAG: Return [<<Sel2>>]
+
/// CHECK-START: int TestMinMax.minmax3(int) instruction_simplifier$after_gvn (after)
/// CHECK-DAG: <<Par:i\d+>> ParameterValue
/// CHECK-DAG: <<P100:i\d+>> IntConstant 100
/// CHECK-DAG: <<M100:i\d+>> IntConstant -100
- // CHECK-DAG: <<Max:i\d+>> Max [<<Par>>,<<M100>>]
- // CHECK-DAG: <<Min:i\d+>> Min [<<Max>>,<<P100>>]
- // CHECK-DAG: Return [<<Min>>]
+ /// CHECK-DAG: <<Max:i\d+>> Max [<<Par>>,<<M100>>]
+ /// CHECK-DAG: <<Min:i\d+>> Min [<<Max>>,<<P100>>]
+ /// CHECK-DAG: Return [<<Min>>]
//
/// CHECK-START: int TestMinMax.minmax3(int) instruction_simplifier$after_gvn (after)
/// CHECK-NOT: Select
@@ -579,14 +588,23 @@
return (x > 100) ? 100 : ((x < -100) ? -100 : x);
}
- // b/239385201: Disable checks for Min and Max
+ /// CHECK-START: int TestMinMax.minmax4(int) select_generator (after)
+ /// CHECK-DAG: <<Par:i\d+>> ParameterValue
+ /// CHECK-DAG: <<P100:i\d+>> IntConstant 100
+ /// CHECK-DAG: <<M100:i\d+>> IntConstant -100
+ /// CHECK-DAG: <<Cnd1:z\d+>> GreaterThanOrEqual [<<Par>>,<<M100>>]
+ /// CHECK-DAG: <<Cnd2:z\d+>> LessThanOrEqual [<<Par>>,<<P100>>]
+ /// CHECK-DAG: <<Sel1:i\d+>> Select [<<P100>>,<<Par>>,<<Cnd2>>]
+ /// CHECK-DAG: <<Sel2:i\d+>> Select [<<M100>>,<<Sel1>>,<<Cnd1>>]
+ /// CHECK-DAG: Return [<<Sel2>>]
+
/// CHECK-START: int TestMinMax.minmax4(int) instruction_simplifier$after_gvn (after)
/// CHECK-DAG: <<Par:i\d+>> ParameterValue
/// CHECK-DAG: <<P100:i\d+>> IntConstant 100
/// CHECK-DAG: <<M100:i\d+>> IntConstant -100
- // CHECK-DAG: <<Min:i\d+>> Min [<<Par>>,<<P100>>]
- // CHECK-DAG: <<Max:i\d+>> Max [<<Min>>,<<M100>>]
- // CHECK-DAG: Return [<<Max>>]
+ /// CHECK-DAG: <<Min:i\d+>> Min [<<Par>>,<<P100>>]
+ /// CHECK-DAG: <<Max:i\d+>> Max [<<Min>>,<<M100>>]
+ /// CHECK-DAG: Return [<<Max>>]
//
/// CHECK-START: int TestMinMax.minmax4(int) instruction_simplifier$after_gvn (after)
/// CHECK-NOT: Select