Clean up InductionVarAnalysis.

Move temporary members to local variables and allocations
from `ArenaAllocator` to `ScopedArenaAllocator`. While this
requires passing more parameters around, it also exposes
whether these parameters are constant or mutable.

Rewrite the strongly connected component (SCC) search to
avoid recursion. The recursion depth was dependent on the
input code, so essentially arbitrary, and therefore there
was a risk of stack overflow.

Clean up a few other minor things in `InductionVarAnalysis`
and `LoopOptimization`.

Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 216762268
Change-Id: Ifed50b8e62e47487edc683564352880df2158247

1 files changed, 37 insertions, 32 deletions

diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index a48aa90059..616100b068 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -19,6 +19,9 @@
 
 #include <string>
 
+#include "base/arena_containers.h"
+#include "base/array_ref.h"
+#include "base/scoped_arena_containers.h"
 #include "nodes.h"
 #include "optimization.h"
 
@@ -42,11 +45,8 @@ class HInductionVarAnalysis : public HOptimization {
   static constexpr const char* kInductionPassName = "induction_var_analysis";
 
  private:
-  struct NodeInfo {
-    explicit NodeInfo(uint32_t d) : depth(d), done(false) {}
-    uint32_t depth;
-    bool done;
-  };
+  struct NodeInfo;
+  struct StackEntry;
 
   enum InductionClass {
     kInvariant,
@@ -118,9 +118,6 @@ class HInductionVarAnalysis : public HOptimization {
     DataType::Type type;  // precision of operation
   };
 
-  bool IsVisitedNode(HInstruction* instruction) const {
-    return map_.find(instruction) != map_.end();
-  }
 
   InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
     DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
@@ -153,47 +150,65 @@ class HInductionVarAnalysis : public HOptimization {
 
   // Methods for analysis.
   void VisitLoop(HLoopInformation* loop);
-  void VisitNode(HLoopInformation* loop, HInstruction* instruction);
-  uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
+  size_t TryVisitNodes(HLoopInformation* loop,
+                       HInstruction* start_instruction,
+                       size_t global_depth,
+                       /*inout*/ ScopedArenaSafeMap<HInstruction*, NodeInfo>* visited_instructions);
+  void ExtractScc(ArrayRef<const StackEntry> stack_tail, ScopedArenaVector<HInstruction*>* scc);
   void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
-  void ClassifyNonTrivial(HLoopInformation* loop);
-  InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
+  void ClassifyNonTrivial(HLoopInformation* loop, ArrayRef<const StackEntry> stack_tail);
+  InductionInfo* RotatePeriodicInduction(InductionInfo* induction,
+                                         InductionInfo* last,
+                                         DataType::Type type);
 
   // Transfer operations.
   InductionInfo* TransferPhi(HLoopInformation* loop,
                              HInstruction* phi,
                              size_t input_index,
                              size_t adjust_input_size);
-  InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
-  InductionInfo* TransferNeg(InductionInfo* a);
-  InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
+  InductionInfo* TransferAddSub(InductionInfo* a,
+                                InductionInfo* b,
+                                InductionOp op,
+                                DataType::Type type);
+  InductionInfo* TransferNeg(InductionInfo* a, DataType::Type type);
+  InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b, DataType::Type type);
   InductionInfo* TransferConversion(InductionInfo* a, DataType::Type from, DataType::Type to);
 
   // Solvers.
-  InductionInfo* SolvePhi(HInstruction* phi, size_t input_index, size_t adjust_input_size);
+  InductionInfo* SolvePhi(HInstruction* phi,
+                          size_t input_index,
+                          size_t adjust_input_size,
+                          const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle);
   InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
                                    HInstruction* entry_phi,
-                                   HInstruction* phi);
+                                   HInstruction* phi,
+                                   const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
+                                   DataType::Type type);
   InductionInfo* SolveAddSub(HLoopInformation* loop,
                              HInstruction* entry_phi,
                              HInstruction* instruction,
                              HInstruction* x,
                              HInstruction* y,
                              InductionOp op,
-                             bool is_first_call);  // possibly swaps x and y to try again
+                             const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
+                             DataType::Type type);
   InductionInfo* SolveOp(HLoopInformation* loop,
                          HInstruction* entry_phi,
                          HInstruction* instruction,
                          HInstruction* x,
                          HInstruction* y,
-                         InductionOp op);
+                         InductionOp op,
+                         DataType::Type type);
   InductionInfo* SolveTest(HLoopInformation* loop,
                            HInstruction* entry_phi,
                            HInstruction* instruction,
-                           int64_t oppositive_value);
+                           int64_t opposite_value,
+                           DataType::Type type);
   InductionInfo* SolveConversion(HLoopInformation* loop,
                                  HInstruction* entry_phi,
-                                 HTypeConversion* conversion);
+                                 HTypeConversion* conversion,
+                                 const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
+                                 /*inout*/ DataType::Type* type);
 
   //
   // Loop trip count analysis methods.
@@ -241,7 +256,7 @@ class HInductionVarAnalysis : public HOptimization {
   HInstruction* GetShiftConstant(HLoopInformation* loop,
                                  HInstruction* instruction,
                                  InductionInfo* initial);
-  void AssignCycle(HPhi* phi);
+  void AssignCycle(HPhi* phi, ArrayRef<HInstruction* const> scc);
   ArenaSet<HInstruction*>* LookupCycle(HPhi* phi);
 
   // Constants.
@@ -255,16 +270,6 @@ class HInductionVarAnalysis : public HOptimization {
   static std::string FetchToString(HInstruction* fetch);
   static std::string InductionToString(InductionInfo* info);
 
-  // TODO: fine tune the following data structures, only keep relevant data.
-
-  // Temporary book-keeping during the analysis.
-  uint32_t global_depth_;
-  ArenaVector<HInstruction*> stack_;
-  ArenaSafeMap<HInstruction*, NodeInfo> map_;
-  ArenaVector<HInstruction*> scc_;
-  ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
-  DataType::Type type_;
-
   /**
    * 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.