[InstSimplify] vector div/rem with any zero element in divisor is undef

[spatel]

Summary

This was suggested as a DAG simplification in the review for rL297026 :
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20170306/435253.html
...but let's start with IR since we have actual docs for IR (LangRef).

[mkuper]

Would that mean that this transformation (very naive SLP vectorization) would become illegal:

%z1 = urem i8 %x1, %y1
%z2 = urem i8 %x2, %y2
ret i8 %z1

Into:

%vx1 = insertelement <2 x i8> undef, i8 %x1, i32 0
%vx2 = insertelement <2 x i8> %vx1, i8 %x2, i32 1
%vy1 = insertelement <2 x i8> undef, i8 %y1, i32 0
%vy2 = insertelement <2 x i8> %vy1, i8 %y2, i32 1
%vz = urem <2 x i8> %vx2, %vy2
%z = extractelement <2 x i8>%vz, i32 0
ret i8 %z

?

I'm not sure this is something we want.

[efriedma]

Would that mean that this transformation (very naive SLP vectorization) would become illegal:

Why would that be illegal? Both snippets have undefined behavior if and only if y1 or y2 is zero (or undef, or poison).

[mkuper]

In D30665#693613, @efriedma wrote:

Would that mean that this transformation (very naive SLP vectorization) would become illegal:

Why would that be illegal? Both snippets have undefined behavior if and only if y1 or y2 is zero (or undef, or poison).

Er, right, bad example. Let me think if I have a good one. What I'm aiming at is that I don't want to propagate undef from a lane that's never used into a lane that's actually used.

[efriedma]

The logic goes something like this: division by zero is undefined behavior, therefore the instruction is unreachable, therefore we can replace all uses with undef.

[spatel]

In D30665#693615, @mkuper wrote:

In D30665#693613, @efriedma wrote:

Would that mean that this transformation (very naive SLP vectorization) would become illegal:

Why would that be illegal? Both snippets have undefined behavior if and only if y1 or y2 is zero (or undef, or poison).

Er, right, bad example. Let me think if I have a good one. What I'm aiming at is that I don't want to propagate undef from a lane that's never used into a lane that's actually used.

I had the same concern. I was remembering something like this:
https://bugs.llvm.org/show_bug.cgi?id=20059
...but we solved that by limiting the transform with isSafeToSpeculativelyExecute(). That's what protects us from Bad Things with any div/rem. If there's some other transform that makes us use a value from a lane that shouldn't have been touched, then it must already be wrong?

[nlopes]

LGTM

llvm/trunk/docs/LangRef.rst

 Semantics:
 """"""""""
 
 The value produced is the unsigned integer quotient of the two operands.
 
 Note that unsigned integer division and signed integer division are
 distinct operations; for signed integer division, use '``sdiv``'.
 
-Division by zero leads to undefined behavior.
+Division by zero is undefined behavior. For vectors, if any element
+of the divisor is zero, the operation has undefined behavior.
+
 
 If the ``exact`` keyword is present, the result value of the ``udiv`` is
 a :ref:`poison value <poisonvalues>` if %op1 is not a multiple of %op2 (as
 such, "((a udiv exact b) mul b) == a").
 
 Example:
 """"""""
 

 """"""""""
 
 The value produced is the signed integer quotient of the two operands
 rounded towards zero.
 
 Note that signed integer division and unsigned integer division are
 distinct operations; for unsigned integer division, use '``udiv``'.
 
-Division by zero leads to undefined behavior. Overflow also leads to
-undefined behavior; this is a rare case, but can occur, for example, by
-doing a 32-bit division of -2147483648 by -1.
+Division by zero is undefined behavior. For vectors, if any element
+of the divisor is zero, the operation has undefined behavior.
+Overflow also leads to undefined behavior; this is a rare case, but can
+occur, for example, by doing a 32-bit division of -2147483648 by -1.
 
 If the ``exact`` keyword is present, the result value of the ``sdiv`` is
 a :ref:`poison value <poisonvalues>` if the result would be rounded.
 
 Example:
 """"""""
 
 .. code-block:: text

 """"""""""
 
 This instruction returns the unsigned integer *remainder* of a division.
 This instruction always performs an unsigned division to get the
 remainder.
 
 Note that unsigned integer remainder and signed integer remainder are
 distinct operations; for signed integer remainder, use '``srem``'.
  
-Taking the remainder of a division by zero leads to undefined behavior.
+Taking the remainder of a division by zero is undefined behavior.
+For vectors, if any element of the divisor is zero, the operation has 
+undefined behavior.
 
 Example:
 """"""""
 
 .. code-block:: text
 
       <result> = urem i32 4, %var          ; yields i32:result = 4 % %var
 

 Forum <http://mathforum.org/dr.math/problems/anne.4.28.99.html>`_. For a
 table of how this is implemented in various languages, please see
 `Wikipedia: modulo
 operation <http://en.wikipedia.org/wiki/Modulo_operation>`_.
 
 Note that signed integer remainder and unsigned integer remainder are
 distinct operations; for unsigned integer remainder, use '``urem``'.
 
-Taking the remainder of a division by zero leads to undefined behavior.
+Taking the remainder of a division by zero is undefined behavior.
+For vectors, if any element of the divisor is zero, the operation has 
+undefined behavior.
 Overflow also leads to undefined behavior; this is a rare case, but can
 occur, for example, by taking the remainder of a 32-bit division of
 -2147483648 by -1. (The remainder doesn't actually overflow, but this
 rule lets srem be implemented using instructions that return both the
 result of the division and the remainder.)
 
 Example:
 """"""""

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.
+  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())
+        return UndefValue::get(Ty);
+    }
+  }
+
   // undef / X -> 0
   // undef % X -> 0
   if (match(Op0, m_Undef()))
     return Constant::getNullValue(Ty);
 
   // 0 / X -> 0
   // 0 % X -> 0
   if (match(Op0, m_Zero()))

llvm/trunk/test/Transforms/InstCombine/vector-urem.ll

 ; CHECK-LABEL: @test_v4i32_const_pow2(
 ; CHECK-NEXT:    [[TMP1:%.*]] = urem <4 x i32> %a0, <i32 1, i32 2, i32 4, i32 8>
 ; CHECK-NEXT:    ret <4 x i32> [[TMP1]]
 ;
   %1 = urem <4 x i32> %a0, <i32 1, i32 2, i32 4, i32 8>
   ret <4 x i32> %1
 }
 
-define <4 x i32> @test_v4i32_const_pow2_or_zero(<4 x i32> %a0) {
-; CHECK-LABEL: @test_v4i32_const_pow2_or_zero(
-; CHECK-NEXT:    [[TMP1:%.*]] = urem <4 x i32> %a0, <i32 1, i32 2, i32 0, i32 8>
-; CHECK-NEXT:    ret <4 x i32> [[TMP1]]
-;
-  %1 = urem <4 x i32> %a0, <i32 1, i32 2, i32 0, i32 8>
-  ret <4 x i32> %1
-}

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

 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
-; FIXME: Division-by-zero is undef. UB in any vector lane means the whole op is undef.
+; Division-by-zero is undef. UB in any vector lane means the whole op is undef.
 
 define <2 x i8> @sdiv_zero_elt_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @sdiv_zero_elt_vec(
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv <2 x i8> %x, <i8 -42, i8 0>
-; CHECK-NEXT:    ret <2 x i8> [[DIV]]
+; CHECK-NEXT:    ret <2 x i8> undef
 ;
   %div = sdiv <2 x i8> %x, <i8 -42, i8 0>
   ret <2 x i8> %div
 }
 
 define <2 x i8> @udiv_zero_elt_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @udiv_zero_elt_vec(
-; CHECK-NEXT:    [[DIV:%.*]] = udiv <2 x i8> %x, <i8 0, i8 42>
-; CHECK-NEXT:    ret <2 x i8> [[DIV]]
+; CHECK-NEXT:    ret <2 x i8> undef
 ;
   %div = udiv <2 x i8> %x, <i8 0, i8 42>
   ret <2 x i8> %div
 }
 
 ; FIXME: 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.

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

 ; NOTE: Assertions have been autogenerated by update_test_checks.py
 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
-; FIXME: Division-by-zero is undef. UB in any vector lane means the whole op is undef.
+; Division-by-zero is undef. UB in any vector lane means the whole op is undef.
 
 define <2 x i8> @srem_zero_elt_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @srem_zero_elt_vec(
-; CHECK-NEXT:    [[REM:%.*]] = srem <2 x i8> %x, <i8 -42, i8 0>
-; CHECK-NEXT:    ret <2 x i8> [[REM]]
+; CHECK-NEXT:    ret <2 x i8> undef
 ;
   %rem = srem <2 x i8> %x, <i8 -42, i8 0>
   ret <2 x i8> %rem
 }
 
 define <2 x i8> @urem_zero_elt_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @urem_zero_elt_vec(
-; CHECK-NEXT:    [[REM:%.*]] = urem <2 x i8> %x, <i8 0, i8 42>
-; CHECK-NEXT:    ret <2 x i8> [[REM]]
+; CHECK-NEXT:    ret <2 x i8> undef
 ;
   %rem = urem <2 x i8> %x, <i8 0, i8 42>
   ret <2 x i8> %rem
 }
 
 ; FIXME: 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.