[ValueTracking] Add canCreateUndefOrPoison & let canCreatePoison use Operator

[aqjune]

Summary

This patch

• adds canCreateUndefOrPoison
• refactors canCreatePoison so it can deal with constantexprs

canCreateUndefOrPoison will be used at D83926.

[jdoerfert]

llvm/include/llvm/Analysis/ValueTracking.h

607

Drive by: Now that I see this, I would prefer the public API to have two functions. I'm fine if others disagree but for the users it seems more natural to have canCreateUndef and canCreateUndefOrPoison, (and maybe canCreatePoison).

llvm/lib/Analysis/ValueTracking.cpp

4783

This seems wrong. A load of an uninitialized location should produce undef for example, shouldn't it? I fear there are way more things that can produce undef. The default should be true here.

[nikic]

llvm/include/llvm/Analysis/ValueTracking.h

607

Same here. I would prefer there to only be canCreatePoison and canCreatePoisonOrUndef. Just canCreateUndef by itself would be a footgun, because poison relaxes to undef. I don't see an immediate use for a "can create undef excluding undef that was originally poison" query.

llvm/lib/Analysis/ValueTracking.cpp

4783

Returning true here would make this function always return true :) If we drop the "undef only" mode, then returning false should be fine, as this function only needs to deal with cases where undef is possible but poison is not.

[jdoerfert]

llvm/lib/Analysis/ValueTracking.cpp

4783

What about my load example? poison is not possible but undef is, returning false still seems wrong, or maybe I'm just confused..

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4783

Loads can also return poison, and canCreatePoison() will return true for them. (Having load/store implicitly filter poison would prevent mem2reg/SROA.)

[jdoerfert]

llvm/lib/Analysis/ValueTracking.cpp

4783

Loads *can* return poison. Some are known *not to* but still *can* return undef. Are we sure this implicit link between the two procedures is wise? I mean, even if the situation I describe doesn't happen now, how do you prevent someone from making canCreatePoison smarter and introducing a bug here?

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4783

Okay, I see your concern now. In that case I would suggest combining these into a single canCreateUndefOrPoison() function with a PoisonOnly flag (for the PoisonChecking consumer). That should make it obvious that these need to be considered as a unit.

[jdoerfert]

llvm/lib/Analysis/ValueTracking.cpp

4783

The implementation (=logic) to determine poison and undef should be at the same place. We can expose it via multiple functions but from the perspective of determining it the two are closely connection (IMHO).

[aqjune]

Reflect comments

[aqjune]

llvm/include/llvm/Analysis/ValueTracking.h

607

Leaving canCreateUndefOrPoison and canCreatePoison only, since it turns out that canCreateUndef could not be used to resolve the instsimplify problem at D83360

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

4723

Added noundef return attribute check here since this is a pretty small change

[nikic]

LG

llvm/unittests/Analysis/ValueTrackingTest.cpp

809

This might be more obvious if it tested for canCreateUndefOrPoison && !canCreatePoison == Undef.

[jdoerfert]

llvm/lib/Analysis/ValueTracking.cpp

4784

Thx :)

llvm/include/llvm/Analysis/ValueTracking.h

 //===- llvm/Analysis/ValueTracking.h - Walk computations --------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains routines that help analyze properties that chains of
 // computations have.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_VALUETRACKING_H
 #define LLVM_ANALYSIS_VALUETRACKING_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/Operator.h"
 #include <cassert>
 #include <cstdint>
 
 namespace llvm {
 
 class AddOperator;
 class APInt;
 class AssumptionCache;
class Value;
 
   /// Return true if this function can prove that if PoisonI is executed
   /// and yields a poison value, then that will trigger undefined behavior.
   ///
   /// Note that this currently only considers the basic block that is
   /// the parent of I.
   bool programUndefinedIfPoison(const Instruction *PoisonI);
 
-  /// Return true if I can create poison from non-poison operands.
+  /// Return true if Op can create poison from non-poison operands.
   /// For vectors, canCreatePoison returns true if there is potential poison in
   /// any element of the result when vectors without poison are given as
   /// operands.
-  /// For example, given `I = shl <2 x i32> %x, <0, 32>`, this function returns
-  /// true. If I raises immediate UB but never creates poison (e.g. sdiv I, 0),
+  /// For example, given `Op = shl <2 x i32> %x, <0, 32>`, this function returns
+  /// true. If Op raises immediate UB but never creates poison (e.g. sdiv I, 0),
   /// canCreatePoison returns false.
-  bool canCreatePoison(const Instruction *I);
+  bool canCreatePoison(const Operator *Op);
+
+  /// Return true if I can create undef from non-undef & non-poison operands.
+  /// If ConsiderPoisonAsUndef is true, return true as well if Op can create
+  /// poison from non-undef & non-poison operands.
+  bool canCreateUndef(const Operator *Op, bool ConsiderPoisonAsUndef);
 
   /// Return true if this function can prove that V is never undef value
   /// or poison value.
   //
   /// If CtxI and DT are specified this method performs flow-sensitive analysis
   /// and returns true if it is guaranteed to be never undef or poison
   /// immediately before the CtxI.
   bool isGuaranteedNotToBeUndefOrPoison(const Value *V,

llvm/lib/Analysis/ValueTracking.cpp

 //===- ValueTracking.cpp - Walk computations to compute properties --------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
auto AllUsesGuardedByBranch = [&](const BranchInst *BI) {
     }
 
     return true;
   };
 
   return llvm::any_of(GuardingBranches, AllUsesGuardedByBranch);
 }
 
-bool llvm::canCreatePoison(const Instruction *I) {
+bool llvm::canCreatePoison(const Operator *Op) {
   // See whether I has flags that may create poison
-  if (isa<OverflowingBinaryOperator>(I) &&
-      (I->hasNoSignedWrap() || I->hasNoUnsignedWrap()))
+  if (const auto *OvOp = dyn_cast<OverflowingBinaryOperator>(Op)) {
+    if (OvOp->hasNoSignedWrap() || OvOp->hasNoUnsignedWrap())
       return true;
-  if (isa<PossiblyExactOperator>(I) && I->isExact())
+  }
+  if (const auto *ExactOp = dyn_cast<PossiblyExactOperator>(Op))
+    if (ExactOp->isExact())
       return true;
-  if (auto *FP = dyn_cast<FPMathOperator>(I)) {
+  if (auto *FP = dyn_cast<FPMathOperator>(Op)) {
     auto FMF = FP->getFastMathFlags();
     if (FMF.noNaNs() || FMF.noInfs())
       return true;
   }
-  if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
+  if (auto *GEP = dyn_cast<GEPOperator>(Op))
     if (GEP->isInBounds())
       return true;
 
-  unsigned Opcode = I->getOpcode();
+  unsigned Opcode = Op->getOpcode();
 
   // Check whether opcode is a poison-generating operation
   switch (Opcode) {
   case Instruction::Shl:
   case Instruction::AShr:
   case Instruction::LShr: {
     // Shifts return poison if shiftwidth is larger than the bitwidth.
-    if (auto *C = dyn_cast<Constant>(I->getOperand(1))) {
+    if (auto *C = dyn_cast<Constant>(Op->getOperand(1))) {
       SmallVector<Constant *, 4> ShiftAmounts;
       if (auto *FVTy = dyn_cast<FixedVectorType>(C->getType())) {
         unsigned NumElts = FVTy->getNumElements();
         for (unsigned i = 0; i < NumElts; ++i)
           ShiftAmounts.push_back(C->getAggregateElement(i));
       } else if (isa<ScalableVectorType>(C->getType()))
         return true; // Can't tell, just return true to be safe
       else
case Instruction::FPToUI:
     // fptosi/ui yields poison if the resulting value does not fit in the
     // destination type.
     return true;
   case Instruction::Call:
   case Instruction::CallBr:
   case Instruction::Invoke:
     // Function calls can return a poison value even if args are non-poison
     // values.
     return true;
   case Instruction::InsertElement:
   case Instruction::ExtractElement: {
     // If index exceeds the length of the vector, it returns poison
-    auto *VTy = cast<VectorType>(I->getOperand(0)->getType());
-    unsigned IdxOp = I->getOpcode() == Instruction::InsertElement ? 2 : 1;
-    auto *Idx = dyn_cast<ConstantInt>(I->getOperand(IdxOp));
+    auto *VTy = cast<VectorType>(Op->getOperand(0)->getType());
+    unsigned IdxOp = Op->getOpcode() == Instruction::InsertElement ? 2 : 1;
+    auto *Idx = dyn_cast<ConstantInt>(Op->getOperand(IdxOp));
     if (!Idx || Idx->getZExtValue() >= VTy->getElementCount().Min)
       return true;
     return false;
   }
   case Instruction::FNeg:
   case Instruction::PHI:
   case Instruction::Select:
   case Instruction::URem:
   case Instruction::SRem:
   case Instruction::ShuffleVector:
   case Instruction::ExtractValue:
   case Instruction::InsertValue:
   case Instruction::Freeze:
   case Instruction::ICmp:
   case Instruction::FCmp:
   case Instruction::GetElementPtr:
     return false;
-  default:
-    if (isa<CastInst>(I))
+  default: {
+    const auto *CE = dyn_cast<ConstantExpr>(Op);
+    if (isa<CastInst>(Op) || (CE && CE->isCast()))
       return false;
-    else if (isa<BinaryOperator>(I))
+    else if (isa<BinaryOperator>(Op))
       return false;
     // Be conservative and return true.
     return true;
   }
   }
+}
+
+bool llvm::canCreateUndef(const Operator *Op, bool ConsiderPoisonAsUndef) {
+  // If ConsiderPoisonAsUndef is set and canCreatePoison(op) holds, return true.
+  // canCreatePoison(op) returns true if op returns poison when its operands are
+  // non-poison, meaning that they can be undef.
+  // canCreatePoison can be still used here, and it relies on the observation
+  // that for any operation op and value v1 v2, if `op v1 v2` returned poison
+  // and either v1 or v2 is undef, there exists non-undef value v1' and v2' s.t.
+  // `op v1' v2'` also returns poison.
+  // For example, `shl i32 1, undef` returns poison, as well as `shl i32 1, 33`.
+  //
+  // If a new operation is added or existing one's semantics is updated so it
+  // does not return poison on any non-undef operands but returns poison on
+  // undef operands, this should be updated.
+  if (ConsiderPoisonAsUndef && canCreatePoison(Op))
+    return true;
+
+  if (Op->getOpcode() == Instruction::ShuffleVector) {
+    // shufflevector may return undef.
+    ArrayRef<int> Mask = isa<ConstantExpr>(Op) ?
+            cast<ConstantExpr>(Op)->getShuffleMask() :
+            cast<ShuffleVectorInst>(Op)->getShuffleMask();
+    return any_of(Mask, [](int Elt) { return Elt == UndefMaskElem; });
+  }
+
+  return false;
+}
+
 
 bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V,
                                             const Instruction *CtxI,
                                             const DominatorTree *DT,
                                             unsigned Depth) {
   if (Depth >= MaxDepth)
     return false;
 
   // If the value is a freeze instruction, then it can never

llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp

 //===- PoisonChecking.cpp - -----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
for (Instruction &I : BB) {
             CreateAssertNot(B, getPoisonFor(ValToPoison, Op));
           }
 
       SmallVector<Value*, 4> Checks;
       if (propagatesPoison(&I))
         for (Value *V : I.operands())
           Checks.push_back(getPoisonFor(ValToPoison, V));
 
-      if (canCreatePoison(&I))
+      if (canCreatePoison(cast<Operator>(&I)))
         generateCreationChecks(I, Checks);
       ValToPoison[&I] = buildOrChain(B, Checks);
     }
 
   for (BasicBlock &BB : F)
     for (auto I = BB.begin(); isa<PHINode>(&*I); I++) {
       auto *OldPHI = cast<PHINode>(&*I);
       if (!ValToPoison.count(OldPHI))

llvm/unittests/Analysis/ValueTrackingTest.cpp

 //===- ValueTrackingTest.cpp - ValueTracking tests ------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
for (auto &I : BB) {
     if (isa<ReturnInst>(&I))
       break;
     EXPECT_EQ(propagatesPoison(&I), Data[Index].first)
         << "Incorrect answer at instruction " << Index << " = " << I;
     Index++;
   }
 }
 
-TEST(ValueTracking, canCreatePoison) {
+TEST(ValueTracking, canCreatePoisonOrUndef) {
   std::string AsmHead =
       "declare i32 @g(i32)\n"
       "define void @f(i32 %x, i32 %y, float %fx, float %fy, i1 %cond, "
       "<4 x i32> %vx, <4 x i32> %vx2, <vscale x 4 x i32> %svx, i8* %p) {\n";
   std::string AsmTail = "  ret void\n}";
-  // (can create poison?, IR instruction)
-  SmallVector<std::pair<bool, std::string>, 32> Data = {
-      {false, "add i32 %x, %y"},
-      {true, "add nsw nuw i32 %x, %y"},
-      {true, "shl i32 %x, %y"},
-      {true, "shl <4 x i32> %vx, %vx2"},
-      {true, "shl nsw i32 %x, %y"},
-      {true, "shl nsw <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
-      {false, "shl i32 %x, 31"},
-      {true, "shl i32 %x, 32"},
-      {false, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
-      {true, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
-      {true, "ashr i32 %x, %y"},
-      {true, "ashr exact i32 %x, %y"},
-      {false, "ashr i32 %x, 31"},
-      {true, "ashr exact i32 %x, 31"},
-      {false, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
-      {true, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
-      {true, "ashr exact <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
-      {true, "lshr i32 %x, %y"},
-      {true, "lshr exact i32 %x, 31"},
-      {false, "udiv i32 %x, %y"},
-      {true, "udiv exact i32 %x, %y"},
-      {false, "getelementptr i8, i8* %p, i32 %x"},
-      {true, "getelementptr inbounds i8, i8* %p, i32 %x"},
-      {true, "fneg nnan float %fx"},
-      {false, "fneg float %fx"},
-      {false, "fadd float %fx, %fy"},
-      {true, "fadd nnan float %fx, %fy"},
-      {false, "urem i32 %x, %y"},
-      {true, "fptoui float %fx to i32"},
-      {true, "fptosi float %fx to i32"},
-      {false, "bitcast float %fx to i32"},
-      {false, "select i1 %cond, i32 %x, i32 %y"},
-      {true, "select nnan i1 %cond, float %fx, float %fy"},
-      {true, "extractelement <4 x i32> %vx, i32 %x"},
-      {false, "extractelement <4 x i32> %vx, i32 3"},
-      {true, "extractelement <vscale x 4 x i32> %svx, i32 4"},
-      {true, "insertelement <4 x i32> %vx, i32 %x, i32 %y"},
-      {false, "insertelement <4 x i32> %vx, i32 %x, i32 3"},
-      {true, "insertelement <vscale x 4 x i32> %svx, i32 %x, i32 4"},
-      {false, "freeze i32 %x"},
-      {true, "call i32 @g(i32 %x)"},
-      {true, "fcmp nnan oeq float %fx, %fy"},
-      {false, "fcmp oeq float %fx, %fy"}};
+  // (can create poison?, can create undef?, IR instruction)
+  SmallVector<std::tuple<bool, bool, std::string>, 32> Data = {
+      {false, false, "add i32 %x, %y"},
+      {true, false, "add nsw nuw i32 %x, %y"},
+      {true, false, "shl i32 %x, %y"},
+      {true, false, "shl <4 x i32> %vx, %vx2"},
+      {true, false, "shl nsw i32 %x, %y"},
+      {true, false, "shl nsw <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
+      {false, false, "shl i32 %x, 31"},
+      {true, false, "shl i32 %x, 32"},
+      {false, false, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
+      {true, false, "shl <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
+      {true, false, "ashr i32 %x, %y"},
+      {true, false, "ashr exact i32 %x, %y"},
+      {false, false, "ashr i32 %x, 31"},
+      {true, false, "ashr exact i32 %x, 31"},
+      {false, false, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
+      {true, false, "ashr <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 32>"},
+      {true, false, "ashr exact <4 x i32> %vx, <i32 0, i32 1, i32 2, i32 3>"},
+      {true, false, "lshr i32 %x, %y"},
+      {true, false, "lshr exact i32 %x, 31"},
+      {false, false, "udiv i32 %x, %y"},
+      {true, false, "udiv exact i32 %x, %y"},
+      {false, false, "getelementptr i8, i8* %p, i32 %x"},
+      {true, false, "getelementptr inbounds i8, i8* %p, i32 %x"},
+      {true, false, "fneg nnan float %fx"},
+      {false, false, "fneg float %fx"},
+      {false, false, "fadd float %fx, %fy"},
+      {true, false, "fadd nnan float %fx, %fy"},
+      {false, false, "urem i32 %x, %y"},
+      {true, false, "fptoui float %fx to i32"},
+      {true, false, "fptosi float %fx to i32"},
+      {false, false, "bitcast float %fx to i32"},
+      {false,false,  "select i1 %cond, i32 %x, i32 %y"},
+      {true, false, "select nnan i1 %cond, float %fx, float %fy"},
+      {true, false, "extractelement <4 x i32> %vx, i32 %x"},
+      {false, false, "extractelement <4 x i32> %vx, i32 3"},
+      {true, false, "extractelement <vscale x 4 x i32> %svx, i32 4"},
+      {true, false, "insertelement <4 x i32> %vx, i32 %x, i32 %y"},
+      {false, false, "insertelement <4 x i32> %vx, i32 %x, i32 3"},
+      {true, false, "insertelement <vscale x 4 x i32> %svx, i32 %x, i32 4"},
+      {false, false, "freeze i32 %x"},
+      {false, false, "shufflevector <4 x i32> %vx, <4 x i32> %vx2, "
+                    "<4 x i32> <i32 0, i32 1, i32 2, i32 3>"},
+      {false, true, "shufflevector <4 x i32> %vx, <4 x i32> %vx2, "
+                    "<4 x i32> <i32 0, i32 1, i32 2, i32 undef>"},
+      {false, true, "shufflevector <vscale x 4 x i32> %svx, "
+                    "<vscale x 4 x i32> %svx, <vscale x 4 x i32> undef"},
+      {true, false, "call i32 @g(i32 %x)"},
+      {true, false, "fcmp nnan oeq float %fx, %fy"},
+      {false, false, "fcmp oeq float %fx, %fy"}};
 
   std::string AssemblyStr = AsmHead;
   for (auto &Itm : Data)
-    AssemblyStr += Itm.second + "\n";
+    AssemblyStr += std::get<2>(Itm) + "\n";
   AssemblyStr += AsmTail;
 
   LLVMContext Context;
   SMDiagnostic Error;
   auto M = parseAssemblyString(AssemblyStr, Error, Context);
   assert(M && "Bad assembly?");
 
   auto *F = M->getFunction("f");
   assert(F && "Bad assembly?");
 
   auto &BB = F->getEntryBlock();
 
   int Index = 0;
   for (auto &I : BB) {
     if (isa<ReturnInst>(&I))
       break;
-    EXPECT_EQ(canCreatePoison(&I), Data[Index].first)
-        << "Incorrect answer at instruction " << Index << " = " << I;
+    bool Poison = std::get<0>(Data[Index]);
+    bool Undef = std::get<1>(Data[Index]);
+    EXPECT_EQ(canCreatePoison(cast<Operator>(&I)), Poison)
+        << "Incorrect answer of canCreatePoison at instruction " << Index
+        << " = " << I;
+    EXPECT_EQ(canCreateUndef(cast<Operator>(&I), false), Undef)
+        << "Incorrect answer of canCreateUndef at instruction " << Index
+        << " = " << I;
+    EXPECT_EQ(canCreateUndef(cast<Operator>(&I), true), Undef || Poison)
+        << "Incorrect answer of canCreateUndef at instruction " << Index
+        << " = " << I;
     Index++;
   }
 }
 
 TEST_F(ComputeKnownBitsTest, ComputeKnownBits) {
   parseAssembly(
       "define i32 @test(i32 %a, i32 %b) {\n"
       "  %ash = mul i32 %a, 8\n"