[DAG] recognize div/rem by 0 as undef before trying constant folding

[spatel]

Summary

As discussed in the review thread for rL297026, this is actually 2 changes that would independently fix all of the test cases in the patch:

1. Return undef in FoldConstantArithmetic for div/rem by 0.
2. Move basic undef simplifications for div/rem (simplifyDivRem()) before foldBinopIntoSelect() as a matter of efficiency.

I can split it up, but I'm not sure yet how to expose the failures once either one of the fixes goes in.

I will handle the case of vectors with any zero element as a follow-up unless we want to do it all in one step. That change is the DAG sibling for D30665 + adding a check of vector elements to FoldConstantVectorArithmetic().

There are likely more improvements for undef handling needed for functions like isConstantSplatVector(), so I can also try to fix those too.

[spatel]

Patch updated:
Changing the definition of isConstantOrConstantVector() to include undef may have unintended consequences (there's a test in test/CodeGen/ARM/select.ll that will trigger the assert in foldBinOpIntoSelect()), so just assert that an undef result from DAG.getNode() is ok for now.

[spatel]

Patch updated:
I didn't notice that an extra x86 test (for https://bugs.llvm.org/show_bug.cgi?id=30693) was failing with this change because it has div-by-0.
I can't tell if that test is useful or not any more ( cc'ing @zvi ).

[efriedma]

I doubt pr30693.ll is still usefully testing anything with this patch... this is the problem with bugpoint-reduced tests. Needs to either be fixed or deleted.

Looks good otherwise.

[zvi]

I agree this test is no longer valuable. I'm fine with removing it.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (!isConstantOrConstantVector(CF, true) &&
     return SDValue();
 
   // We have a select-of-constants followed by a binary operator with a
   // constant. Eliminate the binop by pulling the constant math into the select.
   // Example: add (select Cond, CT, CF), C1 --> select Cond, CT + C1, CF + C1
   EVT VT = Sel.getValueType();
   SDLoc DL(Sel);
   SDValue NewCT = DAG.getNode(BinOpcode, DL, VT, CT, C1);
-  assert((isConstantOrConstantVector(NewCT) ||
+  assert((NewCT.isUndef() || isConstantOrConstantVector(NewCT) ||
           isConstantFPBuildVectorOrConstantFP(NewCT)) &&
          "Failed to constant fold a binop with constant operands");
 
   SDValue NewCF = DAG.getNode(BinOpcode, DL, VT, CF, C1);
-  assert((isConstantOrConstantVector(NewCF) ||
+  assert((NewCF.isUndef() || isConstantOrConstantVector(NewCF) ||
           isConstantFPBuildVectorOrConstantFP(NewCF)) &&
          "Failed to constant fold a binop with constant operands");
 
   return DAG.getSelect(DL, VT, Sel.getOperand(0), NewCT, NewCF);
 }
 
 SDValue DAGCombiner::visitADD(SDNode *N) {
   SDValue N0 = N->getOperand(0);
if (N0C && N1C && !N0C->isOpaque() && !N1C->isOpaque())
     return DAG.FoldConstantArithmetic(ISD::SDIV, DL, VT, N0C, N1C);
   // fold (sdiv X, 1) -> X
   if (N1C && N1C->isOne())
     return N0;
   // fold (sdiv X, -1) -> 0-X
   if (N1C && N1C->isAllOnesValue())
     return DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), N0);
 
+  if (SDValue V = simplifyDivRem(N, DAG))
+    return V;
+
   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);
 
SDValue DAGCombiner::visitSDIV(SDNode *N) {
 
   // sdiv, srem -> sdivrem
   // If the divisor is constant, then return DIVREM only if isIntDivCheap() is
   // true.  Otherwise, we break the simplification logic in visitREM().
   if (!N1C || TLI.isIntDivCheap(N->getValueType(0), Attr))
     if (SDValue DivRem = useDivRem(N))
         return DivRem;
 
-  if (SDValue V = simplifyDivRem(N, DAG))
-    return V;
-
   return SDValue();
 }
 
 SDValue DAGCombiner::visitUDIV(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N->getValueType(0);
 
   // fold vector ops
   if (VT.isVector())
     if (SDValue FoldedVOp = SimplifyVBinOp(N))
       return FoldedVOp;
 
   SDLoc DL(N);
 
   // fold (udiv c1, c2) -> c1/c2
   ConstantSDNode *N0C = isConstOrConstSplat(N0);
   ConstantSDNode *N1C = isConstOrConstSplat(N1);
   if (N0C && N1C)
     if (SDValue Folded = DAG.FoldConstantArithmetic(ISD::UDIV, DL, VT,
                                                     N0C, N1C))
       return Folded;
 
+  if (SDValue V = simplifyDivRem(N, DAG))
+    return V;
+
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
   // fold (udiv x, (1 << c)) -> x >>u c
   if (isConstantOrConstantVector(N1, /*NoOpaques*/ true) &&
       DAG.isKnownToBeAPowerOfTwo(N1)) {
     SDValue LogBase2 = BuildLogBase2(N1, DL);
     AddToWorklist(LogBase2.getNode());
SDValue DAGCombiner::visitUDIV(SDNode *N) {
 
   // sdiv, srem -> sdivrem
   // If the divisor is constant, then return DIVREM only if isIntDivCheap() is
   // true.  Otherwise, we break the simplification logic in visitREM().
   if (!N1C || TLI.isIntDivCheap(N->getValueType(0), Attr))
     if (SDValue DivRem = useDivRem(N))
         return DivRem;
 
-  if (SDValue V = simplifyDivRem(N, DAG))
-    return V;
-
   return SDValue();
 }
 
 // handles ISD::SREM and ISD::UREM
 SDValue DAGCombiner::visitREM(SDNode *N) {
   unsigned Opcode = N->getOpcode();
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N->getValueType(0);
   bool isSigned = (Opcode == ISD::SREM);
   SDLoc DL(N);
 
   // fold (rem c1, c2) -> c1%c2
   ConstantSDNode *N0C = isConstOrConstSplat(N0);
   ConstantSDNode *N1C = isConstOrConstSplat(N1);
   if (N0C && N1C)
     if (SDValue Folded = DAG.FoldConstantArithmetic(Opcode, DL, VT, N0C, N1C))
       return Folded;
 
+  if (SDValue V = simplifyDivRem(N, DAG))
+    return V;
+
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
   if (isSigned) {
     // If we know the sign bits of both operands are zero, strength reduce to a
     // urem instead.  Handles (X & 0x0FFFFFFF) %s 16 -> X&15
     if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0))
       return DAG.getNode(ISD::UREM, DL, VT, N0, N1);
if (OptimizedDiv.getNode() && OptimizedDiv.getNode() != Div.getNode()) {
       return Sub;
     }
   }
 
   // sdiv, srem -> sdivrem
   if (SDValue DivRem = useDivRem(N))
     return DivRem.getValue(1);
 
-  if (SDValue V = simplifyDivRem(N, DAG))
-    return V;
-
   return SDValue();
 }
 
 SDValue DAGCombiner::visitMULHS(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N->getValueType(0);
   SDLoc DL(N);

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 }
 
 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL,
                                              EVT VT, const ConstantSDNode *Cst1,
                                              const ConstantSDNode *Cst2) {
   if (Cst1->isOpaque() || Cst2->isOpaque())
     return SDValue();
 
+  // Division/remainder with a zero divisor is undefined behavior.
+  if ((Opcode == ISD::SDIV || Opcode == ISD::UDIV ||
+       Opcode == ISD::SREM || Opcode == ISD::UREM) &&
+      Cst2->isNullValue())
+    return getUNDEF(VT);
+
   std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
                                             Cst2->getAPIntValue());
   if (!Folded.second)
     return SDValue();
   return getConstant(Folded.first, DL, VT);
 }
 
 SDValue SelectionDAG::FoldSymbolOffset(unsigned Opcode, EVT VT,

test/CodeGen/X86/div-rem-simplify.ll

 define <4 x i32> @udiv_vec0(<4 x i32> %x) {
 ; CHECK-LABEL: udiv_vec0:
 ; CHECK:       # BB#0:
 ; CHECK-NEXT:    retq
   %div = udiv <4 x i32> %x, zeroinitializer
   ret <4 x i32> %div
 }
 
+; Make sure we handle undef before we try to fold constants from the select with the 0.
+; These used to assert because we can't fold div/rem-by-0 into APInt.
+
+define i32 @sel_urem0(i1 %cond) {
+; CHECK-LABEL: sel_urem0:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    retq
+  %sel = select i1 %cond, i32 23, i32 234
+  %rem = urem i32 %sel, 0
+  ret i32 %rem
+}
+
+define i32 @sel_srem0(i1 %cond) {
+; CHECK-LABEL: sel_srem0:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    retq
+  %sel = select i1 %cond, i32 23, i32 234
+  %rem = srem i32 %sel, 0
+  ret i32 %rem
+}
+
+define i32 @sel_udiv0(i1 %cond) {
+; CHECK-LABEL: sel_udiv0:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    retq
+  %sel = select i1 %cond, i32 23, i32 234
+  %div = udiv i32 %sel, 0
+  ret i32 %div
+}
+
+define i32 @sel_sdiv0(i1 %cond) {
+; CHECK-LABEL: sel_sdiv0:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    retq
+  %sel = select i1 %cond, i32 23, i32 234
+  %div = sdiv i32 %sel, 0
+  ret i32 %div
+}
+
+; Make sure we handle undef before we try to fold constants from the select with the vector 0.
+; These used to assert because we can't fold div/rem-by-0 into APInt.
+
+define <4 x i32> @sel_urem0_vec(i1 %cond) {
+; CHECK-LABEL: sel_urem0_vec:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    retq
+  %sel = select i1 %cond, <4 x i32> <i32 -1, i32 0, i32 1, i32 2>, <4 x i32> <i32 11, i32 12, i32 13, i32 14>
+  %rem = urem <4 x i32> %sel, zeroinitializer
+  ret <4 x i32> %rem
+}
+
+define <4 x i32> @sel_srem0_vec(i1 %cond) {
+; CHECK-LABEL: sel_srem0_vec:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    retq
+  %sel = select i1 %cond, <4 x i32> <i32 -1, i32 0, i32 1, i32 2>, <4 x i32> <i32 11, i32 12, i32 13, i32 14>
+  %rem = srem <4 x i32> %sel, zeroinitializer
+  ret <4 x i32> %rem
+}
+
+define <4 x i32> @sel_udiv0_vec(i1 %cond) {
+; CHECK-LABEL: sel_udiv0_vec:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    retq
+  %sel = select i1 %cond, <4 x i32> <i32 -1, i32 0, i32 1, i32 2>, <4 x i32> <i32 11, i32 12, i32 13, i32 14>
+  %div = udiv <4 x i32> %sel, zeroinitializer
+  ret <4 x i32> %div
+}
+
+define <4 x i32> @sel_sdiv0_vec(i1 %cond) {
+; CHECK-LABEL: sel_sdiv0_vec:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    retq
+  %sel = select i1 %cond, <4 x i32> <i32 -1, i32 0, i32 1, i32 2>, <4 x i32> <i32 11, i32 12, i32 13, i32 14>
+  %div = sdiv <4 x i32> %sel, zeroinitializer
+  ret <4 x i32> %div
+}
+

test/CodeGen/X86/pr30693.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; PR30693
 ; RUN: llc < %s -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 @var_35 = external local_unnamed_addr global i32, align 4
 @var_14 = external local_unnamed_addr global i16, align 2
 
 ; Function Attrs: uwtable
 define void @_Z3foov() local_unnamed_addr #0 {
 ; CHECK-LABEL: _Z3foov:
 ; CHECK:       # BB#0: # %entry
-; CHECK-NEXT:    movslq {{.*}}(%rip), %rax
-; CHECK-NEXT:    movzwl {{.*}}(%rip), %esi
-; CHECK-NEXT:    imull %eax, %esi
-; CHECK-NEXT:    xorl %edi, %edi
-; CHECK-NEXT:    vpxor %xmm0, %xmm0, %xmm0
-; CHECK-NEXT:    vxorps %ymm1, %ymm1, %ymm1
-; CHECK-NEXT:    jmp .LBB0_1
+; CHECK-NEXT:    vmovdqa {{.*#+}} ymm0 = [36611,36611,36611,36611,36611,36611,36611,36611,36611,36611,36611,36611,36611,36611,36611,36611]
+; CHECK-NEXT:    vxorps %xmm1, %xmm1, %xmm1
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    vxorps %ymm2, %ymm2, %ymm2
+; CHECK-NEXT:    vbroadcastss {{.*}}(%rip), %ymm3
+; CHECK-NEXT:    testq %rax, %rax
+; CHECK-NEXT:    je .LBB0_2
+; CHECK-NEXT:    jmp .LBB0_9
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_7: # %for.cond.cleanup477.loopexit
-; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    vpbroadcastd {{.*}}(%rip), %ymm2
-; CHECK-NEXT:    vmovdqu %ymm2, (%rax)
-; CHECK-NEXT:  .LBB0_1: # %vector.ph1520
+; CHECK-NEXT:    # in Loop: Header=BB0_2 Depth=1
+; CHECK-NEXT:    vmovups %ymm3, (%rax)
+; CHECK-NEXT:    testq %rax, %rax
+; CHECK-NEXT:    jne .LBB0_9
+; CHECK-NEXT:  .LBB0_2: # %vector.body1512.prol.loopexit
 ; CHECK-NEXT:    # =>This Loop Header: Depth=1
 ; CHECK-NEXT:    # Child Loop BB0_3 Depth 2
-; CHECK-NEXT:    xorl %eax, %eax
-; CHECK-NEXT:    xorl %edx, %edx
-; CHECK-NEXT:    idivl %edi
-; CHECK-NEXT:    movl %eax, %ecx
-; CHECK-NEXT:    xorl %eax, %eax
-; CHECK-NEXT:    xorl %edx, %edx
-; CHECK-NEXT:    idivq %rdi
-; CHECK-NEXT:    testq %rax, %rax
-; CHECK-NEXT:    jne .LBB0_8
-; CHECK-NEXT:  # BB#2: # %vector.body1512.prol.loopexit
-; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    vpbroadcastw %xmm0, %ymm2
-; CHECK-NEXT:    vpbroadcastw %xmm0, %xmm3
+; CHECK-NEXT:    vpbroadcastw %xmm0, %ymm4
+; CHECK-NEXT:    vpbroadcastw %xmm0, %xmm5
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_3: # %for.cond74.loopexit.us
-; CHECK-NEXT:    # Parent Loop BB0_1 Depth=1
+; CHECK-NEXT:    # Parent Loop BB0_2 Depth=1
 ; CHECK-NEXT:    # => This Inner Loop Header: Depth=2
-; CHECK-NEXT:    vmovdqu %xmm0, (%rax)
-; CHECK-NEXT:    testb %dil, %dil
+; CHECK-NEXT:    vmovups %xmm1, (%rax)
+; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB0_3
 ; CHECK-NEXT:  # BB#4: # %for.cond337.preheader.lr.ph
-; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    vmovups %ymm1, (%rax)
-; CHECK-NEXT:    vmovdqu %ymm2, (%rax)
-; CHECK-NEXT:    vmovdqu %xmm3, (%rax)
+; CHECK-NEXT:    # in Loop: Header=BB0_2 Depth=1
+; CHECK-NEXT:    vmovups %ymm2, (%rax)
+; CHECK-NEXT:    vmovdqu %ymm4, (%rax)
+; CHECK-NEXT:    vmovdqu %xmm5, (%rax)
 ; CHECK-NEXT:    testl %eax, %eax
 ; CHECK-NEXT:    jg .LBB0_9
 ; CHECK-NEXT:  # BB#5: # %for.cond385.preheader
-; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
+; CHECK-NEXT:    # in Loop: Header=BB0_2 Depth=1
 ; CHECK-NEXT:    testl %eax, %eax
-; CHECK-NEXT:    jle .LBB0_10
-; CHECK-NEXT:  # BB#6: # %for.cond399.preheader.lr.ph.us.1
-; CHECK-NEXT:    # in Loop: Header=BB0_1 Depth=1
+; CHECK-NEXT:    jle .LBB0_6
+; CHECK-NEXT:  # BB#8: # %for.cond399.preheader.lr.ph.us.1
+; CHECK-NEXT:    # in Loop: Header=BB0_2 Depth=1
 ; CHECK-NEXT:    testl %eax, %eax
 ; CHECK-NEXT:    jle .LBB0_7
-; CHECK-NEXT:  .LBB0_9: # %for.cond337.preheader.us.preheader
-; CHECK-NEXT:    vmovdqu %ymm0, (%rax)
-; CHECK-NEXT:    vmovdqu %ymm0, (%rax)
-; CHECK-NEXT:  .LBB0_8: # %vector.body1512.prol.preheader
-; CHECK-NEXT:    imull %ecx, %esi
-; CHECK-NEXT:    imull %eax, %esi
-; CHECK-NEXT:    imull %ecx, %esi
-; CHECK-NEXT:    imull %eax, %esi
-; CHECK-NEXT:    addl $36611, %esi # imm = 0x8F03
-; CHECK-NEXT:    vmovd %esi, %xmm0
-; CHECK-NEXT:    vpbroadcastw %xmm0, %ymm0
+; CHECK-NEXT:  .LBB0_9: # %vector.body1512.prol.preheader
 ; CHECK-NEXT:    vmovdqu %ymm0, (%rax)
 ; CHECK-NEXT:    vmovdqu %ymm0, (%rax)
-; CHECK-NEXT:  .LBB0_10: # %for.cond392.preheader.preheader
+; CHECK-NEXT:  .LBB0_6: # %for.cond392.preheader.preheader
 ; CHECK-NEXT:    vmovdqu %ymm0, (%rax)
 ; CHECK-NEXT:    vmovdqu %ymm0, (%rax)
 ; CHECK-NEXT:    vmovdqu %ymm0, (%rax)
 ; CHECK-NEXT:    vmovdqu %ymm0, (%rax)
 entry:
   %0 = load i32, i32* @var_35, align 4
   %1 = load i16, i16* @var_14, align 2
   %conv34 = zext i16 %1 to i64