[SimplifyCFG] Optimize CFG when null is passed to a function with nonnull argument

[xbolva00]

Summary

Example:

__attribute__((nonnull,noinline)) char * pinc(char *p)  {
  return ++p;
}

char * foo(bool b, char *a) {
       return pinc(b ? 0 : a);


}

optimize to

char * foo(bool b, char *a) {
       return pinc(a);


}

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6598

Why llvm::?

6600

Two issues:

1. I believe this is subtle incorrect in conjunction with the GEP rule above. Accessing memory at gep null, x is always UB, but passing it to a nonnull argument isn't UB as long as x is not zero.

2. I'm not sure what the current state on this is (@aqjune), but I believe the plan is to make passing null to nonnull argument poison rather than UB. This optimization would only be valid using nonnull + noundef.

[jdoerfert]

test missing?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6600

FWIW, I'm, forever, in favor of making nonnull violation poison not UB.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6600

1, but here we only care about foo(null) and not foo(gep null, x).
See C->isNullValue() check.

2, ok, I was wondering about noundef too..

[aqjune]

Yeah, I believe passing null to nonnull should not immediately raise UB; it will block useful analyses. The patch is D90529, and I need to push it... Maybe it is time to reduce the number of patches that are still open by me.

For the example, I think this InstCombine transformation will work. noundef isn't necessary.

%s = select i1 %cond, i8* null, i8* %a
call void @foo(i8* nonnull %s)
->
call void @foo(i8* nonnull %a)

This is correct because
(1) If %cond was true, foo's argument is nonnull null which is equivalent to passing poison. Therefore it can be folded into arbitrary value such as %a.
(2) If %cond was false, it is already %a, so that's fine.

For the SimplifyCFG change, noundef is necessary. :) Maybe we can have both SimplifyCFG and InstCombine?

[xbolva00]

Restrict to nonnull+noundef.
Handle GEPs.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6598

We have the variable "Use" already here.

[xbolva00]

For the example, I think this InstCombine transformation will work. noundef isn't necessary.

Yeah, I will do it as a follow up patch.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6599

Or just continue if I is GEP?

[jdoerfert]

Why only use GEPs? And it looks to me you only check the offset, doesn't that miscompile:
call(nonnull noundef (gep %p, 0)) which an arbitrary %p?

I would have assumed you check for nonnull and noundef, then you ask isKnownNull, and it's UB if all 3 are true.

[xbolva00]

Avoid optimization if inner instruction is GEP.
Added test.

[xbolva00]

In D94180#2484644, @jdoerfert wrote:

Why only use GEPs? And it looks to me you only check the offset, doesn't that miscompile:
call(nonnull noundef (gep %p, 0)) which an arbitrary %p?

Added test9_gep_mismatch.

I would have assumed you check for nonnull and noundef, then you ask isKnownNull, and it's UB if all 3 are true.

We dont have 'isKnownNull' or miss I something?

[jdoerfert]

I think I was and am confused. V == C is null at the location the new code is inserted, correct? Is V also equal to I? As I said, I'm confused.

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6600

Just checking for GEP here isn't enough, you could also have another bitcast in between for example. The right way to handle it would be to add an extra boolean argument to passingValueIsAlwaysUndefined() that can be changed when looking through a GEP.

llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll

350

With inbounds the transform is actually fine, so we'd want to test without inbounds (or with both).

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6591–6592

And what if C is actually undef?

[xbolva00]

define void @test9_gep_mismatch(i1 %X, i8* %Y,  i8* %P) {
; CHECK-LABEL: @test9_gep_mismatch(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[X:%.*]], i8* null, i8* [[Y:%.*]]
; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[P:%.*]], i64 0
; CHECK-NEXT:    [[TMP0:%.*]] = call i8* @foo(i8* [[GEP]])
; CHECK-NEXT:    ret void
;
entry:
  br i1 %X, label %if, label %else

if:
  br label %else

else:
  %phi = phi i8* [ %Y, %entry ], [ null, %if ]
  %gep = getelementptr inbounds i8, i8* %phi, i64 7
  call i8* @foo(i8* %gep)
  ret void
}

So for this case,

Use is

call i8* @foo(i8* %gep)

I is

%gep = getelementptr inbounds i8, i8* %phi, i64 7

and V is a incoming value from phi. We bailt out if V is not constant, it needs to be null value.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6591–6592

So in this case, we require noundef attribute only (?) @aqjune

I will add a testcase.

[jdoerfert]

(Don't wait for me to finish the review)

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6591–6592

noundef undef -> instant UB

[xbolva00]

Introduce new extra bool argument to handle issue mentioned by @nikic

[xbolva00]

Is this something what you propose, @nikic ?

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1348

Why does this pass a pointer to bool, rather than just a bool?

6606

I would expect this to be something like return !IsUndefinedFromGEP, with IsUndefinedFromGEP being a simple bool.

[xbolva00]

Simplified implementation.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6606

Yes, simplier. Thanks

[xbolva00]

Any comments from @jdoerfert / @nikic ?

[jdoerfert]

Generally LGTM, assuming you are fine with my comments. If you want to continue the discussion, we can as well.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6547

Nit: style IsUndefFrom...

I would call it differently though. I tried to understand it from the name and I couldn't. Looking at the code longer, what it basically encodes is PtrValueMayBeModified. So if your C is null or undef and not modified, it will reach the call as null or undef. If it is (potentially) modified it might reach as something other than null.

6571

/* IsUndef... */ true

6597

llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll

209

rename to nonnull_noundef_arg, nonnull_arg, etc. or something similar descriptive.

[xbolva00]

Addressed review comments.

[nikic]

Logic looks fine now, though the GEP handling can be made a bit more lax.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6571

Could be more precise using something like:

if (!GEP->isInBounds() || !GEP->hasAllZeroIndices())
  IsUndefFromGEP = true;
return passingValueIsAlwaysUndefined(V, GEP, IsUndefFromGEP);

Though that makes the naming even more awkward. @jdoerfert's suggestion of PtrValueMayBeModified would make more sense.

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6591–6592

Yep, and will we watch it if the null ptr is defined?

[xbolva00]

Addressed review comments

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6571

Thanks, applied in new patch.

6591–6592

Ops, fixed.

Added test for this case.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

for (const PHINode &PN : Succ->phis()) {
       if (BB1V != BB2V && (BB1V == I1 || BB2V == I2)) {
         return false;
       }
     }
   }
   return true;
 }
 
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I);
 
 /// Given a conditional branch that goes to BB1 and BB2, hoist any common code
 /// in the two blocks up into the branch block. The caller of this function
 /// guarantees that BI's block dominates BB1 and BB2.
 bool SimplifyCFGOpt::HoistThenElseCodeToIf(BranchInst *BI,
                                            const TargetTransformInfo &TTI) {
   // This does very trivial matching, with limited scanning, to find identical
   // instructions in the two blocks.  In particular, we don't want to get into
if (BasicBlock *PrevBB = allPredecessorsComeFromSameSource(BB))
         if (PBI != BI && PBI->isConditional())
           if (mergeConditionalStores(PBI, BI, DTU, DL, TTI))
             return requestResimplify();
 
   return false;
 }
 
 /// Check if passing a value to an instruction will cause undefined behavior.
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) {
   Constant *C = dyn_cast<Constant>(V);
   if (!C)
     return false;
 
   if (I->use_empty())
     return false;
 
   if (C->isNullValue() || isa<UndefValue>(C)) {
     // Only look at the first use, avoid hurting compile time with long uselists
     User *Use = *I->user_begin();
 
     // Now make sure that there are no instructions in between that can alter
     // control flow (eg. calls)
     for (BasicBlock::iterator
              i = ++BasicBlock::iterator(I),
              UI = BasicBlock::iterator(dyn_cast<Instruction>(Use));
          i != UI; ++i)
       if (i == I->getParent()->end() || i->mayHaveSideEffects())
         return false;
 
     // Look through GEPs. A load from a GEP derived from NULL is still undefined
     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Use))
       if (GEP->getPointerOperand() == I)
         return passingValueIsAlwaysUndefined(V, GEP);
 
     // Look through bitcasts.
     if (BitCastInst *BC = dyn_cast<BitCastInst>(Use))
       return passingValueIsAlwaysUndefined(V, BC);
 
     // Load from null is undefined.
     if (LoadInst *LI = dyn_cast<LoadInst>(Use))
       if (!LI->isVolatile())
         return !NullPointerIsDefined(LI->getFunction(),
                                      LI->getPointerAddressSpace());
 
     // Store to null is undefined.
     if (StoreInst *SI = dyn_cast<StoreInst>(Use))
       if (!SI->isVolatile())
         return (!NullPointerIsDefined(SI->getFunction(),
                                       SI->getPointerAddressSpace())) &&
                SI->getPointerOperand() == I;
 
+    if (auto *CB = dyn_cast<CallBase>(Use)) {
+      if (NullPointerIsDefined(CB->getFunction()))
+        return false;
       // A call to null is undefined.
-    if (auto *CB = dyn_cast<CallBase>(Use))
-      return !NullPointerIsDefined(CB->getFunction()) &&
-             CB->getCalledOperand() == I;
+      if (CB->getCalledOperand() == I)
+        return true;
+
+      // Passing null to a nonnnull+noundef argument is undefined.
+      for (const llvm::Use &Arg : CB->args())
+        if (Arg == I) {
+          if (const auto *GEPI = dyn_cast<GetElementPtrInst>(I)) {
+            const DataLayout &DL = I->getParent()->getModule()->getDataLayout();
+            APInt Offset(DL.getIndexTypeSizeInBits(GEPI->getType()), 0);
+            if (!GEPI->accumulateConstantOffset(DL, Offset) ||
+                Offset.isNullValue())
+              continue;
+          }
+          unsigned ArgIdx = CB->getArgOperandNo(&Arg);
+          if (CB->paramHasAttr(ArgIdx, Attribute::NonNull) &&
+              CB->paramHasAttr(ArgIdx, Attribute::NoUndef))
+            return true;
+        }
+    }
   }
   return false;
 }
 
 /// If BB has an incoming value that will always trigger undefined behavior
 /// (eg. null pointer dereference), remove the branch leading here.
 static bool removeUndefIntroducingPredecessor(BasicBlock *BB,
                                               DomTreeUpdater *DTU) {

llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll

 define void @test5(i1 %cond, i8* %ptr) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND:%.*]], true
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    store i8 2, i8* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ;
-
 entry:
   br i1 %cond, label %bb1, label %bb3
 
 bb3:
   br label %bb2
 
 bb1:
   br label %bb2
 
 bb2:
   %ptr.2 = phi i8* [ %ptr, %bb3 ], [ null, %bb1 ]
   store i8 2, i8* %ptr.2, align 8
   ret void
 }
 
 define void @test5_no_null_opt(i1 %cond, i8* %ptr) #0 {
 ; CHECK-LABEL: @test5_no_null_opt(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[PTR_2:%.*]] = select i1 [[COND:%.*]], i8* null, i8* [[PTR:%.*]]
 ; CHECK-NEXT:    store i8 2, i8* [[PTR_2]], align 8
 ; CHECK-NEXT:    ret void
 ;
-
 entry:
   br i1 %cond, label %bb1, label %bb3
 
 bb3:
   br label %bb2
 
 bb1:
   br label %bb2
if:
   br label %else
 
 else:
   %phi = phi void ()* [ %Y, %entry ], [ null, %if ]
   call void %phi()
   ret void
 }
 
-declare i8* @foo(i8* nonnull %p);
+declare i8* @foo(i8* nonnull noundef %p);
+declare i8* @bar(i8* nonnull %p);
 define void @test9(i1 %X, i8* %Y) {
-;
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[X:%.*]], i8* null, i8* [[Y:%.*]]
-; CHECK-NEXT:    [[TMP0:%.*]] = call i8* @foo(i8* [[SPEC_SELECT]])
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8* @foo(i8* [[Y:%.*]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %X, label %if, label %else
 
 if:
   br label %else
 
 else:
   %phi = phi i8* [ %Y, %entry ], [ null, %if ]
   call i8* @foo(i8* %phi)
   ret void
 }
 
-define void @test9_no_null_opt(i1 %X, i8* %Y) #0 {
+define void @test9_callsite(i1 %X, i8* %Y) {
+; CHECK-LABEL: @test9_callsite(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8* @bar(i8* noundef nonnull [[Y:%.*]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %X, label %if, label %else
+
+if:
+  br label %else
+
+else:
+  %phi = phi i8* [ %Y, %entry ], [ null, %if ]
+  call i8* @bar(i8* nonnull noundef %phi)
+  ret void
+}
+
+define void @test9_gep_nonzero(i1 %X, i8* %Y) {
+; CHECK-LABEL: @test9_gep(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[Y:%.*]], i64 12
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8* @foo(i8* [[GEP]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %X, label %if, label %else
+
+if:
+  br label %else
+
+else:
+  %phi = phi i8* [ %Y, %entry ], [ null, %if ]
+  %gep = getelementptr inbounds i8, i8* %phi, i64 12
+  call i8* @foo(i8* %gep)
+  ret void
+}
+
+define void @test9_gep_unknown(i1 %X, i8* %Y, i64 %I) {
+; CHECK-LABEL: @test9_gep_unknown(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[X:%.*]], i8* null, i8* [[Y:%.*]]
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[SPEC_SELECT]], i64 [[I:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = call i8* @foo(i8* [[GEP]])
+; CHECK-NEXT:    ret void
 ;
+entry:
+  br i1 %X, label %if, label %else
+
+if:
+  br label %else
+
+else:
+  %phi = phi i8* [ %Y, %entry ], [ null, %if ]
+  %gep = getelementptr inbounds i8, i8* %phi, i64 %I
+  call i8* @foo(i8* %gep)
+  ret void
+}
+
+define void @test9_missing_noundef(i1 %X, i8* %Y) {
+; CHECK-LABEL: @test9_missing_noundef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[X:%.*]], i8* null, i8* [[Y:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = call i8* @bar(i8* [[SPEC_SELECT]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %X, label %if, label %else
+
+if:
+  br label %else
+
+else:
+  %phi = phi i8* [ %Y, %entry ], [ null, %if ]
+  call i8* @bar(i8* %phi)
+  ret void
+}
+
+define void @test9_no_null_opt(i1 %X, i8* %Y) #0 {
 ; CHECK-LABEL: @test9_no_null_opt(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[X:%.*]], i8* null, i8* [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = call i8* @foo(i8* [[SPEC_SELECT]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %X, label %if, label %else
 
 if:
   br label %else
 
 else:
   %phi = phi i8* [ %Y, %entry ], [ null, %if ]
   call i8* @foo(i8* %phi)
   ret void
 }
 
 
 
 attributes #0 = { null_pointer_is_valid }