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   static constexpr const char* kInductionPassName = "induction_var_analysis";
43 
44  private:
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     kPolynomial,
55     kGeometric,
56     kWrapAround,
57     kPeriodic
58   };
59 
60   enum InductionOp {
61     // Operations.
62     kNop,
63     kAdd,
64     kSub,
65     kNeg,
66     kMul,
67     kDiv,
68     kRem,
69     kXor,
70     kFetch,
71     // Trip-counts.
72     kTripCountInLoop,        // valid in full loop; loop is finite
73     kTripCountInBody,        // valid in body only; loop is finite
74     kTripCountInLoopUnsafe,  // valid in full loop; loop may be infinite
75     kTripCountInBodyUnsafe,  // valid in body only; loop may be infinite
76     // Comparisons for trip-count tests.
77     kLT,
78     kLE,
79     kGT,
80     kGE
81   };
82 
83   /**
84    * Defines a detected induction as:
85    *   (1) invariant:
86    *         op: a + b, a - b, -b, a * b, a / b, a % b, a ^ b, fetch
87    *   (2) linear:
88    *         nop: a * i + b
89    *   (3) polynomial:
90    *         nop: sum_lt(a) + b, for linear a
91    *   (4) geometric:
92    *         op: a * fetch^i + b, a * fetch^-i + b
93    *   (5) wrap-around
94    *         nop: a, then defined by b
95    *   (6) periodic
96    *         nop: a, then defined by b (repeated when exhausted)
97    *   (7) trip-count:
98    *         tc: defined by a, taken-test in b
99    */
100   struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> {
InductionInfoInductionInfo101     InductionInfo(InductionClass ic,
102                   InductionOp op,
103                   InductionInfo* a,
104                   InductionInfo* b,
105                   HInstruction* f,
106                   Primitive::Type t)
107         : induction_class(ic),
108           operation(op),
109           op_a(a),
110           op_b(b),
111           fetch(f),
112           type(t) {}
113     InductionClass induction_class;
114     InductionOp operation;
115     InductionInfo* op_a;
116     InductionInfo* op_b;
117     HInstruction* fetch;
118     Primitive::Type type;  // precision of operation
119   };
120 
IsVisitedNode(HInstruction * instruction)121   bool IsVisitedNode(HInstruction* instruction) const {
122     return map_.find(instruction) != map_.end();
123   }
124 
CreateInvariantOp(InductionOp op,InductionInfo * a,InductionInfo * b)125   InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
126     DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
127     return CreateSimplifiedInvariant(op, a, b);
128   }
129 
CreateInvariantFetch(HInstruction * f)130   InductionInfo* CreateInvariantFetch(HInstruction* f) {
131     DCHECK(f != nullptr);
132     return new (graph_->GetArena())
133         InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType());
134   }
135 
CreateTripCount(InductionOp op,InductionInfo * a,InductionInfo * b,Primitive::Type type)136   InductionInfo* CreateTripCount(InductionOp op,
137                                  InductionInfo* a,
138                                  InductionInfo* b,
139                                  Primitive::Type type) {
140     DCHECK(a != nullptr && b != nullptr);
141     return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, type);
142   }
143 
CreateInduction(InductionClass ic,InductionOp op,InductionInfo * a,InductionInfo * b,HInstruction * f,Primitive::Type type)144   InductionInfo* CreateInduction(InductionClass ic,
145                                  InductionOp op,
146                                  InductionInfo* a,
147                                  InductionInfo* b,
148                                  HInstruction* f,
149                                  Primitive::Type type) {
150     DCHECK(a != nullptr && b != nullptr);
151     return new (graph_->GetArena()) InductionInfo(ic, op, a, b, f, type);
152   }
153 
154   // Methods for analysis.
155   void VisitLoop(HLoopInformation* loop);
156   void VisitNode(HLoopInformation* loop, HInstruction* instruction);
157   uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
158   void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
159   void ClassifyNonTrivial(HLoopInformation* loop);
160   InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
161 
162   // Transfer operations.
163   InductionInfo* TransferPhi(HLoopInformation* loop,
164                              HInstruction* phi,
165                              size_t input_index,
166                              size_t adjust_input_size);
167   InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
168   InductionInfo* TransferNeg(InductionInfo* a);
169   InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
170   InductionInfo* TransferConversion(InductionInfo* a, Primitive::Type from, Primitive::Type to);
171 
172   // Solvers.
173   InductionInfo* SolvePhi(HInstruction* phi, size_t input_index, size_t adjust_input_size);
174   InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
175                                    HInstruction* entry_phi,
176                                    HInstruction* phi);
177   InductionInfo* SolveAddSub(HLoopInformation* loop,
178                              HInstruction* entry_phi,
179                              HInstruction* instruction,
180                              HInstruction* x,
181                              HInstruction* y,
182                              InductionOp op,
183                              bool is_first_call);  // possibly swaps x and y to try again
184   InductionInfo* SolveOp(HLoopInformation* loop,
185                          HInstruction* entry_phi,
186                          HInstruction* instruction,
187                          HInstruction* x,
188                          HInstruction* y,
189                          InductionOp op);
190   InductionInfo* SolveTest(HLoopInformation* loop,
191                            HInstruction* entry_phi,
192                            HInstruction* instruction,
193                            int64_t oppositive_value);
194   InductionInfo* SolveConversion(HLoopInformation* loop,
195                                  HInstruction* entry_phi,
196                                  HTypeConversion* conversion);
197 
198   // Trip count information.
199   void VisitControl(HLoopInformation* loop);
200   void VisitCondition(HLoopInformation* loop,
201                       InductionInfo* a,
202                       InductionInfo* b,
203                       Primitive::Type type,
204                       IfCondition cmp);
205   void VisitTripCount(HLoopInformation* loop,
206                       InductionInfo* lower_expr,
207                       InductionInfo* upper_expr,
208                       InductionInfo* stride,
209                       int64_t stride_value,
210                       Primitive::Type type,
211                       IfCondition cmp);
212   bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp);
213   bool IsFinite(InductionInfo* upper_expr,
214                 int64_t stride_value,
215                 Primitive::Type type,
216                 IfCondition cmp);
217   bool FitsNarrowerControl(InductionInfo* lower_expr,
218                            InductionInfo* upper_expr,
219                            int64_t stride_value,
220                            Primitive::Type type,
221                            IfCondition cmp);
222 
223   // Assign and lookup.
224   void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
225   InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
226   InductionInfo* CreateConstant(int64_t value, Primitive::Type type);
227   InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
228   HInstruction* GetShiftConstant(HLoopInformation* loop,
229                                  HInstruction* instruction,
230                                  InductionInfo* initial);
231   void AssignCycle(HPhi* phi);
232   ArenaSet<HInstruction*>* LookupCycle(HPhi* phi);
233 
234   // Constants.
235   bool IsExact(InductionInfo* info, /*out*/ int64_t* value);
236   bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value);
237   bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value);
238 
239   // Helpers.
240   static bool IsNarrowingLinear(InductionInfo* info);
241   static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
242   static std::string FetchToString(HInstruction* fetch);
243   static std::string InductionToString(InductionInfo* info);
244 
245   // TODO: fine tune the following data structures, only keep relevant data.
246 
247   // Temporary book-keeping during the analysis.
248   uint32_t global_depth_;
249   ArenaVector<HInstruction*> stack_;
250   ArenaSafeMap<HInstruction*, NodeInfo> map_;
251   ArenaVector<HInstruction*> scc_;
252   ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
253   Primitive::Type type_;
254 
255   /**
256    * Maintains the results of the analysis as a mapping from loops to a mapping from instructions
257    * to the induction information for that instruction in that loop.
258    */
259   ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
260 
261   /**
262    * Preserves induction cycle information for each loop-phi.
263    */
264   ArenaSafeMap<HPhi*, ArenaSet<HInstruction*>> cycles_;
265 
266   friend class InductionVarAnalysisTest;
267   friend class InductionVarRange;
268   friend class InductionVarRangeTest;
269 
270   DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
271 };
272 
273 }  // namespace art
274 
275 #endif  // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
276