summaryrefslogtreecommitdiff
path: root/compiler
diff options
context:
space:
mode:
Diffstat (limited to 'compiler')
-rw-r--r--compiler/optimizing/code_flow_simplifier.cc112
-rw-r--r--compiler/optimizing/code_flow_simplifier_test.cc38
-rw-r--r--compiler/optimizing/optimizing_unit_test.h16
3 files changed, 118 insertions, 48 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_;
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-12-30 07:36:56 +0000