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

[jdoerfert]

Summary

Same as D60846 but with a fix for the problem encountered there which
was a missing context adjustment in the handling of PHI nodes.

[jdoerfert]

Add tests from D60846 and fix the bug exposed there

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

556

You can use Q.getWithInstruction(InTI) here.

llvm/lib/Analysis/ValueTracking.cpp

1906

Why can't this be an assert? Looks like the Constant case is fully handled first in isKnownNonZero().

[jdoerfert]

llvm/lib/Analysis/InstructionSimplify.cpp

556

Thx, will do.

llvm/lib/Analysis/ValueTracking.cpp

1906

I thought so too, run it, and caused the assert to trigger. The last case has two ifs nested. That is already a way out of the first case, might be more.

I don't think we want to look at dominance of constants (for now) so I just return false. There is actually something we could do here, but hat is a different story.

[jdoerfert]

Simplified as suggested

[jdoerfert]

Any more comments :)

[lebedev.ri]

Since the regression that reverted D60846 appears to be resolved, LG.

llvm/lib/Analysis/ValueTracking.cpp

1906

While there, should this be

if (isa<Constant>(V))
  return isa<ConstantPointerNull>(V);

?

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

95

Precommit

[jdoerfert]

llvm/lib/Analysis/ValueTracking.cpp

1906

I don't think so, and unfortunately !isa<ConstantPointerNull> doesn't work either (but that would be closer). I was hoping that "easy" constants don't make it here and hard ones would need us to inspect the surrounding (and are unlikely anyway, e.g., globals with weak linkage)

[nikic]

Apparently this got reverted in rG6ea47759008526dc11f5064b266de95c61915581.

[nikic]

For reference, here's the IR reproducer based on the provided C code:

define zeroext i8 @test(i8* nocapture readonly %0) local_unnamed_addr #0 {
  br label %2

2:                                                ; preds = %5, %1
  %.06 = phi i8 [ 0, %1 ], [ %11, %5 ]
  %.0 = phi i32 [ 0, %1 ], [ 1, %5 ]
  %3 = icmp eq i32 %.0, 0
  br i1 %3, label %5, label %4

4:                                                ; preds = %2
  ret i8 %.06

5:                                                ; preds = %2
  %6 = load i8, i8* %0, align 1
  %7 = zext i8 %6 to i32
  %8 = shl nuw nsw i32 %.0, 3
  %9 = shl nuw nsw i32 %7, %8
  %10 = trunc i32 %9 to i8
  %11 = or i8 %.06, %10
  %12 = add nuw nsw i32 %.0, 1
  br label %2
}

The ret gets optimized to ret i8 0 with this patch.

[lebedev.ri]

Yep, that looks like a miscompile to me.
alive doesn't support phi's yet, so i'm not 100% sure,
but if i manually unroll it (since we know we will return after first iteration),
i get

; ModuleID = './example.ll'
source_filename = "./example.ll"
define zeroext i8 @test(i8* %arg) local_unnamed_addr {
bb:
  %tmp4 = load i8, i8* %arg, align 1
  %tmp5 = zext i8 %tmp4 to i32
  %tmp6 = shl nuw nsw i32 0, 3
  %tmp7 = shl nuw nsw i32 %tmp5, %tmp6
  %tmp8 = trunc i32 %tmp7 to i8
  %tmp9 = or i8 0, %tmp8
  %tmp10 = add nuw nsw i32 0, 1
  ret i8 %tmp9
}

which is just

define zeroext i8 @test(i8* nocapture readonly %arg) local_unnamed_addr #0 {
bb:
  %tmp4 = load i8, i8* %arg, align 1
  ret i8 %tmp4
}

And that replacement says the load is always 0.

[jdoerfert]

@nikic Thanks for reopening this, I did not see the problem at all!

Same thing as last time. When we recurse through PHI nodes we need to update the context instruction or we get information for the wrong place. This time I fixed it in computeKnownBits.

I created D71181 with the proper fixes and additional test case.

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

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/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
non_zero:
   %ctz = call <8 x i64> @llvm.cttz.v8i64(<8 x i64> %x, i1 false)
   br label %exit
 
 exit:
   %res = phi <8 x i64> [ %ctz, %non_zero ], [ zeroinitializer, %start ]
   ret <8 x i64> %res
 }
 
 ; Test that exposed a bug in the PHI handling after D60846. No folding should happen here!
 define void @D60846_misompile(i1* %p) {
 ; CHECK-LABEL: @D60846_misompile(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[I:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ [[I_INC:%.*]], [[COMMON:%.*]] ]
 ; CHECK-NEXT:    [[IS_ZERO:%.*]] = icmp eq i16 [[I]], 0
 ; CHECK-NEXT:    br i1 [[IS_ZERO]], label [[COMMON]], label [[NON_ZERO:%.*]]

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

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: