Bug fix and a proposed improvement in integer division expansion

[dshtilman]

Summary

The special case code in udiv expansion is currently broken, namely the check for divisor==1 :

` // ; special-cases:

// ;   %ret0_1      = icmp eq i32 %divisor, 0
// ;   %ret0_2      = icmp eq i32 %dividend, 0
// ;   %ret0_3      = or i1 %ret0_1, %ret0_2
// ;   %tmp0        = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)
// ;   %tmp1        = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)
// ;   %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
// ;   %retVal      = select i1 %ret0, i32 0, i32 %dividend
// ;   %earlyRet    = or i1 %ret0, %retDividend
// ;   br i1 %earlyRet, label %end, label %bb1

`
The intention must have been to use %tmp0, not %sr.

The following patch fixes this special case and also extends it to cover divisions by a power of 2 which will be routed through a simple shift right instead of going through the huge loop. Division by 1 will also go through the shift right yielding the dividend (shifted by zero).

lib/Transforms/Utils/IntegerDivision.cpp

static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
   }
 
   ConstantInt *True = Builder.getTrue();
 
   BasicBlock *IBB = Builder.GetInsertBlock();
   Function *F = IBB->getParent();
   Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
                                              DivTy);
+  Function *CTTZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::cttz,
+                                             DivTy);
 
   // Our CFG is going to look like:
   // +---------------------+
   // | special-cases       |
   // |   ...               |
   // +---------------------+
   //  |       |
   //  |   +----------+
BasicBlock *BB1       = BasicBlock::Create(Builder.getContext(),
                                              "udiv-bb1", F, End);
 
   // We'll be overwriting the terminator to insert our extra blocks
   SpecialCases->getTerminator()->eraseFromParent();
 
   // Same instructions are generated for both i32 (msb 31) and i64 (msb 63).
 
   // First off, check for special cases: dividend or divisor is zero, divisor
-  // is greater than dividend, and divisor is 1.
+  // is greater than dividend, and divisor is a power of 2.
   // ; special-cases:
   // ;   %ret0_1      = icmp eq i32 %divisor, 0
   // ;   %ret0_2      = icmp eq i32 %dividend, 0
   // ;   %ret0_3      = or i1 %ret0_1, %ret0_2
   // ;   %tmp0        = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)
   // ;   %tmp1        = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)
   // ;   %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
-  // ;   %retVal      = select i1 %ret0, i32 0, i32 %dividend
+  // ;   %tmp14       = tail call i32 @llvm.cttz.i32(i32 %divisor, i1 true)
+  // ;   %tmp15       = add i32 %tmp0, %tmp14
+  // ;   %retDividend = icmp eq i32 %tmp15, 31
+  // ;   %dividend_1  = lshr i32 %dividend, %tmp14
+  // ;   %retVal      = select i1 %ret0, i32 0, i32 %dividend_1
   // ;   %earlyRet    = or i1 %ret0, %retDividend
   // ;   br i1 %earlyRet, label %end, label %bb1
   Builder.SetInsertPoint(SpecialCases);
   Value *Ret0_1      = Builder.CreateICmpEQ(Divisor, Zero);
   Value *Ret0_2      = Builder.CreateICmpEQ(Dividend, Zero);
   Value *Ret0_3      = Builder.CreateOr(Ret0_1, Ret0_2);
   Value *Tmp0 = Builder.CreateCall(CTLZ, {Divisor, True});
   Value *Tmp1 = Builder.CreateCall(CTLZ, {Dividend, True});
   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 *RetVal      = Builder.CreateSelect(Ret0, Zero, Dividend);
+  Value *Tmp14       = Builder.CreateCall(CTTZ, {Divisor, True});
+  Value *Tmp15       = Builder.CreateAdd(Tmp0, Tmp14);
+  Value *RetDividend = Builder.CreateICmpEQ(Tmp15, MSB);
+  Value *Dividend_1  = Builder.CreateLShr(Dividend, Tmp14);
+  Value *RetVal      = Builder.CreateSelect(Ret0, Zero, Dividend_1);
   Value *EarlyRet    = Builder.CreateOr(Ret0, RetDividend);
   Builder.CreateCondBr(EarlyRet, End, BB1);
 
   // ; bb1:                                             ; preds = %special-cases
   // ;   %sr_1     = add i32 %sr, 1
   // ;   %tmp2     = sub i32 31, %sr
   // ;   %q        = shl i32 %dividend, %tmp2
   // ;   %skipLoop = icmp eq i32 %sr_1, 0