Induction variable analysis (with unit tests).
Rationale:
Induction variable analysis forms the basis of a wide
variety of compiler optimizations. This implementation
finds induction variables using the elegant SSA-based
algorithm defined by [Gerlek et al.].
Change-Id: I79b8dce33ffb8b283c179699a8dff5bd196f75b2
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
new file mode 100644
index 0000000..09a0a38
--- /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_