Fix Integer Division Expansion special case of divide by 1

[aditya_nandakumar]

Summary

I think the handling of special case of divide by 1 is incorrect in udivsi3.c (compiler-rt) and it’s equivalent in llvm/lib/Transforms/Utils/IntegerDivision.cpp

I think we want to check if the clz(divisor) == (Num_word_bits - 1) rather than checking
(clz(divisor) - clz(dividend)) == (Num_word_bits - 1)

I also think compiler-rt should be updated -
http://llvm.org/svn/llvm-project/compiler-rt/trunk/lib/builtins/udivsi3.c

sr = builtin_clz(d) - builtin_clz(n);

/* 0 <= sr <= n_uword_bits - 1 or sr large */
if (sr > n_uword_bits - 1)  /* d > r */
    return 0;
if (sr == n_uword_bits - 1)  /* d == 1 */
    return n;

The last line should be replaced with

if ( __buildin_clz(d) == n_uword_bits - 1)

		return n;

[aditya_nandakumar]

+ llvm-commits-list

[MatzeB]

Hi Aditya,

please upload a patch with full context next time (see http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface). We also try to create test cases when we fix a bug.

The change itself looks okay to me, but I'd wait for a LGTM from the original author (milseman) as I don't understand the motivation of using CTLZ there instead of just comparing the dividend and divisor so I may be missing something.

lib/Transforms/Utils/IntegerDivision.cpp

   // ;   %sr          = sub nsw i32 %tmp0, %tmp1
   // ;   %ret0_4      = icmp ugt i32 %sr, 31
   // ;   %ret0        = or i1 %ret0_3, %ret0_4
-  // ;   %retDividend = icmp eq i32 %sr, 31
+  // ;   %retDividend = icmp eq i32 %tmp0, 31
   // ;   %retVal      = select i1 %ret0, i32 0, i32 %dividend
   // ;   %earlyRet    = or i1 %ret0, %retDividend
   // ;   br i1 %earlyRet, label %end, label %bb1

   Value *SR          = Builder.CreateSub(Tmp0, Tmp1);
   Value *Ret0_4      = Builder.CreateICmpUGT(SR, MSB);
   Value *Ret0        = Builder.CreateOr(Ret0_3, Ret0_4);
-  Value *RetDividend = Builder.CreateICmpEQ(SR, MSB);
+  Value *RetDividend = Builder.CreateICmpEQ(Tmp0, MSB);
   Value *RetVal      = Builder.CreateSelect(Ret0, Zero, Dividend);
   Value *EarlyRet    = Builder.CreateOr(Ret0, RetDividend);
   Builder.CreateCondBr(EarlyRet, End, BB1);