[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
+}
+