[BypassSlowDivision] Teach bypass slow division not to interfere with div by constant where constants have been constant hoisted, but not moved from their basic block

[craig.topper]

Summary

DAGCombiner doesn't pay attention to whether constants are opaque before doing the div by constant optimization. So BypassSlowDivision shouldn't introduce control flow that would make DAGCombiner unable to see an opaque constant. This can occur when a div and rem of the same constant are used in the same basic block. it will be hoisted, but not leave the block.

Longer term we probably need to look into the X86 immediate cost model used by constant hoisting and maybe not mark div/rem immediates for hoisting at all.

This fixes the case from PR38649.

[spatel]

lib/Transforms/Utils/BypassSlowDivision.cpp

200–203

Similar check - can we handle div opcodes here?
There's an IR version of peekThroughBitcast() in InstCombineInternal.h. Lift that to a higher header, so we can use it here too?

[craig.topper]

lib/Transforms/Utils/BypassSlowDivision.cpp

200–203

This code is specifically looking for a code sequence that you might find in a hash function. I don't think we want to check for div here. And it wouldn't help with the problem since this is called on the inputs to the div/rem.

In my case, I need to know the bitcast is there because I need to check the parent so peekthroughbitcast isn't useful.

[spatel]

lib/Transforms/Utils/BypassSlowDivision.cpp

395–397

Use dyn_cast to reduce code:

if (auto *BitCast = dyn_cast<BitCastInst>(Divisor))
  if (BitCast->getParent() == SlowDivOrRem->getParent() &&
      isa<ConstantInt>(BitCast->getOperand(0)))
    return None;

[craig.topper]

Use dyn_cast

[spatel]

LGTM

lib/Transforms/Utils/BypassSlowDivision.cpp

bool FastDivInsertionTask::isHashLikeValue(Value *V, VisitedSetTy &Visited) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I)
     return false;
 
   switch (I->getOpcode()) {
   case Instruction::Xor:
     return true;
   case Instruction::Mul: {
     // After Constant Hoisting pass, long constants may be represented as
     // bitcast instructions. As a result, some constants may look like an
     // instruction at first, and an additional check is necessary to find out if
     // an operand is actually a constant.
     Value *Op1 = I->getOperand(1);
     ConstantInt *C = dyn_cast<ConstantInt>(Op1);
     if (!C && isa<BitCastInst>(Op1))
       C = dyn_cast<ConstantInt>(cast<BitCastInst>(Op1)->getOperand(0));
     return C && C->getValue().getMinSignedBits() > BypassType->getBitWidth();
   }
   case Instruction::PHI:
     // Stop IR traversal in case of a crazy input code. This limits recursion
Optional<QuotRemPair> FastDivInsertionTask::insertFastDivAndRem() {
 
   if (isa<ConstantInt>(Divisor)) {
     // If the divisor is not a constant, DAGCombiner will convert it to a
     // multiplication by a magic constant.  It isn't clear if it is worth
     // introducing control flow to get a narrower multiply.
     return None;
   }
 
+  // After Constant Hoisting pass, long constants may be represented as
+  // bitcast instructions. As a result, some constants may look like an
+  // instruction at first, and an additional check is necessary to find out if
+  // an operand is actually a constant.
+  if (isa<BitCastInst>(Divisor) &&
+      cast<BitCastInst>(Divisor)->getParent() == SlowDivOrRem->getParent() &&
+      isa<ConstantInt>(cast<BitCastInst>(Divisor)->getOperand(0))) {
+    return None;
+  }
+
   if (DividendShort && !isSignedOp()) {
     // 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. In this case, no division is needed
     //    at all: The quotient is 0 and the remainder is equal to Dividend.
     //

test/CodeGen/X86/divide-by-constant.ll

 ; X32-NEXT:    movl %edi, %edx
 ; X32-NEXT:    addl $12, %esp
 ; X32-NEXT:    popl %esi
 ; X32-NEXT:    popl %edi
 ; X32-NEXT:    popl %ebx
 ; X32-NEXT:    popl %ebp
 ; X32-NEXT:    retl
 ;
-; X64-FAST-LABEL: PR38622:
-; X64-FAST:       # %bb.0:
-; X64-FAST-NEXT:    movq %rdi, %rax
-; X64-FAST-NEXT:    shrq $11, %rax
-; X64-FAST-NEXT:    movabsq $4835703278458517, %rcx # imm = 0x112E0BE826D695
-; X64-FAST-NEXT:    mulq %rcx
-; X64-FAST-NEXT:    shrq $9, %rdx
-; X64-FAST-NEXT:    imull $-294967296, %edx, %eax # imm = 0xEE6B2800
-; X64-FAST-NEXT:    subl %eax, %edi
-; X64-FAST-NEXT:    movq %rdx, %rax
-; X64-FAST-NEXT:    movl %edi, %edx
-; X64-FAST-NEXT:    retq
-;
-; X64-SLOW-LABEL: PR38622:
-; X64-SLOW:       # %bb.0:
-; X64-SLOW-NEXT:    movl $4000000000, %ecx # imm = 0xEE6B2800
-; X64-SLOW-NEXT:    movq %rdi, %rax
-; X64-SLOW-NEXT:    shrq $32, %rax
-; X64-SLOW-NEXT:    je .LBB14_1
-; X64-SLOW-NEXT:  # %bb.2:
-; X64-SLOW-NEXT:    xorl %edx, %edx
-; X64-SLOW-NEXT:    movq %rdi, %rax
-; X64-SLOW-NEXT:    divq %rcx
-; X64-SLOW-NEXT:    # kill: def $edx killed $edx killed $rdx
-; X64-SLOW-NEXT:    retq
-; X64-SLOW-NEXT:  .LBB14_1:
-; X64-SLOW-NEXT:    xorl %edx, %edx
-; X64-SLOW-NEXT:    movl %edi, %eax
-; X64-SLOW-NEXT:    divl %ecx
-; X64-SLOW-NEXT:    # kill: def $edx killed $edx def $rdx
-; X64-SLOW-NEXT:    # kill: def $eax killed $eax def $rax
-; X64-SLOW-NEXT:    # kill: def $edx killed $edx killed $rdx
-; X64-SLOW-NEXT:    retq
+; X64-LABEL: PR38622:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    shrq $11, %rax
+; X64-NEXT:    movabsq $4835703278458517, %rcx # imm = 0x112E0BE826D695
+; X64-NEXT:    mulq %rcx
+; X64-NEXT:    shrq $9, %rdx
+; X64-NEXT:    imull $-294967296, %edx, %eax # imm = 0xEE6B2800
+; X64-NEXT:    subl %eax, %edi
+; X64-NEXT:    movq %rdx, %rax
+; X64-NEXT:    movl %edi, %edx
+; X64-NEXT:    retq
   %2 = udiv i64 %0, 4000000000
   %3 = urem i64 %0, 4000000000
   %4 = trunc i64 %3 to i32
   %5 = insertvalue { i64, i32 } undef, i64 %2, 0
   %6 = insertvalue { i64, i32 } %5, i32 %4, 1
   ret { i64, i32 } %6
 }
 

 ; X32-NEXT:    movl %edi, %edx
 ; X32-NEXT:    addl $12, %esp
 ; X32-NEXT:    popl %esi
 ; X32-NEXT:    popl %edi
 ; X32-NEXT:    popl %ebx
 ; X32-NEXT:    popl %ebp
 ; X32-NEXT:    retl
 ;
-; X64-FAST-LABEL: PR38622_signed:
-; X64-FAST:       # %bb.0:
-; X64-FAST-NEXT:    movabsq $1237940039285380275, %rcx # imm = 0x112E0BE826D694B3
-; X64-FAST-NEXT:    movq %rdi, %rax
-; X64-FAST-NEXT:    imulq %rcx
-; X64-FAST-NEXT:    movq %rdx, %rcx
-; X64-FAST-NEXT:    shrq $63, %rcx
-; X64-FAST-NEXT:    sarq $28, %rdx
-; X64-FAST-NEXT:    leaq (%rdx,%rcx), %rax
-; X64-FAST-NEXT:    addl %ecx, %edx
-; X64-FAST-NEXT:    imull $-294967296, %edx, %ecx # imm = 0xEE6B2800
-; X64-FAST-NEXT:    subl %ecx, %edi
-; X64-FAST-NEXT:    movl %edi, %edx
-; X64-FAST-NEXT:    retq
-;
-; X64-SLOW-LABEL: PR38622_signed:
-; X64-SLOW:       # %bb.0:
-; X64-SLOW-NEXT:    movl $4000000000, %ecx # imm = 0xEE6B2800
-; X64-SLOW-NEXT:    movq %rdi, %rax
-; X64-SLOW-NEXT:    shrq $32, %rax
-; X64-SLOW-NEXT:    je .LBB15_1
-; X64-SLOW-NEXT:  # %bb.2:
-; X64-SLOW-NEXT:    movq %rdi, %rax
-; X64-SLOW-NEXT:    cqto
-; X64-SLOW-NEXT:    idivq %rcx
-; X64-SLOW-NEXT:    # kill: def $edx killed $edx killed $rdx
-; X64-SLOW-NEXT:    retq
-; X64-SLOW-NEXT:  .LBB15_1:
-; X64-SLOW-NEXT:    xorl %edx, %edx
-; X64-SLOW-NEXT:    movl %edi, %eax
-; X64-SLOW-NEXT:    divl %ecx
-; X64-SLOW-NEXT:    # kill: def $edx killed $edx def $rdx
-; X64-SLOW-NEXT:    # kill: def $eax killed $eax def $rax
-; X64-SLOW-NEXT:    # kill: def $edx killed $edx killed $rdx
-; X64-SLOW-NEXT:    retq
+; X64-LABEL: PR38622_signed:
+; X64:       # %bb.0:
+; X64-NEXT:    movabsq $1237940039285380275, %rcx # imm = 0x112E0BE826D694B3
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    imulq %rcx
+; X64-NEXT:    movq %rdx, %rcx
+; X64-NEXT:    shrq $63, %rcx
+; X64-NEXT:    sarq $28, %rdx
+; X64-NEXT:    leaq (%rdx,%rcx), %rax
+; X64-NEXT:    addl %ecx, %edx
+; X64-NEXT:    imull $-294967296, %edx, %ecx # imm = 0xEE6B2800
+; X64-NEXT:    subl %ecx, %edi
+; X64-NEXT:    movl %edi, %edx
+; X64-NEXT:    retq
   %2 = sdiv i64 %0, 4000000000
   %3 = srem i64 %0, 4000000000
   %4 = trunc i64 %3 to i32
   %5 = insertvalue { i64, i32 } undef, i64 %2, 0
   %6 = insertvalue { i64, i32 } %5, i32 %4, 1
   ret { i64, i32 } %6
 }