diff options
8 files changed, 227 insertions, 6 deletions
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc index 5b5cd2e3b8..be6c268f5d 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -16,6 +16,7 @@ #include "induction_var_analysis.h" +#include "base/scoped_arena_containers.h" #include "induction_var_range.h" namespace art HIDDEN { @@ -214,18 +215,25 @@ struct HInductionVarAnalysis::StackEntry { size_t low_depth; }; -HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph, const char* name) - : HOptimization(graph, name), +HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph, + OptimizingCompilerStats* stats, + const char* name) + : HOptimization(graph, name, stats), induction_(std::less<const HLoopInformation*>(), graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)), - cycles_(std::less<HPhi*>(), - graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)) { + cycles_(std::less<HPhi*>(), graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)) { } bool HInductionVarAnalysis::Run() { // Detects sequence variables (generalized induction variables) during an outer to inner // traversal of all loops using Gerlek's algorithm. The order is important to enable // range analysis on outer loop while visiting inner loops. + + if (IsPathologicalCase()) { + MaybeRecordStat(stats_, MethodCompilationStat::kNotVarAnalyzedPathological); + return false; + } + for (HBasicBlock* graph_block : graph_->GetReversePostOrder()) { // Don't analyze irreducible loops. if (graph_block->IsLoopHeader() && !graph_block->GetLoopInformation()->IsIrreducible()) { @@ -1576,4 +1584,84 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) { return ""; } +void HInductionVarAnalysis::CalculateLoopHeaderPhisInARow( + HPhi* initial_phi, + ScopedArenaSafeMap<HPhi*, int>& cached_values, + ScopedArenaAllocator& allocator) { + DCHECK(initial_phi->IsLoopHeaderPhi()); + ScopedArenaQueue<HPhi*> worklist(allocator.Adapter(kArenaAllocInductionVarAnalysis)); + worklist.push(initial_phi); + // Used to check which phis are in the current chain we are checking. + ScopedArenaSet<HPhi*> phis_in_chain(allocator.Adapter(kArenaAllocInductionVarAnalysis)); + while (!worklist.empty()) { + HPhi* current_phi = worklist.front(); + DCHECK(current_phi->IsLoopHeaderPhi()); + if (cached_values.find(current_phi) != cached_values.end()) { + // Already processed. + worklist.pop(); + continue; + } + + phis_in_chain.insert(current_phi); + int max_value = 0; + bool pushed_other_phis = false; + for (size_t index = 0; index < current_phi->InputCount(); index++) { + // If the input is not a loop header phi, we only have 1 (current_phi). + int current_value = 1; + if (current_phi->InputAt(index)->IsLoopHeaderPhi()) { + HPhi* loop_header_phi = current_phi->InputAt(index)->AsPhi(); + auto it = cached_values.find(loop_header_phi); + if (it != cached_values.end()) { + current_value += it->second; + } else if (phis_in_chain.find(current_phi) == phis_in_chain.end()) { + // Push phis which aren't in the chain already to be processed. + pushed_other_phis = true; + worklist.push(loop_header_phi); + } + // Phis in the chain will get processed later. We keep `current_value` as 1 to avoid + // double counting `loop_header_phi`. + } + max_value = std::max(max_value, current_value); + } + + if (!pushed_other_phis) { + // Only finish processing after all inputs were processed. + worklist.pop(); + phis_in_chain.erase(current_phi); + cached_values.FindOrAdd(current_phi, max_value); + } + } +} + +bool HInductionVarAnalysis::IsPathologicalCase() { + ScopedArenaAllocator local_allocator(graph_->GetArenaStack()); + ScopedArenaSafeMap<HPhi*, int> cached_values( + std::less<HPhi*>(), local_allocator.Adapter(kArenaAllocInductionVarAnalysis)); + + // Due to how our induction passes work, we will take a lot of time compiling if we have several + // loop header phis in a row. If we have more than 15 different loop header phis in a row, we + // don't perform the analysis. + constexpr int kMaximumLoopHeaderPhisInARow = 15; + + for (HBasicBlock* block : graph_->GetReversePostOrder()) { + if (!block->IsLoopHeader()) { + continue; + } + + for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + DCHECK(it.Current()->IsLoopHeaderPhi()); + HPhi* phi = it.Current()->AsPhi(); + CalculateLoopHeaderPhisInARow(phi, cached_values, local_allocator); + DCHECK(cached_values.find(phi) != cached_values.end()) + << " we should have a value for Phi " << phi->GetId() + << " in block " << phi->GetBlock()->GetBlockId(); + if (cached_values.find(phi)->second > kMaximumLoopHeaderPhisInARow) { + return true; + } + } + } + + return false; +} + } // namespace art diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h index 124c3b4e64..050950089a 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -39,7 +39,9 @@ namespace art HIDDEN { */ class HInductionVarAnalysis : public HOptimization { public: - explicit HInductionVarAnalysis(HGraph* graph, const char* name = kInductionPassName); + explicit HInductionVarAnalysis(HGraph* graph, + OptimizingCompilerStats* stats = nullptr, + const char* name = kInductionPassName); bool Run() override; @@ -308,6 +310,15 @@ class HInductionVarAnalysis : public HOptimization { static std::string FetchToString(HInstruction* fetch); static std::string InductionToString(InductionInfo* info); + // Returns true if we have a pathological case we don't want to analyze. + bool IsPathologicalCase(); + // Starting with initial_phi, it calculates how many loop header phis in a row we have. To do + // this, we count the loop header phi which are used as an input of other loop header phis. It + // uses `cached_values` to avoid recomputing results. + void CalculateLoopHeaderPhisInARow(HPhi* initial_phi, + ScopedArenaSafeMap<HPhi*, int>& cached_values, + ScopedArenaAllocator& allocator); + /** * Maintains the results of the analysis as a mapping from loops to a mapping from instructions * to the induction information for that instruction in that loop. diff --git a/compiler/optimizing/optimization.cc b/compiler/optimizing/optimization.cc index 73a47517bf..e1b97b4aac 100644 --- a/compiler/optimizing/optimization.cc +++ b/compiler/optimizing/optimization.cc @@ -197,7 +197,8 @@ ArenaVector<HOptimization*> ConstructOptimizations( opt = most_recent_side_effects = new (allocator) SideEffectsAnalysis(graph, pass_name); break; case OptimizationPass::kInductionVarAnalysis: - opt = most_recent_induction = new (allocator) HInductionVarAnalysis(graph, pass_name); + opt = most_recent_induction = + new (allocator) HInductionVarAnalysis(graph, stats, pass_name); break; // // Passes that need prior analysis. diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h index 698a1471c3..866c88382a 100644 --- a/compiler/optimizing/optimizing_compiler_stats.h +++ b/compiler/optimizing/optimizing_compiler_stats.h @@ -112,6 +112,7 @@ enum class MethodCompilationStat { kNotInlinedUnresolved, kNotInlinedPolymorphic, kNotInlinedCustom, + kNotVarAnalyzedPathological, kTryInline, kConstructorFenceGeneratedNew, kConstructorFenceGeneratedFinal, diff --git a/test/2254-checker-not-var-analyzed-pathological/expected-stderr.txt b/test/2254-checker-not-var-analyzed-pathological/expected-stderr.txt new file mode 100644 index 0000000000..e69de29bb2 --- /dev/null +++ b/test/2254-checker-not-var-analyzed-pathological/expected-stderr.txt diff --git a/test/2254-checker-not-var-analyzed-pathological/expected-stdout.txt b/test/2254-checker-not-var-analyzed-pathological/expected-stdout.txt new file mode 100644 index 0000000000..e69de29bb2 --- /dev/null +++ b/test/2254-checker-not-var-analyzed-pathological/expected-stdout.txt diff --git a/test/2254-checker-not-var-analyzed-pathological/info.txt b/test/2254-checker-not-var-analyzed-pathological/info.txt new file mode 100644 index 0000000000..616c1e77b0 --- /dev/null +++ b/test/2254-checker-not-var-analyzed-pathological/info.txt @@ -0,0 +1,2 @@ +Make sure that a pathological case in induction var analysis +doesn't hang up the compiler. diff --git a/test/2254-checker-not-var-analyzed-pathological/src/Main.java b/test/2254-checker-not-var-analyzed-pathological/src/Main.java new file mode 100644 index 0000000000..484f8661c3 --- /dev/null +++ b/test/2254-checker-not-var-analyzed-pathological/src/Main.java @@ -0,0 +1,118 @@ +/* + * Copyright (C) 2023 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. + */ + +public class Main { + public static void main(String[] args) { + $noinline$assertEquals(0, $noinline$pathologicalCase()); + } + + public static void $noinline$assertEquals(int expected, int result) { + if (expected != result) { + throw new Error("Expected: " + expected + ", found: " + result); + } + } + + // Empty $noinline$ method so that it doesn't get removed. + private static void $noinline$emptyMethod(int val) {} + + // A pathological case which has > 15 loop header phis in a row. + /// CHECK-START: int Main.$noinline$pathologicalCase() induction_var_analysis (before) + /// CHECK: <<Const0:i\d+>> IntConstant 0 + /// CHECK: <<Phi1:i\d+>> Phi [<<Const0>>,<<Add1:i\d+>>] + /// CHECK: <<Phi2:i\d+>> Phi [<<Phi1>>,<<Add2:i\d+>>] + /// CHECK: <<Phi3:i\d+>> Phi [<<Phi2>>,<<Add3:i\d+>>] + /// CHECK: <<Phi4:i\d+>> Phi [<<Phi3>>,<<Add4:i\d+>>] + /// CHECK: <<Phi5:i\d+>> Phi [<<Phi4>>,<<Add5:i\d+>>] + /// CHECK: <<Phi6:i\d+>> Phi [<<Phi5>>,<<Add6:i\d+>>] + /// CHECK: <<Phi7:i\d+>> Phi [<<Phi6>>,<<Add7:i\d+>>] + /// CHECK: <<Phi8:i\d+>> Phi [<<Phi7>>,<<Add8:i\d+>>] + /// CHECK: <<Phi9:i\d+>> Phi [<<Phi8>>,<<Add9:i\d+>>] + /// CHECK: <<Phi10:i\d+>> Phi [<<Phi9>>,<<Add10:i\d+>>] + /// CHECK: <<Phi11:i\d+>> Phi [<<Phi10>>,<<Add11:i\d+>>] + /// CHECK: <<Phi12:i\d+>> Phi [<<Phi11>>,<<Add12:i\d+>>] + /// CHECK: <<Phi13:i\d+>> Phi [<<Phi12>>,<<Add13:i\d+>>] + /// CHECK: <<Phi14:i\d+>> Phi [<<Phi13>>,<<Add14:i\d+>>] + /// CHECK: <<Phi15:i\d+>> Phi [<<Phi14>>,<<Add15:i\d+>>] + /// CHECK: <<Phi16:i\d+>> Phi [<<Phi15>>,<<Add16:i\d+>>] + private static int $noinline$pathologicalCase() { + int value = 0; + for (; value < 3; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 5; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 7; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 9; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 11; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 13; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 15; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 17; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 19; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 21; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 23; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 25; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 27; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 29; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 31; value++) { + $noinline$emptyMethod(value); + } + + for (; value < 33; value++) { + $noinline$emptyMethod(value); + } + + return 0; + } +} |