Skip InductionVarAnalysis for a pathological case
Having a long chain of loop header phis hangs up the compiler.
Note that we can still compile the method if we skip the
InductionVarAnalysis phase.
Bug: 246249941
Fixes: 246249941
Bug: 32545907
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Test: dex2oat compile the app in 246249941
Change-Id: Id2d14b1c4d787f98d656055274c7cfcae6491686
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 5b5cd2e..be6c268 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 @@
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 @@
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 124c3b4..0509500 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -39,7 +39,9 @@
*/
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 @@
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 73a4751..e1b97b4 100644
--- a/compiler/optimizing/optimization.cc
+++ b/compiler/optimizing/optimization.cc
@@ -197,7 +197,8 @@
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 698a147..866c883 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -112,6 +112,7 @@
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 0000000..e69de29
--- /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 0000000..e69de29
--- /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 0000000..616c1e7
--- /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 0000000..484f866
--- /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;
+ }
+}