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