[ConstantFold] Handle undef/poison when constant folding smul_fix/smul_fix_sat

[bjope]

Summary

Do constant folding according to

posion * C -> poison
C * poison -> poison
undef * C -> 0
C * undef -> 0

for smul_fix and smul_fix_sat intrinsics (for any scale).

[bjope]

llvm/lib/Analysis/ConstantFolding.cpp

2808

Just a side note not really related to this patch; I suspect that we perhaps could use APFixedPoint here, somehow, in the future.

[nagisa]

Wouldn't folding C * undef and undef * C into an undef, rather than 0, be valid/better? Is there a reason we cannot do that?

[bjope]

In D98410#2619250, @nagisa wrote:

Wouldn't folding C * undef and undef * C into an undef, rather than 0, be valid/better? Is there a reason we cannot do that?

I figure that it would be wrong if for example C is zero, because then the result can't take any other value than zero. Or if C is 2 and scale is 0, then the result can't be odd. So undef include values that isn't possible for every combination of the other operands.

The poison propagation is a bit more new for me. I hope I got that part correct.

[nikic]

LGTM

[aqjune]

In D98410#2619315, @bjope wrote:

In D98410#2619250, @nagisa wrote:

Wouldn't folding C * undef and undef * C into an undef, rather than 0, be valid/better? Is there a reason we cannot do that?

I figure that it would be wrong if for example C is zero, because then the result can't take any other value than zero. Or if C is 2 and scale is 0, then the result can't be odd. So undef include values that isn't possible for every combination of the other operands.

The poison propagation is a bit more new for me. I hope I got that part correct.

Yep, this is right.

llvm/test/Transforms/InstSimplify/ConstProp/smul-fix.ll

148

I found from LangRef that actually this can be optimized further:

It is undefined behavior if the result value does not fit within the range of the fixed point type.

The result of the third element, llvm.smul.fix.v8i3(2, poison, 2), raises UB because poison can be folded into a large number which explicitly leads to UB.
Then, output elements not only 3rd/4th but also others are okay to be folded to poison.

udiv <x, x>, <0, 1> is also returning <undef, undef> in the same context currently.

Would this optimization be necessary though?

[nagisa]

In D98410#2619315, @bjope wrote:

So undef include values that isn't possible for every combination of the other operands.

Aha, I see! This is an interesting reasoning. I think it is fine to do what you're doing for the sake of simplicity, what follows under the horizontal line below is a bunch of my rambling (feel free to ignore all of it)

---

Taking a regular mul instruction as an example

mul i32 1, undef  # => undef
mul i32 2, undef  # => 0
mul i32 3, undef  # => undef

These make sense to me, though require some roundabout reasoning. 1 * undef = undef is trivial. 2 * undef follows the same reasoning as yours in that there's no bit-pattern undef can take that would result in 0 bit set here. That same reasoning could apply for 3 * undef too – but it does not because of wrap-around (I think).

And this is where the following snippet from the smul.fix definition comes in:

It is undefined behavior if the result value does not fit within the range of the fixed point type.

Basically, unless the intrinsic is multiplying undef by 1 or by 0, I believe there's an implicit invocation of UB. That's because there exist bit patterns of an undef operand that multiplied by other values would cause the resulting value to not fit within the fixed point type's range (right?). Whether we manifest this UB as undef or 0 probably doesn't matter too much, but I think either option would be valid.

[bjope]

In D98410#2619538, @nagisa wrote:

In D98410#2619315, @bjope wrote:

So undef include values that isn't possible for every combination of the other operands.

Aha, I see! This is an interesting reasoning. I think it is fine to do what you're doing for the sake of simplicity, what follows under the horizontal line below is a bunch of my rambling (feel free to ignore all of it)

---

Taking a regular mul instruction as an example

mul i32 1, undef  # => undef
mul i32 2, undef  # => 0
mul i32 3, undef  # => undef

These make sense to me, though require some roundabout reasoning. 1 * undef = undef is trivial. 2 * undef follows the same reasoning as yours in that there's bit-pattern undef can take that would result in lower bit set here. That same reasoning could apply for 3 * undef too – but it does not because of wrap-around (I think).

And this is where the following snippet from the smul.fix definition comes in:

It is undefined behavior if the result value does not fit within the range of the fixed point type.

Basically, unless the intrinsic is multiplying undef by 1 or by 0, I believe there's an implicit invocation of UB. That's because there exist bit patterns of an undef operand that multiplied by other values would cause the resulting value to not fit within the fixed point type's range (right?). Whether we manifest this UB as undef or 0 probably doesn't matter too much, but I think either option would be valid.

It depends a bit on the scale. If you for example multiply by 0.5 then you won't get any overflow. On the other hand, smul.fix with scale=0 is pretty much like a regular mul but not sure we need to make a special case for that.

[aqjune]

llvm/test/Transforms/InstSimplify/ConstProp/smul-fix.ll

148

The result of the third element, llvm.smul.fix.v8i3(2, poison, 2), raises UB because poison can be folded into a large number which explicitly leads to UB.

Nevermind, I forgot the scale thing.
The first argument is actually 0.5 and the second one is, well, poison / 4, so it is UB if "0.5 * (poison / 4)" can overflow. Is my understanding right?
Then, I think it is uncertain whether this is UB or not.

[bjope]

llvm/test/Transforms/InstSimplify/ConstProp/smul-fix.ll

148

Yes, the example llvm.smul.fix.i3(2, poison, 2) is multiplying poison/4 by 0.5. That should not raise poison itself (you can't get overflow when multiplying by 0.5). Although, I've assumed that poison should be propagated here as we multiply be something that is poison.

But you are right that there could be situations when we could detect overflow in constant folding of smul.fix, and thereby introducing poison. For example if having (smul.fix.i4 -8, -8, 3) , which means that we multiply -1 by -1. The result would be out of range for a 4-bit fixed point value with scale 3 (the largest representable number would be 1/2+1/4+1/8). That has not been consideredi n this patch (focus was to deal with undef/poison already being present in the inputs).
As I wrote at line 2808, it might be possible to use APFixedPoint to calculate the result in the future. And I think that API can return a bool indicating if there was overflow. So that could make it pretty simple to deduce if overflow happened or not.

[aqjune]

llvm/test/Transforms/InstSimplify/ConstProp/smul-fix.ll

148

Thank you for the example!

Yes, the example llvm.smul.fix.i3(2, poison, 2) is multiplying poison/4 by 0.5. That should not raise poison itself (you can't get overflow when multiplying by 0.5). Although, I've assumed that poison should be propagated here as we multiply be something that is poison.

Would it be great if this is clarified in LangRef as well? Maybe I can simply add 'if any of the operands is poison, the result is poison' there.

[bjope]

llvm/test/Transforms/InstSimplify/ConstProp/smul-fix.ll

148

Thank you for the example!

Yes, the example llvm.smul.fix.i3(2, poison, 2) is multiplying poison/4 by 0.5. That should not raise poison itself (you can't get overflow when multiplying by 0.5). Although, I've assumed that poison should be propagated here as we multiply be something that is poison.

Would it be great if this is clarified in LangRef as well? Maybe I can simply add 'if any of the operands is poison, the result is poison' there.

Isn't this basically described here already https://llvm.org/docs/LangRef.html#poison-values ; "An instruction that depends on a poison value, produces a poison value itself".
So there is nothing special with smul.fix.* compared to other instructions such as add/mul/xor etc.

llvm/lib/Analysis/ConstantFolding.cpp

if (const auto *Op2 = dyn_cast<ConstantFP>(Operands[1])) {
               Op3->getValueAPF());
           return ConstantFP::get(Ty->getContext(), V);
         }
         }
       }
     }
   }
 
-  if (const auto *Op1 = dyn_cast<ConstantInt>(Operands[0])) {
-    if (const auto *Op2 = dyn_cast<ConstantInt>(Operands[1])) {
-      if (const auto *Op3 = dyn_cast<ConstantInt>(Operands[2])) {
-        switch (IntrinsicID) {
-        default: break;
-        case Intrinsic::smul_fix:
-        case Intrinsic::smul_fix_sat: {
-          // This code performs rounding towards negative infinity in case the
-          // result cannot be represented exactly for the given scale. Targets
-          // that do care about rounding should use a target hook for specifying
-          // how rounding should be done, and provide their own folding to be
-          // consistent with rounding. This is the same approach as used by
-          // DAGTypeLegalizer::ExpandIntRes_MULFIX.
-          const APInt &Lhs = Op1->getValue();
-          const APInt &Rhs = Op2->getValue();
-          unsigned Scale = Op3->getValue().getZExtValue();
-          unsigned Width = Lhs.getBitWidth();
-          assert(Scale < Width && "Illegal scale.");
-          unsigned ExtendedWidth = Width * 2;
-          APInt Product = (Lhs.sextOrSelf(ExtendedWidth) *
-                           Rhs.sextOrSelf(ExtendedWidth)).ashr(Scale);
-          if (IntrinsicID == Intrinsic::smul_fix_sat) {
-            APInt MaxValue =
-              APInt::getSignedMaxValue(Width).sextOrSelf(ExtendedWidth);
-            APInt MinValue =
-              APInt::getSignedMinValue(Width).sextOrSelf(ExtendedWidth);
-            Product = APIntOps::smin(Product, MaxValue);
-            Product = APIntOps::smax(Product, MinValue);
-          }
-          return ConstantInt::get(Ty->getContext(),
-                                  Product.sextOrTrunc(Width));
-        }
-        }
-      }
+  if (IntrinsicID == Intrinsic::smul_fix ||
+      IntrinsicID == Intrinsic::smul_fix_sat) {
+    // poison * C -> poison
+    // C * poison -> poison
+    if (isa<PoisonValue>(Operands[0]) || isa<PoisonValue>(Operands[1]))
+      return PoisonValue::get(Ty);
+
+    const APInt *C0, *C1;
+    if (!getConstIntOrUndef(Operands[0], C0) ||
+        !getConstIntOrUndef(Operands[1], C1))
+      return nullptr;
+
+    // undef * C -> 0
+    // C * undef -> 0
+    if (!C0 || !C1)
+      return Constant::getNullValue(Ty);
+
+    // This code performs rounding towards negative infinity in case the result
+    // cannot be represented exactly for the given scale. Targets that do care
+    // about rounding should use a target hook for specifying how rounding
+    // should be done, and provide their own folding to be consistent with
+    // rounding. This is the same approach as used by
+    unsigned Scale = cast<ConstantInt>(Operands[2])->getZExtValue();
+    unsigned Width = C0->getBitWidth();
+    APInt Product = (C0->sextOrSelf(ExtendedWidth) *
+                     C1->sextOrSelf(ExtendedWidth)).ashr(Scale);
+      APInt Max = APInt::getSignedMaxValue(Width).sextOrSelf(ExtendedWidth);
+      APInt Min = APInt::getSignedMinValue(Width).sextOrSelf(ExtendedWidth);
+      Product = APIntOps::smin(Product, Max);
+      Product = APIntOps::smax(Product, Min);
     }
+    return ConstantInt::get(Ty->getContext(), Product.sextOrTrunc(Width));
   }
 
   if (IntrinsicID == Intrinsic::fshl || IntrinsicID == Intrinsic::fshr) {
     const APInt *C0, *C1, *C2;
     if (!getConstIntOrUndef(Operands[0], C0) ||
         !getConstIntOrUndef(Operands[1], C1) ||
         !getConstIntOrUndef(Operands[2], C2))
       return nullptr;

llvm/test/Transforms/InstSimplify/ConstProp/smul-fix-sat.ll

 define i32 @test_smul_fix_sat_i32_0() {
 ; CHECK-LABEL: @test_smul_fix_sat_i32_0(
 ; CHECK-NEXT:    ret i32 536870912
 ;
   %r = call i32 @llvm.smul.fix.sat.i32(i32 1073741824, i32 1073741824, i32 31) ; 0.5 * 0.5
   ret i32 %r
 }
 
+define i32 @test_smul_fix_sat_i32_undef_x() {
+; CHECK-LABEL: @test_smul_fix_sat_i32_undef_x(
+; CHECK-NEXT:    ret i32 0
+;
+  %r = call i32 @llvm.smul.fix.sat.i32(i32 undef, i32 1073741824, i32 31)
+  ret i32 %r
+}
+
+define i32 @test_smul_fix_sat_i32_x_undef() {
+; CHECK-LABEL: @test_smul_fix_sat_i32_x_undef(
+; CHECK-NEXT:    ret i32 0
+;
+  %r = call i32 @llvm.smul.fix.sat.i32(i32 17, i32 undef, i32 31)
+  ret i32 %r
+}
+
 ;-----------------------------------------------------------------------------
 ; More extensive tests based on vectors (basically using the scalar fold
 ; for each index).
 ;-----------------------------------------------------------------------------
 
 declare <8 x i3> @llvm.smul.fix.sat.v8i3(<8 x i3>, <8 x i3>, i32)
 
 define <8 x i3> @test_smul_fix_sat_v8i3_0() {

 ; CHECK-NEXT:    ret <8 x i3> <i3 -3, i3 -3, i3 -2, i3 -1, i3 0, i3 0, i3 1, i3 2>
 ;
   %r = call <8 x i3> @llvm.smul.fix.sat.v8i3(
   <8 x i3> <i3 -4, i3 -3, i3 -2, i3 -1, i3 0, i3 1, i3 2, i3 3>,
   <8 x i3> <i3 3, i3 3, i3 3, i3 3, i3 3, i3 3, i3 3, i3 3>,
   i32 2)
   ret <8 x i3> %r
 }
+
+define <8 x i3> @test_smul_fix_sat_v8i3_9() {
+; CHECK-LABEL: @test_smul_fix_sat_v8i3_9(
+; CHECK-NEXT:    ret <8 x i3> <i3 0, i3 0, i3 poison, i3 poison, i3 1, i3 1, i3 1, i3 1>
+;
+  %r = call <8 x i3> @llvm.smul.fix.sat.v8i3(
+  <8 x i3> <i3 2, i3 undef, i3 2, i3 poison, i3 2, i3 2, i3 2, i3 2>,
+  <8 x i3> <i3 undef, i3 2, i3 poison, i3 2, i3 2, i3 2, i3 2, i3 2>,
+  i32 2)
+  ret <8 x i3> %r
+}

llvm/test/Transforms/InstSimplify/ConstProp/smul-fix.ll

 define i32 @test_smul_fix_i32_0() {
 ; CHECK-LABEL: @test_smul_fix_i32_0(
 ; CHECK-NEXT:    ret i32 536870912
 ;
   %r = call i32 @llvm.smul.fix.i32(i32 1073741824, i32 1073741824, i32 31) ; 0.5 * 0.5
   ret i32 %r
 }
 
+define i32 @test_smul_fix_i32_undef_x() {
+; CHECK-LABEL: @test_smul_fix_i32_undef_x(
+; CHECK-NEXT:    ret i32 0
+;
+  %r = call i32 @llvm.smul.fix.i32(i32 undef, i32 1073741824, i32 31) ; undef * 0.5
+  ret i32 %r
+}
+
+define i32 @test_smul_fix_i32_x_undef() {
+; CHECK-LABEL: @test_smul_fix_i32_x_undef(
+; CHECK-NEXT:    ret i32 0
+;
+  %r = call i32 @llvm.smul.fix.i32(i32 1073741824, i32 undef, i32 31)
+  ret i32 %r
+}
+
+
 ;-----------------------------------------------------------------------------
 ; More extensive tests based on vectors (basically using the scalar fold
 ; for each index).
 ;-----------------------------------------------------------------------------
 
 declare <8 x i3> @llvm.smul.fix.v8i3(<8 x i3>, <8 x i3>, i32)
 
 define <8 x i3> @test_smul_fix_v8i3_0() {

 ; CHECK-NEXT:    ret <8 x i3> <i3 -3, i3 -3, i3 -2, i3 -1, i3 0, i3 0, i3 1, i3 2>
 ;
   %r = call <8 x i3> @llvm.smul.fix.v8i3(
   <8 x i3> <i3 -4, i3 -3, i3 -2, i3 -1, i3 0, i3 1, i3 2, i3 3>,
   <8 x i3> <i3 3, i3 3, i3 3, i3 3, i3 3, i3 3, i3 3, i3 3>,
   i32 2)
   ret <8 x i3> %r
 }
+
+define <8 x i3> @test_smul_fix_v8i3_9() {
+; CHECK-LABEL: @test_smul_fix_v8i3_9(
+; CHECK-NEXT:    ret <8 x i3> <i3 0, i3 0, i3 poison, i3 poison, i3 1, i3 1, i3 1, i3 1>
+;
+  %r = call <8 x i3> @llvm.smul.fix.v8i3(
+  <8 x i3> <i3 2, i3 undef, i3 2, i3 poison, i3 2, i3 2, i3 2, i3 2>,
+  <8 x i3> <i3 undef, i3 2, i3 poison, i3 2, i3 2, i3 2, i3 2, i3 2>,
+  i32 2)
+  ret <8 x i3> %r
+}