From d661c115a57277e64e8225d2d69629635f7d4e3a Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Wed, 22 Jan 2025 14:23:27 +0000 Subject: Optimizing: Remove `CreateDoWhileLoop()`. And do some other gtest cleanup. Test: m test-art-host-gtest Test: testrunner.py --host --optimizing Change-Id: I9d2c3241e5cd9f96722284c4654b8b2fd446b104 --- compiler/optimizing/code_flow_simplifier_test.cc | 14 +++--- compiler/optimizing/load_store_elimination_test.cc | 2 +- compiler/optimizing/optimizing_unit_test.h | 57 ++++++++++++---------- 3 files changed, 37 insertions(+), 36 deletions(-) (limited to 'compiler/optimizing') diff --git a/compiler/optimizing/code_flow_simplifier_test.cc b/compiler/optimizing/code_flow_simplifier_test.cc index a382f0f6f6..1abd9f8fa6 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,7 @@ 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 `HSelect` optimization in an irreducible loop. @@ -84,10 +84,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(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 +97,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/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 CreateDoWhileLoopWithInstructions( HBasicBlock* loop_exit, std::initializer_list 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..21998b19da 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 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 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`: // // @@ -923,6 +908,19 @@ class OptimizingUnitTestHelper { return {phi, add}; } + std::tuple 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(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,16 @@ class OptimizingUnitTestHelper { return val; } + // 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); @@ -1006,11 +1014,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); } -- cgit v1.2.3-59-g8ed1b From 1bf1220ef5a723793035e7f21d708d3201842959 Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Wed, 22 Jan 2025 15:34:37 +0000 Subject: 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 --- compiler/optimizing/code_flow_simplifier.cc | 112 ++++++++++++--------- compiler/optimizing/code_flow_simplifier_test.cc | 38 +++++++ compiler/optimizing/optimizing_unit_test.h | 16 +++ .../smali/Main2.smali | 6 +- test/663-checker-select-generator/src/Main.java | 5 +- 5 files changed, 123 insertions(+), 54 deletions(-) (limited to 'compiler/optimizing') 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 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(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 expected) { + return RangeEquals(block->GetPredecessors(), expected); + } + + static bool InputsEqual(HInstruction* instruction, + std::initializer_list 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 + static bool RangeEquals(Range&& range, std::initializer_list expected) { + return std::distance(range.begin(), range.end()) == expected.size() && + std::equal(range.begin(), range.end(), expected.begin()); + } + std::vector> dex_files_; std::unique_ptr 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: <> IntConstant 1 ## CHECK-DAG: <> IntConstant 13 ## CHECK-DAG: <> IntConstant 42 -## CHECK-DAG: <> Phi [<>,<>,<>] -## CHECK-DAG: <> Phi [<>,<>,<>] +## CHECK-DAG: <> Phi [<>,<>] +## CHECK-DAG: <> Phi [<>,<>] ## CHECK-DAG: <> Add [<>,<>] ## CHECK-DAG: <> LessThanOrEqual [<>,<>] -## CHECK-DAG: If [<>] +## CHECK-DAG: <>,<>,<>] - /// CHECK-DAG: Return [<>] + /// CHECK-DAG: <> Select [<>,<>,<>] + /// CHECK-DAG: Return [<