[ValueTracking] Allow context-sensitive nullness check for non-pointers

[jdoerfert]

Summary

Same as D60846 and D69571 but with a fix for the problem encountered
after them. Both times it was a missing context adjustment in the
handling of PHI nodes.

The reproducers created from the bugs that caused the old commits to be
reverted are included.

[merge_guards_bot]

Build result: pass - 60603 tests passed, 0 failed and 726 were skipped.

Log files: console-log.txt, CMakeCache.txt

[lebedev.ri]

The fix makes sense to me, i've always found that CxtI very easy to get wrong..
@spatel / @nikic ?

[nikic]

LG to me as well.

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
   PHINode *PI = cast<PHINode>(LHS);
 
   // Bail out if RHS and the phi may be mutually interdependent due to a loop.
   if (!valueDominatesPHI(RHS, PI, Q.DT))
     return nullptr;
 
   // Evaluate the BinOp on the incoming phi values.
   Value *CommonValue = nullptr;
-  for (Value *Incoming : PI->incoming_values()) {
+  for (unsigned u = 0, e = PI->getNumIncomingValues(); u < e; ++u) {
+    Value *Incoming = PI->getIncomingValue(u);
+    Instruction *InTI = PI->getIncomingBlock(u)->getTerminator();
     // If the incoming value is the phi node itself, it can safely be skipped.
     if (Incoming == PI) continue;
-    Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse);
+    // Change the context instruction to the "edge" that flows into the phi.
+    // This is important because that is where incoming is actually "evaluated"
+    // even though it is used later somewhere else.
+    Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q.getWithInstruction(InTI),
+                               MaxRecurse);
     // If the operation failed to simplify, or simplified to a different value
     // to previously, then give up.
     if (!V || (CommonValue && V != CommonValue))
       return nullptr;
     CommonValue = V;
   }
 
   return CommonValue;

llvm/lib/Analysis/ValueTracking.cpp

case Instruction::PHI: {
     const PHINode *P = cast<PHINode>(I);
     // Handle the case of a simple two-predecessor recurrence PHI.
     // There's a lot more that could theoretically be done here, but
     // this is sufficient to catch some interesting cases.
     if (P->getNumIncomingValues() == 2) {
       for (unsigned i = 0; i != 2; ++i) {
         Value *L = P->getIncomingValue(i);
         Value *R = P->getIncomingValue(!i);
+        Instruction *RInst = P->getIncomingBlock(!i)->getTerminator();
+        Instruction *LInst = P->getIncomingBlock(i)->getTerminator();
         Operator *LU = dyn_cast<Operator>(L);
         if (!LU)
           continue;
         unsigned Opcode = LU->getOpcode();
         // Check for operations that have the property that if
         // both their operands have low zero bits, the result
         // will have low zero bits.
         if (Opcode == Instruction::Add ||
             Opcode == Instruction::Sub ||
             Opcode == Instruction::And ||
             Opcode == Instruction::Or ||
             Opcode == Instruction::Mul) {
           Value *LL = LU->getOperand(0);
           Value *LR = LU->getOperand(1);
           // Find a recurrence.
           if (LL == I)
             L = LR;
           else if (LR == I)
             L = LL;
           else
             continue; // Check for recurrence with L and R flipped.
+
+          // Change the context instruction to the "edge" that flows into the
+          // phi. This is important because that is where the value is actually
+          // "evaluated" even though it is used later somewhere else. (see also
+          // D69571).
+          Query RecQ = Q;
+
           // Ok, we have a PHI of the form L op= R. Check for low
           // zero bits.
-          computeKnownBits(R, Known2, Depth + 1, Q);
+          RecQ.CxtI = RInst;
+          computeKnownBits(R, Known2, Depth + 1, RecQ);
 
           // We need to take the minimum number of known bits
           KnownBits Known3(Known);
-          computeKnownBits(L, Known3, Depth + 1, Q);
+          RecQ.CxtI = LInst;
+          computeKnownBits(L, Known3, Depth + 1, RecQ);
 
           Known.Zero.setLowBits(std::min(Known2.countMinTrailingZeros(),
                                          Known3.countMinTrailingZeros()));
 
           auto *OverflowOp = dyn_cast<OverflowingBinaryOperator>(LU);
           if (OverflowOp && Q.IIQ.hasNoSignedWrap(OverflowOp)) {
             // If initial value of recurrence is nonnegative, and we are adding
             // a nonnegative number with nsw, the result can only be nonnegative
case Instruction::PHI: {
     // taking conservative care to avoid excessive recursion.
     if (Depth < MaxDepth - 1 && !Known.Zero && !Known.One) {
       // Skip if every incoming value references to ourself.
       if (dyn_cast_or_null<UndefValue>(P->hasConstantValue()))
         break;
 
       Known.Zero.setAllBits();
       Known.One.setAllBits();
-      for (Value *IncValue : P->incoming_values()) {
+      for (unsigned u = 0, e = P->getNumIncomingValues(); u < e; ++u) {
+        Value *IncValue = P->getIncomingValue(u);
         // Skip direct self references.
         if (IncValue == P) continue;
 
+        // Change the context instruction to the "edge" that flows into the
+        // phi. This is important because that is where the value is actually
+        // "evaluated" even though it is used later somewhere else. (see also
+        // D69571).
+        Query RecQ = Q;
+        RecQ.CxtI = P->getIncomingBlock(u)->getTerminator();
+
         Known2 = KnownBits(BitWidth);
         // Recurse, but cap the recursion to one level, because we don't
         // want to waste time spinning around in loops.
-        computeKnownBits(IncValue, Known2, MaxDepth - 1, Q);
+        computeKnownBits(IncValue, Known2, MaxDepth - 1, RecQ);
         Known.Zero &= Known2.Zero;
         Known.One &= Known2.One;
         // If all bits have been ruled out, there's no need to check
         // more operands.
         if (!Known.Zero && !Known.One)
           break;
       }
     }
static bool isGEPKnownNonNull(const GEPOperator *GEP, unsigned Depth,
   }
 
   return false;
 }
 
 static bool isKnownNonNullFromDominatingCondition(const Value *V,
                                                   const Instruction *CtxI,
                                                   const DominatorTree *DT) {
-  assert(V->getType()->isPointerTy() && "V must be pointer type");
-  assert(!isa<ConstantData>(V) && "Did not expect ConstantPointerNull");
+  if (isa<Constant>(V))
+    return false;
 
   if (!CtxI || !DT)
     return false;
 
   unsigned NumUsesExplored = 0;
   for (auto *U : V->users()) {
     // Avoid massive lists
     if (NumUsesExplored >= DomConditionsMaxUses)
if (V->getType()->isPointerTy()) {
     if (const auto *Call = dyn_cast<CallBase>(V)) {
       if (Call->isReturnNonNull())
         return true;
       if (const auto *RP = getArgumentAliasingToReturnedPointer(Call, true))
         return isKnownNonZero(RP, Depth, Q);
     }
   }
 
-
-  // Check for recursive pointer simplifications.
-  if (V->getType()->isPointerTy()) {
-    if (isKnownNonNullFromDominatingCondition(V, Q.CxtI, Q.DT))
-      return true;
 
+  // Check for recursive pointer simplifications.
+  if (V->getType()->isPointerTy()) {
     // Look through bitcast operations, GEPs, and int2ptr instructions as they
     // do not alter the value, or at least not the nullness property of the
     // value, e.g., int2ptr is allowed to zero/sign extend the value.
     //
     // Note that we have to take special care to avoid looking through
     // truncating casts, e.g., int2ptr/ptr2int with appropriate sizes, as well
     // as casts that can alter the value, e.g., AddrSpaceCasts.
     if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V))

llvm/test/Transforms/Attributor/nonnull.ll

 ; ATTRIBUTOR_NPM:       4:
 ; ATTRIBUTOR_NPM-NEXT:    [[TMP5:%.*]] = zext i32 [[TMP1]] to i64
 ; ATTRIBUTOR_NPM-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, i32* [[TMP0:%.*]], i64 [[TMP5]]
 ; ATTRIBUTOR_NPM-NEXT:    br label [[TMP8:%.*]]
 ; ATTRIBUTOR_NPM:       7:
 ; ATTRIBUTOR_NPM-NEXT:    ret void
 ; ATTRIBUTOR_NPM:       8:
 ; ATTRIBUTOR_NPM-NEXT:    [[TMP9:%.*]] = phi i32 [ 1, [[TMP4]] ], [ [[TMP10:%.*]], [[TMP8]] ]
-; ATTRIBUTOR_NPM-NEXT:    tail call void @sink(i32* [[TMP6]])
+; ATTRIBUTOR_NPM-NEXT:    tail call void @sink(i32* nonnull [[TMP6]])
 ; ATTRIBUTOR_NPM-NEXT:    [[TMP10]] = add nuw nsw i32 [[TMP9]], 1
 ; ATTRIBUTOR_NPM-NEXT:    [[TMP11:%.*]] = icmp eq i32 [[TMP10]], [[TMP1]]
 ; ATTRIBUTOR_NPM-NEXT:    br i1 [[TMP11]], label [[TMP7]], label [[TMP8]]
 ;
   %3 = icmp ne i32 %1, 0
   br i1 %3, label %4, label %7
 
 4:                                                ; preds = %2

llvm/test/Transforms/InstCombine/known-non-zero.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 declare i64 @llvm.cttz.i64(i64, i1)
 
 declare i64 @llvm.ctlz.i64(i64, i1)
 
 declare <8 x i64> @llvm.cttz.v8i64(<8 x i64>, i1)
 
 define i32 @test0(i64 %x) {
 ; CHECK-LABEL: @test0(
 ; CHECK-NEXT:  start:
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i64 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C]], label [[EXIT:%.*]], label [[NON_ZERO:%.*]]
 ; CHECK:       non_zero:
-; CHECK-NEXT:    [[CTZ:%.*]] = call i64 @llvm.cttz.i64(i64 [[X]], i1 false), !range !0
+; CHECK-NEXT:    [[CTZ:%.*]] = call i64 @llvm.cttz.i64(i64 [[X]], i1 true), !range !0
 ; CHECK-NEXT:    [[CTZ32:%.*]] = trunc i64 [[CTZ]] to i32
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[CTZ32]], [[NON_ZERO]] ], [ 0, [[START:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 start:
   %c = icmp eq i64 %x, 0

 }
 
 define i32 @test1(i64 %x) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  start:
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i64 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[C]], label [[EXIT:%.*]], label [[NON_ZERO:%.*]]
 ; CHECK:       non_zero:
-; CHECK-NEXT:    [[CTZ:%.*]] = call i64 @llvm.ctlz.i64(i64 [[X]], i1 false), !range !0
+; CHECK-NEXT:    [[CTZ:%.*]] = call i64 @llvm.ctlz.i64(i64 [[X]], i1 true), !range !0
 ; CHECK-NEXT:    [[CTZ32:%.*]] = trunc i64 [[CTZ]] to i32
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[CTZ32]], [[NON_ZERO]] ], [ 0, [[START:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 start:
   %c = icmp eq i64 %x, 0

llvm/test/Transforms/InstSimplify/known-non-zero.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
 define i64 @test0(i64 %x) {
 ; CHECK-LABEL: @test0(
 ; CHECK-NEXT:  start:
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq i64 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[A]], label [[EXIT:%.*]], label [[NON_ZERO:%.*]]
 ; CHECK:       non_zero:
-; CHECK-NEXT:    [[B:%.*]] = icmp eq i64 [[X]], 0
-; CHECK-NEXT:    br i1 [[B]], label [[UNREACHABLE:%.*]], label [[EXIT]]
+; CHECK-NEXT:    br i1 false, label [[UNREACHABLE:%.*]], label [[EXIT]]
 ; CHECK:       unreachable:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[C:%.*]] = phi i64 [ 0, [[START:%.*]] ], [ 1, [[NON_ZERO]] ], [ 2, [[UNREACHABLE]] ]
 ; CHECK-NEXT:    ret i64 [[C]]
 ;
 start:
   %a = icmp eq i64 %x, 0

 }
 
 define i64 @test1(i64 %x) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  start:
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq i64 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[A]], label [[EXIT:%.*]], label [[NON_ZERO:%.*]]
 ; CHECK:       non_zero:
-; CHECK-NEXT:    [[B:%.*]] = icmp ugt i64 [[X]], 0
-; CHECK-NEXT:    br i1 [[B]], label [[EXIT]], label [[UNREACHABLE:%.*]]
+; CHECK-NEXT:    br i1 true, label [[EXIT]], label [[UNREACHABLE:%.*]]
 ; CHECK:       unreachable:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[C:%.*]] = phi i64 [ 0, [[START:%.*]] ], [ [[X]], [[NON_ZERO]] ], [ 0, [[UNREACHABLE]] ]
 ; CHECK-NEXT:    ret i64 [[C]]
 ;
 start:
   %a = icmp eq i64 %x, 0

 ; CHECK-NEXT:    br i1 [[A]], label [[EXIT:%.*]], label [[NON_ZERO:%.*]]
 ; CHECK:       non_zero:
 ; CHECK-NEXT:    br i1 [[Y:%.*]], label [[ONE:%.*]], label [[TWO:%.*]]
 ; CHECK:       one:
 ; CHECK-NEXT:    br label [[MAINBLOCK:%.*]]
 ; CHECK:       two:
 ; CHECK-NEXT:    br label [[MAINBLOCK]]
 ; CHECK:       mainblock:
-; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[X]], [[ONE]] ], [ 42, [[TWO]] ]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[P]], 0
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = phi i1 [ [[CMP]], [[MAINBLOCK]] ], [ true, [[START:%.*]] ]
+; CHECK-NEXT:    [[RES:%.*]] = phi i1 [ false, [[MAINBLOCK]] ], [ true, [[START:%.*]] ]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
 start:
   %a = icmp eq i64 %x, 0
   br i1 %a, label %exit, label %non_zero
 
 non_zero:
   br i1 %y, label %one, label %two
 
 one:
   br label %mainblock
 
 two:
   br label %mainblock
 
 mainblock:
   %p = phi i64 [ %x, %one ], [ 42, %two ]
   %cmp = icmp eq i64 %p, 0
   br label %exit
 
 exit:
   %res = phi i1 [ %cmp, %mainblock ], [ 1, %start ]
   ret i1 %res
 }
+
+
+; The code below exposed a bug similar to the one exposed by D60846, see the commit 6ea477590085.
+; In a nutshell, we should not replace %result.0 with 0 here.
+
+define zeroext i8 @update_phi_query_loc_in_recursive_call(i8* nocapture readonly %p){
+; CHECK-LABEL: @update_phi_query_loc_in_recursive_call(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[RESULT_0:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[CONV2:%.*]], [[FOR_BODY:%.*]] ]
+; CHECK-NEXT:    [[SHIFT_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ 1, [[FOR_BODY]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[SHIFT_0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret i8 [[RESULT_0]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i8, i8* [[P:%.*]], align 1
+; CHECK-NEXT:    [[CONV:%.*]] = zext i8 [[TMP0]] to i32
+; CHECK-NEXT:    [[MUL:%.*]] = shl nuw nsw i32 [[SHIFT_0]], 3
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i32 [[CONV]], [[MUL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[SHL]] to i8
+; CHECK-NEXT:    [[CONV2]] = or i8 [[RESULT_0]], [[TMP1]]
+; CHECK-NEXT:    br label [[FOR_COND]]
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %result.0 = phi i8 [ 0, %entry ], [ %conv2, %for.body ]
+  %shift.0 = phi i32 [ 0, %entry ], [ 1, %for.body ]
+  %cmp = icmp eq i32 %shift.0, 0
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  ret i8 %result.0
+
+for.body:                                         ; preds = %for.cond
+  %0 = load i8, i8* %p, align 1
+  %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
+}

llvm/test/Transforms/LICM/hoist-mustexec.ll

for.cond.cleanup:
   ret i32 %add
 
 fail:
   call void @f()
   ret i32 -1
 }
 
 ; requires fact length is non-zero
-; TODO: IsKnownNonNullFromDominatingConditions is currently only be done for
-; pointers; should handle integers too
 define i32 @test4(i32* noalias nocapture readonly %a) nounwind uwtable {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[A:%.*]], align 4, !range !0
 ; CHECK-NEXT:    [[IS_ZERO:%.*]] = icmp eq i32 [[LEN]], 0
 ; CHECK-NEXT:    br i1 [[IS_ZERO]], label [[FAIL:%.*]], label [[PREHEADER:%.*]]
 ; CHECK:       preheader:
+; CHECK-NEXT:    [[I1:%.*]] = load i32, i32* [[A]], align 4
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[INC:%.*]], [[CONTINUE:%.*]] ]
 ; CHECK-NEXT:    [[ACC:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[ADD:%.*]], [[CONTINUE]] ]
 ; CHECK-NEXT:    [[R_CHK:%.*]] = icmp ult i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[R_CHK]], label [[CONTINUE]], label [[FAIL_LOOPEXIT:%.*]]
 ; CHECK:       continue:
-; CHECK-NEXT:    [[I1:%.*]] = load i32, i32* [[A]], align 4
 ; CHECK-NEXT:    [[ADD]] = add nsw i32 [[I1]], [[ACC]]
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 1000
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.cond.cleanup:
 ; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE]] ]
 ; CHECK-NEXT:    ret i32 [[ADD_LCSSA]]
 ; CHECK:       fail.loopexit: