1 //===----- DivisionByConstantInfo.cpp - division by constant -*- C++ -*----===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// This file implements support for optimizing divisions by a constant 10 /// 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/Support/DivisionByConstantInfo.h" 14 15 using namespace llvm; 16 17 /// Calculate the magic numbers required to implement a signed integer division 18 /// by a constant as a sequence of multiplies, adds and shifts. Requires that 19 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S. 20 /// Warren, Jr., Chapter 10. 21 SignedDivisionByConstantInfo SignedDivisionByConstantInfo::get(const APInt &D) { 22 assert(!D.isZero() && "Precondition violation."); 23 24 // We'd be endlessly stuck in the loop. 25 assert(D.getBitWidth() >= 3 && "Does not work at smaller bitwidths."); 26 27 APInt Delta; 28 APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth()); 29 struct SignedDivisionByConstantInfo Retval; 30 31 APInt AD = D.abs(); 32 APInt T = SignedMin + (D.lshr(D.getBitWidth() - 1)); 33 APInt ANC = T - 1 - T.urem(AD); // absolute value of NC 34 unsigned P = D.getBitWidth() - 1; // initialize P 35 APInt Q1, R1, Q2, R2; 36 // initialize Q1 = 2P/abs(NC); R1 = rem(2P,abs(NC)) 37 APInt::udivrem(SignedMin, ANC, Q1, R1); 38 // initialize Q2 = 2P/abs(D); R2 = rem(2P,abs(D)) 39 APInt::udivrem(SignedMin, AD, Q2, R2); 40 do { 41 P = P + 1; 42 Q1 <<= 1; // update Q1 = 2P/abs(NC) 43 R1 <<= 1; // update R1 = rem(2P/abs(NC)) 44 if (R1.uge(ANC)) { // must be unsigned comparison 45 ++Q1; 46 R1 -= ANC; 47 } 48 Q2 <<= 1; // update Q2 = 2P/abs(D) 49 R2 <<= 1; // update R2 = rem(2P/abs(D)) 50 if (R2.uge(AD)) { // must be unsigned comparison 51 ++Q2; 52 R2 -= AD; 53 } 54 // Delta = AD - R2 55 Delta = AD; 56 Delta -= R2; 57 } while (Q1.ult(Delta) || (Q1 == Delta && R1.isZero())); 58 59 Retval.Magic = std::move(Q2); 60 ++Retval.Magic; 61 if (D.isNegative()) 62 Retval.Magic.negate(); // resulting magic number 63 Retval.ShiftAmount = P - D.getBitWidth(); // resulting shift 64 return Retval; 65 } 66 67 /// Calculate the magic numbers required to implement an unsigned integer 68 /// division by a constant as a sequence of multiplies, adds and shifts. 69 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry 70 /// S. Warren, Jr., chapter 10. 71 /// LeadingZeros can be used to simplify the calculation if the upper bits 72 /// of the divided value are known zero. 73 UnsignedDivisionByConstantInfo 74 UnsignedDivisionByConstantInfo::get(const APInt &D, unsigned LeadingZeros, 75 bool AllowEvenDivisorOptimization) { 76 assert(!D.isZero() && !D.isOne() && "Precondition violation."); 77 assert(D.getBitWidth() > 1 && "Does not work at smaller bitwidths."); 78 79 APInt Delta; 80 struct UnsignedDivisionByConstantInfo Retval; 81 Retval.IsAdd = false; // initialize "add" indicator 82 APInt AllOnes = 83 APInt::getLowBitsSet(D.getBitWidth(), D.getBitWidth() - LeadingZeros); 84 APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth()); 85 APInt SignedMax = APInt::getSignedMaxValue(D.getBitWidth()); 86 87 // Calculate NC, the largest dividend such that NC.urem(D) == D-1. 88 APInt NC = AllOnes - (AllOnes + 1 - D).urem(D); 89 assert(NC.urem(D) == D - 1 && "Unexpected NC value"); 90 unsigned P = D.getBitWidth() - 1; // initialize P 91 APInt Q1, R1, Q2, R2; 92 // initialize Q1 = 2P/NC; R1 = rem(2P,NC) 93 APInt::udivrem(SignedMin, NC, Q1, R1); 94 // initialize Q2 = (2P-1)/D; R2 = rem((2P-1),D) 95 APInt::udivrem(SignedMax, D, Q2, R2); 96 do { 97 P = P + 1; 98 if (R1.uge(NC - R1)) { 99 // update Q1 100 Q1 <<= 1; 101 ++Q1; 102 // update R1 103 R1 <<= 1; 104 R1 -= NC; 105 } else { 106 Q1 <<= 1; // update Q1 107 R1 <<= 1; // update R1 108 } 109 if ((R2 + 1).uge(D - R2)) { 110 if (Q2.uge(SignedMax)) 111 Retval.IsAdd = true; 112 // update Q2 113 Q2 <<= 1; 114 ++Q2; 115 // update R2 116 R2 <<= 1; 117 ++R2; 118 R2 -= D; 119 } else { 120 if (Q2.uge(SignedMin)) 121 Retval.IsAdd = true; 122 // update Q2 123 Q2 <<= 1; 124 // update R2 125 R2 <<= 1; 126 ++R2; 127 } 128 // Delta = D - 1 - R2 129 Delta = D; 130 --Delta; 131 Delta -= R2; 132 } while (P < D.getBitWidth() * 2 && 133 (Q1.ult(Delta) || (Q1 == Delta && R1.isZero()))); 134 135 if (Retval.IsAdd && !D[0] && AllowEvenDivisorOptimization) { 136 unsigned PreShift = D.countr_zero(); 137 APInt ShiftedD = D.lshr(PreShift); 138 Retval = 139 UnsignedDivisionByConstantInfo::get(ShiftedD, LeadingZeros + PreShift); 140 assert(Retval.IsAdd == 0 && Retval.PreShift == 0); 141 Retval.PreShift = PreShift; 142 return Retval; 143 } 144 145 Retval.Magic = std::move(Q2); // resulting magic number 146 ++Retval.Magic; 147 Retval.PostShift = P - D.getBitWidth(); // resulting shift 148 // Reduce shift amount for IsAdd. 149 if (Retval.IsAdd) { 150 assert(Retval.PostShift > 0 && "Unexpected shift"); 151 Retval.PostShift -= 1; 152 } 153 Retval.PreShift = 0; 154 return Retval; 155 } 156