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

4 files changed, 107 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,