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;
+    }
+}