From 1490796dd28c80e987a0a9306104141c52022982 Mon Sep 17 00:00:00 2001 From: Craig Topper Date: Thu, 29 Dec 2022 09:35:34 -0800 Subject: [PATCH] [Support] Fix what I think is an off by 1 bug in UnsignedDivisionByConstantInfo. The code in Hacker's Delight says `nc = -1 - (-d)%d;` But we have `NC = AllOnes - (AllOnes-D)%D` The Hacker's Delight code is written for the LeadingZeros==0 case. `AllOnes - D` is not the same as `-d` from Hacker's Delight. This patch changes the code to `NC = AllOnes - (AllOnes+1-D)%D` This will increment AllOnes to 0 in the LeadingZeros==0 case. This will make it equivalent to -D. I believe this is also correct for LeadingZeros>0. At least for i8, i16, and i32 the only divisor that changes is ((1 << (BitWidth-1)) | 1). Or 127 for i8, 32769 for i16, and 2147483649 for i32. These are all large enough that the quotient is 0 or 1 so InstCombine replaces them with an icmp and zext before SelectionDAG. Reviewed By: lebedev.ri Differential Revision: https://reviews.llvm.org/D140636 --- llvm/lib/Support/DivisionByConstantInfo.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/llvm/lib/Support/DivisionByConstantInfo.cpp b/llvm/lib/Support/DivisionByConstantInfo.cpp index c842240..b290760 100644 --- a/llvm/lib/Support/DivisionByConstantInfo.cpp +++ b/llvm/lib/Support/DivisionByConstantInfo.cpp @@ -82,7 +82,9 @@ UnsignedDivisionByConstantInfo::get(const APInt &D, unsigned LeadingZeros) { APInt SignedMin = APInt::getSignedMinValue(D.getBitWidth()); APInt SignedMax = APInt::getSignedMaxValue(D.getBitWidth()); - APInt NC = AllOnes - (AllOnes - D).urem(D); + // Calculate NC, the largest dividend such that NC.urem(D) == D-1. + APInt NC = AllOnes - (AllOnes + 1 - D).urem(D); + assert(NC.urem(D) == D - 1 && "Unexpected NC value"); unsigned P = D.getBitWidth() - 1; // initialize P APInt Q1, R1, Q2, R2; // initialize Q1 = 2P/NC; R1 = rem(2P,NC) -- 2.7.4