InstSimplify: If divisor element is undef simplify to undef

[zvi]

Summary

If any vector divisor element is undef, we can arbitrarily choose it be
zero which would make the div/rem an undef value by definition.

[spatel]

LGTM. Just curious - do we have vector intrinsics or any passes that create vector integer division?

[zvi]

In D42485#986599, @spatel wrote:

LGTM. Just curious - do we have vector intrinsics or any passes that create vector integer division?

There is ongoing work starting with D41944 to make divide more friendly to auto-vectorization (or other optimizations that may want to speculate division). Though this patch is not directly connected to it.

[spatel]

After discussing this with @RKSimon , I think this patch was wrong. Undef in a lane is not the same as undefined behavior in a lane.

So we're not allowed to assume the undef value is '0' here. This will cause trouble when paired with InstCombiner::SimplifyDemandedVectorElts().

Example:

define i8 @sdiv_undef_elt_vec(<4 x i8> %x) {
  %div = sdiv <4 x i8> %x, <i8 1, i8 2, i8 3, i8 4>
  %ext0 = extractelement <4 x i8> %div, i32 0
  %ext1 = extractelement <4 x i8> %div, i32 1
  %add = add i8 %ext0, %ext1
  ret i8 %add
}

Simplification based on demanded lanes could replace the last 2 constant divisor elements with 'undef'. This patch will then have the whole function produce undef. That can't be right.

[spatel]

We have the correct logic in 'isUndefShift()':

// If all lanes of a vector shift are undefined the whole shift is.

[efriedma]

udiv etc. have undefined behavior if any element of the divisor is undef. Even without optimizations, it could raise SIGFPE on x86. (See also D41944.)

Simplification based on demanded lanes could replace the last 2 constant divisor elements with 'undef'.

That shouldn't happen.

[spatel]

In D42485#1005795, @efriedma wrote:

udiv etc. have undefined behavior if any element of the divisor is undef. Even without optimizations, it could raise SIGFPE on x86. (See also D41944.)

Simplification based on demanded lanes could replace the last 2 constant divisor elements with 'undef'.

That shouldn't happen.

Ah - thanks! This reminds me of the bug from D4424. So IIUC, it is ok for SimplifyDemandedVectorElts() to replace constants in ops that can't trap (are safe to speculate). But just like it's not ok to do that shuffle transform for div/rem, we can't replace constants in div/rem.

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

if (match(Op1, m_Undef()))
     return Op1;
 
   // X / 0 -> undef
   // X % 0 -> undef
   // We don't need to preserve faults!
   if (match(Op1, m_Zero()))
     return UndefValue::get(Ty);
 
-  // If any element of a constant divisor vector is zero, the whole op is undef.
+  // If any element of a constant divisor vector is zero or undef, the whole op
+  // is undef.
   auto *Op1C = dyn_cast<Constant>(Op1);
   if (Op1C && Ty->isVectorTy()) {
     unsigned NumElts = Ty->getVectorNumElements();
     for (unsigned i = 0; i != NumElts; ++i) {
       Constant *Elt = Op1C->getAggregateElement(i);
-      if (Elt && Elt->isNullValue())
+      if (Elt && (Elt->isNullValue() || isa<UndefValue>(Elt)))
         return UndefValue::get(Ty);
     }
   }
 
   // undef / X -> 0
   // undef % X -> 0
   if (match(Op0, m_Undef()))
     return Constant::getNullValue(Ty);

llvm/trunk/test/Transforms/InstSimplify/div.ll

 define <2 x i8> @udiv_zero_elt_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @udiv_zero_elt_vec(
 ; CHECK-NEXT:    ret <2 x i8> undef
 ;
   %div = udiv <2 x i8> %x, <i8 0, i8 42>
   ret <2 x i8> %div
 }
 
+define <2 x i8> @sdiv_undef_elt_vec(<2 x i8> %x) {
+; CHECK-LABEL: @sdiv_undef_elt_vec(
+; CHECK-NEXT:    ret <2 x i8> undef
+;
+  %div = sdiv <2 x i8> %x, <i8 -42, i8 undef>
+  ret <2 x i8> %div
+}
+
+define <2 x i8> @udiv_undef_elt_vec(<2 x i8> %x) {
+; CHECK-LABEL: @udiv_undef_elt_vec(
+; CHECK-NEXT:    ret <2 x i8> undef
+;
+  %div = udiv <2 x i8> %x, <i8 undef, i8 42>
+  ret <2 x i8> %div
+}
+
 ; Division-by-zero is undef. UB in any vector lane means the whole op is undef.
 ; Thus, we can simplify this: if any element of 'y' is 0, we can do anything.
 ; Therefore, assume that all elements of 'y' must be 1.
 
 define <2 x i1> @sdiv_bool_vec(<2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @sdiv_bool_vec(
 ; CHECK-NEXT:    ret <2 x i1> %x
 ;

llvm/trunk/test/Transforms/InstSimplify/rem.ll

 define <2 x i8> @urem_zero_elt_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @urem_zero_elt_vec(
 ; CHECK-NEXT:    ret <2 x i8> undef
 ;
   %rem = urem <2 x i8> %x, <i8 0, i8 42>
   ret <2 x i8> %rem
 }
 
+define <2 x i8> @srem_undef_elt_vec(<2 x i8> %x) {
+; CHECK-LABEL: @srem_undef_elt_vec(
+; CHECK-NEXT:    ret <2 x i8> undef
+;
+  %rem = srem <2 x i8> %x, <i8 -42, i8 undef>
+  ret <2 x i8> %rem
+}
+
+define <2 x i8> @urem_undef_elt_vec(<2 x i8> %x) {
+; CHECK-LABEL: @urem_undef_elt_vec(
+; CHECK-NEXT:    ret <2 x i8> undef
+;
+  %rem = urem <2 x i8> %x, <i8 undef, i8 42>
+  ret <2 x i8> %rem
+}
+
 ; Division-by-zero is undef. UB in any vector lane means the whole op is undef.
 ; Thus, we can simplify this: if any element of 'y' is 0, we can do anything.
 ; Therefore, assume that all elements of 'y' must be 1.
 
 define <2 x i1> @srem_bool_vec(<2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @srem_bool_vec(
 ; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;