[ConstantFold] Fold operations to poison if possible

[aqjune]

Summary

This patch updates ConstantFold, so operations are folded into poison if possible.

<alive2 proofs>
casts: https://alive2.llvm.org/ce/z/WSj7rw
binary operations (arithmetic): https://alive2.llvm.org/ce/z/_7dEyJ
binary operations (bitwise): https://alive2.llvm.org/ce/z/cezjVN
vector/aggregate operations: https://alive2.llvm.org/ce/z/BQ7hWz
unary ops: https://alive2.llvm.org/ce/z/yBRs4q
other ops: https://alive2.llvm.org/ce/z/iXbcFD

[aqjune]

Alive2's support for poison is so new that alive2.llvm.org isn't supporting it yet.
I'll attach the proof when poison is supported; I locally checked that the tests pass.

llvm/test/Transforms/InstSimplify/ConstProp/poison.ll

115

The GEP had to be written as a constant expr because InstSimplify's SimplifyGEPInst wasn't calling llvm::ConstantFoldGetElementPtr.

[aqjune]

clang-format

[aqjune]

llvm/lib/IR/ConstantFold.cpp

784

This is poison because select poison, ?, ? is poison.

841

This is poison because undef can be folded into out-of-bounds index, which makes extractelement yield poison according to LangRef.

905

This is poison because insertelement with out-of-bounds index yields poison.

[aqjune]

llvm/lib/IR/ConstantFold.cpp

841

(I see that this is slightly different from shufflevector, which states that undef mask blocks poison.
In the case of shufflevector, the mask should be either undef or integer constant: undef rather works as a special value stating the result should be undef.
But, insertelement can accept variable index. An undef value at the index can be folded to any value, including out-of-bounds.
This is my understanding, and if this seems okay, I'll make a separate LangRef patch that explicitly says insertelement with undef index is poison (and extractelement as well).

[aqjune]

alive2 now interprets poison. Here are the proofs:

casts: https://alive2.llvm.org/ce/z/WSj7rw
binary operations (arithmetic): https://alive2.llvm.org/ce/z/_7dEyJ
binary operations (bitwise): https://alive2.llvm.org/ce/z/cezjVN
vector/aggregate operations: https://alive2.llvm.org/ce/z/BQ7hWz
unary ops: https://alive2.llvm.org/ce/z/yBRs4q
other ops: https://alive2.llvm.org/ce/z/iXbcFD

[nikic]

llvm/lib/IR/ConstantFold.cpp

1115

I don't get this, why do we care about IsScalarOrScalarVec here? Isn't just this sufficient here (all binops propagate poison)?

if (isa<PoisonValue>(C1) || isa<PoisonValue>(C2))
  return PoisonValue::get(C1->getType());

[aqjune]

address a comment

[aqjune]

llvm/lib/IR/ConstantFold.cpp

1115

That's right, fixed

[nikic]

LGTM

There seem to be still quite a few places where UndefValue can be replaced with PoisonValue in ConstantFold, do you plan to follow up on that?

[nikic]

llvm/test/Transforms/InstSimplify/ConstProp/poison.ll

115

It looks like it does invoke constant folding, but there is an earlier check for an undef base pointer, which also catches poison. When that is replaced to check poison first, it should work correctly.

[aqjune]

Yes, I can make a follow-up patch that does e.g., C / 0 -> poison soon. Thanks!

llvm/test/Transforms/InstSimplify/ConstProp/poison.ll

115

I missed that it was calling ConstantFoldConstant at last. Thank you for the info.

llvm/lib/IR/ConstantFold.cpp

static Constant *getFoldedOffsetOf(Type *Ty, Constant *FieldNo, Type *DestTy,
   C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
                                                     DestTy, false),
                             C, DestTy);
   return C;
 }
 
 Constant *llvm::ConstantFoldCastInstruction(unsigned opc, Constant *V,
                                             Type *DestTy) {
+  if (isa<PoisonValue>(V))
+    return PoisonValue::get(DestTy);
+
   if (isa<UndefValue>(V)) {
     // zext(undef) = 0, because the top bits will be zero.
     // sext(undef) = 0, because the top bits will all be the same.
     // [us]itofp(undef) = 0, because the result value is bounded.
     if (opc == Instruction::ZExt || opc == Instruction::SExt ||
         opc == Instruction::UIToFP || opc == Instruction::SIToFP)
       return Constant::getNullValue(DestTy);
     return UndefValue::get(DestTy);
if (ConstantVector *CondV = dyn_cast<ConstantVector>(Cond)) {
     Type *Ty = IntegerType::get(CondV->getContext(), 32);
     for (unsigned i = 0, e = V1VTy->getNumElements(); i != e; ++i) {
       Constant *V;
       Constant *V1Element = ConstantExpr::getExtractElement(V1,
                                                     ConstantInt::get(Ty, i));
       Constant *V2Element = ConstantExpr::getExtractElement(V2,
                                                     ConstantInt::get(Ty, i));
       auto *Cond = cast<Constant>(CondV->getOperand(i));
-      if (V1Element == V2Element) {
+      if (isa<PoisonValue>(Cond)) {
+        V = PoisonValue::get(V1Element->getType());
+      } else if (V1Element == V2Element) {
         V = V1Element;
       } else if (isa<UndefValue>(Cond)) {
         V = isa<UndefValue>(V1Element) ? V1Element : V2Element;
       } else {
         if (!isa<ConstantInt>(Cond)) break;
         V = Cond->isNullValue() ? V2Element : V1Element;
       }
       Result.push_back(V);
     }
 
     // If we were able to build the vector, return it.
     if (Result.size() == V1VTy->getNumElements())
       return ConstantVector::get(Result);
   }
 
+  if (isa<PoisonValue>(Cond))
+    return PoisonValue::get(V1->getType());
+
   if (isa<UndefValue>(Cond)) {
     if (isa<UndefValue>(V1)) return V1;
     return V2;
   }
 
   if (V1 == V2) return V1;
 
+  if (isa<PoisonValue>(V1))
+    return V2;
+  if (isa<PoisonValue>(V2))
+    return V1;
+
   // If the true or false value is undef, we can fold to the other value as
   // long as the other value isn't poison.
   auto NotPoison = [](Constant *C) {
+    if (isa<PoisonValue>(C))
+      return false;
+
     // TODO: We can analyze ConstExpr by opcode to determine if there is any
     //       possibility of poison.
     if (isa<ConstantExpr>(C))
       return false;
 
     if (isa<ConstantInt>(C) || isa<GlobalVariable>(C) || isa<ConstantFP>(C) ||
         isa<ConstantPointerNull>(C) || isa<Function>(C))
       return true;
Constant *llvm::ConstantFoldSelectInstruction(Constant *Cond,
 
   return nullptr;
 }
 
 Constant *llvm::ConstantFoldExtractElementInstruction(Constant *Val,
                                                       Constant *Idx) {
   auto *ValVTy = cast<VectorType>(Val->getType());
 
+  // extractelt poison, C -> poison
+  // extractelt C, undef -> poison
+  if (isa<PoisonValue>(Val) || isa<UndefValue>(Idx))
+    return PoisonValue::get(ValVTy->getElementType());
+
   // extractelt undef, C -> undef
-  // extractelt C, undef -> undef
-  if (isa<UndefValue>(Val) || isa<UndefValue>(Idx))
+  if (isa<UndefValue>(Val))
     return UndefValue::get(ValVTy->getElementType());
 
   auto *CIdx = dyn_cast<ConstantInt>(Idx);
   if (!CIdx)
     return nullptr;
 
   if (auto *ValFVTy = dyn_cast<FixedVectorType>(Val->getType())) {
-    // ee({w,x,y,z}, wrong_value) -> undef
+    // ee({w,x,y,z}, wrong_value) -> poison
     if (CIdx->uge(ValFVTy->getNumElements()))
-      return UndefValue::get(ValFVTy->getElementType());
+      return PoisonValue::get(ValFVTy->getElementType());
   }
 
   // ee (gep (ptr, idx0, ...), idx) -> gep (ee (ptr, idx), ee (idx0, idx), ...)
   if (auto *CE = dyn_cast<ConstantExpr>(Val)) {
     if (CE->getOpcode() == Instruction::GetElementPtr) {
       SmallVector<Constant *, 8> Ops;
       Ops.reserve(CE->getNumOperands());
       for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) {
Constant *llvm::ConstantFoldExtractElementInstruction(Constant *Val,
 
   return Val->getAggregateElement(CIdx);
 }
 
 Constant *llvm::ConstantFoldInsertElementInstruction(Constant *Val,
                                                      Constant *Elt,
                                                      Constant *Idx) {
   if (isa<UndefValue>(Idx))
-    return UndefValue::get(Val->getType());
+    return PoisonValue::get(Val->getType());
 
   ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx);
   if (!CIdx) return nullptr;
 
   // Do not iterate on scalable vector. The num of elements is unknown at
   // compile-time.
   if (isa<ScalableVectorType>(Val->getType()))
     return nullptr;
Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode, Constant *C1,
   Constant *Identity = ConstantExpr::getBinOpIdentity(Opcode, C1->getType());
   if (Identity) {
     if (C1 == Identity)
       return C2;
     if (C2 == Identity)
       return C1;
   }
 
+  // Binary operations propagate poison.
+  if (isa<PoisonValue>(C1) || isa<PoisonValue>(C2))
+    return PoisonValue::get(C1->getType());
+
   // Handle scalar UndefValue and scalable vector UndefValue. Fixed-length
   // vectors are always evaluated per element.
   bool IsScalableVector = isa<ScalableVectorType>(C1->getType());
   bool HasScalarUndefOrScalableVectorUndef =
       (!C1->getType()->isVectorTy() || IsScalableVector) &&
       (isa<UndefValue>(C1) || isa<UndefValue>(C2));
   if (HasScalarUndefOrScalableVectorUndef) {
     switch (static_cast<Instruction::BinaryOps>(Opcode)) {
     case Instruction::Xor:
       if (isa<UndefValue>(C1) && isa<UndefValue>(C2))
         // Handle undef ^ undef -> 0 special case. This is a common
         // idiom (misuse).
         return Constant::getNullValue(C1->getType());
Constant *llvm::ConstantFoldCompareInstruction(unsigned short pred,
   // Fold FCMP_FALSE/FCMP_TRUE unconditionally.
   if (pred == FCmpInst::FCMP_FALSE)
     return Constant::getNullValue(ResultTy);
 
   if (pred == FCmpInst::FCMP_TRUE)
     return Constant::getAllOnesValue(ResultTy);
 
   // Handle some degenerate cases first
+  if (isa<PoisonValue>(C1) || isa<PoisonValue>(C2))
+    return PoisonValue::get(ResultTy);
+
   if (isa<UndefValue>(C1) || isa<UndefValue>(C2)) {
     CmpInst::Predicate Predicate = CmpInst::Predicate(pred);
     bool isIntegerPredicate = ICmpInst::isIntPredicate(Predicate);
     // For EQ and NE, we can always pick a value for the undef to make the
     // predicate pass or fail, so we can return undef.
     // Also, if both operands are undef, we can return undef for int comparison.
     if (ICmpInst::isEquality(Predicate) || (isIntegerPredicate && C1 == C2))
       return UndefValue::get(ResultTy);
Constant *llvm::ConstantFoldGetElementPtr(Type *PointeeTy, Constant *C,
                                           bool InBounds,
                                           Optional<unsigned> InRangeIndex,
                                           ArrayRef<Value *> Idxs) {
   if (Idxs.empty()) return C;
 
   Type *GEPTy = GetElementPtrInst::getGEPReturnType(
       PointeeTy, C, makeArrayRef((Value *const *)Idxs.data(), Idxs.size()));
 
+  if (isa<PoisonValue>(C))
+    return PoisonValue::get(GEPTy);
+
   if (isa<UndefValue>(C))
     return UndefValue::get(GEPTy);
 
   Constant *Idx0 = cast<Constant>(Idxs[0]);
   if (Idxs.size() == 1 && (Idx0->isNullValue() || isa<UndefValue>(Idx0)))
     return GEPTy->isVectorTy() && !C->getType()->isVectorTy()
                ? ConstantVector::getSplat(
                      cast<VectorType>(GEPTy)->getElementCount(), C)

llvm/lib/IR/Constants.cpp

Constant *Constant::getAggregateElement(unsigned Elt) const {
 
   // FIXME: getNumElements() will fail for non-fixed vector types.
   if (isa<ScalableVectorType>(getType()))
     return nullptr;
 
   if (const auto *CAZ = dyn_cast<ConstantAggregateZero>(this))
     return Elt < CAZ->getNumElements() ? CAZ->getElementValue(Elt) : nullptr;
 
+  if (const auto *PV = dyn_cast<PoisonValue>(this))
+    return Elt < PV->getNumElements() ? PV->getElementValue(Elt) : nullptr;
+
   if (const auto *UV = dyn_cast<UndefValue>(this))
     return Elt < UV->getNumElements() ? UV->getElementValue(Elt) : nullptr;
 
   if (const auto *CDS = dyn_cast<ConstantDataSequential>(this))
     return Elt < CDS->getNumElements() ? CDS->getElementAsConstant(Elt)
                                        : nullptr;
   return nullptr;
 }

llvm/test/Transforms/InstSimplify/ConstProp/InsertElement.ll

;
   %vec3 = insertelement <4 x i64> %vec2, i64 -3, i32 2
   %vec4 = insertelement <4 x i64> %vec3, i64 -4, i32 3
   %vec5 = insertelement <4 x i64> %vec3, i64 -5, i32 4
   ret <4 x i64> %vec5
 }
 
 define i64 @extract_undef_index_from_zero_vec() {
 ; CHECK-LABEL: @extract_undef_index_from_zero_vec(
-; CHECK-NEXT:    ret i64 undef
+; CHECK-NEXT:    ret i64 poison
 ;
   %E = extractelement <2 x i64> zeroinitializer, i64 undef
   ret i64 %E
 }
 
 define i64 @extract_undef_index_from_nonzero_vec() {
 ; CHECK-LABEL: @extract_undef_index_from_nonzero_vec(
-; CHECK-NEXT:    ret i64 undef
+; CHECK-NEXT:    ret i64 poison
 ;
   %E = extractelement <2 x i64> <i64 -1, i64 -1>, i64 undef
   ret i64 %E
 }

llvm/test/Transforms/InstSimplify/ConstProp/poison.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instsimplify -S | FileCheck %s
+
+declare void @use(...)
+
+define void @casts() {
+; CHECK-LABEL: @casts(
+; CHECK-NEXT:    call void (...) @use(i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i32 poison, i8 poison, float poison, float poison, float poison, float poison)
+; CHECK-NEXT:    ret void
+;
+  %i1 = trunc i32 poison to i8
+  %i2 = zext i4 poison to i8
+  %i3 = sext i4 poison to i8
+  %i4 = fptoui float poison to i8
+  %i5 = fptosi float poison to i8
+  %i6 = bitcast float poison to i32
+  %i7 = ptrtoint i8* poison to i8
+  %f1 = fptrunc double poison to float
+  %f2 = fpext half poison to float
+  %f3 = uitofp i8 poison to float
+  %f4 = sitofp i8 poison to float
+  call void (...) @use(i8 %i1, i8 %i2, i8 %i3, i8 %i4, i8 %i5, i32 %i6, i8 %i7, float %f1, float %f2, float %f3, float %f4)
+  ret void
+}
+
+define void @casts2() {
+; CHECK-LABEL: @casts2(
+; CHECK-NEXT:    call void (...) @use(i8* poison, i8* poison)
+; CHECK-NEXT:    ret void
+;
+  %p1 = inttoptr i8 poison to i8*
+  %p2 = addrspacecast i8 addrspace(1)* poison to i8*
+  call void (...) @use(i8* %p1, i8* %p2)
+  ret void
+}
+
+define void @unaryops() {
+; CHECK-LABEL: @unaryops(
+; CHECK-NEXT:    call void (...) @use(float poison)
+; CHECK-NEXT:    ret void
+;
+  %f1 = fneg float poison
+  call void (...) @use(float %f1)
+  ret void
+}
+
+define void @binaryops_arith() {
+; CHECK-LABEL: @binaryops_arith(
+; CHECK-NEXT:    call void (...) @use(i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, float poison, float poison, float poison, float poison, float poison, float poison, float poison)
+; CHECK-NEXT:    ret void
+;
+  %i1 = add i8 poison, 1
+  %i2 = sub i8 poison, 1
+  %i3 = mul i8 poison, 2
+  %i4 = udiv i8 poison, 2
+  %i5 = udiv i8 2, poison
+  %i6 = sdiv i8 poison, 2
+  %i7 = sdiv i8 2, poison
+  %i8 = urem i8 poison, 2
+  %i9 = urem i8 2, poison
+  %i10 = srem i8 poison, 2
+  %i11 = srem i8 2, poison
+  %f1 = fadd float poison, 1.0
+  %f2 = fsub float poison, 1.0
+  %f3 = fmul float poison, 2.0
+  %f4 = fdiv float poison, 2.0
+  %f5 = fdiv float 2.0, poison
+  %f6 = frem float poison, 2.0
+  %f7 = frem float 2.0, poison
+  call void (...) @use(i8 %i1, i8 %i2, i8 %i3, i8 %i4, i8 %i5, i8 %i6, i8 %i7, i8 %i8, i8 %i9, i8 %i10, i8 %i11, float %f1, float %f2, float %f3, float %f4, float %f5, float %f6, float %f7)
+  ret void
+}
+
+define void @binaryops_bitwise() {
+; CHECK-LABEL: @binaryops_bitwise(
+; CHECK-NEXT:    call void (...) @use(i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison, i8 poison)
+; CHECK-NEXT:    ret void
+;
+  %i1 = shl i8 poison, 1
+  %i2 = shl i8 1, poison
+  %i3 = lshr i8 poison, 1
+  %i4 = lshr i8 1, poison
+  %i5 = ashr i8 poison, 1
+  %i6 = ashr i8 1, poison
+  %i7 = and i8 poison, 1
+  %i8 = or i8 poison, 1
+  %i9 = xor i8 poison, 1
+  call void (...) @use(i8 %i1, i8 %i2, i8 %i3, i8 %i4, i8 %i5, i8 %i6, i8 %i7, i8 %i8, i8 %i9)
+  ret void
+}
+
+define void @vec_aggr_ops() {
+; CHECK-LABEL: @vec_aggr_ops(
+; CHECK-NEXT:    call void (...) @use(i8 poison, i8 poison, <2 x i8> poison, i8 poison)
+; CHECK-NEXT:    ret void
+;
+  %i1 = extractelement <2 x i8> poison, i64 0
+  %i2 = extractelement <2 x i8> zeroinitializer, i64 poison
+  %i3 = insertelement <2 x i8> zeroinitializer, i8 0, i64 poison
+  %i4 = extractvalue {i8, i8} poison, 0
+  call void (...) @use(i8 %i1, i8 %i2, <2 x i8> %i3, i8 %i4)
+  ret void
+}
+
+define void @other_ops(i8 %x) {
+; CHECK-LABEL: @other_ops(
+; CHECK-NEXT:    call void (...) @use(i1 poison, i1 poison, i8 poison, i8 poison, i8* poison)
+; CHECK-NEXT:    ret void
+;
+  %i1 = icmp eq i8 poison, 1
+  %i2 = fcmp oeq float poison, 1.0
+  %i3 = select i1 poison, i8 1, i8 2
+  %i4 = select i1 true, i8 poison, i8 %x
+  call void (...) @use(i1 %i1, i1 %i2, i8 %i3, i8 %i4, i8* getelementptr (i8, i8* poison, i64 1))
+  ret void
+}

llvm/unittests/IR/ConstantsTest.cpp

TEST(ConstantsTest, AsInstructionsTest) {
   Constant *P4 = ConstantExpr::getPtrToInt(Global2, Int32Ty);
   Constant *P5 = ConstantExpr::getUIToFP(P4, FloatTy);
   Constant *P6 = ConstantExpr::getBitCast(P4, FixedVectorType::get(Int16Ty, 2));
 
   Constant *One = ConstantInt::get(Int32Ty, 1);
   Constant *Two = ConstantInt::get(Int64Ty, 2);
   Constant *Big = ConstantInt::get(Context, APInt{256, uint64_t(-1), true});
   Constant *Elt = ConstantInt::get(Int16Ty, 2015);
-  Constant *Undef16  = UndefValue::get(Int16Ty);
+  Constant *Poison16 = PoisonValue::get(Int16Ty);
   Constant *Undef64  = UndefValue::get(Int64Ty);
   Constant *UndefV16 = UndefValue::get(P6->getType());
+  Constant *PoisonV16 = PoisonValue::get(P6->getType());
 
   #define P0STR "ptrtoint (i32** @dummy to i32)"
   #define P1STR "uitofp (i32 ptrtoint (i32** @dummy to i32) to float)"
   #define P2STR "uitofp (i32 ptrtoint (i32** @dummy to i32) to double)"
   #define P3STR "ptrtoint (i32** @dummy to i1)"
   #define P4STR "ptrtoint (i32** @dummy2 to i32)"
   #define P5STR "uitofp (i32 ptrtoint (i32** @dummy2 to i32) to float)"
   #define P6STR "bitcast (i32 ptrtoint (i32** @dummy2 to i32) to <2 x i16>)"
TEST(ConstantsTest, AsInstructionsTest) {
   //      "getelementptr i32*, i32** @dummy, i32 1");
   CHECK(ConstantExpr::getInBoundsGetElementPtr(PointerType::getUnqual(Int32Ty),
                                                Global, V),
         "getelementptr inbounds i32*, i32** @dummy, i32 1");
 
   CHECK(ConstantExpr::getExtractElement(P6, One), "extractelement <2 x i16> "
         P6STR ", i32 1");
 
-  EXPECT_EQ(Undef16, ConstantExpr::getExtractElement(P6, Two));
-  EXPECT_EQ(Undef16, ConstantExpr::getExtractElement(P6, Big));
-  EXPECT_EQ(Undef16, ConstantExpr::getExtractElement(P6, Undef64));
+  EXPECT_EQ(Poison16, ConstantExpr::getExtractElement(P6, Two));
+  EXPECT_EQ(Poison16, ConstantExpr::getExtractElement(P6, Big));
+  EXPECT_EQ(Poison16, ConstantExpr::getExtractElement(P6, Undef64));
 
   EXPECT_EQ(Elt, ConstantExpr::getExtractElement(
                  ConstantExpr::getInsertElement(P6, Elt, One), One));
   EXPECT_EQ(UndefV16, ConstantExpr::getInsertElement(P6, Elt, Two));
   EXPECT_EQ(UndefV16, ConstantExpr::getInsertElement(P6, Elt, Big));
-  EXPECT_EQ(UndefV16, ConstantExpr::getInsertElement(P6, Elt, Undef64));
+  EXPECT_EQ(PoisonV16, ConstantExpr::getInsertElement(P6, Elt, Undef64));
 }
 
 #ifdef GTEST_HAS_DEATH_TEST
 #ifndef NDEBUG
 TEST(ConstantsTest, ReplaceWithConstantTest) {
   LLVMContext Context;
   std::unique_ptr<Module> M(new Module("MyModule", Context));