[BypassSlowDivision] Use ValueTracking to simplify run-time checks

[n.bozhenov]

Summary

ValueTracking is used for more thorough analysis of operands. Based on
the analysis, either run-time checks can be simplified (e.g. check only
one operand instead of two) or the transformation can be avoided. For
example, it is quite often the case that a divisor is promoted from a
shorter type and run-time checks for it are redundant.

With additional compile-time analysis of values, two special
cases naturally arise and are addressed by the patch:

1. Both operands are known to be short enough. Then, the long division can be simply replaced with a short one without CFG modification.

2. If a division is unsigned and the dividend is known to be short enough then the long division is not needed any more. Because if the divisor is too big for short division then the quotient is obviously zero (and the remainder is equal to the dividend). Actually, the division is not needed when (divisor > dividend).

[n.bozhenov]

This patch is part of a larger patch set:

1. D28196
2. D28197
3. D28198
4. D28199
5. D28200

[jlebar]

I'm excited to see what this does for our GPU kernels.

lib/Transforms/Utils/BypassSlowDivision.cpp

48

Please define what these mean. (The notion of "long" and "short" are important to this patch, but we don't define them anywhere.)

48

Suggest renaming the enum to ValueRange -- you can still abbreviate it "VALRNG" in the enumerators.

78

Check if an integer value fits into a smaller type.

82

This paragraph doesn't add any additional information IMO -- maybe we should just get rid of it.

87

LLVM convention is to start all variable names with upper-case letters -- please fix here and elsewhere.

98

LLVM convention is not to use braces on single-line if statements. Please fix here and elsewhere.

121

Nit, this looks like "dividend random number generator" to me. Spelling out "Range" would only be an extra two chars -- maybe we should do that for both ValRng and Dividend/DivisorRange.

139

Suggest s/tr/Trunc/. In any case please use uppercase.

149

I think it would be clearer if we didn't have this variable and just wrote out ConstantInt::get(I->getType(), 0) in the two places where we need it. As-is, a reader is going to have to use Vim's # to figure out what this variable is, since the function is so long and the uses are so far from the declaration.

151

Long prepositional phrases at the beginning of a sentence should be followed by a comma.

152

comma before "and" (separating independent clauses)

154

In this case, no division is needed at all: The quotient is 0 and the remainder is equal to Dividend.

156

This comment is missing the (really cool) punch line:

So instead of checking at runtime whether Divisor fits into BypassType, we emit a runtime check to differentiate between these two cases. This lets us entirely avoid a long div.

157

"Shortcut" is one word, but also, this control flow is very complicated.

For example, it's confusing that the first if (ShortCut) branch, which is in the "basic block for slow divide operation", actually does something very fast. One could add comments, but they're going to be pretty complicated. ("New BB for long divide, which we bypass if possible, see definition of ShortCut...")

It seems to me we really want to say

if (DividendShort && !UseSignedOp) {
  // Do one thing.
} else {
  // Do something different.
}

Could we refactor the code so we can write it this way?

232

Suggest commenting on what the whole "else" branch is doing:

Check at runtime whether Dividend and Divisor fit in BypassType.

Mentioning the "OR" is more confusing than helpful, I think, because we don't always emit the OR.

test/CodeGen/X86/bypass-slow-division-64.ll

67

The first comment added here is good, but then the ones below are all fragments, which is confusing. Can we make them complete sentences?

[n.bozhenov]

lib/Transforms/Utils/BypassSlowDivision.cpp

157

It seems to me we really want to say

if (DividendShort && !UseSignedOp) {
  // Do one thing.
} else {
  // Do something different.
}

Could we refactor the code so we can write it this way?

I fully agree that the control flow gets overly complex here. But I did it this way because all the paths re-use some parts of the code, so to get a simpler control flow one have either to perform significant refactoring of the code or to introduce a lot of code duplication. And I was kind of reluctant to refactor the code.

I played with refactoring approach and uploaded a couple of patches D29896 and D29897. The first patch does refactoring and extracts a number of auxilliary methods from insertFastDiv function, so that in the second patch these methods can be reused along different code paths as necessary. By the way, I had to convert a number of variables into object attributes, because the same values are used across all these auxilliary methods.

Justin, do you think such refactoring approach should be preferred?

[jlebar]

Justin, do you think such refactoring approach should be preferred?

I'm happy to review these additional patches, but I would prefer to have a relatively fast feedback cycle between my reviewing the code and your addressing the comments. By the time a week has passed, I've already forgotten details about the patch; by the time six weeks pass, I am reviewing totally from scratch.

Do you have time now to push these patches through to completion? If not, maybe you can let me know when you do, and at that point I'll start reviewing?

[n.bozhenov]

Do you have time now to push these patches through to completion? If not, maybe you can let me know when you do, and at that point I'll start reviewing?

Yep. Let's do it now.

[n.bozhenov]

Superseded by D29897.

lib/Transforms/Utils/BypassSlowDivision.cpp

 // For example, on Intel Atom 32-bit divides are slow enough that during
 // runtime it is profitable to check the value of the operands, and if they are
 // positive and less than 256 use an unsigned 8-bit divide.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/Transforms/Utils/Local.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "bypass-slow-division"
namespace {
 
   struct DivPhiNodes {
     PHINode *Quotient;
     PHINode *Remainder;
 
     DivPhiNodes(PHINode *InQuotient, PHINode *InRemainder)
       : Quotient(InQuotient), Remainder(InRemainder) {}
   };
+
+  enum ValRng { VALRNG_SHORT, VALRNG_UNKNOWN, VALRNG_LONG };
 }
 
 namespace llvm {
   template<>
   struct DenseMapInfo<DivOpInfo> {
     static bool isEqual(const DivOpInfo &Val1, const DivOpInfo &Val2) {
       return Val1.SignedOp == Val2.SignedOp &&
              Val1.Dividend == Val2.Dividend &&
static unsigned getHashValue(const DivOpInfo &Val) {
                         reinterpret_cast<uintptr_t>(Val.Divisor)) ^
                         (unsigned)Val.SignedOp;
     }
   };
 
   typedef DenseMap<DivOpInfo, DivPhiNodes> DivCacheTy;
 }
 
+/// \brief Check if the value may fit the shorter type.
+///
+/// The function tests if the operand is known to fit the shorter type or if it
+/// is known to be too wide. In the former case the runtime check can be
+/// simplified, in the latter case bypassing should be avoided.
+static ValRng getValueRange(Value *Op, IntegerType *BypassType,
+                            const DataLayout &DL) {
+  unsigned shortLen = BypassType->getBitWidth();
+  unsigned longLen = cast<IntegerType>(Op->getType())->getBitWidth();
+  unsigned nHiBits = longLen - shortLen;
+  APInt Zeros(longLen, 0), Ones(longLen, 0);
+
+  computeKnownBits(Op, Zeros, Ones, DL);
+
+  if (Ones.countLeadingZeros() < nHiBits) {
+    return VALRNG_LONG;
+  }
+
+  if (Zeros.countLeadingOnes() >= nHiBits) {
+    return VALRNG_SHORT;
+  }
+
+  return VALRNG_UNKNOWN;
+}
+
 // insertFastDiv - Substitutes the div/rem instruction with code that checks the
 // value of the operands and uses a shorter-faster div/rem instruction when
 // possible and the longer-slower div/rem instruction otherwise.
 static bool insertFastDiv(Instruction *I, IntegerType *BypassType,
                           bool UseDivOp, bool UseSignedOp,
                           DivCacheTy &PerBBDivCache) {
   Function *F = I->getParent()->getParent();
+  const DataLayout &DL = I->getModule()->getDataLayout();
+
   // Get instruction operands
   Value *Dividend = I->getOperand(0);
   Value *Divisor = I->getOperand(1);
 
   if (isa<ConstantInt>(Divisor)) {
-    // Division by a constant should have been been solved and replaced earlier
-    // in the pipeline.
+    // Keep division by a constant for DAGCombiner.
     return false;
   }
 
-  // If the numerator is a constant, bail if it doesn't fit into BypassType.
-  if (ConstantInt *ConstDividend = dyn_cast<ConstantInt>(Dividend))
-    if (ConstDividend->getValue().getActiveBits() > BypassType->getBitWidth())
-      return false;
+  ValRng DividendRng = getValueRange(Dividend, BypassType, DL);
+  if (DividendRng == VALRNG_LONG)
+    return false;
+
+  ValRng DivisorRng = getValueRange(Divisor, BypassType, DL);
+  if (DivisorRng == VALRNG_LONG)
 
+  bool DividendShort = (DividendRng == VALRNG_SHORT);
+  bool DivisorShort = (DivisorRng == VALRNG_SHORT);
+
+  // If both operands are known to be short then just replace the long division
+  // with a short one.
+  if (DividendShort && DivisorShort) {
+    IRBuilder<> Builder(I);
+    Value *trDividend = Builder.CreateTrunc(Dividend, BypassType);
+    Value *trDivisor = Builder.CreateTrunc(Divisor, BypassType);
+    Value *trResult = UseDivOp ? Builder.CreateUDiv(trDividend, trDivisor)
+                               : Builder.CreateURem(trDividend, trDivisor);
+    Value *Result = Builder.CreateZExt(trResult, I->getType());
+    I->replaceAllUsesWith(Result);
+    I->eraseFromParent();
+    return true;
+  }
+
   // Basic Block is split before divide
-  BasicBlock *MainBB = &*I->getParent();
+  BasicBlock *MainBB = I->getParent();
   BasicBlock *SuccessorBB = MainBB->splitBasicBlock(I);
+  Value *ZeroV = ConstantInt::get(I->getType(), 0);
 
-  // Add new basic block for slow divide operation
-  BasicBlock *SlowBB =
-      BasicBlock::Create(F->getContext(), "", MainBB->getParent(), SuccessorBB);
-  SlowBB->moveBefore(SuccessorBB);
+  // If the division is unsigned and Dividend is known to be short then either
+  // 1) Divisor is less or equal to Dividend and the result can be computed
+  //    with a short division.
+  // 2) Divisor is greater than Dividend. Then the (long) division is not
+  //    needed at all. In this case the quotient is 0 and the remainder is
+  //    equal to Dividend.
+  bool ShortCut = DividendShort && !UseSignedOp;
+
+  // New basic block for slow divide operation
+  BasicBlock *SlowBB = nullptr;
+  Value *SlowQuotientV = nullptr;
+  Value *SlowRemainderV = nullptr;
+
+  if (ShortCut) {
+    SlowQuotientV = ZeroV;
+    SlowRemainderV = Dividend;
+  } else {
+    SlowBB = BasicBlock::Create(F->getContext(), "", MainBB->getParent(),
+                                SuccessorBB);
     IRBuilder<> SlowBuilder(SlowBB, SlowBB->begin());
-  Value *SlowQuotientV;
-  Value *SlowRemainderV;
     if (UseSignedOp) {
       SlowQuotientV = SlowBuilder.CreateSDiv(Dividend, Divisor);
       SlowRemainderV = SlowBuilder.CreateSRem(Dividend, Divisor);
     } else {
       SlowQuotientV = SlowBuilder.CreateUDiv(Dividend, Divisor);
       SlowRemainderV = SlowBuilder.CreateURem(Dividend, Divisor);
     }
     SlowBuilder.CreateBr(SuccessorBB);
+  }
 
   // Add new basic block for fast divide operation
   BasicBlock *FastBB =
-      BasicBlock::Create(F->getContext(), "", MainBB->getParent(), SuccessorBB);
-  FastBB->moveBefore(SlowBB);
+      BasicBlock::Create(F->getContext(), "", MainBB->getParent(),
+                         ShortCut ? SuccessorBB : SlowBB);
   IRBuilder<> FastBuilder(FastBB, FastBB->begin());
   Value *ShortDivisorV = FastBuilder.CreateCast(Instruction::Trunc, Divisor,
                                                 BypassType);
   Value *ShortDividendV = FastBuilder.CreateCast(Instruction::Trunc, Dividend,
                                                  BypassType);
 
   // udiv/urem because optimization only handles positive numbers
   Value *ShortQuotientV = FastBuilder.CreateUDiv(ShortDividendV, ShortDivisorV);
   Value *ShortRemainderV = FastBuilder.CreateURem(ShortDividendV,
                                                   ShortDivisorV);
   Value *FastQuotientV = FastBuilder.CreateCast(Instruction::ZExt,
                                                 ShortQuotientV,
                                                 Dividend->getType());
   Value *FastRemainderV = FastBuilder.CreateCast(Instruction::ZExt,
                                                  ShortRemainderV,
                                                  Dividend->getType());
   FastBuilder.CreateBr(SuccessorBB);
 
   // Phi nodes for result of div and rem
   IRBuilder<> SuccessorBuilder(SuccessorBB, SuccessorBB->begin());
   PHINode *QuoPhi = SuccessorBuilder.CreatePHI(I->getType(), 2);
-  QuoPhi->addIncoming(SlowQuotientV, SlowBB);
+  QuoPhi->addIncoming(SlowQuotientV, ShortCut ? MainBB : SlowBB);
   QuoPhi->addIncoming(FastQuotientV, FastBB);
   PHINode *RemPhi = SuccessorBuilder.CreatePHI(I->getType(), 2);
-  RemPhi->addIncoming(SlowRemainderV, SlowBB);
+  RemPhi->addIncoming(SlowRemainderV, ShortCut ? MainBB : SlowBB);
   RemPhi->addIncoming(FastRemainderV, FastBB);
 
   // Replace I with appropriate phi node
   if (UseDivOp)
     I->replaceAllUsesWith(QuoPhi);
   else
     I->replaceAllUsesWith(RemPhi);
   I->eraseFromParent();
 
-  // Combine operands into a single value with OR for value testing below
   MainBB->getInstList().back().eraseFromParent();
   IRBuilder<> MainBuilder(MainBB, MainBB->end());
 
   // We should have bailed out above if the divisor is a constant, but the
   // dividend may still be a constant.  Set OrV to our non-constant operands
   // OR'ed together.
   assert(!isa<ConstantInt>(Divisor));
 
-  Value *OrV;
-  if (!isa<ConstantInt>(Dividend))
+  // If CmpV is true then do the short division.
+  Value *CmpV = nullptr;
+  if (ShortCut) {
+    CmpV = MainBuilder.CreateICmpUGE(Dividend, Divisor);
+  } else {
+    // Combine operands into a single value with OR for value testing below
+    Value *OrV = nullptr;
+    if (!DividendShort && !DivisorShort)
       OrV = MainBuilder.CreateOr(Dividend, Divisor);
+    else if (!DividendShort)
+      OrV = Dividend;
     else
       OrV = Divisor;
 
     // BitMask is inverted to check if the operands are
     // larger than the bypass type
     uint64_t BitMask = ~BypassType->getBitMask();
     Value *AndV = MainBuilder.CreateAnd(OrV, BitMask);
 
-  // Compare operand values and branch
-  Value *ZeroV = ConstantInt::getSigned(Dividend->getType(), 0);
-  Value *CmpV = MainBuilder.CreateICmpEQ(AndV, ZeroV);
-  MainBuilder.CreateCondBr(CmpV, FastBB, SlowBB);
+    // Compare operand values
+    CmpV = MainBuilder.CreateICmpEQ(AndV, ZeroV);
+  }
+
+  MainBuilder.CreateCondBr(CmpV, FastBB, ShortCut ? SuccessorBB : SlowBB);
 
   // Cache phi nodes to be used later in place of other instances
   // of div or rem with the same sign, dividend, and divisor
   DivOpInfo Key(UseSignedOp, Dividend, Divisor);
   DivPhiNodes Value(QuoPhi, RemPhi);
   PerBBDivCache.insert(std::pair<DivOpInfo, DivPhiNodes>(Key, Value));
   return true;
 }

test/CodeGen/X86/bypass-slow-division-64.ll

 ; CHECK-NEXT: retq
 ; CHECK-NOT: idivq
 ; CHECK-NOT: divw
   %resultdiv = sdiv i64 %a, %b
   %resultrem = srem i64 %a, %b
   %result = add i64 %resultdiv, %resultrem
   ret i64 %result
 }
+
+; No bypassing should be done in apparently unsuitable cases.
+define i64 @Test_no_bypassing(i32 %a, i64 %b) nounwind {
+; CHECK-LABEL: Test_no_bypassing:
+; CHECK-NOT: divl
+  %a.1 = zext i32 %a to i64
+  ; %a.2 is always negative so the division cannot be bypassed.
+  %a.2 = sub i64 -1, %a.1
+  %res = srem i64 %a.2, %b
+  ret i64 %res
+}
+
+; A simplified run-time check when divisor is known to be short.
+define i64 @Test_check_one_operand(i64 %a, i32 %b) nounwind {
+; CHECK-LABEL: Test_check_one_operand:
+; CHECK-NOT: orq
+; CHECK-DAG: divl
+; CHECK-DAG: idivq
+  %b.1 = zext i32 %b to i64
+  %res = sdiv i64 %a, %b.1
+  ret i64 %res
+}
+
+; A bit of a contrived test to replace a long division with a short one without
+; CFG modification.
+define i64 @Test_check_none(i64 %a, i32 %b) nounwind {
+; CHECK-LABEL: Test_check_none:
+; CHECK-NOT: j
+; CHECK-NOT: divq
+; CHECK:     divl
+; CHECK-NOT: div
+  %a.1 = and i64 %a, 4294967295
+  %b.1 = zext i32 %b to i64
+  %res = udiv i64 %a.1, %b.1
+  ret i64 %res
+}
+
+; Special case to completely get rid of an unsigned long division if the
+; dividend is known to be short enough.
+define i64 @Test_special_case(i32 %a, i64 %b) nounwind {
+; CHECK-LABEL: Test_special_case:
+; CHECK-NOT: shrq
+; CHECK-NOT: orq
+; CHECK:     cmpq
+; CHECK-NOT: divq
+; CHECK:     divl
+; CHECK-NOT: div
+  %a.1 = zext i32 %a to i64
+  %div = udiv i64 %a.1, %b
+  %rem = urem i64 %a.1, %b
+  %res = add i64 %div, %rem
+  ret i64 %res
+}