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, const char* name = kInductionPassName);
39 
40   bool 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                   DataType::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     DataType::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_->GetAllocator())
133         InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType());
134   }
135 
CreateTripCount(InductionOp op,InductionInfo * a,InductionInfo * b,DataType::Type type)136   InductionInfo* CreateTripCount(InductionOp op,
137                                  InductionInfo* a,
138                                  InductionInfo* b,
139                                  DataType::Type type) {
140     DCHECK(a != nullptr && b != nullptr);
141     return new (graph_->GetAllocator()) InductionInfo(kInvariant, op, a, b, nullptr, type);
142   }
143 
CreateInduction(InductionClass ic,InductionOp op,InductionInfo * a,InductionInfo * b,HInstruction * f,DataType::Type type)144   InductionInfo* CreateInduction(InductionClass ic,
145                                  InductionOp op,
146                                  InductionInfo* a,
147                                  InductionInfo* b,
148                                  HInstruction* f,
149                                  DataType::Type type) {
150     DCHECK(a != nullptr && b != nullptr);
151     return new (graph_->GetAllocator()) 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, DataType::Type from, DataType::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   //
199   // Loop trip count analysis methods.
200   //
201 
202   // Trip count information.
203   void VisitControl(HLoopInformation* loop);
204   void VisitCondition(HLoopInformation* loop,
205                       HBasicBlock* body,
206                       InductionInfo* a,
207                       InductionInfo* b,
208                       DataType::Type type,
209                       IfCondition cmp);
210   void VisitTripCount(HLoopInformation* loop,
211                       InductionInfo* lower_expr,
212                       InductionInfo* upper_expr,
213                       InductionInfo* stride,
214                       int64_t stride_value,
215                       DataType::Type type,
216                       IfCondition cmp);
217   bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp);
218   bool IsFinite(InductionInfo* upper_expr,
219                 int64_t stride_value,
220                 DataType::Type type,
221                 IfCondition cmp);
222   bool FitsNarrowerControl(InductionInfo* lower_expr,
223                            InductionInfo* upper_expr,
224                            int64_t stride_value,
225                            DataType::Type type,
226                            IfCondition cmp);
227   bool RewriteBreakLoop(HLoopInformation* loop,
228                         HBasicBlock* body,
229                         int64_t stride_value,
230                         DataType::Type type);
231 
232   //
233   // Helper methods.
234   //
235 
236   // Assign and lookup.
237   void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
238   InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
239   InductionInfo* CreateConstant(int64_t value, DataType::Type type);
240   InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
241   HInstruction* GetShiftConstant(HLoopInformation* loop,
242                                  HInstruction* instruction,
243                                  InductionInfo* initial);
244   void AssignCycle(HPhi* phi);
245   ArenaSet<HInstruction*>* LookupCycle(HPhi* phi);
246 
247   // Constants.
248   bool IsExact(InductionInfo* info, /*out*/ int64_t* value);
249   bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value);
250   bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value);
251 
252   // Helpers.
253   static bool IsNarrowingLinear(InductionInfo* info);
254   static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
255   static std::string FetchToString(HInstruction* fetch);
256   static std::string InductionToString(InductionInfo* info);
257 
258   // TODO: fine tune the following data structures, only keep relevant data.
259 
260   // Temporary book-keeping during the analysis.
261   uint32_t global_depth_;
262   ArenaVector<HInstruction*> stack_;
263   ArenaSafeMap<HInstruction*, NodeInfo> map_;
264   ArenaVector<HInstruction*> scc_;
265   ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
266   DataType::Type type_;
267 
268   /**
269    * Maintains the results of the analysis as a mapping from loops to a mapping from instructions
270    * to the induction information for that instruction in that loop.
271    */
272   ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
273 
274   /**
275    * Preserves induction cycle information for each loop-phi.
276    */
277   ArenaSafeMap<HPhi*, ArenaSet<HInstruction*>> cycles_;
278 
279   friend class InductionVarAnalysisTest;
280   friend class InductionVarRange;
281   friend class InductionVarRangeTest;
282 
283   DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
284 };
285 
286 }  // namespace art
287 
288 #endif  // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
289