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 { 24 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 99 bool IsBooleanValueOrMaterializedCondition(HInstruction* cond_input) { 100 return !cond_input->IsCondition() || !cond_input->IsEmittedAtUseSite(); 101 } 102 103 } // namespace art 104
