summaryrefslogtreecommitdiff
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/code_flow_simplifier.cc112
-rw-r--r--compiler/optimizing/code_flow_simplifier_test.cc52
-rw-r--r--compiler/optimizing/inliner.h3
-rw-r--r--compiler/optimizing/intrinsics.cc8
-rw-r--r--compiler/optimizing/load_store_elimination_test.cc2
-rw-r--r--compiler/optimizing/optimizing_unit_test.h73
-rw-r--r--compiler/optimizing/reference_type_propagation.cc8
7 files changed, 160 insertions, 98 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 a382f0f6f6..8945e03619 100644
--- a/compiler/optimizing/code_flow_simplifier_test.cc
+++ b/compiler/optimizing/code_flow_simplifier_test.cc
@@ -58,7 +58,7 @@ TEST_F(CodeFlowSimplifierTest, testZeroCheckPreventsSelect) {
ManuallyBuildEnvFor(instr, {param, graph_->GetIntConstant(1)});
EXPECT_FALSE(CheckGraphAndTryCodeFlowSimplifier());
- EXPECT_FALSE(phi->GetBlock() == nullptr);
+ EXPECT_INS_RETAINED(phi);
}
// Test that CodeFlowSimplifier succeeds with HAdd.
@@ -68,7 +68,45 @@ TEST_F(CodeFlowSimplifierTest, testSelectWithAdd) {
HAdd* instr = new (GetAllocator()) HAdd(DataType::Type::kInt32, param, param, /*dex_pc=*/ 0);
HPhi* phi = ConstructBasicGraphForSelect(return_block, instr);
EXPECT_TRUE(CheckGraphAndTryCodeFlowSimplifier());
- EXPECT_TRUE(phi->GetBlock() == nullptr);
+ 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.
@@ -84,10 +122,8 @@ TEST_F(CodeFlowSimplifierTest, testSelectInIrreducibleLoop) {
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.
+ auto [left_phi, right_phi, add] =
+ MakeLinearIrreducibleLoopVar(left_header, right_header, body, const1, const0, const1);
HCondition* condition = MakeCondition(left_header, kCondGE, left_phi, n_param);
MakeIf(left_header, condition);
@@ -99,14 +135,14 @@ TEST_F(CodeFlowSimplifierTest, testSelectInIrreducibleLoop) {
ASSERT_TRUE(loop_info != nullptr);
ASSERT_TRUE(loop_info->IsIrreducible());
- EXPECT_TRUE(phi->GetBlock() == nullptr);
+ EXPECT_INS_REMOVED(phi);
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}) {
+ ASSERT_BLOCK_REMOVED(removed_block);
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;
}
}
diff --git a/compiler/optimizing/inliner.h b/compiler/optimizing/inliner.h
index 4afb78a0e2..2ca286ea6a 100644
--- a/compiler/optimizing/inliner.h
+++ b/compiler/optimizing/inliner.h
@@ -246,8 +246,7 @@ class HInliner : public HOptimization {
HInstruction* cursor,
HBasicBlock* bb_cursor);
- HInstanceFieldGet* BuildGetReceiverClass(HInstruction* receiver,
- uint32_t dex_pc) const
+ HInstanceFieldGet* BuildGetReceiverClass(HInstruction* receiver, uint32_t dex_pc) const
REQUIRES_SHARED(Locks::mutator_lock_);
void MaybeRunReferenceTypePropagation(HInstruction* replacement,
diff --git a/compiler/optimizing/intrinsics.cc b/compiler/optimizing/intrinsics.cc
index 713806e217..5323ae2445 100644
--- a/compiler/optimizing/intrinsics.cc
+++ b/compiler/optimizing/intrinsics.cc
@@ -172,15 +172,11 @@ IntrinsicVisitor::ValueOfInfo IntrinsicVisitor::ComputeValueOfInfo(
}
MemberOffset IntrinsicVisitor::GetReferenceDisableIntrinsicOffset() {
- ScopedObjectAccess soa(Thread::Current());
- ArtField* field = WellKnownClasses::java_lang_ref_Reference_disableIntrinsic;
- return field->GetOffset();
+ return WellKnownClasses::java_lang_ref_Reference_disableIntrinsic->GetOffset();
}
MemberOffset IntrinsicVisitor::GetReferenceSlowPathEnabledOffset() {
- ScopedObjectAccess soa(Thread::Current());
- ArtField* field = WellKnownClasses::java_lang_ref_Reference_slowPathEnabled;
- return field->GetOffset();
+ return WellKnownClasses::java_lang_ref_Reference_slowPathEnabled->GetOffset();
}
void IntrinsicVisitor::CreateReferenceGetReferentLocations(HInvoke* invoke,
diff --git a/compiler/optimizing/load_store_elimination_test.cc b/compiler/optimizing/load_store_elimination_test.cc
index 1e5c7082a4..347a050a3b 100644
--- a/compiler/optimizing/load_store_elimination_test.cc
+++ b/compiler/optimizing/load_store_elimination_test.cc
@@ -123,7 +123,7 @@ class LoadStoreEliminationTestBase : public SuperTest, public OptimizingUnitTest
// Return the pre-header and loop block.
std::tuple<HBasicBlock*, HBasicBlock*> CreateDoWhileLoopWithInstructions(
HBasicBlock* loop_exit, std::initializer_list<HInstruction*> suspend_check_env = {}) {
- auto [pre_header, loop] = CreateDoWhileLoop(loop_exit);
+ auto [pre_header, loop, back_edge] = CreateWhileLoop(loop_exit);
MakeSimpleLoopInstructions(loop, loop, suspend_check_env);
return {pre_header, loop};
}
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index 8115ea035d..d81f3804dc 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -90,6 +90,11 @@ inline std::ostream& operator<<(std::ostream& os, const InstructionDumper& id) {
#define ASSERT_INS_REMOVED(a) ASSERT_TRUE(IsRemoved(a)) << "Not removed: " << (InstructionDumper{a})
#define ASSERT_INS_RETAINED(a) ASSERT_FALSE(IsRemoved(a)) << "Removed: " << (InstructionDumper{a})
+#define EXPECT_BLOCK_REMOVED(b) EXPECT_TRUE(IsRemoved(b)) << "Not removed: B" << b->GetBlockId()
+#define EXPECT_BLOCK_RETAINED(b) EXPECT_FALSE(IsRemoved(b)) << "Removed: B" << b->GetBlockId()
+#define ASSERT_BLOCK_REMOVED(b) ASSERT_TRUE(IsRemoved(b)) << "Not removed: B" << b->GetBlockId()
+#define ASSERT_BLOCK_RETAINED(b) ASSERT_FALSE(IsRemoved(b)) << "Removed: B" << b->GetBlockId()
+
inline LiveInterval* BuildInterval(const size_t ranges[][2],
size_t number_of_ranges,
ScopedArenaAllocator* allocator,
@@ -348,6 +353,8 @@ class OptimizingUnitTestHelper {
// empty, leaving the construction of an appropriate condition and `HIf` to the caller.
// Note: The `loop_exit` shall be the "then" successor of the "loop-header". If the `loop_exit`
// is needed as the "else" successor, use `HBlock::SwapSuccessors()` to adjust the order.
+ // Note: A `do { ... } while (...);` loop pattern has the same block structure, except that
+ // the `loop_body` is a single-goto block that exists purely to avoid a critical edge.
std::tuple<HBasicBlock*, HBasicBlock*, HBasicBlock*> CreateWhileLoop(HBasicBlock* loop_exit) {
HBasicBlock* pre_header = AddNewBlock();
HBasicBlock* loop_header = AddNewBlock();
@@ -367,28 +374,6 @@ class OptimizingUnitTestHelper {
return {pre_header, loop_header, loop_body};
}
- // Insert "pre-header" and "loop" blocks before a given `loop_exit` block and connect them in a
- // `do { ... } while (...);` loop pattern. Return the new blocks. Adds `HGoto` to the "pre-header"
- // block but leaves the "loop" block empty, leaving the construction of an appropriate condition
- // and `HIf` to the caller.
- // Note: The `loop_exit` shall be the "then" successor of the "loop". If the `loop_exit`
- // is needed as the "else" successor, use `HBlock::SwapSuccessors()` to adjust the order.
- std::tuple<HBasicBlock*, HBasicBlock*> CreateDoWhileLoop(HBasicBlock* loop_exit) {
- HBasicBlock* pre_header = AddNewBlock();
- HBasicBlock* loop = AddNewBlock();
-
- HBasicBlock* predecessor = loop_exit->GetSinglePredecessor();
- predecessor->ReplaceSuccessor(loop_exit, pre_header);
-
- pre_header->AddSuccessor(loop);
- loop->AddSuccessor(loop_exit); // true successor
- loop->AddSuccessor(loop); // false successor
-
- MakeGoto(pre_header);
-
- return {pre_header, loop};
- }
-
// Insert blocks for an irreducible loop before the `loop_exit`:
//
// <loop_exit's old predecessor>
@@ -923,6 +908,19 @@ class OptimizingUnitTestHelper {
return {phi, add};
}
+ std::tuple<HPhi*, HPhi*, HAdd*> MakeLinearIrreducibleLoopVar(HBasicBlock* left_header,
+ HBasicBlock* right_header,
+ HBasicBlock* body,
+ HInstruction* left_initial,
+ HInstruction* right_initial,
+ HInstruction* increment) {
+ HPhi* left_phi = MakePhi(left_header, {left_initial, /* placeholder */ left_initial});
+ HAdd* add = MakeBinOp<HAdd>(body, left_phi->GetType(), left_phi, increment);
+ HPhi* right_phi = MakePhi(right_header, {right_initial, add});
+ left_phi->ReplaceInput(right_phi, 1u); // Update back-edge input.
+ return {left_phi, right_phi, add};
+ }
+
dex::TypeIndex DefaultTypeIndexForType(DataType::Type type) {
switch (type) {
case DataType::Type::kBool:
@@ -959,6 +957,26 @@ 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;
+ }
+
+ // Returns if the `block` is removed from the graph.
+ static inline bool IsRemoved(HBasicBlock* block) {
+ return block->GetGraph() == nullptr;
+ }
+
protected:
bool CheckGraph(HGraph* graph, std::ostream& oss) {
GraphChecker checker(graph);
@@ -967,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_;
@@ -1006,11 +1030,6 @@ inline std::string Patch(const std::string& original, const diff_t& diff) {
return result;
}
-// Returns if the instruction is removed from the graph.
-inline bool IsRemoved(HInstruction* instruction) {
- return instruction->GetBlock() == nullptr;
-}
-
inline std::ostream& operator<<(std::ostream& oss, const AdjacencyListGraph& alg) {
return alg.Dump(oss);
}
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 3e90a0881f..32b4557de0 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -276,12 +276,8 @@ static void BoundTypeForClassCheck(HInstruction* check) {
return;
}
- {
- ScopedObjectAccess soa(Thread::Current());
- ArtField* field = WellKnownClasses::java_lang_Object_shadowKlass;
- if (field_get->GetFieldInfo().GetField() != field) {
- return;
- }
+ if (field_get->GetFieldInfo().GetField() != WellKnownClasses::java_lang_Object_shadowKlass) {
+ return;
}
if (check->IsIf()) {
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-12-04 00:38:12 +0000