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