[ValueTracking] isKnownNonZero, computeKnownBits for freeze

[aqjune]

Summary

This implements support for isKnownNonZero, computeKnownBits when freeze is involved.

  br (x != 0), BB1, BB2
BB1:
  y = freeze x

In the above program, we can say that y is non-zero. The reason is as follows:

(1) If x was poison, br (x != 0) raised UB
(2) If x was fully undef, the branch again raised UB
(3) If x was non-zero partially undef, say undef | 1, freeze x will return a nondeterministic value which is also non-zero.
(4) If x was just a concrete value, it is trivial

[aqjune]

Consider alloca/undef too, minor update

[jdoerfert]

llvm/include/llvm/Analysis/ValueTracking.h

623–628

We should consider having 3 API functions now. isUndef, isPoison, isUndefOrPoison, with a common impl that takes two booleans. It makes it clearer at the call sites (IMHO).

[reames]

llvm/include/llvm/Analysis/ValueTracking.h

623–628

I agree, this is a very confusing API.

llvm/lib/Analysis/ValueTracking.cpp

1853

I don't think this is worth adding. Such a freeze is trivial, and I'd expect the optimizer to simply remove it instead.

4796–4797

Please test these additions through an existing user, separate and commit separately please.

4802

Same here.

4809

We've ended up with potentially very deep recursion here. In general, ValueTracking works with a small fixed depth window. I think we need to add the same here. (Should be done as a separate patch.)

Note: I don't think we can have a cycle in the graph since we only allow constant arguments to phis.

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

4809

Made a separate patch here: https://reviews.llvm.org/D76010

[aqjune]

Leave value analysis-related parts only

[aqjune]

Update

[fpichet]

What is the status of this patch?
I've seen cases in a out of tree target where an optimization dependent on ValueTracking was not performed because there was a freeze in the way.

[aqjune]

In D75808#2259962, @fpichet wrote:

What is the status of this patch?
I've seen cases in a out of tree target where an optimization dependent on ValueTracking was not performed because there was a freeze in the way.

Hi, this patch has a dependency on D84242; I'll rebase the patch.

llvm/lib/Analysis/ValueTracking.cpp

1853

KnownBits analysis on freeze can be done when the operand is partially undef. (isGuaranteedNotToBePoison vs. isGuaranteedNotToBeUndefOrPoison)

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

1853

And we can do that because "computeKnownBits" provides a "KnownBits or poison" result and not a "KnownBits or undef/poison" result, right?

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

1853

Yes, that's true. Take this example:

y = or i8 x, 1
y.fr = freeze y

The current implementation of computeKnownBits(y) will answer that the LSB of y is one, and this means that y is either poison or any value. y can be poison because or poison, 1 is poison. However, y cannot be full undef because or x, 1 cannot return full undef.

[fpichet]

Another thing: I noticed that SelectionDAG::computeKnownBits doesn't deal with ISD::FREEZE.
Would it be ok to just call computeKnownBits (Op.getOperand(0)) to make it work.
(Since Select_FREEZE just lower to a copy)

[aqjune]

In D75808#2260866, @fpichet wrote:

Another thing: I noticed that SelectionDAG::computeKnownBits doesn't deal with ISD::FREEZE.
Would it be ok to just call computeKnownBits (Op.getOperand(0)) to make it work.
(Since Select_FREEZE just lower to a copy)

It depends on whether SelDag has a poison value - does anyone know whether it has one?

[spatel]

In D75808#2260906, @aqjune wrote:

In D75808#2260866, @fpichet wrote:

Another thing: I noticed that SelectionDAG::computeKnownBits doesn't deal with ISD::FREEZE.
Would it be ok to just call computeKnownBits (Op.getOperand(0)) to make it work.
(Since Select_FREEZE just lower to a copy)

It depends on whether SelDag has a poison value - does anyone know whether it has one?

We have nsw/nuw/exact flags on nodes, so that means poison exists?

[aqjune]

Rebase

[aqjune]

In D75808#2261305, @spatel wrote:

In D75808#2260906, @aqjune wrote:

It depends on whether SelDag has a poison value - does anyone know whether it has one?

We have nsw/nuw/exact flags on nodes, so that means poison exists?

I think so. Whether calling computeKnownBits (Op.getOperand(0)) is valid in SelDag seems non trivial then.

[nikic]

LGTM. This does seem useful as at least assumes and dominating conditions always imply non-poison.

llvm/lib/Analysis/ValueTracking.cpp

1854

Should be Depth + 1 here?

2564

Please fix this tidy warning.

[aqjune]

Address comments

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
 //
 //===----------------------------------------------------------------------===//
 //
bool isGuaranteedToExecuteForEveryIteration(const Instruction *I,
                                               const Loop *L);
 
   /// Return true if I yields poison or raises UB if any of its operands is
   /// poison.
   /// Formally, given I = `r = op v1 v2 .. vN`, propagatesPoison returns true
   /// if, for all i, r is evaluated to poison or op raises UB if vi = poison.
   /// To filter out operands that raise UB on poison, you can use
   /// getGuaranteedNonPoisonOp.
-  bool propagatesPoison(const Instruction *I);
+  bool propagatesPoison(const Operator *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 poison
-  /// value.
+  /// undefined behavior if I is executed and that operand has either a poison
+  /// or a fully undef value.
+  const Value *getGuaranteedNonUndefOrPoisonOp(const Instruction *I);
   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 poison value at the point of execution.
+  /// when I is executed with any operands which appear in KnownUndefOrPoison
+  /// holding a poison or fully undef value at the point of execution.
   bool mustTriggerUB(const Instruction *I,
-                     const SmallSet<const Value *, 16>& KnownPoison);
+                     const SmallSet<const Value *, 16>& KnownUndefOrPoison);
 
-  /// Return true if this function can prove that if PoisonI is executed
-  /// and yields a poison value, then that will trigger undefined behavior.
+  /// Return true if this function can prove that if Inst is executed
+  /// and yields a poison or a fully undef 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);
+  /// the parent of Inst.
+  bool programUndefinedIfUndefOrPoison(const Instruction *Inst);
+  bool programUndefinedIfPoison(const Instruction *Inst);
 
-  /// canCreateUndefOrPoison returns true if Op can create undef or poison from
-  /// non-undef & non-poison operands.
+  /// canCreateUndefOrPoison returns true if Op can create undef bits or poison
+  /// from non-undef & non-poison operands.
   /// For vectors, canCreateUndefOrPoison returns true if there is potential
   /// poison or undef in any element of the result when vectors without
   /// undef/poison poison are given as operands.
   /// For example, given `Op = shl <2 x i32> %x, <0, 32>`, this function returns
   /// true. If Op raises immediate UB but never creates poison or undef
   /// (e.g. sdiv I, 0), canCreatePoison returns false.
   ///
   /// canCreatePoison returns true if Op can create poison from non-poison
   /// operands.
   bool canCreateUndefOrPoison(const Operator *Op);
   bool canCreatePoison(const Operator *Op);
 
-  /// Return true if this function can prove that V is never undef value
-  /// or poison value. If V is an aggregate value or vector, check whether all
-  /// elements (except padding) are not undef or poison.
+  /// Return true if this function can prove that V does not have undef bits or
+  /// and is never poison. If V is an aggregate value or vector, check whether
+  /// all elements (except padding) are not undef or poison.
   /// Note that this is different from canCreateUndefOrPoison because the
   /// function assumes Op's operands are not poison/undef.
   ///
   /// 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,
                                         const Instruction *CtxI = nullptr,
                                         const DominatorTree *DT = nullptr,
                                         unsigned Depth = 0);
+  bool isGuaranteedNotToBePoison(const Value *V,
+                                 const Instruction *CtxI = nullptr,
+                                 const DominatorTree *DT = nullptr,
+                                 unsigned Depth = 0);
 
   /// Specific patterns of select instructions we can match.
   enum SelectPatternFlavor {
     SPF_UNKNOWN = 0,
     SPF_SMIN,                   /// Signed minimum
     SPF_UMIN,                   /// Unsigned minimum
     SPF_SMAX,                   /// Signed maximum
     SPF_UMAX,                   /// Unsigned maximum

llvm/lib/Analysis/ScalarEvolution.cpp

 //===- ScalarEvolution.cpp - Scalar Evolution Analysis --------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
bool ScalarEvolution::isAddRecNeverPoison(const Instruction *I, const Loop *L) {
   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 (propagatesPoison(cast<Instruction>(PoisonUser))) {
+      if (propagatesPoison(cast<Operator>(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

 //===- 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
 //
 //===----------------------------------------------------------------------===//
 //
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) {
         case Intrinsic::smul_with_overflow:
           computeKnownBitsMul(II->getArgOperand(0), II->getArgOperand(1), false,
                               DemandedElts, Known, Known2, Depth, Q);
           break;
         }
       }
     }
     break;
+  case Instruction::Freeze:
+    if (isGuaranteedNotToBePoison(I->getOperand(0), Q.CxtI, Q.DT, Depth))
+      computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
+    break;
   }
 }
 
 /// Determine which bits of V are known to be either zero or one and return
 /// them.
 KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts,
                            unsigned Depth, const Query &Q) {
   KnownBits Known(getBitWidth(V->getType(), Q.DL));
else if (const auto *EEI = dyn_cast<ExtractElementInst>(V)) {
     const Value *Idx = EEI->getIndexOperand();
     auto *CIdx = dyn_cast<ConstantInt>(Idx);
     unsigned NumElts = cast<FixedVectorType>(Vec->getType())->getNumElements();
     APInt DemandedVecElts = APInt::getAllOnesValue(NumElts);
     if (CIdx && CIdx->getValue().ult(NumElts))
       DemandedVecElts = APInt::getOneBitSet(NumElts, CIdx->getZExtValue());
     return isKnownNonZero(Vec, DemandedVecElts, Depth, Q);
   }
+  // Freeze
+  else if (const FreezeInst *FI = dyn_cast<FreezeInst>(V)) {
+    auto Op = FI->getOperand(0);
+    if (isKnownNonZero(Op, Depth, Q) &&
+        isGuaranteedNotToBePoison(Op, Q.CxtI, Q.DT, Depth))
+      return true;
+  }
 
   KnownBits Known(BitWidth);
   computeKnownBits(V, DemandedElts, Known, Depth, Q);
   return Known.One != 0;
 }
 
 bool isKnownNonZero(const Value* V, unsigned Depth, const Query& Q) {
   // FIXME: We currently have no way to represent the DemandedElts of a scalable

 bool llvm::canCreateUndefOrPoison(const Operator *Op) {
   return ::canCreateUndefOrPoison(Op, /*PoisonOnly=*/false);
 }
 
 bool llvm::canCreatePoison(const Operator *Op) {
   return ::canCreateUndefOrPoison(Op, /*PoisonOnly=*/true);
 }
 
-bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V,
+static bool programUndefinedIfUndefOrPoison(const Instruction *Inst,
+                                            bool PoisonOnly);
+
+static bool isGuaranteedNotToBeUndefOrPoison(const Value *V,
                                              const Instruction *CtxI,
                                              const DominatorTree *DT,
-                                            unsigned Depth) {
+                                             unsigned Depth,
+                                             bool PoisonOnly) {
   if (Depth >= MaxDepth)
     return false;
 
   if (const auto *A = dyn_cast<Argument>(V)) {
     if (A->hasAttribute(Attribute::NoUndef))
       return true;
   }
 
   if (auto *C = dyn_cast<Constant>(V)) {
-    if (isa<UndefValue>(C))
+    if (!PoisonOnly && isa<UndefValue>(C))
       return false;
 
     if (isa<ConstantInt>(C) || isa<GlobalVariable>(C) || isa<ConstantFP>(V) ||
         isa<ConstantPointerNull>(C) || isa<Function>(C))
       return true;
 
     if (C->getType()->isVectorTy())
-      return !C->containsUndefElement() && !C->containsConstantExpression();
+      return (PoisonOnly || !C->containsUndefElement()) &&
+              !C->containsConstantExpression();
   }
 
   // Strip cast operations from a pointer value.
   // Note that stripPointerCastsSameRepresentation can strip off getelementptr
   // inbounds with zero offset. To guarantee that the result isn't poison, the
   // stripped pointer is checked as it has to be pointing into an allocated
   // object or be null `null` to ensure `inbounds` getelement pointers with a
   // zero offset could not produce poison.
   // It can strip off addrspacecast that do not change bit representation as
   // well. We believe that such addrspacecast is equivalent to no-op.
   auto *StrippedV = V->stripPointerCastsSameRepresentation();
   if (isa<AllocaInst>(StrippedV) || isa<GlobalVariable>(StrippedV) ||
       isa<Function>(StrippedV) || isa<ConstantPointerNull>(StrippedV))
     return true;
 
   auto OpCheck = [&](const Value *V) {
-    return isGuaranteedNotToBeUndefOrPoison(V, CtxI, DT, Depth + 1);
+    return isGuaranteedNotToBeUndefOrPoison(V, CtxI, DT, Depth + 1, PoisonOnly);
   };
 
   if (auto *Opr = dyn_cast<Operator>(V)) {
     // If the value is a freeze instruction, then it can never
     // be undef or poison.
     if (isa<FreezeInst>(V))
       return true;
 
     if (const auto *CB = dyn_cast<CallBase>(V)) {
       if (CB->hasRetAttr(Attribute::NoUndef))
         return true;
     }
 
-    if (canCreateUndefOrPoison(Opr))
-      return false;
-
-    if (all_of(Opr->operands(), OpCheck))
+    if (!canCreateUndefOrPoison(Opr, PoisonOnly) &&
+        all_of(Opr->operands(), OpCheck))
       return true;
   }
 
   if (auto *I = dyn_cast<Instruction>(V)) {
-    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.
+    // If V is undef, it should be i1 type, otherwise it can be partially undef
+    if ((PoisonOnly || I->getType()->isIntegerTy(1)) &&
+        programUndefinedIfUndefOrPoison(I, PoisonOnly))
       return true;
   }
 
   // CxtI may be null or a cloned instruction.
   if (!CtxI || !CtxI->getParent() || !DT)
     return false;
 
   auto *DNode = DT->getNode(CtxI->getParent());
   if (!DNode)
     // Unreachable block
     return false;
 
   // If V is used as a branch condition before reaching CtxI, V cannot be
   // undef or poison.
   //   br V, BB1, BB2
   // BB1:
   //   CtxI ; V cannot be undef or poison here
   auto *Dominator = DNode->getIDom();
   while (Dominator) {
     auto *TI = Dominator->getBlock()->getTerminator();
 
+    Value *Cond = nullptr;
     if (auto BI = dyn_cast<BranchInst>(TI)) {
-      if (BI->isConditional() && BI->getCondition() == V)
-        return true;
+      if (BI->isConditional())
+        Cond = BI->getCondition();
     } else if (auto SI = dyn_cast<SwitchInst>(TI)) {
-      if (SI->getCondition() == V)
+      Cond = SI->getCondition();
+    }
+
+    if (Cond) {
+      if (Cond == V)
+        return true;
+      else if (PoisonOnly && isa<Operator>(Cond)) {
+        auto *Opr = cast<Operator>(Cond);
+        if (propagatesPoison(Opr) &&
+            any_of(Opr->operand_values(), [&](Value *Op) { return Op == V; }))
           return true;
       }
+    }
 
     Dominator = Dominator->getIDom();
   }
 
   return false;
 }
 
+bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V,
+                                            const Instruction *CtxI,
+                                            const DominatorTree *DT,
+                                            unsigned Depth) {
+  return ::isGuaranteedNotToBeUndefOrPoison(V, CtxI, DT, Depth, false);
+}
+
+bool llvm::isGuaranteedNotToBePoison(const Value *V, const Instruction *CtxI,
+                                     const DominatorTree *DT, unsigned Depth) {
+  return ::isGuaranteedNotToBeUndefOrPoison(V, CtxI, DT, Depth, true);
+}
+
 OverflowResult llvm::computeOverflowForSignedAdd(const AddOperator *Add,
                                                  const DataLayout &DL,
                                                  AssumptionCache *AC,
                                                  const Instruction *CxtI,
                                                  const DominatorTree *DT) {
   return ::computeOverflowForSignedAdd(Add->getOperand(0), Add->getOperand(1),
                                        Add, DL, AC, CxtI, DT);
 }
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::propagatesPoison(const Instruction *I) {
+bool llvm::propagatesPoison(const Operator *I) {
   switch (I->getOpcode()) {
   case Instruction::Freeze:
   case Instruction::Select:
   case Instruction::PHI:
   case Instruction::Call:
   case Instruction::Invoke:
     return false;
   case Instruction::ICmp:
   case Instruction::FCmp:
   case Instruction::GetElementPtr:
     return true;
   default:
     if (isa<BinaryOperator>(I) || isa<UnaryOperator>(I) || isa<CastInst>(I))
       return true;
 
     // Be conservative and return false.
     return false;
   }
 }
 
-const Value *llvm::getGuaranteedNonPoisonOp(const Instruction *I) {
+const Value *llvm::getGuaranteedNonUndefOrPoisonOp(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:
case Instruction::Call:
       }
       return nullptr;
 
     default:
       return nullptr;
   }
 }
 
+const Value *llvm::getGuaranteedNonPoisonOp(const Instruction *I) {
+  // If passing undef to a specific operand of an instruction is UB, passing
+  // poison is also UB.
+  return getGuaranteedNonUndefOrPoisonOp(I);
+}
+
 bool llvm::mustTriggerUB(const Instruction *I,
-                         const SmallSet<const Value *, 16>& KnownPoison) {
-  auto *NotPoison = getGuaranteedNonPoisonOp(I);
-  return (NotPoison && KnownPoison.count(NotPoison));
+                         const SmallSet<const Value *, 16>& KnownUndefOrPoison) {
+  auto *NotUndefOrPoison = getGuaranteedNonUndefOrPoisonOp(I);
+  return (NotUndefOrPoison && KnownUndefOrPoison.count(NotUndefOrPoison));
 }
 
 
-bool llvm::programUndefinedIfPoison(const Instruction *PoisonI) {
+// Checks whether a program raises UB if Inst returned undef or poison.
+// If PoisonOnly is true, it is assumed that Inst returned poison.
+static bool programUndefinedIfUndefOrPoison(const Instruction *Inst,
+                                            bool PoisonOnly) {
   // 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.
+  // executed given that Inst 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();
+  const BasicBlock *BB = Inst->getParent();
 
-  // Set of instructions that we have proved will yield poison if PoisonI
+  // Set of instructions that we have proved will yield undef or poison if Inst
   // does.
-  SmallSet<const Value *, 16> YieldsPoison;
+  SmallSet<const Value *, 16> YieldsUndefOrPoison;
   SmallSet<const BasicBlock *, 4> Visited;
-  YieldsPoison.insert(PoisonI);
-  Visited.insert(PoisonI->getParent());
+  YieldsUndefOrPoison.insert(Inst);
+  Visited.insert(Inst->getParent());
 
-  BasicBlock::const_iterator Begin = PoisonI->getIterator(), End = BB->end();
+  BasicBlock::const_iterator Begin = Inst->getIterator(), End = BB->end();
 
   unsigned Iter = 0;
   while (Iter++ < MaxDepth) {
     for (auto &I : make_range(Begin, End)) {
-      if (&I != PoisonI) {
-        if (mustTriggerUB(&I, YieldsPoison))
+      if (&I != Inst) {
+        if (mustTriggerUB(&I, YieldsUndefOrPoison))
           return true;
         if (!isGuaranteedToTransferExecutionToSuccessor(&I))
           return false;
       }
 
       // Mark poison that propagates from I through uses of I.
-      if (YieldsPoison.count(&I)) {
+      if (PoisonOnly && YieldsUndefOrPoison.count(&I)) {
         for (const User *User : I.users()) {
           const Instruction *UserI = cast<Instruction>(User);
-          if (propagatesPoison(UserI))
-            YieldsPoison.insert(User);
+          if (propagatesPoison(cast<Operator>(UserI)))
+            YieldsUndefOrPoison.insert(User);
         }
       }
     }
 
     if (auto *NextBB = BB->getSingleSuccessor()) {
       if (Visited.insert(NextBB).second) {
         BB = NextBB;
         Begin = BB->getFirstNonPHI()->getIterator();
         End = BB->end();
         continue;
       }
     }
 
     break;
   }
   return false;
 }
 
+bool llvm::programUndefinedIfUndefOrPoison(const Instruction *Inst) {
+  return ::programUndefinedIfUndefOrPoison(Inst, false);
+}
+
+bool llvm::programUndefinedIfPoison(const Instruction *Inst) {
+  return ::programUndefinedIfUndefOrPoison(Inst, true);
+}
+
 static bool isKnownNonNaN(const Value *V, FastMathFlags FMF) {
   if (FMF.noNaNs())
     return true;
 
   if (auto *C = dyn_cast<ConstantFP>(V))
     return !C->isNaN();
 
   if (auto *C = dyn_cast<ConstantDataVector>(V)) {

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) {
       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 (propagatesPoison(&I))
+      if (propagatesPoison(cast<Operator>(&I)))
         for (Value *V : I.operands())
           Checks.push_back(getPoisonFor(ValToPoison, V));
 
       if (canCreatePoison(cast<Operator>(&I)))
         generateCreationChecks(I, Checks);
       ValToPoison[&I] = buildOrChain(B, Checks);
     }
 

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
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 (!propagatesPoison(I) && I != Root)
+    if (!propagatesPoison(cast<Operator>(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/test/Transforms/InstSimplify/known-non-zero.ll

for.body:                                         ; preds = %for.cond
   %conv = zext i8 %0 to i32
   %mul = shl nuw nsw i32 %shift.0, 3
   %shl = shl nuw nsw i32 %conv, %mul
   %1 = trunc i32 %shl to i8
   %conv2 = or i8 %result.0, %1
   %inc = add nuw nsw i32 %shift.0, 1
   br label %for.cond
 }
+
+define i1 @freeze_nonzero(i8 %x, i8 %mask) {
+; CHECK-LABEL: @freeze_nonzero(
+; CHECK-NEXT:    [[Y:%.*]] = or i8 [[X:%.*]], [[MASK:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = icmp ne i8 [[Y]], 0
+; CHECK-NEXT:    br i1 [[C]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    ret i1 false
+; CHECK:       B:
+; CHECK-NEXT:    ret i1 false
+;
+  %y = or i8 %x, %mask
+  %c = icmp ne i8 %y, 0
+  br i1 %c, label %A, label %B
+A:
+  %fr = freeze i8 %y
+  %c2 = icmp eq i8 %fr, 0
+  ret i1 %c2
+B:
+  ret i1 0
+}
 No newline at end of file

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
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/ConstantRange.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/SourceMgr.h"
TEST(ValueTracking, propagatesPoison) {
   assert(F && "Bad assembly?");
 
   auto &BB = F->getEntryBlock();
 
   int Index = 0;
   for (auto &I : BB) {
     if (isa<ReturnInst>(&I))
       break;
-    EXPECT_EQ(propagatesPoison(&I), Data[Index].first)
+    EXPECT_EQ(propagatesPoison(cast<Operator>(&I)), Data[Index].first)
         << "Incorrect answer at instruction " << Index << " = " << I;
     Index++;
   }
 }
 
+TEST_F(ValueTrackingTest, programUndefinedIfPoison) {
+  parseAssembly(
+      "declare i32 @any_num()"
+      "define void @test(i32 %mask) {\n"
+      "  %A = call i32 @any_num()\n"
+      "  %B = or i32 %A, %mask\n"
+      "  udiv i32 1, %B"
+      "  ret void\n"
+      "}\n");
+  // If %A was poison, udiv raises UB regardless of %mask's avlue
+  EXPECT_EQ(programUndefinedIfPoison(A), true);
+}
+
+TEST_F(ValueTrackingTest, programUndefinedIfUndefOrPoison) {
+  parseAssembly(
+      "declare i32 @any_num()"
+      "define void @test(i32 %mask) {\n"
+      "  %A = call i32 @any_num()\n"
+      "  %B = or i32 %A, %mask\n"
+      "  udiv i32 1, %B"
+      "  ret void\n"
+      "}\n");
+  // If %A was undef and %mask was 1, udiv does not raise UB
+  EXPECT_EQ(programUndefinedIfUndefOrPoison(A), false);
+}
+
+TEST_F(ValueTrackingTest, isGuaranteedNotToBePoison_exploitBranchCond) {
+  parseAssembly(
+      "declare i1 @any_bool()"
+      "define void @test(i1 %y) {\n"
+      "  %A = call i1 @any_bool()\n"
+      "  %cond = and i1 %A, %y\n"
+      "  br i1 %cond, label %BB1, label %BB2\n"
+      "BB1:\n"
+      "  ret void\n"
+      "BB2:\n"
+      "  ret void\n"
+      "}\n");
+  DominatorTree DT(*F);
+  for (auto &BB : *F) {
+    if (&BB == &F->getEntryBlock())
+      continue;
+
+    EXPECT_EQ(isGuaranteedNotToBePoison(A, BB.getTerminator(), &DT), true)
+        << "isGuaranteedNotToBePoison does not hold at " << *BB.getTerminator();
+  }
+}
+
 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?, can create undef?, IR instruction)
   SmallVector<std::pair<std::pair<bool, bool>, std::string>, 32> Data = {
parseAssembly(
       "declare void @llvm.assume(i1)\n");
   AssumptionCache AC(*F);
   KnownBits Known = computeKnownBits(
       A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
   EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
   EXPECT_EQ(Known.One.getZExtValue(), 0u);
 }
 
+TEST_F(ComputeKnownBitsTest, ComputeKnownBitsFreeze) {
+  parseAssembly(
+      "define void @test() {\n"
+      "  %m = call i32 @any_num()\n"
+      "  %A = freeze i32 %m\n"
+      "  %n = and i32 %m, 31\n"
+      "  %c = icmp eq i32 %n, 0\n"
+      "  call void @llvm.assume(i1 %c)\n"
+      "  ret void\n"
+      "}\n"
+      "declare void @llvm.assume(i1)\n"
+      "declare i32 @any_num()\n");
+  AssumptionCache AC(*F);
+  KnownBits Known = computeKnownBits(
+      A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
+  EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
+  EXPECT_EQ(Known.One.getZExtValue(), 0u);
+}
+
 class IsBytewiseValueTest : public ValueTrackingTest,
                             public ::testing::WithParamInterface<
                                 std::pair<const char *, const char *>> {
 protected:
 };
 
 const std::pair<const char *, const char *> IsBytewiseValueTests[] = {
     {