[DAGCombiner] After performing the division by constant optimization for a DIV or REM node, replace the users of the corresponding REM or DIV node if it exists.

[craig.topper]

Summary

Currently we expand the two nodes separately. This gives DAG combiner an opportunity to optimize the expanded sequence taking into account only one set of users. When we expand the other node we'll create the expansion again, but might not be able to optimize it the same way. So the nodes won't CSE and we'll have two similarish sequences in the same basic block. By expanding both nodes at the same time we'll avoid prematurely optimizing the expansion until both the division and remainder have been replaced.

Improves the test case from PR38217. There may be additional opportunities after this.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3437 ↗

(On Diff #179677)

Indentation is quite confusing here?

[craig.topper]

Fix bad indentation

[RKSimon]

LGTM - there might be a minor code cleanup opportunity to move more of this inside visitSDIVLike/visitUDIVLike as a future NFC.

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitSDIV(SDNode *N) {
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
   // If we know the sign bits of both operands are zero, strength reduce to a
   // udiv instead.  Handles (X&15) /s 4 -> X&15 >> 2
   if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0))
     return DAG.getNode(ISD::UDIV, DL, N1.getValueType(), N0, N1);
 
-  if (SDValue V = visitSDIVLike(N0, N1, N))
+  if (SDValue V = visitSDIVLike(N0, N1, N)) {
+    // If the corresponding remainder node exists, update its users with
+    // (Dividend - (Quotient * Divisor).
+    if (SDNode *RemNode = DAG.getNodeIfExists(ISD::SREM, N->getVTList(),
+                                              { N0, N1 })) {
+      SDValue Mul = DAG.getNode(ISD::MUL, DL, VT, V, N1);
+      SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0, Mul);
+      AddToWorklist(Mul.getNode());
+      AddToWorklist(Sub.getNode());
+      CombineTo(RemNode, Sub);
+    }
     return V;
+  }
 
   // sdiv, srem -> sdivrem
   // If the divisor is constant, then return DIVREM only if isIntDivCheap() is
   // true.  Otherwise, we break the simplification logic in visitREM().
   AttributeList Attr = DAG.getMachineFunction().getFunction().getAttributes();
   if (!N1C || TLI.isIntDivCheap(N->getValueType(0), Attr))
     if (SDValue DivRem = useDivRem(N))
         return DivRem;
return DAG.getSelect(DL, VT, DAG.getSetCC(DL, CCVT, N0, N1, ISD::SETEQ),
                          DAG.getConstant(0, DL, VT));
 
   if (SDValue V = simplifyDivRem(N, DAG))
     return V;
 
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
-  if (SDValue V = visitUDIVLike(N0, N1, N))
+  if (SDValue V = visitUDIVLike(N0, N1, N)) {
+    // If the corresponding remainder node exists, update its users with
+    // (Dividend - (Quotient * Divisor).
+    if (SDNode *RemNode = DAG.getNodeIfExists(ISD::UREM, N->getVTList(),
+                                              { N0, N1 })) {
+      SDValue Mul = DAG.getNode(ISD::MUL, DL, VT, V, N1);
+      SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0, Mul);
+      AddToWorklist(Mul.getNode());
+      AddToWorklist(Sub.getNode());
+      CombineTo(RemNode, Sub);
+    }
     return V;
+  }
 
   // sdiv, srem -> sdivrem
   // If the divisor is constant, then return DIVREM only if isIntDivCheap() is
   // true.  Otherwise, we break the simplification logic in visitREM().
   AttributeList Attr = DAG.getMachineFunction().getFunction().getAttributes();
   if (!N1C || TLI.isIntDivCheap(N->getValueType(0), Attr))
     if (SDValue DivRem = useDivRem(N))
         return DivRem;
SDValue DAGCombiner::visitREM(SDNode *N) {
   // speculative DIV must not cause a DIVREM conversion.  We guard against this
   // by skipping the simplification if isIntDivCheap().  When div is not cheap,
   // combine will not return a DIVREM.  Regardless, checking cheapness here
   // makes sense since the simplification results in fatter code.
   if (DAG.isKnownNeverZero(N1) && !TLI.isIntDivCheap(VT, Attr)) {
     SDValue OptimizedDiv =
         isSigned ? visitSDIVLike(N0, N1, N) : visitUDIVLike(N0, N1, N);
     if (OptimizedDiv.getNode()) {
+      // If the equivalent Div node also exists, update its users.
+      unsigned DivOpcode = isSigned ? ISD::SDIV : ISD::UDIV;
+      if (SDNode *DivNode = DAG.getNodeIfExists(DivOpcode, N->getVTList(),
+                                                { N0, N1 }))
+        CombineTo(DivNode, OptimizedDiv);
       SDValue Mul = DAG.getNode(ISD::MUL, DL, VT, OptimizedDiv, N1);
       SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0, Mul);
       AddToWorklist(OptimizedDiv.getNode());
       AddToWorklist(Mul.getNode());
       return Sub;
     }
   }
 

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

 ; X32-NEXT:    popl %ebp
 ; X32-NEXT:    retl
 ;
 ; 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, %rax
 ; 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:    sarq $28, %rax
+; X64-NEXT:    addq %rcx, %rax
+; X64-NEXT:    imull $-294967296, %eax, %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
 }

llvm/trunk/test/CodeGen/X86/pr38217.ll

 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_2: # =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    movq %r9, %rax
 ; CHECK-NEXT:    mulq %r8
 ; CHECK-NEXT:    shrq $11, %rdx
 ; CHECK-NEXT:    imulq $10000, %rdx, %rax # imm = 0x2710
 ; CHECK-NEXT:    movq %r9, %rdi
 ; CHECK-NEXT:    subq %rax, %rdi
-; CHECK-NEXT:    imulq $1374389535, %rdi, %rcx # imm = 0x51EB851F
-; CHECK-NEXT:    movq %rcx, %rax
+; CHECK-NEXT:    imulq $1374389535, %rdi, %rax # imm = 0x51EB851F
 ; CHECK-NEXT:    shrq $37, %rax
-; CHECK-NEXT:    imull $100, %eax, %eax
-; CHECK-NEXT:    subl %eax, %edi
-; CHECK-NEXT:    shrq $36, %rcx
-; CHECK-NEXT:    andl $510, %ecx # imm = 0x1FE
+; CHECK-NEXT:    imull $100, %eax, %ecx
+; CHECK-NEXT:    subl %ecx, %edi
 ; CHECK-NEXT:    movl %r10d, %r11d
-; CHECK-NEXT:    movq %rsi, %rax
-; CHECK-NEXT:    subq %r11, %rax
+; CHECK-NEXT:    movq %rsi, %rcx
+; CHECK-NEXT:    subq %r11, %rcx
 ; CHECK-NEXT:    movzwl _ZL11DIGIT_TABLE(%rdi,%rdi), %edi
-; CHECK-NEXT:    movw %di, -1(%rax)
-; CHECK-NEXT:    movzwl _ZL11DIGIT_TABLE(%rcx), %ecx
-; CHECK-NEXT:    movw %cx, -3(%rax)
+; CHECK-NEXT:    movw %di, -1(%rcx)
+; CHECK-NEXT:    movzwl _ZL11DIGIT_TABLE(%rax,%rax), %eax
+; CHECK-NEXT:    movw %ax, -3(%rcx)
 ; CHECK-NEXT:    addl $4, %r10d
 ; CHECK-NEXT:    cmpq $99999999, %r9 # imm = 0x5F5E0FF
 ; CHECK-NEXT:    movq %rdx, %r9
 ; CHECK-NEXT:    ja .LBB0_2
 ; CHECK-NEXT:  .LBB0_3:
 ; CHECK-NEXT:    retq
   %3 = icmp ugt i64 %0, 9999
   br i1 %3, label %4, label %31