[ValueTracking] Let analyses assume a value cannot be partially poison

[aqjune]

Summary

This is RFC for fixes in poison-related functions of ValueTracking.
These functions assume that a value can be poison bitwisely, but the semantics
of bitwise poison is not clear at the moment.
Allowing a value to have bitwise poison adds complexity to reasoning about
correctness of optimizations.

This patch makes the analysis functions simply assume that a value is
either fully poison or not, which has been used to understand the correctness
of a few previous optimizations.
The bitwise poison semantics seems to be only used by these functions as well.

In terms of implementation, using value-wise poison concept makes existing
functions do more precise analysis, which is what this patch contains.

[nikic]

llvm/include/llvm/Analysis/ValueTracking.h

568

This doesn't seem to line up with the implementation, e.g. division ops return true for propagatesPoison.

I'm also not sure why we would not want to return true for immediate UB. It's a stronger condition, but it should always be fine to relax immediate UB into returning poison.

[aqjune]

Correctly handle div/rems

[aqjune]

llvm/include/llvm/Analysis/ValueTracking.h

568

Thanks, fixed.

I'm also not sure why we would not want to return true for immediate UB. It's a stronger condition, but it should always be fine to relax immediate UB into returning poison.

I think this is more natural in the sense that the operation wouldn't return a value when UB happened; it immediately exits the program.
It is analogous to what canCreatePoison(I) returns when I raises UB as well.

[aqjune]

Add unit tests for propagatesPoison

[aqjune]

Rebase

[jdoerfert]

llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp

348

Is this true? I mean, don't you check for binary operands above?

llvm/test/Analysis/ScalarEvolution/nsw.ll

242 ↗

(On Diff #259029)

Given the name of the function I tried to figure out what the reasoning here is.

1. This patch is not NFC. Maybe split the wording changes from the functional ones.
2. It seems valid to derive both nuw and nsw here but we should confirm with the history and the author of this test.

242 ↗

(On Diff #259029)

Forget the NFC part but we could still split the wording changes from the rest ;)

[aqjune]

Leave wording changes only

[aqjune]

I'll make a separate patch for the functional changes.
BTW, regarding the lldb failure that happened on the previous version of this patch, I ran ninja check-all on my ARM machine (with lldb included in the enable_project list) and couldn't reproduce the error. :/ As the patch is being separated, it will be a good chance to see which part is the root cause.

llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp

348

It was my misunderstanding about the code, updated.

[aqjune]

llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp

348

BTW, what do you think about making this explicit in LangRef? I can make a patch for this.
If and/or blocks poison propagation, removal of trivial and/ors becomes invalid, because it makes the resulting program more poisonous.

[jdoerfert]

This patch now only removes the Full part from the comments and names? If so, I think that makes sense. Let someone else give a second opinion though.

llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp

348

That's a good question. I guess we could either say that bits you "overwrite" with and/or are not poison anymore but I am unsure that is what we want. The problem is that various operations could be used to fix bits and we should handle them all the same (x = y - y, x = y * 0, ...).

That said, we should have a discussion (= ask others).

[nikic]

LG from my side. I believe this matches how we have been treating poison in practice, and matches what is most useful. The bitwise reasoning we do for undef is something of a PITA.

[aqjune]

llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp

348

I can run Alive2 with several semantics on or/and & see what kind of optimizations are allowed/disallowed. It may take some time, but can be done by Friday.
I'll leave the result + references to relevant people at D78615.

llvm/include/llvm/Analysis/ValueTracking.h

class Value;
   /// Return true if this function can prove that the instruction I
   /// is executed for every iteration of the loop L.
   ///
   /// Note that this currently only considers the loop header.
   bool isGuaranteedToExecuteForEveryIteration(const Instruction *I,
                                               const Loop *L);
 
   /// Return true if this function can prove that I is guaranteed to yield
-  /// full-poison (all bits poison) if at least one of its operands are
-  /// full-poison (all bits poison).
-  ///
-  /// The exact rules for how poison propagates through instructions have
-  /// not been settled as of 2015-07-10, so this function is conservative
-  /// and only considers poison to be propagated in uncontroversial
-  /// cases. There is no attempt to track values that may be only partially
-  /// poison.
-  bool propagatesFullPoison(const Instruction *I);
+  /// poison if at least one of its operands is poison.
+  bool propagatesPoison(const Instruction *I);
 
   /// Return either nullptr or an operand of I such that I will trigger
-  /// undefined behavior if I is executed and that operand has a full-poison
-  /// value (all bits poison).
-  const Value *getGuaranteedNonFullPoisonOp(const Instruction *I);
+  /// undefined behavior if I is executed and that operand has a poison
+  /// value.
+  const Value *getGuaranteedNonPoisonOp(const Instruction *I);
 
   /// Return true if the given instruction must trigger undefined behavior.
   /// when I is executed with any operands which appear in KnownPoison holding
-  /// a full-poison value at the point of execution.
+  /// a poison value at the point of execution.
   bool mustTriggerUB(const Instruction *I,
                      const SmallSet<const Value *, 16>& KnownPoison);
 
   /// Return true if this function can prove that if PoisonI is executed
-  /// and yields a full-poison value (all bits poison), then that will
-  /// trigger undefined behavior.
+  /// 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 programUndefinedIfFullPoison(const Instruction *PoisonI);
+  bool programUndefinedIfPoison(const Instruction *PoisonI);
 
   /// Return true if I 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),
   /// canCreatePoison returns false.

llvm/lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::isSCEVExprNeverPoison(const Instruction *I) {
   // requires computing the SCEV of the operands, which can be expensive. This
   // check we can do cheaply to rule out some cases early.
   Loop *InnermostContainingLoop = LI.getLoopFor(I->getParent());
   if (InnermostContainingLoop == nullptr ||
       InnermostContainingLoop->getHeader() != I->getParent())
     return false;
 
   // Only proceed if we can prove that I does not yield poison.
-  if (!programUndefinedIfFullPoison(I))
+  if (!programUndefinedIfPoison(I))
     return false;
 
   // At this point we know that if I is executed, then it does not wrap
   // according to at least one of NSW or NUW. If I is not executed, then we do
   // not know if the calculation that I represents would wrap. Multiple
   // instructions can map to the same SCEV. If we apply NSW or NUW from I to
   // the SCEV, we must guarantee no wrapping for that SCEV also when it is
   // derived from other instructions that map to the same SCEV. We cannot make
bool ScalarEvolution::isAddRecNeverPoison(const Instruction *I, const Loop *L) {
   auto *LatchBB = L->getLoopLatch();
   if (!ExitingBB || !LatchBB || ExitingBB != LatchBB)
     return false;
 
   SmallPtrSet<const Instruction *, 16> Pushed;
   SmallVector<const Instruction *, 8> PoisonStack;
 
   // We start by assuming \c I, the post-inc add recurrence, is poison.  Only
-  // things that are known to be fully poison under that assumption go on the
+  // things that are known to be poison under that assumption go on the
   // PoisonStack.
   Pushed.insert(I);
   PoisonStack.push_back(I);
 
   bool LatchControlDependentOnPoison = false;
   while (!PoisonStack.empty() && !LatchControlDependentOnPoison) {
     const Instruction *Poison = PoisonStack.pop_back_val();
 
     for (auto *PoisonUser : Poison->users()) {
-      if (propagatesFullPoison(cast<Instruction>(PoisonUser))) {
+      if (propagatesPoison(cast<Instruction>(PoisonUser))) {
         if (Pushed.insert(cast<Instruction>(PoisonUser)).second)
           PoisonStack.push_back(cast<Instruction>(PoisonUser));
       } else if (auto *BI = dyn_cast<BranchInst>(PoisonUser)) {
         assert(BI->isConditional() && "Only possibility!");
         if (BI->getParent() == LatchBB) {
           LatchControlDependentOnPoison = true;
           break;
         }

llvm/lib/Analysis/ValueTracking.cpp

bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V,
   if (auto II = dyn_cast<ICmpInst>(V)) {
     if (llvm::all_of(II->operands(), [](const Value *V) {
           return isGuaranteedNotToBeUndefOrPoison(V);
         }))
       return true;
   }
 
   if (auto I = dyn_cast<Instruction>(V)) {
-    if (programUndefinedIfFullPoison(I) && I->getType()->isIntegerTy(1))
+    if (programUndefinedIfPoison(I) && I->getType()->isIntegerTy(1))
       // Note: once we have an agreement that poison is a value-wise concept,
       // we can remove the isIntegerTy(1) constraint.
       return true;
   }
 
   // CxtI may be null or a cloned instruction.
   if (!CtxI || !CtxI->getParent() || !DT)
     return false;
bool llvm::isGuaranteedToExecuteForEveryIteration(const Instruction *I,
 
   for (const Instruction &LI : *L->getHeader()) {
     if (&LI == I) return true;
     if (!isGuaranteedToTransferExecutionToSuccessor(&LI)) return false;
   }
   llvm_unreachable("Instruction not contained in its own parent basic block.");
 }
 
-bool llvm::propagatesFullPoison(const Instruction *I) {
+bool llvm::propagatesPoison(const Instruction *I) {
   // TODO: This should include all instructions apart from phis, selects and
   // call-like instructions.
   switch (I->getOpcode()) {
   case Instruction::Add:
   case Instruction::Sub:
   case Instruction::Xor:
   case Instruction::Trunc:
   case Instruction::BitCast:
case Instruction::ICmp:
     // instance, x s< (x +nsw 1) can be folded to true.
     return true;
 
   default:
     return false;
   }
 }
 
-const Value *llvm::getGuaranteedNonFullPoisonOp(const Instruction *I) {
+const Value *llvm::getGuaranteedNonPoisonOp(const Instruction *I) {
   switch (I->getOpcode()) {
     case Instruction::Store:
       return cast<StoreInst>(I)->getPointerOperand();
 
     case Instruction::Load:
       return cast<LoadInst>(I)->getPointerOperand();
 
     case Instruction::AtomicCmpXchg:
switch (I->getOpcode()) {
 
     default:
       return nullptr;
   }
 }
 
 bool llvm::mustTriggerUB(const Instruction *I,
                          const SmallSet<const Value *, 16>& KnownPoison) {
-  auto *NotPoison = getGuaranteedNonFullPoisonOp(I);
+  auto *NotPoison = getGuaranteedNonPoisonOp(I);
   return (NotPoison && KnownPoison.count(NotPoison));
 }
 
 
-bool llvm::programUndefinedIfFullPoison(const Instruction *PoisonI) {
+bool llvm::programUndefinedIfPoison(const Instruction *PoisonI) {
   // We currently only look for uses of poison values within the same basic
   // block, as that makes it easier to guarantee that the uses will be
   // executed given that PoisonI is executed.
   //
   // FIXME: Expand this to consider uses beyond the same basic block. To do
   // this, look out for the distinction between post-dominance and strong
   // post-dominance.
   const BasicBlock *BB = PoisonI->getParent();
for (auto &I : make_range(Begin, End)) {
         if (!isGuaranteedToTransferExecutionToSuccessor(&I))
           return false;
       }
 
       // Mark poison that propagates from I through uses of I.
       if (YieldsPoison.count(&I)) {
         for (const User *User : I.users()) {
           const Instruction *UserI = cast<Instruction>(User);
-          if (propagatesFullPoison(UserI))
+          if (propagatesPoison(UserI))
             YieldsPoison.insert(User);
         }
       }
     }
 
     if (auto *NextBB = BB->getSingleSuccessor()) {
       if (Visited.insert(NextBB).second) {
         BB = NextBB;

llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp

static bool rewrite(Function &F) {
   for (BasicBlock &BB : F)
     for (Instruction &I : BB) {
       if (isa<PHINode>(I)) continue;
 
       IRBuilder<> B(cast<Instruction>(&I));
       
       // Note: There are many more sources of documented UB, but this pass only
       // attempts to find UB triggered by propagation of poison.
-      if (Value *Op = const_cast<Value*>(getGuaranteedNonFullPoisonOp(&I)))
+      if (Value *Op = const_cast<Value*>(getGuaranteedNonPoisonOp(&I)))
         CreateAssertNot(B, getPoisonFor(ValToPoison, Op));
 
       if (LocalCheck)
         if (auto *RI = dyn_cast<ReturnInst>(&I))
           if (RI->getNumOperands() != 0) {
             Value *Op = RI->getOperand(0);
             CreateAssertNot(B, getPoisonFor(ValToPoison, Op));
           }
 
       SmallVector<Value*, 4> Checks;
-      if (propagatesFullPoison(&I))
+      if (propagatesPoison(&I))
         for (Value *V : I.operands())
           Checks.push_back(getPoisonFor(ValToPoison, V));
 
       if (canCreatePoison(&I))
         generateCreationChecks(I, Checks);
       ValToPoison[&I] = buildOrChain(B, Checks);
     }
 
- Strict mode - (i.e. must analyze every operand)
      - Poison through memory
      - Function ABIs
      - Full coverage of intrinsics, etc.. (ouch)
 
    Instructions w/Unclear Semantics:
    - shufflevector - It would seem reasonable for an out of bounds mask element
      to produce poison, but the LangRef does not state.  
    - and/or - It would seem reasonable for poison to propagate from both
-     arguments, but LangRef doesn't state and propagatesFullPoison doesn't
+     arguments, but LangRef doesn't state and propagatesPoison doesn't
      include these two.
    - all binary ops w/vector operands - The likely interpretation would be that
      any element overflowing should produce poison for the entire result, but
      the LangRef does not state.
    - Floating point binary ops w/fmf flags other than (nnan, noinfs).  It seems
      strange that only certian flags should be documented as producing poison.
 
    Cases of clear poison semantics not yet implemented:
    - Exact flags on ashr/lshr produce poison
    - NSW/NUW flags on shl produce poison
    - Inbounds flag on getelementptr produce poison
    - fptosi/fptoui (out of bounds input) produce poison
    - Scalable vector types for insertelement/extractelement
    - Floating point binary ops w/fmf nnan/noinfs flags produce poison
  */

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

while (!Worklist.empty()) {
     const Instruction *I = Worklist.pop_back_val();
 
     // If we know this must trigger UB on a path leading our target.
     if (mustTriggerUB(I, KnownPoison) && DT->dominates(I, OnPathTo))
       return true;
 
     // If we can't analyze propagation through this instruction, just skip it
     // and transitive users.  Safe as false is a conservative result.
-    if (!propagatesFullPoison(I) && I != Root)
+    if (!propagatesPoison(I) && I != Root)
       continue;
 
     if (KnownPoison.insert(I).second)
       for (const User *User : I->users())
         Worklist.push_back(cast<Instruction>(User));
   }
 
   // Might be non-UB, or might have a path we couldn't prove must execute on

llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

if (LHS->getType() == RHS->getType()) {
         RecursivelyDeleteTriviallyDeadInstructions(I);
         return true;
       }
     }
   }
 
   // Add I to DominatingExprs if it's an add/sub that can't sign overflow.
   if (match(I, m_NSWAdd(m_Value(LHS), m_Value(RHS)))) {
-    if (programUndefinedIfFullPoison(I)) {
+    if (programUndefinedIfPoison(I)) {
       const SCEV *Key =
           SE->getAddExpr(SE->getUnknown(LHS), SE->getUnknown(RHS));
       DominatingAdds[Key].push_back(I);
     }
   } else if (match(I, m_NSWSub(m_Value(LHS), m_Value(RHS)))) {
-    if (programUndefinedIfFullPoison(I)) {
+    if (programUndefinedIfPoison(I)) {
       const SCEV *Key =
           SE->getAddExpr(SE->getUnknown(LHS), SE->getUnknown(RHS));
       DominatingSubs[Key].push_back(I);
     }
   }
   return false;
 }
 

llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll

 loop2:
   %f = load float, float* %ptr, align 4
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop
 exit:
   ret void
 }
 
-; Demonstrate why we need a Visited set in llvm::programUndefinedIfFullPoison.
+; Demonstrate why we need a Visited set in llvm::programUndefinedIfPoison.
 define void @test-add-not-header5(float* %input, i32 %offset) {
 ; CHECK-LABEL: @test-add-not-header5
 entry:
   br label %loop
 loop:
   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 
 ; CHECK: %index32 =