1 //===----- DivisonByConstantInfo.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 unsigned P; 23 APInt AD, ANC, Delta, Q1, R1, Q2, R2, T; 24 APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth()); 25 struct SignedDivisionByConstantInfo Retval; 26 27 AD = D.abs(); 28 T = SignedMin + (D.lshr(D.getBitWidth() - 1)); 29 ANC = T - 1 - T.urem(AD); // absolute value of NC 30 P = D.getBitWidth() - 1; // initialize P 31 Q1 = SignedMin.udiv(ANC); // initialize Q1 = 2P/abs(NC) 32 R1 = SignedMin - Q1 * ANC; // initialize R1 = rem(2P,abs(NC)) 33 Q2 = SignedMin.udiv(AD); // initialize Q2 = 2P/abs(D) 34 R2 = SignedMin - Q2 * AD; // initialize R2 = rem(2P,abs(D)) 35 do { 36 P = P + 1; 37 Q1 = Q1 << 1; // update Q1 = 2P/abs(NC) 38 R1 = R1 << 1; // update R1 = rem(2P/abs(NC)) 39 if (R1.uge(ANC)) { // must be unsigned comparison 40 Q1 = Q1 + 1; 41 R1 = R1 - ANC; 42 } 43 Q2 = Q2 << 1; // update Q2 = 2P/abs(D) 44 R2 = R2 << 1; // update R2 = rem(2P/abs(D)) 45 if (R2.uge(AD)) { // must be unsigned comparison 46 Q2 = Q2 + 1; 47 R2 = R2 - AD; 48 } 49 Delta = AD - R2; 50 } while (Q1.ult(Delta) || (Q1 == Delta && R1 == 0)); 51 52 Retval.Magic = Q2 + 1; 53 if (D.isNegative()) 54 Retval.Magic = -Retval.Magic; // resulting magic number 55 Retval.ShiftAmount = P - D.getBitWidth(); // resulting shift 56 return Retval; 57 } 58 59 /// Calculate the magic numbers required to implement an unsigned integer 60 /// division by a constant as a sequence of multiplies, adds and shifts. 61 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry 62 /// S. Warren, Jr., chapter 10. 63 /// LeadingZeros can be used to simplify the calculation if the upper bits 64 /// of the divided value are known zero. 65 UnsignedDivisonByConstantInfo 66 UnsignedDivisonByConstantInfo::get(const APInt &D, unsigned LeadingZeros) { 67 unsigned P; 68 APInt NC, Delta, Q1, R1, Q2, R2; 69 struct UnsignedDivisonByConstantInfo Retval; 70 Retval.IsAdd = false; // initialize "add" indicator 71 APInt AllOnes = APInt::getAllOnes(D.getBitWidth()).lshr(LeadingZeros); 72 APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth()); 73 APInt SignedMax = APInt::getSignedMaxValue(D.getBitWidth()); 74 75 NC = AllOnes - (AllOnes - D).urem(D); 76 P = D.getBitWidth() - 1; // initialize P 77 Q1 = SignedMin.udiv(NC); // initialize Q1 = 2P/NC 78 R1 = SignedMin - Q1 * NC; // initialize R1 = rem(2P,NC) 79 Q2 = SignedMax.udiv(D); // initialize Q2 = (2P-1)/D 80 R2 = SignedMax - Q2 * D; // initialize R2 = rem((2P-1),D) 81 do { 82 P = P + 1; 83 if (R1.uge(NC - R1)) { 84 Q1 = Q1 + Q1 + 1; // update Q1 85 R1 = R1 + R1 - NC; // update R1 86 } else { 87 Q1 = Q1 + Q1; // update Q1 88 R1 = R1 + R1; // update R1 89 } 90 if ((R2 + 1).uge(D - R2)) { 91 if (Q2.uge(SignedMax)) 92 Retval.IsAdd = true; 93 Q2 = Q2 + Q2 + 1; // update Q2 94 R2 = R2 + R2 + 1 - D; // update R2 95 } else { 96 if (Q2.uge(SignedMin)) 97 Retval.IsAdd = true; 98 Q2 = Q2 + Q2; // update Q2 99 R2 = R2 + R2 + 1; // update R2 100 } 101 Delta = D - 1 - R2; 102 } while (P < D.getBitWidth() * 2 && 103 (Q1.ult(Delta) || (Q1 == Delta && R1 == 0))); 104 Retval.Magic = Q2 + 1; // resulting magic number 105 Retval.ShiftAmount = P - D.getBitWidth(); // resulting shift 106 return Retval; 107 } 108