From f79077ad9e7b1e5b885466dce7f672130ee7efea Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Thu, 23 Jan 2025 14:45:35 +0000 Subject: Optimizing: Rename `HCodeFlowSimplifier`... ... to `HControlFlowSimplifier` because "control flow" is the correct technical term. Test: m test-art-host-gtest Test: testrunner.py --host --optimizing Change-Id: I2607ac699fa33c3e7ca7f54364e1e8497148412b --- compiler/Android.bp | 4 +- compiler/optimizing/code_flow_simplifier.cc | 360 --------------------- compiler/optimizing/code_flow_simplifier.h | 120 ------- compiler/optimizing/code_flow_simplifier_test.cc | 150 --------- compiler/optimizing/control_flow_simplifier.cc | 360 +++++++++++++++++++++ compiler/optimizing/control_flow_simplifier.h | 120 +++++++ .../optimizing/control_flow_simplifier_test.cc | 150 +++++++++ compiler/optimizing/dead_code_elimination.cc | 6 +- compiler/optimizing/optimization.cc | 12 +- compiler/optimizing/optimization.h | 2 +- compiler/optimizing/optimizing_compiler.cc | 2 +- libartbase/base/arena_allocator.cc | 2 +- libartbase/base/arena_allocator.h | 2 +- .../2265-checker-select-binary-unary/src/Main.java | 8 +- .../src/Main.java | 8 +- .../smali/Main2.smali | 24 +- .../src-art/Main.java | 38 +-- .../smali/TestCase.smali | 4 +- test/474-checker-boolean-input/src/Main.java | 8 +- .../smali/TestCase.smali | 2 +- .../src/TestCompare.java | 6 +- .../src/TestMinMax.java | 8 +- .../src/TestRotate.java | 8 +- .../src/TestSignum.java | 4 +- .../smali/TestCase.smali | 2 +- .../smali/SmaliTests.smali | 12 +- .../src/Main.java | 8 +- test/657-branches/src/Main.java | 4 +- test/663-checker-select-generator/src/Main.java | 50 +-- test/850-checker-branches/smali/TestCase.smali | 2 +- 30 files changed, 743 insertions(+), 743 deletions(-) delete mode 100644 compiler/optimizing/code_flow_simplifier.cc delete mode 100644 compiler/optimizing/code_flow_simplifier.h delete mode 100644 compiler/optimizing/code_flow_simplifier_test.cc create mode 100644 compiler/optimizing/control_flow_simplifier.cc create mode 100644 compiler/optimizing/control_flow_simplifier.h create mode 100644 compiler/optimizing/control_flow_simplifier_test.cc diff --git a/compiler/Android.bp b/compiler/Android.bp index c904746435..67cd48ba42 100644 --- a/compiler/Android.bp +++ b/compiler/Android.bp @@ -147,13 +147,13 @@ art_cc_defaults { "optimizing/bounds_check_elimination.cc", "optimizing/builder.cc", "optimizing/cha_guard_optimization.cc", - "optimizing/code_flow_simplifier.cc", "optimizing/code_generation_data.cc", "optimizing/code_generator.cc", "optimizing/code_generator_utils.cc", "optimizing/code_sinking.cc", "optimizing/constant_folding.cc", "optimizing/constructor_fence_redundancy_elimination.cc", + "optimizing/control_flow_simplifier.cc", "optimizing/data_type.cc", "optimizing/dead_code_elimination.cc", "optimizing/escape.cc", @@ -459,8 +459,8 @@ art_cc_defaults { "linker/output_stream_test.cc", "oat/jni_stub_hash_map_test.cc", "optimizing/bounds_check_elimination_test.cc", - "optimizing/code_flow_simplifier_test.cc", "optimizing/constant_folding_test.cc", + "optimizing/control_flow_simplifier_test.cc", "optimizing/data_type_test.cc", "optimizing/dead_code_elimination_test.cc", "optimizing/dominator_test.cc", diff --git a/compiler/optimizing/code_flow_simplifier.cc b/compiler/optimizing/code_flow_simplifier.cc deleted file mode 100644 index 855da3e959..0000000000 --- a/compiler/optimizing/code_flow_simplifier.cc +++ /dev/null @@ -1,360 +0,0 @@ -/* - * Copyright (C) 2016 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "code_flow_simplifier.h" - -#include "optimizing/nodes.h" -#include "reference_type_propagation.h" - -namespace art HIDDEN { - -static constexpr size_t kMaxInstructionsInBranch = 1u; - -HCodeFlowSimplifier::HCodeFlowSimplifier(HGraph* graph, - OptimizingCompilerStats* stats, - const char* name) - : HOptimization(graph, name, stats) { -} - -// Returns true if `block` has only one predecessor, ends with a Goto -// or a Return and contains at most `kMaxInstructionsInBranch` other -// movable instruction with no side-effects. -static bool IsSimpleBlock(HBasicBlock* block) { - if (block->GetPredecessors().size() != 1u) { - return false; - } - DCHECK(block->GetPhis().IsEmpty()); - - size_t num_instructions = 0u; - for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { - HInstruction* instruction = it.Current(); - if (instruction->IsControlFlow()) { - return instruction->IsGoto() || instruction->IsReturn(); - } else if (instruction->CanBeMoved() && - !instruction->HasSideEffects() && - !instruction->CanThrow()) { - if (instruction->IsSelect() && instruction->AsSelect()->GetCondition()->GetBlock() == block) { - // Count one HCondition and HSelect in the same block as a single instruction. - // This enables finding nested selects. - continue; - } else if (++num_instructions > kMaxInstructionsInBranch) { - return false; // bail as soon as we exceed number of allowed instructions - } - } else { - return false; - } - } - - LOG(FATAL) << "Unreachable"; - UNREACHABLE(); -} - -// Returns true if 'block1' and 'block2' are empty and merge into the -// same single successor. -static bool BlocksMergeTogether(HBasicBlock* block1, HBasicBlock* block2) { - return block1->GetSingleSuccessor() == block2->GetSingleSuccessor(); -} - -// 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 {false, nullptr}; - } - } - return {true, select_phi}; -} - -bool HCodeFlowSimplifier::TryGenerateSelectSimpleDiamondPattern( - HBasicBlock* block, ScopedArenaSafeMap* 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(); - // TODO(solanes): Extend to support multiple phis? e.g. - // int a, b; - // if (bool) { - // a = 0; b = 1; - // } else { - // a = 1; b = 2; - // } - // // use a and b - 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 { - 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 || 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 = 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. - } - } - - // 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 && 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); - } - - 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. - 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 - } - } - - // 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* HCodeFlowSimplifier::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); - - // No need to update dominance information. There's a chance that `merges_into_second_merge` - // doesn't come before `first_merge` but we don't need to fix it since `merges_into_second_merge` - // will disappear from the graph altogether when doing the follow-up - // TryGenerateSelectSimpleDiamondPattern. - - return inner_if_block; -} - -bool HCodeFlowSimplifier::Run() { - bool did_select = false; - // Select cache with local allocator. - ScopedArenaAllocator allocator(graph_->GetArenaStack()); - ScopedArenaSafeMap cache( - std::less(), allocator.Adapter(kArenaAllocCodeFlowSimplifier)); - - // 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 { - // 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; - } - } - } - - return did_select; -} - -} // namespace art diff --git a/compiler/optimizing/code_flow_simplifier.h b/compiler/optimizing/code_flow_simplifier.h deleted file mode 100644 index 36d8d3d95b..0000000000 --- a/compiler/optimizing/code_flow_simplifier.h +++ /dev/null @@ -1,120 +0,0 @@ -/* - * Copyright (C) 2016 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/* - * This optimization recognizes the common diamond selection pattern and - * replaces it with an instance of the HSelect instruction. - * - * Recognized patterns: - * - * If [ Condition ] - * / \ - * false branch true branch - * \ / - * Phi [FalseValue, TrueValue] - * - * and - * - * If [ Condition ] - * / \ - * false branch true branch - * return FalseValue return TrueValue - * - * The pattern will be simplified if `true_branch` and `false_branch` each - * contain at most one instruction without any side effects. - * - * Blocks are merged into one and Select replaces the If and the Phi. - * - * For the first pattern it simplifies to: - * - * true branch - * false branch - * Select [FalseValue, TrueValue, Condition] - * - * For the second pattern it simplifies to: - * - * true branch - * false branch - * return Select [FalseValue, TrueValue, Condition] - * - * Note: In order to recognize no side-effect blocks, this optimization must be - * run after the instruction simplifier has removed redundant suspend checks. - */ - -#ifndef ART_COMPILER_OPTIMIZING_CODE_FLOW_SIMPLIFIER_H_ -#define ART_COMPILER_OPTIMIZING_CODE_FLOW_SIMPLIFIER_H_ - -#include "base/macros.h" -#include "base/scoped_arena_containers.h" -#include "optimization.h" -#include "optimizing/nodes.h" - -namespace art HIDDEN { - -class HCodeFlowSimplifier : public HOptimization { - public: - HCodeFlowSimplifier(HGraph* graph, - OptimizingCompilerStats* stats, - const char* name = kCodeFlowSimplifierPassName); - - bool Run() override; - - static constexpr const char* kCodeFlowSimplifierPassName = "code_flow_simplifier"; - - private: - bool TryGenerateSelectSimpleDiamondPattern(HBasicBlock* block, - ScopedArenaSafeMap* 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(HCodeFlowSimplifier); -}; - -} // namespace art - -#endif // ART_COMPILER_OPTIMIZING_CODE_FLOW_SIMPLIFIER_H_ diff --git a/compiler/optimizing/code_flow_simplifier_test.cc b/compiler/optimizing/code_flow_simplifier_test.cc deleted file mode 100644 index 8945e03619..0000000000 --- a/compiler/optimizing/code_flow_simplifier_test.cc +++ /dev/null @@ -1,150 +0,0 @@ -/* - * Copyright (C) 2018 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "code_flow_simplifier.h" - -#include "base/arena_allocator.h" -#include "base/macros.h" -#include "builder.h" -#include "nodes.h" -#include "optimizing_unit_test.h" -#include "side_effects_analysis.h" - -namespace art HIDDEN { - -class CodeFlowSimplifierTest : public OptimizingUnitTest { - protected: - HPhi* ConstructBasicGraphForSelect(HBasicBlock* return_block, HInstruction* instr) { - HParameterValue* bool_param = MakeParam(DataType::Type::kBool); - HIntConstant* const1 = graph_->GetIntConstant(1); - - auto [if_block, then_block, else_block] = CreateDiamondPattern(return_block, bool_param); - - AddOrInsertInstruction(then_block, instr); - HPhi* phi = MakePhi(return_block, {instr, const1}); - return phi; - } - - bool CheckGraphAndTryCodeFlowSimplifier() { - graph_->BuildDominatorTree(); - EXPECT_TRUE(CheckGraph()); - - SideEffectsAnalysis side_effects(graph_); - side_effects.Run(); - return HCodeFlowSimplifier(graph_, /*handles*/ nullptr, /*stats*/ nullptr).Run(); - } -}; - -// HDivZeroCheck might throw and should not be hoisted from the conditional to an unconditional. -TEST_F(CodeFlowSimplifierTest, testZeroCheckPreventsSelect) { - HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid(); - HParameterValue* param = MakeParam(DataType::Type::kInt32); - HDivZeroCheck* instr = new (GetAllocator()) HDivZeroCheck(param, 0); - HPhi* phi = ConstructBasicGraphForSelect(return_block, instr); - - ManuallyBuildEnvFor(instr, {param, graph_->GetIntConstant(1)}); - - EXPECT_FALSE(CheckGraphAndTryCodeFlowSimplifier()); - EXPECT_INS_RETAINED(phi); -} - -// Test that CodeFlowSimplifier succeeds with HAdd. -TEST_F(CodeFlowSimplifierTest, testSelectWithAdd) { - HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid(); - HParameterValue* param = MakeParam(DataType::Type::kInt32); - HAdd* instr = new (GetAllocator()) HAdd(DataType::Type::kInt32, param, param, /*dex_pc=*/ 0); - HPhi* phi = ConstructBasicGraphForSelect(return_block, instr); - EXPECT_TRUE(CheckGraphAndTryCodeFlowSimplifier()); - 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(); - auto [split, left_header, right_header, body] = CreateIrreducibleLoop(return_block); - - HParameterValue* split_param = MakeParam(DataType::Type::kBool); - HParameterValue* bool_param = MakeParam(DataType::Type::kBool); - HParameterValue* n_param = MakeParam(DataType::Type::kInt32); - - MakeIf(split, split_param); - - HInstruction* const0 = graph_->GetIntConstant(0); - HInstruction* const1 = graph_->GetIntConstant(1); - 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); - - auto [if_block, then_block, else_block] = CreateDiamondPattern(body, bool_param); - HPhi* phi = MakePhi(body, {const1, const0}); - - EXPECT_TRUE(CheckGraphAndTryCodeFlowSimplifier()); - HLoopInformation* loop_info = left_header->GetLoopInformation(); - ASSERT_TRUE(loop_info != nullptr); - ASSERT_TRUE(loop_info->IsIrreducible()); - - 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_FALSE(loop_info->GetBlocks().IsBitSet(removed_block_id)) << removed_block_id; - } -} - -} // namespace art diff --git a/compiler/optimizing/control_flow_simplifier.cc b/compiler/optimizing/control_flow_simplifier.cc new file mode 100644 index 0000000000..3e1c0ac0fc --- /dev/null +++ b/compiler/optimizing/control_flow_simplifier.cc @@ -0,0 +1,360 @@ +/* + * Copyright (C) 2016 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "control_flow_simplifier.h" + +#include "optimizing/nodes.h" +#include "reference_type_propagation.h" + +namespace art HIDDEN { + +static constexpr size_t kMaxInstructionsInBranch = 1u; + +HControlFlowSimplifier::HControlFlowSimplifier(HGraph* graph, + OptimizingCompilerStats* stats, + const char* name) + : HOptimization(graph, name, stats) { +} + +// Returns true if `block` has only one predecessor, ends with a Goto +// or a Return and contains at most `kMaxInstructionsInBranch` other +// movable instruction with no side-effects. +static bool IsSimpleBlock(HBasicBlock* block) { + if (block->GetPredecessors().size() != 1u) { + return false; + } + DCHECK(block->GetPhis().IsEmpty()); + + size_t num_instructions = 0u; + for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { + HInstruction* instruction = it.Current(); + if (instruction->IsControlFlow()) { + return instruction->IsGoto() || instruction->IsReturn(); + } else if (instruction->CanBeMoved() && + !instruction->HasSideEffects() && + !instruction->CanThrow()) { + if (instruction->IsSelect() && instruction->AsSelect()->GetCondition()->GetBlock() == block) { + // Count one HCondition and HSelect in the same block as a single instruction. + // This enables finding nested selects. + continue; + } else if (++num_instructions > kMaxInstructionsInBranch) { + return false; // bail as soon as we exceed number of allowed instructions + } + } else { + return false; + } + } + + LOG(FATAL) << "Unreachable"; + UNREACHABLE(); +} + +// Returns true if 'block1' and 'block2' are empty and merge into the +// same single successor. +static bool BlocksMergeTogether(HBasicBlock* block1, HBasicBlock* block2) { + return block1->GetSingleSuccessor() == block2->GetSingleSuccessor(); +} + +// 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 {false, nullptr}; + } + } + return {true, select_phi}; +} + +bool HControlFlowSimplifier::TryGenerateSelectSimpleDiamondPattern( + HBasicBlock* block, ScopedArenaSafeMap* 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(); + // TODO(solanes): Extend to support multiple phis? e.g. + // int a, b; + // if (bool) { + // a = 0; b = 1; + // } else { + // a = 1; b = 2; + // } + // // use a and b + 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 { + 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 || 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 = 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. + } + } + + // 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 && 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); + } + + 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. + 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 + } + } + + // 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* HControlFlowSimplifier::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); + + // No need to update dominance information. There's a chance that `merges_into_second_merge` + // doesn't come before `first_merge` but we don't need to fix it since `merges_into_second_merge` + // will disappear from the graph altogether when doing the follow-up + // TryGenerateSelectSimpleDiamondPattern. + + return inner_if_block; +} + +bool HControlFlowSimplifier::Run() { + bool did_select = false; + // Select cache with local allocator. + ScopedArenaAllocator allocator(graph_->GetArenaStack()); + ScopedArenaSafeMap cache( + std::less(), allocator.Adapter(kArenaAllocControlFlowSimplifier)); + + // 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 { + // 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; + } + } + } + + return did_select; +} + +} // namespace art diff --git a/compiler/optimizing/control_flow_simplifier.h b/compiler/optimizing/control_flow_simplifier.h new file mode 100644 index 0000000000..0c74ec299f --- /dev/null +++ b/compiler/optimizing/control_flow_simplifier.h @@ -0,0 +1,120 @@ +/* + * Copyright (C) 2016 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/* + * This optimization recognizes the common diamond selection pattern and + * replaces it with an instance of the HSelect instruction. + * + * Recognized patterns: + * + * If [ Condition ] + * / \ + * false branch true branch + * \ / + * Phi [FalseValue, TrueValue] + * + * and + * + * If [ Condition ] + * / \ + * false branch true branch + * return FalseValue return TrueValue + * + * The pattern will be simplified if `true_branch` and `false_branch` each + * contain at most one instruction without any side effects. + * + * Blocks are merged into one and Select replaces the If and the Phi. + * + * For the first pattern it simplifies to: + * + * true branch + * false branch + * Select [FalseValue, TrueValue, Condition] + * + * For the second pattern it simplifies to: + * + * true branch + * false branch + * return Select [FalseValue, TrueValue, Condition] + * + * Note: In order to recognize no side-effect blocks, this optimization must be + * run after the instruction simplifier has removed redundant suspend checks. + */ + +#ifndef ART_COMPILER_OPTIMIZING_CONTROL_FLOW_SIMPLIFIER_H_ +#define ART_COMPILER_OPTIMIZING_CONTROL_FLOW_SIMPLIFIER_H_ + +#include "base/macros.h" +#include "base/scoped_arena_containers.h" +#include "optimization.h" +#include "optimizing/nodes.h" + +namespace art HIDDEN { + +class HControlFlowSimplifier : public HOptimization { + public: + HControlFlowSimplifier(HGraph* graph, + OptimizingCompilerStats* stats, + const char* name = kControlFlowSimplifierPassName); + + bool Run() override; + + static constexpr const char* kControlFlowSimplifierPassName = "control_flow_simplifier"; + + private: + bool TryGenerateSelectSimpleDiamondPattern(HBasicBlock* block, + ScopedArenaSafeMap* 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(HControlFlowSimplifier); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_CONTROL_FLOW_SIMPLIFIER_H_ diff --git a/compiler/optimizing/control_flow_simplifier_test.cc b/compiler/optimizing/control_flow_simplifier_test.cc new file mode 100644 index 0000000000..2e88c6c77b --- /dev/null +++ b/compiler/optimizing/control_flow_simplifier_test.cc @@ -0,0 +1,150 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "control_flow_simplifier.h" + +#include "base/arena_allocator.h" +#include "base/macros.h" +#include "builder.h" +#include "nodes.h" +#include "optimizing_unit_test.h" +#include "side_effects_analysis.h" + +namespace art HIDDEN { + +class ControlFlowSimplifierTest : public OptimizingUnitTest { + protected: + HPhi* ConstructBasicGraphForSelect(HBasicBlock* return_block, HInstruction* instr) { + HParameterValue* bool_param = MakeParam(DataType::Type::kBool); + HIntConstant* const1 = graph_->GetIntConstant(1); + + auto [if_block, then_block, else_block] = CreateDiamondPattern(return_block, bool_param); + + AddOrInsertInstruction(then_block, instr); + HPhi* phi = MakePhi(return_block, {instr, const1}); + return phi; + } + + bool CheckGraphAndTryControlFlowSimplifier() { + graph_->BuildDominatorTree(); + EXPECT_TRUE(CheckGraph()); + + SideEffectsAnalysis side_effects(graph_); + side_effects.Run(); + return HControlFlowSimplifier(graph_, /*handles*/ nullptr, /*stats*/ nullptr).Run(); + } +}; + +// HDivZeroCheck might throw and should not be hoisted from the conditional to an unconditional. +TEST_F(ControlFlowSimplifierTest, testZeroCheckPreventsSelect) { + HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid(); + HParameterValue* param = MakeParam(DataType::Type::kInt32); + HDivZeroCheck* instr = new (GetAllocator()) HDivZeroCheck(param, 0); + HPhi* phi = ConstructBasicGraphForSelect(return_block, instr); + + ManuallyBuildEnvFor(instr, {param, graph_->GetIntConstant(1)}); + + EXPECT_FALSE(CheckGraphAndTryControlFlowSimplifier()); + EXPECT_INS_RETAINED(phi); +} + +// Test that ControlFlowSimplifier succeeds with HAdd. +TEST_F(ControlFlowSimplifierTest, testSelectWithAdd) { + HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid(); + HParameterValue* param = MakeParam(DataType::Type::kInt32); + HAdd* instr = new (GetAllocator()) HAdd(DataType::Type::kInt32, param, param, /*dex_pc=*/ 0); + HPhi* phi = ConstructBasicGraphForSelect(return_block, instr); + EXPECT_TRUE(CheckGraphAndTryControlFlowSimplifier()); + EXPECT_INS_REMOVED(phi); +} + +// Test that ControlFlowSimplifier succeeds if there is an additional `HPhi` with identical inputs. +TEST_F(ControlFlowSimplifierTest, 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(CheckGraphAndTryControlFlowSimplifier()); + + 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(ControlFlowSimplifierTest, testSelectInIrreducibleLoop) { + HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid(); + auto [split, left_header, right_header, body] = CreateIrreducibleLoop(return_block); + + HParameterValue* split_param = MakeParam(DataType::Type::kBool); + HParameterValue* bool_param = MakeParam(DataType::Type::kBool); + HParameterValue* n_param = MakeParam(DataType::Type::kInt32); + + MakeIf(split, split_param); + + HInstruction* const0 = graph_->GetIntConstant(0); + HInstruction* const1 = graph_->GetIntConstant(1); + 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); + + auto [if_block, then_block, else_block] = CreateDiamondPattern(body, bool_param); + HPhi* phi = MakePhi(body, {const1, const0}); + + EXPECT_TRUE(CheckGraphAndTryControlFlowSimplifier()); + HLoopInformation* loop_info = left_header->GetLoopInformation(); + ASSERT_TRUE(loop_info != nullptr); + ASSERT_TRUE(loop_info->IsIrreducible()); + + 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_FALSE(loop_info->GetBlocks().IsBitSet(removed_block_id)) << removed_block_id; + } +} + +} // namespace art diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc index ede909526d..c5ec0b93b2 100644 --- a/compiler/optimizing/dead_code_elimination.cc +++ b/compiler/optimizing/dead_code_elimination.cc @@ -526,10 +526,10 @@ void HDeadCodeElimination::MaybeAddPhi(HBasicBlock* block) { // | // 8 // `7` (which would be `block` in this example), and `6` will come from both the true path and - // the false path of `1`. We bumped into something similar in `HCodeFlowSimplifier`. See - // `HCodeFlowSimplifier::TryFixupDoubleDiamondPattern()`. + // the false path of `1`. We bumped into something similar in `HControlFlowSimplifier`. See + // `HControlFlowSimplifier::TryFixupDoubleDiamondPattern()`. // TODO(solanes): Figure out if we can fix up the graph into a double diamond in a generic way - // so that `HDeadCodeElimination` and `HCodeFlowSimplifier` can take advantage of it. + // so that `HDeadCodeElimination` and `HControlFlowSimplifier` can take advantage of it. if (!same_input) { // `1` and `7` having the opposite condition is a case we are missing. We could potentially diff --git a/compiler/optimizing/optimization.cc b/compiler/optimizing/optimization.cc index c876254050..31780739bc 100644 --- a/compiler/optimizing/optimization.cc +++ b/compiler/optimizing/optimization.cc @@ -40,10 +40,10 @@ #include "bounds_check_elimination.h" #include "cha_guard_optimization.h" -#include "code_flow_simplifier.h" #include "code_sinking.h" #include "constant_folding.h" #include "constructor_fence_redundancy_elimination.h" +#include "control_flow_simplifier.h" #include "dead_code_elimination.h" #include "dex/code_item_accessors-inl.h" #include "driver/compiler_options.h" @@ -88,8 +88,8 @@ const char* OptimizationPassName(OptimizationPass pass) { return HDeadCodeElimination::kDeadCodeEliminationPassName; case OptimizationPass::kInliner: return HInliner::kInlinerPassName; - case OptimizationPass::kCodeFlowSimplifier: - return HCodeFlowSimplifier::kCodeFlowSimplifierPassName; + case OptimizationPass::kControlFlowSimplifier: + return HControlFlowSimplifier::kControlFlowSimplifierPassName; case OptimizationPass::kAggressiveInstructionSimplifier: case OptimizationPass::kInstructionSimplifier: return InstructionSimplifier::kInstructionSimplifierPassName; @@ -146,10 +146,10 @@ const char* OptimizationPassName(OptimizationPass pass) { OptimizationPass OptimizationPassByName(const std::string& pass_name) { X(OptimizationPass::kBoundsCheckElimination); X(OptimizationPass::kCHAGuardOptimization); - X(OptimizationPass::kCodeFlowSimplifier); X(OptimizationPass::kCodeSinking); X(OptimizationPass::kConstantFolding); X(OptimizationPass::kConstructorFenceRedundancyElimination); + X(OptimizationPass::kControlFlowSimplifier); X(OptimizationPass::kDeadCodeElimination); X(OptimizationPass::kGlobalValueNumbering); X(OptimizationPass::kInductionVarAnalysis); @@ -266,8 +266,8 @@ ArenaVector ConstructOptimizations( pass_name); break; } - case OptimizationPass::kCodeFlowSimplifier: - opt = new (allocator) HCodeFlowSimplifier(graph, stats, pass_name); + case OptimizationPass::kControlFlowSimplifier: + opt = new (allocator) HControlFlowSimplifier(graph, stats, pass_name); break; case OptimizationPass::kInstructionSimplifier: opt = new (allocator) InstructionSimplifier(graph, codegen, stats, pass_name); diff --git a/compiler/optimizing/optimization.h b/compiler/optimizing/optimization.h index 395c45e3f7..0f0a15f7c9 100644 --- a/compiler/optimizing/optimization.h +++ b/compiler/optimizing/optimization.h @@ -70,10 +70,10 @@ enum class OptimizationPass { kAggressiveInstructionSimplifier, kBoundsCheckElimination, kCHAGuardOptimization, - kCodeFlowSimplifier, kCodeSinking, kConstantFolding, kConstructorFenceRedundancyElimination, + kControlFlowSimplifier, kDeadCodeElimination, kGlobalValueNumbering, kInductionVarAnalysis, diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 5067872ee4..76c201d6a9 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -666,7 +666,7 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph, "reference_type_propagation$after_gvn", OptimizationPass::kGlobalValueNumbering), // Simplification (TODO: only if GVN occurred). - OptDef(OptimizationPass::kCodeFlowSimplifier), + OptDef(OptimizationPass::kControlFlowSimplifier), OptDef(OptimizationPass::kConstantFolding, "constant_folding$after_gvn"), OptDef(OptimizationPass::kInstructionSimplifier, diff --git a/libartbase/base/arena_allocator.cc b/libartbase/base/arena_allocator.cc index e665ce95c3..6e51402045 100644 --- a/libartbase/base/arena_allocator.cc +++ b/libartbase/base/arena_allocator.cc @@ -77,7 +77,7 @@ const char* const ArenaAllocatorStatsImpl::kAllocNames[] = { "SsaLiveness ", "SsaPhiElim ", "RefTypeProp ", - "CodeFlowSimp ", + "CtrlFlowSimp ", "SideEffects ", "RegAllocator ", "RegAllocVldt ", diff --git a/libartbase/base/arena_allocator.h b/libartbase/base/arena_allocator.h index b32921f0e3..e47319c53e 100644 --- a/libartbase/base/arena_allocator.h +++ b/libartbase/base/arena_allocator.h @@ -88,7 +88,7 @@ enum ArenaAllocKind { kArenaAllocSsaLiveness, kArenaAllocSsaPhiElimination, kArenaAllocReferenceTypePropagation, - kArenaAllocCodeFlowSimplifier, + kArenaAllocControlFlowSimplifier, kArenaAllocSideEffectsAnalysis, kArenaAllocRegisterAllocator, kArenaAllocRegisterAllocatorValidate, diff --git a/test/2265-checker-select-binary-unary/src/Main.java b/test/2265-checker-select-binary-unary/src/Main.java index 94c2bf7796..61f4b053aa 100644 --- a/test/2265-checker-select-binary-unary/src/Main.java +++ b/test/2265-checker-select-binary-unary/src/Main.java @@ -31,7 +31,7 @@ public class Main { assertIntEquals(12, $noinline$testLongToInt(1, 0)); } - /// CHECK-START: long Main.$noinline$testIntToLong(int, int) code_flow_simplifier (after) + /// CHECK-START: long Main.$noinline$testIntToLong(int, int) control_flow_simplifier (after) /// CHECK: <> LongConstant 10 /// CHECK: <> IntConstant 1 /// CHECK: <> IntConstant 2 @@ -54,7 +54,7 @@ public class Main { return result + (a < b ? c : d); } - /// CHECK-START: float Main.$noinline$testIntToFloat(int, int) code_flow_simplifier (after) + /// CHECK-START: float Main.$noinline$testIntToFloat(int, int) control_flow_simplifier (after) /// CHECK: <> FloatConstant 10 /// CHECK: <> IntConstant 1 /// CHECK: <> IntConstant 2 @@ -77,7 +77,7 @@ public class Main { return result + (a < b ? c : d); } - /// CHECK-START: byte Main.$noinline$testIntToByte(int, int) code_flow_simplifier (after) + /// CHECK-START: byte Main.$noinline$testIntToByte(int, int) control_flow_simplifier (after) /// CHECK: <> IntConstant 10 /// CHECK: <> IntConstant 257 /// CHECK: <> IntConstant 258 @@ -102,7 +102,7 @@ public class Main { return (byte) (result + (byte) (a < b ? c : d)); } - /// CHECK-START: int Main.$noinline$testLongToInt(int, int) code_flow_simplifier (after) + /// CHECK-START: int Main.$noinline$testLongToInt(int, int) control_flow_simplifier (after) /// CHECK: <> IntConstant 10 /// CHECK: <> LongConstant 4294967297 /// CHECK: <> LongConstant 4294967298 diff --git a/test/458-checker-instruct-simplification/src/Main.java b/test/458-checker-instruct-simplification/src/Main.java index 9600c43028..f65d339dae 100644 --- a/test/458-checker-instruct-simplification/src/Main.java +++ b/test/458-checker-instruct-simplification/src/Main.java @@ -1231,7 +1231,7 @@ public class Main { /// CHECK-DAG: <> Phi [<>,<>] /// CHECK-DAG: Return [<>] - /// CHECK-START: int Main.$noinline$booleanFieldNotEqualOne() code_flow_simplifier (after) + /// CHECK-START: int Main.$noinline$booleanFieldNotEqualOne() control_flow_simplifier (after) /// CHECK-DAG: <> StaticFieldGet /// CHECK-DAG: <> IntConstant 13 /// CHECK-DAG: <> IntConstant 54 @@ -1252,7 +1252,7 @@ public class Main { /// CHECK-DAG: <> Phi [<>,<>] /// CHECK-DAG: Return [<>] - /// CHECK-START: int Main.$noinline$booleanFieldEqualZero() code_flow_simplifier (after) + /// CHECK-START: int Main.$noinline$booleanFieldEqualZero() control_flow_simplifier (after) /// CHECK-DAG: <> StaticFieldGet /// CHECK-DAG: <> IntConstant 13 /// CHECK-DAG: <> IntConstant 54 @@ -1278,7 +1278,7 @@ public class Main { /// CHECK-DAG: <> Phi [<>,<>] /// CHECK-DAG: Return [<>] - /// CHECK-START: int Main.$noinline$intConditionNotEqualOne(int) code_flow_simplifier (after) + /// CHECK-START: int Main.$noinline$intConditionNotEqualOne(int) control_flow_simplifier (after) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> IntConstant 13 /// CHECK-DAG: <> IntConstant 42 @@ -1308,7 +1308,7 @@ public class Main { /// CHECK-DAG: <> Phi [<>,<>] /// CHECK-DAG: Return [<>] - /// CHECK-START: int Main.$noinline$intConditionEqualZero(int) code_flow_simplifier (after) + /// CHECK-START: int Main.$noinline$intConditionEqualZero(int) control_flow_simplifier (after) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> IntConstant 13 /// CHECK-DAG: <> IntConstant 42 diff --git a/test/463-checker-boolean-simplifier/smali/Main2.smali b/test/463-checker-boolean-simplifier/smali/Main2.smali index 9bf0bc1b13..f52700f34c 100644 --- a/test/463-checker-boolean-simplifier/smali/Main2.smali +++ b/test/463-checker-boolean-simplifier/smali/Main2.smali @@ -31,7 +31,7 @@ # Elementary test negating a boolean. Verifies that blocks are merged and # empty branches removed. -## CHECK-START: boolean Main2.BooleanNot(boolean) code_flow_simplifier (before) +## CHECK-START: boolean Main2.BooleanNot(boolean) control_flow_simplifier (before) ## CHECK-DAG: <> ParameterValue ## CHECK-DAG: <> IntConstant 0 ## CHECK-DAG: <> IntConstant 1 @@ -39,24 +39,24 @@ ## CHECK-DAG: <> Phi [<>,<>] ## CHECK-DAG: Return [<>] -## CHECK-START: boolean Main2.BooleanNot(boolean) code_flow_simplifier (before) +## CHECK-START: boolean Main2.BooleanNot(boolean) control_flow_simplifier (before) ## CHECK: Goto ## CHECK: Goto ## CHECK: Goto ## CHECK-NOT: Goto -## CHECK-START: boolean Main2.BooleanNot(boolean) code_flow_simplifier (after) +## CHECK-START: boolean Main2.BooleanNot(boolean) control_flow_simplifier (after) ## CHECK-DAG: <> ParameterValue ## CHECK-DAG: <> IntConstant 0 ## CHECK-DAG: <> IntConstant 1 ## CHECK-DAG: <> Select [<>,<>,<>] ## CHECK-DAG: Return [<>] -## CHECK-START: boolean Main2.BooleanNot(boolean) code_flow_simplifier (after) +## CHECK-START: boolean Main2.BooleanNot(boolean) control_flow_simplifier (after) ## CHECK-NOT: If ## CHECK-NOT: Phi -## CHECK-START: boolean Main2.BooleanNot(boolean) code_flow_simplifier (after) +## CHECK-START: boolean Main2.BooleanNot(boolean) control_flow_simplifier (after) ## CHECK: Goto ## CHECK-NOT: Goto @@ -86,7 +86,7 @@ # Program which further uses negated conditions. # Note that Phis are discovered retrospectively. -## CHECK-START: boolean Main2.ValuesOrdered(int, int, int) code_flow_simplifier (before) +## CHECK-START: boolean Main2.ValuesOrdered(int, int, int) control_flow_simplifier (before) ## CHECK-DAG: <> ParameterValue ## CHECK-DAG: <> ParameterValue ## CHECK-DAG: <> ParameterValue @@ -103,7 +103,7 @@ ## CHECK-DAG: <> Phi [<>,<>] ## CHECK-DAG: <> Phi [<>,<>] -## CHECK-START: boolean Main2.ValuesOrdered(int, int, int) code_flow_simplifier (after) +## CHECK-START: boolean Main2.ValuesOrdered(int, int, int) control_flow_simplifier (after) ## CHECK-DAG: <> ParameterValue ## CHECK-DAG: <> ParameterValue ## CHECK-DAG: <> ParameterValue @@ -164,7 +164,7 @@ goto :goto_a .end method -## CHECK-START: int Main2.NegatedCondition(boolean) code_flow_simplifier (before) +## CHECK-START: int Main2.NegatedCondition(boolean) control_flow_simplifier (before) ## CHECK-DAG: <> ParameterValue ## CHECK-DAG: <> IntConstant 42 ## CHECK-DAG: <> IntConstant 43 @@ -172,14 +172,14 @@ ## CHECK-DAG: <> Phi [<>,<>] ## CHECK-DAG: Return [<>] -## CHECK-START: int Main2.NegatedCondition(boolean) code_flow_simplifier (after) +## CHECK-START: int Main2.NegatedCondition(boolean) control_flow_simplifier (after) ## CHECK-DAG: <> ParameterValue ## CHECK-DAG: <> IntConstant 42 ## CHECK-DAG: <> IntConstant 43 ## CHECK-DAG: <> Select [<>,<>,<>] ## CHECK-DAG: Return [<>] - /// CHECK-START: int Main.SimpleTrueBlock(boolean, int) code_flow_simplifier (after) + /// CHECK-START: int Main.SimpleTrueBlock(boolean, int) control_flow_simplifier (after) /// CHECK-NOT: If public static int SimpleTrueBlock(boolean x, int y) { return x ? y + 42 : 43; } - /// CHECK-START: int Main.SimpleFalseBlock(boolean, int) code_flow_simplifier (after) + /// CHECK-START: int Main.SimpleFalseBlock(boolean, int) control_flow_simplifier (after) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> IntConstant 42 @@ -115,14 +115,14 @@ public class Main { /// CHECK-DAG: <> Select [<>,<>,<>] /// CHECK-DAG: Return [<>] - /// CHECK-START: int Main.SimpleBothBlocks(boolean, int, int) code_flow_simplifier (after) + /// CHECK-START: int Main.SimpleBothBlocks(boolean, int, int) control_flow_simplifier (after) /// CHECK-NOT: If public static int SimpleBothBlocks(boolean x, int y, int z) { return x ? y + 42 : z + 43; } - /// CHECK-START: int Main.ThreeBlocks(boolean, boolean) code_flow_simplifier (after) + /// CHECK-START: int Main.ThreeBlocks(boolean, boolean) control_flow_simplifier (after) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> IntConstant 1 @@ -160,7 +160,7 @@ public class Main { } } - /// CHECK-START: int Main.TrueBlockWithTooManyInstructions(boolean) code_flow_simplifier (before) + /// CHECK-START: int Main.TrueBlockWithTooManyInstructions(boolean) control_flow_simplifier (before) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> IntConstant 2 @@ -170,14 +170,14 @@ public class Main { /// CHECK-DAG: <> Add [<>,<>] /// CHECK-DAG: Phi [<>,<>] - /// CHECK-START: int Main.TrueBlockWithTooManyInstructions(boolean) code_flow_simplifier (after) + /// CHECK-START: int Main.TrueBlockWithTooManyInstructions(boolean) control_flow_simplifier (after) /// CHECK-NOT: Select public int TrueBlockWithTooManyInstructions(boolean x) { return x ? (read_field + 2) : 43; } - /// CHECK-START: int Main.FalseBlockWithTooManyInstructions(boolean) code_flow_simplifier (before) + /// CHECK-START: int Main.FalseBlockWithTooManyInstructions(boolean) control_flow_simplifier (before) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> IntConstant 3 @@ -187,14 +187,14 @@ public class Main { /// CHECK-DAG: <> Add [<>,<>] /// CHECK-DAG: Phi [<>,<>] - /// CHECK-START: int Main.FalseBlockWithTooManyInstructions(boolean) code_flow_simplifier (after) + /// CHECK-START: int Main.FalseBlockWithTooManyInstructions(boolean) control_flow_simplifier (after) /// CHECK-NOT: Select public int FalseBlockWithTooManyInstructions(boolean x) { return x ? 42 : (read_field + 3); } - /// CHECK-START: int Main.TrueBlockWithSideEffects(boolean) code_flow_simplifier (before) + /// CHECK-START: int Main.TrueBlockWithSideEffects(boolean) control_flow_simplifier (before) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> IntConstant 42 @@ -203,14 +203,14 @@ public class Main { /// CHECK-DAG: InstanceFieldSet [<>,<>] /// CHECK-DAG: Phi [<>,<>] - /// CHECK-START: int Main.TrueBlockWithSideEffects(boolean) code_flow_simplifier (after) + /// CHECK-START: int Main.TrueBlockWithSideEffects(boolean) control_flow_simplifier (after) /// CHECK-NOT: Select public int TrueBlockWithSideEffects(boolean x) { return x ? (write_field = 42) : 43; } - /// CHECK-START: int Main.FalseBlockWithSideEffects(boolean) code_flow_simplifier (before) + /// CHECK-START: int Main.FalseBlockWithSideEffects(boolean) control_flow_simplifier (before) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> IntConstant 42 @@ -219,7 +219,7 @@ public class Main { /// CHECK-DAG: InstanceFieldSet [<>,<>] /// CHECK-DAG: Phi [<>,<>] - /// CHECK-START: int Main.FalseBlockWithSideEffects(boolean) code_flow_simplifier (after) + /// CHECK-START: int Main.FalseBlockWithSideEffects(boolean) control_flow_simplifier (after) /// CHECK-NOT: Select public int FalseBlockWithSideEffects(boolean x) { diff --git a/test/468-checker-bool-simplif-regression/smali/TestCase.smali b/test/468-checker-bool-simplif-regression/smali/TestCase.smali index 965bf2d330..10f2a4abe7 100644 --- a/test/468-checker-bool-simplif-regression/smali/TestCase.smali +++ b/test/468-checker-bool-simplif-regression/smali/TestCase.smali @@ -18,7 +18,7 @@ .field public static value:Z -## CHECK-START: boolean TestCase.testCase() code_flow_simplifier (before) +## CHECK-START: boolean TestCase.testCase() control_flow_simplifier (before) ## CHECK-DAG: <> IntConstant 0 ## CHECK-DAG: <> IntConstant 1 ## CHECK-DAG: <> StaticFieldGet @@ -26,7 +26,7 @@ ## CHECK-DAG: <> Phi [<>,<>] ## CHECK-DAG: Return [<>] -## CHECK-START: boolean TestCase.testCase() code_flow_simplifier (after) +## CHECK-START: boolean TestCase.testCase() control_flow_simplifier (after) ## CHECK-DAG: <> IntConstant 0 ## CHECK-DAG: <> IntConstant 1 ## CHECK-DAG: <> StaticFieldGet diff --git a/test/474-checker-boolean-input/src/Main.java b/test/474-checker-boolean-input/src/Main.java index fbffa70473..6799f677bb 100644 --- a/test/474-checker-boolean-input/src/Main.java +++ b/test/474-checker-boolean-input/src/Main.java @@ -27,7 +27,7 @@ public class Main { * we implement a suitable type analysis. */ - /// CHECK-START: boolean Main.TestPhiAsBoolean(int) code_flow_simplifier (after) + /// CHECK-START: boolean Main.TestPhiAsBoolean(int) control_flow_simplifier (after) /// CHECK-DAG: <> Phi /// CHECK-DAG: Select [{{i\d+}},{{i\d+}},<>] @@ -47,7 +47,7 @@ public class Main { * we implement a suitable type analysis. */ - /// CHECK-START: boolean Main.TestAndAsBoolean(boolean, boolean) code_flow_simplifier (after) + /// CHECK-START: boolean Main.TestAndAsBoolean(boolean, boolean) control_flow_simplifier (after) /// CHECK-DAG: <> And /// CHECK-DAG: Select [{{i\d+}},{{i\d+}},<>] @@ -64,7 +64,7 @@ public class Main { * we implement a suitable type analysis. */ - /// CHECK-START: boolean Main.TestOrAsBoolean(boolean, boolean) code_flow_simplifier (after) + /// CHECK-START: boolean Main.TestOrAsBoolean(boolean, boolean) control_flow_simplifier (after) /// CHECK-DAG: <> Or /// CHECK-DAG: Select [{{i\d+}},{{i\d+}},<>] @@ -81,7 +81,7 @@ public class Main { * we implement a suitable type analysis. */ - /// CHECK-START: boolean Main.TestXorAsBoolean(boolean, boolean) code_flow_simplifier (after) + /// CHECK-START: boolean Main.TestXorAsBoolean(boolean, boolean) control_flow_simplifier (after) /// CHECK-DAG: <> Xor /// CHECK-DAG: Select [{{i\d+}},{{i\d+}},<>] diff --git a/test/485-checker-dce-loop-update/smali/TestCase.smali b/test/485-checker-dce-loop-update/smali/TestCase.smali index 53e352a16a..efc60d5470 100644 --- a/test/485-checker-dce-loop-update/smali/TestCase.smali +++ b/test/485-checker-dce-loop-update/smali/TestCase.smali @@ -162,7 +162,7 @@ ## CHECK-START: int TestCase.testExitPredecessors(int, boolean, boolean) dead_code_elimination$after_inlining (after) ## CHECK-NOT: IntConstant 5 -## CHECK-START: int TestCase.testExitPredecessors(int, boolean, boolean) code_flow_simplifier (after) +## CHECK-START: int TestCase.testExitPredecessors(int, boolean, boolean) control_flow_simplifier (after) ## CHECK-DAG: <> ParameterValue ## CHECK-DAG: <> ParameterValue ## CHECK-DAG: <> ParameterValue diff --git a/test/567-checker-builder-intrinsics/src/TestCompare.java b/test/567-checker-builder-intrinsics/src/TestCompare.java index 0f4f0bee31..eb51cfe1c2 100644 --- a/test/567-checker-builder-intrinsics/src/TestCompare.java +++ b/test/567-checker-builder-intrinsics/src/TestCompare.java @@ -37,7 +37,7 @@ public class TestCompare { } } - /// CHECK-START: int TestCompare.compareBooleans(boolean, boolean) code_flow_simplifier (after) + /// CHECK-START: int TestCompare.compareBooleans(boolean, boolean) control_flow_simplifier (after) /// CHECK-NOT: Phi /// CHECK-START: int TestCompare.compareBooleans(boolean, boolean) instruction_simplifier$before_codegen (after) @@ -64,7 +64,7 @@ public class TestCompare { /// CHECK-START: int TestCompare.compareBooleans2(boolean, boolean) builder (after) /// CHECK-NOT: InvokeStaticOrDirect - /// CHECK-START: int TestCompare.compareBooleans2(boolean, boolean) code_flow_simplifier (after) + /// CHECK-START: int TestCompare.compareBooleans2(boolean, boolean) control_flow_simplifier (after) /// CHECK: <> ParameterValue /// CHECK: <> ParameterValue /// CHECK-DAG: <> IntConstant 0 @@ -74,7 +74,7 @@ public class TestCompare { /// CHECK-DAG: <> Compare [<>,<>] /// CHECK-DAG: Return [<>] - /// CHECK-START: int TestCompare.compareBooleans2(boolean, boolean) code_flow_simplifier (after) + /// CHECK-START: int TestCompare.compareBooleans2(boolean, boolean) control_flow_simplifier (after) /// CHECK-NOT: Phi /// CHECK-START: int TestCompare.compareBooleans2(boolean, boolean) instruction_simplifier$before_codegen (after) diff --git a/test/567-checker-builder-intrinsics/src/TestMinMax.java b/test/567-checker-builder-intrinsics/src/TestMinMax.java index 36cd1e6e47..af7c343d55 100644 --- a/test/567-checker-builder-intrinsics/src/TestMinMax.java +++ b/test/567-checker-builder-intrinsics/src/TestMinMax.java @@ -564,7 +564,7 @@ public class TestMinMax { return x; } - /// CHECK-START: int TestMinMax.minmax3(int) code_flow_simplifier (after) + /// CHECK-START: int TestMinMax.minmax3(int) control_flow_simplifier (after) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> IntConstant 100 /// CHECK-DAG: <> IntConstant -100 @@ -588,7 +588,7 @@ public class TestMinMax { return (x > 100) ? 100 : ((x < -100) ? -100 : x); } - /// CHECK-START: int TestMinMax.minmax4(int) code_flow_simplifier (after) + /// CHECK-START: int TestMinMax.minmax4(int) control_flow_simplifier (after) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> IntConstant 100 /// CHECK-DAG: <> IntConstant -100 @@ -612,7 +612,7 @@ public class TestMinMax { return (x < -100) ? -100 : ((x > 100) ? 100 : x); } - /// CHECK-START: int TestMinMax.minmaxCSEScalar(int, int) code_flow_simplifier (after) + /// CHECK-START: int TestMinMax.minmaxCSEScalar(int, int) control_flow_simplifier (after) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> LessThanOrEqual [<>,<>] @@ -648,7 +648,7 @@ public class TestMinMax { return t1 + t2 + t3 + t4 + t5 + t6; } - /// CHECK-START: int TestMinMax.minmaxCSEArray(int[], int[]) code_flow_simplifier (after) + /// CHECK-START: int TestMinMax.minmaxCSEArray(int[], int[]) control_flow_simplifier (after) /// CHECK-DAG: <> ArrayGet /// CHECK-DAG: <> ArrayGet /// CHECK-DAG: <> LessThanOrEqual [<>,<>] diff --git a/test/567-checker-builder-intrinsics/src/TestRotate.java b/test/567-checker-builder-intrinsics/src/TestRotate.java index 3a8ffc1335..322c55ac56 100644 --- a/test/567-checker-builder-intrinsics/src/TestRotate.java +++ b/test/567-checker-builder-intrinsics/src/TestRotate.java @@ -281,7 +281,7 @@ public class TestRotate { /// CHECK-START: int TestRotate.$inline$rotateLeftBoolean(boolean, int) builder (after) /// CHECK-NOT: InvokeStaticOrDirect - /// CHECK-START: int TestRotate.$inline$rotateLeftBoolean(boolean, int) code_flow_simplifier (after) + /// CHECK-START: int TestRotate.$inline$rotateLeftBoolean(boolean, int) control_flow_simplifier (after) /// CHECK: <> ParameterValue /// CHECK: <> ParameterValue /// CHECK-DAG: <> IntConstant 0 @@ -290,7 +290,7 @@ public class TestRotate { /// CHECK-DAG: <> Rol [<>,<>] /// CHECK-DAG: Return [<>] - /// CHECK-START: int TestRotate.$inline$rotateLeftBoolean(boolean, int) code_flow_simplifier (after) + /// CHECK-START: int TestRotate.$inline$rotateLeftBoolean(boolean, int) control_flow_simplifier (after) /// CHECK-NOT: Phi /// CHECK-START: int TestRotate.$inline$rotateLeftBoolean(boolean, int) instruction_simplifier$before_codegen (after) @@ -522,7 +522,7 @@ public class TestRotate { /// CHECK-START: int TestRotate.rotateRightBoolean(boolean, int) builder (after) /// CHECK-NOT: InvokeStaticOrDirect - /// CHECK-START: int TestRotate.rotateRightBoolean(boolean, int) code_flow_simplifier (after) + /// CHECK-START: int TestRotate.rotateRightBoolean(boolean, int) control_flow_simplifier (after) /// CHECK: <> ParameterValue /// CHECK: <> ParameterValue /// CHECK-DAG: <> IntConstant 0 @@ -531,7 +531,7 @@ public class TestRotate { /// CHECK-DAG: <> Ror [<>,<>] /// CHECK-DAG: Return [<>] - /// CHECK-START: int TestRotate.rotateRightBoolean(boolean, int) code_flow_simplifier (after) + /// CHECK-START: int TestRotate.rotateRightBoolean(boolean, int) control_flow_simplifier (after) /// CHECK-NOT: Phi /// CHECK-START: int TestRotate.rotateRightBoolean(boolean, int) instruction_simplifier$before_codegen (after) diff --git a/test/567-checker-builder-intrinsics/src/TestSignum.java b/test/567-checker-builder-intrinsics/src/TestSignum.java index 0ec6b3a0a0..bc146beb9d 100644 --- a/test/567-checker-builder-intrinsics/src/TestSignum.java +++ b/test/567-checker-builder-intrinsics/src/TestSignum.java @@ -81,7 +81,7 @@ public class TestSignum { /// CHECK-START: int TestSignum.signBoolean(boolean) builder (after) /// CHECK-NOT: InvokeStaticOrDirect - /// CHECK-START: int TestSignum.signBoolean(boolean) code_flow_simplifier (after) + /// CHECK-START: int TestSignum.signBoolean(boolean) control_flow_simplifier (after) /// CHECK-DAG: <> ParameterValue /// CHECK-DAG: <> IntConstant 0 /// CHECK-DAG: <> IntConstant 1 @@ -89,7 +89,7 @@ public class TestSignum { /// CHECK-DAG: <> Compare [<>,<>] /// CHECK-DAG: Return [<>] - /// CHECK-START: int TestSignum.signBoolean(boolean) code_flow_simplifier (after) + /// CHECK-START: int TestSignum.signBoolean(boolean) control_flow_simplifier (after) /// CHECK-NOT: Phi /// CHECK-START: int TestSignum.signBoolean(boolean) instruction_simplifier$after_gvn (after) diff --git a/test/592-checker-regression-bool-input/smali/TestCase.smali b/test/592-checker-regression-bool-input/smali/TestCase.smali index 29037ab397..8e9ad809c0 100644 --- a/test/592-checker-regression-bool-input/smali/TestCase.smali +++ b/test/592-checker-regression-bool-input/smali/TestCase.smali @@ -16,7 +16,7 @@ .super Ljava/lang/Object; -## CHECK-START: boolean TestCase.testCase() code_flow_simplifier (after) +## CHECK-START: boolean TestCase.testCase() control_flow_simplifier (after) ## CHECK-DAG: <> Select ## CHECK-DAG: Return [<