Merge "Induction variable analysis (with unit tests)."

1 files changed, 171 insertions, 0 deletions

diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
new file mode 100644
index 0000000000..09a0a380a1
--- /dev/null
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -0,0 +1,171 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
+#define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
+
+#include <string>
+
+#include "nodes.h"
+#include "optimization.h"
+
+namespace art {
+
+/**
+ * Induction variable analysis.
+ *
+ * Based on the paper by M. Gerlek et al.
+ * "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form"
+ * (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995).
+ */
+class HInductionVarAnalysis : public HOptimization {
+ public:
+  explicit HInductionVarAnalysis(HGraph* graph);
+
+  // TODO: design public API useful in later phases
+
+  /**
+   * Returns string representation of induction found for the instruction
+   * in the given loop (for testing and debugging only).
+   */
+  std::string InductionToString(HLoopInformation* loop, HInstruction* instruction) {
+    return InductionToString(LookupInfo(loop, instruction));
+  }
+
+  void Run() OVERRIDE;
+
+ private:
+  static constexpr const char* kInductionPassName = "induction_var_analysis";
+
+  struct NodeInfo {
+    explicit NodeInfo(uint32_t d) : depth(d), done(false) {}
+    uint32_t depth;
+    bool done;
+  };
+
+  enum InductionClass {
+    kNone,
+    kInvariant,
+    kLinear,
+    kWrapAround,
+    kPeriodic,
+    kMonotonic
+  };
+
+  enum InductionOp {
+    kNop,  // no-operation: a true induction
+    kAdd,
+    kSub,
+    kNeg,
+    kMul,
+    kDiv,
+    kFetch
+  };
+
+  /**
+   * Defines a detected induction as:
+   *   (1) invariant:
+   *         operation: a + b, a - b, -b, a * b, a / b
+   *       or
+   *         fetch: fetch from HIR
+   *   (2) linear:
+   *         nop: a * i + b
+   *   (3) wrap-around
+   *         nop: a, then defined by b
+   *   (4) periodic
+   *         nop: a, then defined by b (repeated when exhausted)
+   *   (5) monotonic
+   *         // TODO: determine representation
+   */
+  struct InductionInfo : public ArenaObject<kArenaAllocMisc> {
+    InductionInfo(InductionClass ic,
+                  InductionOp op,
+                  InductionInfo* a,
+                  InductionInfo* b,
+                  HInstruction* f)
+        : induction_class(ic),
+          operation(op),
+          op_a(a),
+          op_b(b),
+          fetch(f) {}
+    InductionClass induction_class;
+    InductionOp operation;
+    InductionInfo* op_a;
+    InductionInfo* op_b;
+    HInstruction* fetch;
+  };
+
+  inline bool IsVisitedNode(int id) const {
+    return map_.find(id) != map_.end();
+  }
+
+  inline InductionInfo* NewInductionInfo(
+      InductionClass c,
+      InductionOp op,
+      InductionInfo* a,
+      InductionInfo* b,
+      HInstruction* i) {
+    return new (graph_->GetArena()) InductionInfo(c, op, a, b, i);
+  }
+
+  // Methods for analysis.
+  void VisitLoop(HLoopInformation* loop);
+  void VisitNode(HLoopInformation* loop, HInstruction* instruction);
+  uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
+  void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
+  void ClassifyNonTrivial(HLoopInformation* loop);
+
+  // Transfer operations.
+  InductionInfo* TransferPhi(InductionInfo* a, InductionInfo* b);
+  InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
+  InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
+  InductionInfo* TransferNeg(InductionInfo* a);
+  InductionInfo* TransferCycleOverPhi(HInstruction* phi);
+  InductionInfo* TransferCycleOverAddSub(HLoopInformation* loop,
+                                         HInstruction* x,
+                                         HInstruction* y,
+                                         InductionOp op,
+                                         bool first);
+
+  // Assign and lookup.
+  void PutInfo(int loop_id, int id, InductionInfo* info);
+  InductionInfo* GetInfo(int loop_id, int id);
+  void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
+  InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
+  bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
+  std::string InductionToString(InductionInfo* info);
+
+  // Bookkeeping during and after analysis.
+  // TODO: fine tune data structures, only keep relevant data
+
+  uint32_t global_depth_;
+
+  ArenaVector<HInstruction*> stack_;
+  ArenaVector<HInstruction*> scc_;
+
+  // Mappings of instruction id to node and induction information.
+  ArenaSafeMap<int, NodeInfo> map_;
+  ArenaSafeMap<int, InductionInfo*> cycle_;
+
+  // Mapping from loop id to mapping of instruction id to induction information.
+  ArenaSafeMap<int, ArenaSafeMap<int, InductionInfo*>> induction_;
+
+  DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_