• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 #include "code_generator_utils.h"
18 
19 #include <android-base/logging.h>
20 
21 #include "nodes.h"
22 
23 namespace art HIDDEN {
24 
CalculateMagicAndShiftForDivRem(int64_t divisor,bool is_long,int64_t * magic,int * shift)25 void CalculateMagicAndShiftForDivRem(int64_t divisor, bool is_long,
26                                      int64_t* magic, int* shift) {
27   // It does not make sense to calculate magic and shift for zero divisor.
28   DCHECK_NE(divisor, 0);
29 
30   /* Implementation according to H.S.Warren's "Hacker's Delight" (Addison Wesley, 2002)
31    * Chapter 10 and T.Grablund, P.L.Montogomery's "Division by Invariant Integers Using
32    * Multiplication" (PLDI 1994).
33    * The magic number M and shift S can be calculated in the following way:
34    * Let nc be the most positive value of numerator(n) such that nc = kd - 1,
35    * where divisor(d) >= 2.
36    * Let nc be the most negative value of numerator(n) such that nc = kd + 1,
37    * where divisor(d) <= -2.
38    * Thus nc can be calculated like:
39    * nc = exp + exp % d - 1, where d >= 2 and exp = 2^31 for int or 2^63 for long
40    * nc = -exp + (exp + 1) % d, where d >= 2 and exp = 2^31 for int or 2^63 for long
41    *
42    * So the shift p is the smallest p satisfying
43    * 2^p > nc * (d - 2^p % d), where d >= 2
44    * 2^p > nc * (d + 2^p % d), where d <= -2.
45    *
46    * The magic number M is calculated by
47    * M = (2^p + d - 2^p % d) / d, where d >= 2
48    * M = (2^p - d - 2^p % d) / d, where d <= -2.
49    *
50    * Notice that p is always bigger than or equal to 32 (resp. 64), so we just return 32 - p
51    * (resp. 64 - p) as the shift number S.
52    */
53 
54   int64_t p = is_long ? 63 : 31;
55   const uint64_t exp = is_long ? (UINT64_C(1) << 63) : (UINT32_C(1) << 31);
56 
57   // Initialize the computations.
58   uint64_t abs_d = (divisor >= 0) ? divisor : -divisor;
59   uint64_t sign_bit = is_long ? static_cast<uint64_t>(divisor) >> 63 :
60                                 static_cast<uint32_t>(divisor) >> 31;
61   uint64_t tmp = exp + sign_bit;
62   uint64_t abs_nc = tmp - 1 - (tmp % abs_d);
63   uint64_t quotient1 = exp / abs_nc;
64   uint64_t remainder1 = exp % abs_nc;
65   uint64_t quotient2 = exp / abs_d;
66   uint64_t remainder2 = exp % abs_d;
67 
68   /*
69    * To avoid handling both positive and negative divisor, "Hacker's Delight"
70    * introduces a method to handle these 2 cases together to avoid duplication.
71    */
72   uint64_t delta;
73   do {
74     p++;
75     quotient1 = 2 * quotient1;
76     remainder1 = 2 * remainder1;
77     if (remainder1 >= abs_nc) {
78       quotient1++;
79       remainder1 = remainder1 - abs_nc;
80     }
81     quotient2 = 2 * quotient2;
82     remainder2 = 2 * remainder2;
83     if (remainder2 >= abs_d) {
84       quotient2++;
85       remainder2 = remainder2 - abs_d;
86     }
87     delta = abs_d - remainder2;
88   } while (quotient1 < delta || (quotient1 == delta && remainder1 == 0));
89 
90   *magic = (divisor > 0) ? (quotient2 + 1) : (-quotient2 - 1);
91 
92   if (!is_long) {
93     *magic = static_cast<int>(*magic);
94   }
95 
96   *shift = is_long ? p - 64 : p - 32;
97 }
98 
IsBooleanValueOrMaterializedCondition(HInstruction * cond_input)99 bool IsBooleanValueOrMaterializedCondition(HInstruction* cond_input) {
100   return !cond_input->IsCondition() || !cond_input->IsEmittedAtUseSite();
101 }
102 
103 // A helper class to group functions analyzing if values are non-negative
104 // at the point of use. The class keeps some context used by the functions.
105 // The class is not supposed to be used directly or its instances to be kept.
106 // The main function using it is HasNonNegativeInputAt.
107 // If you want to use the class methods you need to become a friend of the class.
108 class UnsignedUseAnalyzer {
109  private:
UnsignedUseAnalyzer(ArenaAllocator * allocator)110   explicit UnsignedUseAnalyzer(ArenaAllocator* allocator)
111       : seen_values_(allocator->Adapter(kArenaAllocCodeGenerator)) {
112   }
113 
114   bool IsNonNegativeUse(HInstruction* target_user, HInstruction* value);
115   bool IsComparedValueNonNegativeInBlock(HInstruction* value,
116                                          HCondition* cond,
117                                          HBasicBlock* target_block);
118 
119   ArenaSet<HInstruction*> seen_values_;
120 
121   friend bool HasNonNegativeInputAt(HInstruction* instr, size_t i);
122 };
123 
124 // Check that the value compared with a non-negavite value is
125 // non-negative in the specified basic block.
IsComparedValueNonNegativeInBlock(HInstruction * value,HCondition * cond,HBasicBlock * target_block)126 bool UnsignedUseAnalyzer::IsComparedValueNonNegativeInBlock(HInstruction* value,
127                                                             HCondition* cond,
128                                                             HBasicBlock* target_block) {
129   DCHECK(cond->HasInput(value));
130 
131   // To simplify analysis, we require:
132   // 1. The condition basic block and target_block to be different.
133   // 2. The condition basic block to end with HIf.
134   // 3. HIf to use the condition.
135   if (cond->GetBlock() == target_block ||
136       !cond->GetBlock()->EndsWithIf() ||
137       cond->GetBlock()->GetLastInstruction()->InputAt(0) != cond) {
138     return false;
139   }
140 
141   // We need to find a successor basic block of HIf for the case when instr is non-negative.
142   // If the successor dominates target_block, instructions in target_block see a non-negative value.
143   HIf* if_instr = cond->GetBlock()->GetLastInstruction()->AsIf();
144   HBasicBlock* successor = nullptr;
145   switch (cond->GetCondition()) {
146     case kCondGT:
147     case kCondGE: {
148       if (cond->GetLeft() == value) {
149         // The expression is v > A or v >= A.
150         // If A is non-negative, we need the true successor.
151         if (IsNonNegativeUse(cond, cond->GetRight())) {
152           successor = if_instr->IfTrueSuccessor();
153         } else {
154           return false;
155         }
156       } else {
157         DCHECK_EQ(cond->GetRight(), value);
158         // The expression is A > v or A >= v.
159         // If A is non-negative, we need the false successor.
160         if (IsNonNegativeUse(cond, cond->GetLeft())) {
161           successor = if_instr->IfFalseSuccessor();
162         } else {
163           return false;
164         }
165       }
166       break;
167     }
168 
169     case kCondLT:
170     case kCondLE: {
171       if (cond->GetLeft() == value) {
172         // The expression is v < A or v <= A.
173         // If A is non-negative, we need the false successor.
174         if (IsNonNegativeUse(cond, cond->GetRight())) {
175           successor = if_instr->IfFalseSuccessor();
176         } else {
177           return false;
178         }
179       } else {
180         DCHECK_EQ(cond->GetRight(), value);
181         // The expression is A < v or A <= v.
182         // If A is non-negative, we need the true successor.
183         if (IsNonNegativeUse(cond, cond->GetLeft())) {
184           successor = if_instr->IfTrueSuccessor();
185         } else {
186           return false;
187         }
188       }
189       break;
190     }
191 
192     default:
193       return false;
194   }
195   DCHECK_NE(successor, nullptr);
196 
197   return successor->Dominates(target_block);
198 }
199 
200 // Check the value used by target_user is non-negative.
IsNonNegativeUse(HInstruction * target_user,HInstruction * value)201 bool UnsignedUseAnalyzer::IsNonNegativeUse(HInstruction* target_user, HInstruction* value) {
202   DCHECK(target_user->HasInput(value));
203 
204   // Prevent infinitive recursion which can happen when the value is an induction variable.
205   if (!seen_values_.insert(value).second) {
206     return false;
207   }
208 
209   // Check if the value is always non-negative.
210   if (IsGEZero(value)) {
211     return true;
212   }
213 
214   for (const HUseListNode<HInstruction*>& use : value->GetUses()) {
215     HInstruction* user = use.GetUser();
216     if (user == target_user) {
217       continue;
218     }
219 
220     // If the value is compared with some non-negative value, this can guarantee the value to be
221     // non-negative at its use.
222     // JFYI: We're not using HTypeConversion to bind the new information because it would
223     // increase the complexity of optimizations: HTypeConversion can create a dependency
224     // which does not exist in the input program, for example:
225     // between two uses, 1st - cmp, 2nd - target_user.
226     if (user->IsCondition()) {
227       // The condition must dominate target_user to guarantee that the value is always checked
228       // before it is used by target_user.
229       if (user->GetBlock()->Dominates(target_user->GetBlock()) &&
230           IsComparedValueNonNegativeInBlock(value, user->AsCondition(), target_user->GetBlock())) {
231         return true;
232       }
233     }
234 
235     // TODO The value is non-negative if it is used as an array index before.
236     // TODO The value is non-negative if it is initialized by a positive number and all of its
237     //      modifications keep the value non-negative, for example the division operation.
238   }
239 
240   return false;
241 }
242 
HasNonNegativeInputAt(HInstruction * instr,size_t i)243 bool HasNonNegativeInputAt(HInstruction* instr, size_t i) {
244   UnsignedUseAnalyzer analyzer(instr->GetBlock()->GetGraph()->GetAllocator());
245   return analyzer.IsNonNegativeUse(instr, instr->InputAt(i));
246 }
247 
HasNonNegativeOrMinIntInputAt(HInstruction * instr,size_t i)248 bool HasNonNegativeOrMinIntInputAt(HInstruction* instr, size_t i) {
249   HInstruction* input = instr->InputAt(i);
250   return input->IsAbs() ||
251          IsInt64Value(input, DataType::MinValueOfIntegralType(input->GetType())) ||
252          HasNonNegativeInputAt(instr, i);
253 }
254 
255 }  // namespace art
256