1 /*
2  * Copyright (C) 2015 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
18 #define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
19 
20 #include <string>
21 
22 #include "nodes.h"
23 #include "optimization.h"
24 
25 namespace art {
26 
27 /**
28  * Induction variable analysis. This class does not have a direct public API.
29  * Instead, the results of induction variable analysis can be queried through
30  * friend classes, such as InductionVarRange.
31  *
32  * The analysis implementation is based on the paper by M. Gerlek et al.
33  * "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form"
34  * (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995).
35  */
36 class HInductionVarAnalysis : public HOptimization {
37  public:
38   explicit HInductionVarAnalysis(HGraph* graph);
39 
40   void Run() OVERRIDE;
41 
42  private:
43   static constexpr const char* kInductionPassName = "induction_var_analysis";
44 
45   struct NodeInfo {
NodeInfoNodeInfo46     explicit NodeInfo(uint32_t d) : depth(d), done(false) {}
47     uint32_t depth;
48     bool done;
49   };
50 
51   enum InductionClass {
52     kInvariant,
53     kLinear,
54     kWrapAround,
55     kPeriodic
56   };
57 
58   enum InductionOp {
59     // No-operation: a true induction.
60     kNop,
61     // Various invariant operations.
62     kAdd,
63     kSub,
64     kNeg,
65     kMul,
66     kDiv,
67     kFetch,
68     // Trip-counts.
69     kTripCountInLoop,        // valid in full loop; loop is finite
70     kTripCountInBody,        // valid in body only; loop is finite
71     kTripCountInLoopUnsafe,  // valid in full loop; loop may be infinite
72     kTripCountInBodyUnsafe,  // valid in body only; loop may be infinite
73     // Comparisons for trip-count tests.
74     kLT,
75     kLE,
76     kGT,
77     kGE
78   };
79 
80   /**
81    * Defines a detected induction as:
82    *   (1) invariant:
83    *         operation: a + b, a - b, -b, a * b, a / b
84    *       or:
85    *         fetch: fetch from HIR
86    *   (2) linear:
87    *         nop: a * i + b
88    *   (3) wrap-around
89    *         nop: a, then defined by b
90    *   (4) periodic
91    *         nop: a, then defined by b (repeated when exhausted)
92    *   (5) trip-count:
93    *         tc: defined by a, taken-test in b
94    */
95   struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> {
InductionInfoInductionInfo96     InductionInfo(InductionClass ic,
97                   InductionOp op,
98                   InductionInfo* a,
99                   InductionInfo* b,
100                   HInstruction* f,
101                   Primitive::Type t)
102         : induction_class(ic),
103           operation(op),
104           op_a(a),
105           op_b(b),
106           fetch(f),
107           type(t) {}
108     InductionClass induction_class;
109     InductionOp operation;
110     InductionInfo* op_a;
111     InductionInfo* op_b;
112     HInstruction* fetch;
113     Primitive::Type type;  // precision of induction
114   };
115 
IsVisitedNode(HInstruction * instruction)116   bool IsVisitedNode(HInstruction* instruction) const {
117     return map_.find(instruction) != map_.end();
118   }
119 
CreateInvariantOp(InductionOp op,InductionInfo * a,InductionInfo * b)120   InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
121     DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
122     return CreateSimplifiedInvariant(op, a, b);
123   }
124 
CreateInvariantFetch(HInstruction * f)125   InductionInfo* CreateInvariantFetch(HInstruction* f) {
126     DCHECK(f != nullptr);
127     return new (graph_->GetArena())
128         InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType());
129   }
130 
CreateTripCount(InductionOp op,InductionInfo * a,InductionInfo * b,Primitive::Type type)131   InductionInfo* CreateTripCount(InductionOp op,
132                                  InductionInfo* a,
133                                  InductionInfo* b,
134                                  Primitive::Type type) {
135     DCHECK(a != nullptr);
136     return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, type);
137   }
138 
CreateInduction(InductionClass ic,InductionInfo * a,InductionInfo * b,Primitive::Type type)139   InductionInfo* CreateInduction(InductionClass ic,
140                                  InductionInfo* a,
141                                  InductionInfo* b,
142                                  Primitive::Type type) {
143     DCHECK(a != nullptr && b != nullptr);
144     return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr, type);
145   }
146 
147   // Methods for analysis.
148   void VisitLoop(HLoopInformation* loop);
149   void VisitNode(HLoopInformation* loop, HInstruction* instruction);
150   uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
151   void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
152   void ClassifyNonTrivial(HLoopInformation* loop);
153   InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
154 
155   // Transfer operations.
156   InductionInfo* TransferPhi(HLoopInformation* loop, HInstruction* phi, size_t input_index);
157   InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
158   InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
159   InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type);
160   InductionInfo* TransferNeg(InductionInfo* a);
161   InductionInfo* TransferCnv(InductionInfo* a, Primitive::Type from, Primitive::Type to);
162 
163   // Solvers.
164   InductionInfo* SolvePhi(HInstruction* phi, size_t input_index);
165   InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
166                                    HInstruction* entry_phi,
167                                    HInstruction* phi);
168   InductionInfo* SolveAddSub(HLoopInformation* loop,
169                              HInstruction* entry_phi,
170                              HInstruction* instruction,
171                              HInstruction* x,
172                              HInstruction* y,
173                              InductionOp op,
174                              bool is_first_call);
175   InductionInfo* SolveCnv(HTypeConversion* conversion);
176 
177   // Trip count information.
178   void VisitControl(HLoopInformation* loop);
179   void VisitCondition(HLoopInformation* loop,
180                       InductionInfo* a,
181                       InductionInfo* b,
182                       Primitive::Type type,
183                       IfCondition cmp);
184   void VisitTripCount(HLoopInformation* loop,
185                       InductionInfo* lower_expr,
186                       InductionInfo* upper_expr,
187                       InductionInfo* stride,
188                       int64_t stride_value,
189                       Primitive::Type type,
190                       IfCondition cmp);
191   bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp);
192   bool IsFinite(InductionInfo* upper_expr,
193                 int64_t stride_value,
194                 Primitive::Type type,
195                 IfCondition cmp);
196   bool FitsNarrowerControl(InductionInfo* lower_expr,
197                            InductionInfo* upper_expr,
198                            int64_t stride_value,
199                            Primitive::Type type,
200                            IfCondition cmp);
201 
202   // Assign and lookup.
203   void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
204   InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
205   InductionInfo* CreateConstant(int64_t value, Primitive::Type type);
206   InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
207 
208   // Constants.
209   bool IsExact(InductionInfo* info, /*out*/ int64_t* value);
210   bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value);
211   bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value);
212 
213   // Helpers.
214   static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
215   static std::string InductionToString(InductionInfo* info);
216 
217   // TODO: fine tune the following data structures, only keep relevant data.
218 
219   // Temporary book-keeping during the analysis.
220   uint32_t global_depth_;
221   ArenaVector<HInstruction*> stack_;
222   ArenaVector<HInstruction*> scc_;
223   ArenaSafeMap<HInstruction*, NodeInfo> map_;
224   ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
225   Primitive::Type type_;
226 
227   /**
228    * Maintains the results of the analysis as a mapping from loops to a mapping from instructions
229    * to the induction information for that instruction in that loop.
230    */
231   ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
232 
233   friend class InductionVarAnalysisTest;
234   friend class InductionVarRange;
235   friend class InductionVarRangeTest;
236 
237   DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
238 };
239 
240 }  // namespace art
241 
242 #endif  // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
243