[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

580

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

580

I agree, this is a very confusing API.

llvm/lib/Analysis/ValueTracking.cpp

1800

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

4550–4551

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

4554

Same here.

4561

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

4561

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

1800

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

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

1800

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

1800

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

1801

Should be Depth + 1 here?

2470

Please fix this tidy warning.

[aqjune]

Address comments

llvm/include/llvm/Analysis/ValueTracking.h

class Value;
   /// trigger undefined behavior.
   ///
   /// Note that this currently only considers the basic block that is
   /// the parent of I.
   bool programUndefinedIfFullPoison(const Instruction *PoisonI);
 
   /// Return true if this function can prove that V is never undef value
   /// or poison value.
-  //
+  ///
+  /// If AllowUndef is true, it checks whether the value is not poison only.
+  ///
   /// 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,
+  bool isGuaranteedNotToBeUndefOrPoison(const Value *V, bool AllowUndef = false,
                                         const Instruction *CtxI = nullptr,
                                         const DominatorTree *DT = nullptr);
 
   /// 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/InstructionSimplify.cpp

Value *llvm::SimplifyCall(CallBase *Call, const SimplifyQuery &Q) {
   }
 
   return ConstantFoldCall(Call, F, ConstantArgs, Q.TLI);
 }
 
 /// Given operands for a Freeze, see if we can fold the result.
 static Value *SimplifyFreezeInst(Value *Op0, const SimplifyQuery &Q) {
   // Use a utility function defined in ValueTracking.
-  if (llvm::isGuaranteedNotToBeUndefOrPoison(Op0, Q.CxtI, Q.DT))
+  if (llvm::isGuaranteedNotToBeUndefOrPoison(Op0, false, Q.CxtI, Q.DT))
     return Op0;
   // We have room for improvement.
   return nullptr;
 }
 
 Value *llvm::SimplifyFreezeInst(Value *Op0, const SimplifyQuery &Q) {
   return ::SimplifyFreezeInst(Op0, Q);
 }

llvm/lib/Analysis/ValueTracking.cpp

if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) {
         case Intrinsic::smul_with_overflow:
           computeKnownBitsMul(II->getArgOperand(0), II->getArgOperand(1), false,
                               Known, Known2, Depth, Q);
           break;
         }
       }
     }
     break;
+  case Instruction::Freeze:
+    if (isGuaranteedNotToBeUndefOrPoison(I->getOperand(0), true, Q.CxtI, Q.DT))
+      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, unsigned Depth, const Query &Q) {
   KnownBits Known(getBitWidth(V->getType(), Q.DL));
   computeKnownBits(V, Known, Depth, Q);
else if (const PHINode *PN = dyn_cast<PHINode>(V)) {
     }
     // Check if all incoming values are non-zero constant.
     bool AllNonZeroConstants = llvm::all_of(PN->operands(), [](Value *V) {
       return isa<ConstantInt>(V) && !cast<ConstantInt>(V)->isZero();
     });
     if (AllNonZeroConstants)
       return true;
   }
+  // freeze
+  else if (const FreezeInst *FI = dyn_cast<FreezeInst>(V)) {
+    auto Op = FI->getOperand(0);
+    if (isKnownNonZero(Op, Depth, Q) &&
+        isGuaranteedNotToBeUndefOrPoison(Op, true, Q.CxtI, Q.DT))
+      return true;
+  }
 
   KnownBits Known(BitWidth);
   computeKnownBits(V, Known, Depth, Q);
   return Known.One != 0;
 }
 
 /// Return true if V2 == V1 + X, where X is known non-zero.
 static bool isAddOfNonZero(const Value *V1, const Value *V2, const Query &Q) {
auto AllUsesGuardedByBranch = [&](const BranchInst *BI) {
     }
 
     return true;
   };
 
   return llvm::any_of(GuardingBranches, AllUsesGuardedByBranch);
 }
 
-bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V,
+bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V, bool AllowUndef,
                                             const Instruction *CtxI,
                                             const DominatorTree *DT) {
   // If the value is a freeze instruction, then it can never
   // be undef or poison.
   if (isa<FreezeInst>(V))
     return true;
   // TODO: Some instructions are guaranteed to return neither undef
   // nor poison if their arguments are not poison/undef.
 
   // TODO: Deal with other Constant subclasses.
-  if (isa<ConstantInt>(V) || isa<GlobalVariable>(V))
+  if (isa<ConstantInt>(V) || isa<ConstantFP>(V) || isa<GlobalVariable>(V) ||
+      isa<Function>(V))
     return true;
 
+  if (auto BI = dyn_cast<BitCastInst>(V))
+    return isGuaranteedNotToBeUndefOrPoison(BI->getOperand(0), AllowUndef, CtxI,
+                                            DT);
+
   if (auto PN = dyn_cast<PHINode>(V)) {
     if (llvm::all_of(PN->incoming_values(), [](const Use &U) {
           return isa<ConstantInt>(U.get());
         }))
       return true;
   }
 
   if (auto II = dyn_cast<ICmpInst>(V)) {
-    if (llvm::all_of(II->operands(), [](const Value *V) {
-          return isGuaranteedNotToBeUndefOrPoison(V);
+    if (llvm::all_of(II->operands(), [&](const Value *V) {
+          return isGuaranteedNotToBeUndefOrPoison(V, AllowUndef, CtxI, DT);
         }))
       return true;
   }
 
   if (auto I = dyn_cast<Instruction>(V)) {
-    if (programUndefinedIfFullPoison(I) && I->getType()->isIntegerTy(1))
+    if (AllowUndef && programUndefinedIfFullPoison(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;
 
+  // Retrieves operands from I = '(cmp op1 op2) and/or (cmp op3 op4) and/or ..',
+  // and checks whether V is in [op1, op2, op3, op4, ..]
+  auto ComparesValue = [V](const Value *Expr) {
+    auto I = dyn_cast<Instruction>(Expr);
+    SmallVector<const Instruction *, 16> Worklist;
+    SmallPtrSet<const Instruction *, 4> Visited;
+    Worklist.push_back(I);
+    Visited.insert(I);
+
+    while (!Worklist.empty()) {
+      const Instruction *NextI = Worklist.pop_back_val();
+      if (auto II = dyn_cast<ICmpInst>(NextI)) {
+        if (II->getOperand(0) == V || II->getOperand(1) == V)
+          return true;
+      } else if (auto BI = dyn_cast<BinaryOperator>(NextI)) {
+        if (BI->getOpcode() == Instruction::And ||
+             BI->getOpcode() == Instruction::Or) {
+          auto Op1 = dyn_cast<Instruction>(BI->getOperand(0));
+          auto Op2 = dyn_cast<Instruction>(BI->getOperand(0));
+          if (Op1 && Visited.insert(Op1).second)
+            Worklist.push_back(Op1);
+          if (Op2 && Visited.insert(Op2).second)
+            Worklist.push_back(Op2);
+        }
+      }
+    }
+    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 = DT->getNode(CtxI->getParent())->getIDom();
   while (Dominator) {
     auto *TI = Dominator->getBlock()->getTerminator();
 
-    if (auto BI = dyn_cast<BranchInst>(TI)) {
-      if (BI->isConditional() && BI->getCondition() == V)
+    const Value *Cond = nullptr;
+    if (auto BI = dyn_cast<BranchInst>(TI))
+      Cond = BI->isConditional() ? BI->getCondition() : nullptr;
+    else if (auto SI = dyn_cast<SwitchInst>(TI))
+      Cond = SI->getCondition();
+
+    if (Cond) {
+      if (Cond == V)
         return true;
-    } else if (auto SI = dyn_cast<SwitchInst>(TI)) {
-      if (SI->getCondition() == V)
+      else if (AllowUndef && ComparesValue(Cond))
+        //  br (V != 0), BB1, BB2
+        // BB1:
+        //  CtxI ; V cannot be poison here.
+        //       ; Note that V can partially be undef, e.g. V = (undef | 1).
+        //       ; In that case, 'V == 0' becomes simply false.
         return true;
     }
 
     Dominator = Dominator->getIDom();
   }
 
   return false;
 }

llvm/test/Transforms/InstSimplify/freeze.ll

 define i32 @make_const() {
 ; CHECK-LABEL: @make_const(
 ; CHECK-NEXT:    ret i32 10
 ;
   %x = freeze i32 10
   ret i32 %x
 }
 
+define float @make_const2() {
+; CHECK-LABEL: @make_const2(
+; CHECK-NEXT:    ret float 1.000000e+01
+;
+  %x = freeze float 10.0
+  ret float %x
+}
+
+@glb = constant i32 0
+
+define i32* @make_const_glb() {
+; CHECK-LABEL: @make_const_glb(
+; CHECK-NEXT:    ret i32* @glb
+;
+  %k = freeze i32* @glb
+  ret i32* %k
+}
+
+define i32()* @make_const_fn() {
+; CHECK-LABEL: @make_const_fn(
+; CHECK-NEXT:    ret i32 ()* @make_const
+;
+  %k = freeze i32()* @make_const
+  ret i32()* %k
+}
+
 define i1 @brcond(i1 %c, i1 %c2) {
 ; CHECK-LABEL: @brcond(
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[A:%.*]], label [[B:%.*]]
 ; CHECK:       A:
 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[A2:%.*]], label [[B]]
 ; CHECK:       A2:
 ; CHECK-NEXT:    ret i1 [[C]]
 ; CHECK:       B:

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
+}
+
+define i1 @freeze_nonzero2(i8 %x, i8 %mask, i1 %mycond) {
+; CHECK-LABEL: @freeze_nonzero2(
+; CHECK-NEXT:    [[Y:%.*]] = or i8 [[X:%.*]], [[MASK:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = icmp ne i8 [[Y]], 0
+; CHECK-NEXT:    [[CC:%.*]] = and i1 [[C]], [[MYCOND:%.*]]
+; CHECK-NEXT:    br i1 [[CC]], 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
+  %cc = and i1 %c, %mycond
+  br i1 %cc, label %A, label %B
+A:
+  %fr = freeze i8 %y
+  %c2 = icmp eq i8 %fr, 0
+  ret i1 %c2
+B:
+  ret i1 0
+}