156 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8///9/// This file implements support for optimizing divisions by a constant10///11//===----------------------------------------------------------------------===//12 13#include "llvm/Support/DivisionByConstantInfo.h"14 15using namespace llvm;16 17/// Calculate the magic numbers required to implement a signed integer division18/// by a constant as a sequence of multiplies, adds and shifts. Requires that19/// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.20/// Warren, Jr., Chapter 10.21SignedDivisionByConstantInfo 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 NC34 unsigned P = D.getBitWidth() - 1; // initialize P35 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 comparison45 ++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 comparison51 ++Q2;52 R2 -= AD;53 }54 // Delta = AD - R255 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 number63 Retval.ShiftAmount = P - D.getBitWidth(); // resulting shift64 return Retval;65}66 67/// Calculate the magic numbers required to implement an unsigned integer68/// 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", Henry70/// S. Warren, Jr., chapter 10.71/// LeadingZeros can be used to simplify the calculation if the upper bits72/// of the divided value are known zero.73UnsignedDivisionByConstantInfo74UnsignedDivisionByConstantInfo::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" indicator82 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 P91 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 Q1100 Q1 <<= 1;101 ++Q1;102 // update R1103 R1 <<= 1;104 R1 -= NC;105 } else {106 Q1 <<= 1; // update Q1107 R1 <<= 1; // update R1108 }109 if ((R2 + 1).uge(D - R2)) {110 if (Q2.uge(SignedMax))111 Retval.IsAdd = true;112 // update Q2113 Q2 <<= 1;114 ++Q2;115 // update R2116 R2 <<= 1;117 ++R2;118 R2 -= D;119 } else {120 if (Q2.uge(SignedMin))121 Retval.IsAdd = true;122 // update Q2123 Q2 <<= 1;124 // update R2125 R2 <<= 1;126 ++R2;127 }128 // Delta = D - 1 - R2129 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 number146 ++Retval.Magic;147 Retval.PostShift = P - D.getBitWidth(); // resulting shift148 // 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