[SimplifyCFG] Improve the precision of `PtrValueMayBeModified`

[DianQK]

Summary

The result value of getelementptr inbounds (TY, null, not zero) is a poison value. We can think of it as undefined behavior.

Please let me know if there is anything I don't understand correctly.

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7128

This is only the case if !NullPointerIsDefined(GEP->getFunction(), GEP->getPointerAddressSpace()).

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7128

Though we should probably just move that check to the start of the function, because we end up repeating it everywhere anyway.

[jdoerfert]

llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll

517

I'm worried because I didn't see a test with inbounds gep and @fn_noundef_arg call.
!GEP->hasAllZeroIndices() does not imply non zero. It means we don't know it's all zero.
Can we make sure we don't accidentally read poison into the situation where it could as well be null.

[DianQK]

Add NullPointerIsDefined check and fn_noundef_arg case

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7142

The first block probably isn't supposed to be there?

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7128

I think it would be fine to call NullPointerIsDefined directly on each gep, load and store, because we still have to query address space.

Would it be cleaner to just use NullPointerIsDefined?

7142

Sorry I didn't get.
First, we only focus two cases:
a. getelementptr (TY, null, not zero) -> maybe be modified
a. getelementptr inbounds (TY, null, not zero) -> poison?

The first

if (!GEP->isInBounds()) {
   PtrValueMayBeModified = true;
}

is the "a" case.

7142

These two cases are:
a. getelementptr (TY, null, not zero) -> maybe be modified
b. getelementptr inbounds (TY, null, not zero) -> poison?

llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll

517

I have added the fn_noundef_arg case.
For all ptr cases, PtrValueMayBeModified is used to check if it always be null.

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7142

Ping? Is there something I misunderstood?

[StephenFan]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7143–7145

This condition equivalent to

if (!GEP->isInBounds() ||
      NullPointerIsDefined(GEP->getFunction(),
                            GEP->getPointerAddressSpace())) {

which repeats the above if statement.

[DianQK]

Simplify the branch logic

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7143–7145

Thank you so much, you saved me.
I was getting wrapped up in this pile of if branches.

[nikic]

Missing a test with inbounds + null_pointer_is_valid, I think?

[DianQK]

Add some tests with inbounds + null_pointer_is_valid.

[nikic]

LGTM

[xbolva00]

Precommit tests?

Otherwise looks good.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7126

may be?

7128

poison? (only if null is undefined)

why question mark? Maybe:

poison iff null is undefined?

[DianQK]

Thank you very much for your review!

Further, we should remove the bool GetElementPtrInst::hasAllZeroIndices() method altogether. Then we don't need to consider the gep zero case anymore.
What do you think?

Although this may require additional work, possibly:

• add assertions created by GEP instructions or automatically convert them to other instructions
• automatically convert GEP directives after optimizations like constant propagation

[DianQK]

Fixed typo

[DianQK]

In D144563#4152211, @xbolva00 wrote:

Precommit tests?

Otherwise looks good.

Thanks, it should look better now.
I'm going to run ninja check-all with clang.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

if (C->isNullValue() || isa<UndefValue>(C)) {
     if (any_of(InstrRange, [](Instruction &I) {
           return !isGuaranteedToTransferExecutionToSuccessor(&I);
         }))
       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) {
-        if (!GEP->isInBounds() || !GEP->hasAllZeroIndices())
+        // The current base address is null, there are four cases to consider:
+        // getelementptr (TY, null, 0)                 -> null
+        // getelementptr (TY, null, not zero)          -> may be modified
+        // getelementptr inbounds (TY, null, 0)        -> null
+        // getelementptr inbounds (TY, null, not zero) -> poison iff null is
+        // undefined?
+        if (!GEP->hasAllZeroIndices() &&
+            (!GEP->isInBounds() ||
+             NullPointerIsDefined(GEP->getFunction(),
+                                  GEP->getPointerAddressSpace())))
           PtrValueMayBeModified = true;
         return passingValueIsAlwaysUndefined(V, GEP, PtrValueMayBeModified);
       }
 
     // Look through return.
     if (ReturnInst *Ret = dyn_cast<ReturnInst>(Use)) {
       bool HasNoUndefAttr =
           Ret->getFunction()->hasRetAttribute(Attribute::NoUndef);
       // Return undefined to a noundef return value is undefined.
       if (isa<UndefValue>(C) && HasNoUndefAttr)
         return true;
       // Return null to a nonnull+noundef return value is undefined.
       if (C->isNullValue() && HasNoUndefAttr &&
           Ret->getFunction()->hasRetAttribute(Attribute::NonNull)) {
         return !PtrValueMayBeModified;
       }
     }
 
     // Look through bitcasts.
     if (BitCastInst *BC = dyn_cast<BitCastInst>(Use))

llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll

else:
   %gep = getelementptr i8, ptr %phi, i64 12
   call ptr @fn_nonnull_noundef_arg(ptr %gep)
   ret void
 }
 
 define void @test9_gep_inbounds_nonzero(i1 %X, ptr %Y) {
 ; CHECK-LABEL: @test9_gep_inbounds_nonzero(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, ptr [[Y:%.*]], i64 12
+; CHECK-NEXT:    [[TMP1:%.*]] = call ptr @fn_nonnull_noundef_arg(ptr [[GEP]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %X, label %if, label %else
+
+if:
+  br label %else
+
+else:
+  %phi = phi ptr [ %Y, %entry ], [ null, %if ]
+  %gep = getelementptr inbounds i8, ptr %phi, i64 12
+  call ptr @fn_nonnull_noundef_arg(ptr %gep)
+  ret void
+}
+
+define void @test9_gep_inbounds_nonzero_null_defined(i1 %X, ptr %Y) #0 {
+; CHECK-LABEL: @test9_gep_inbounds_nonzero_null_defined(
+; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[X:%.*]], ptr null, ptr [[Y:%.*]]
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, ptr [[SPEC_SELECT]], i64 12
 ; CHECK-NEXT:    [[TMP0:%.*]] = call ptr @fn_nonnull_noundef_arg(ptr [[GEP]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %X, label %if, label %else
 
 if:
   br label %else
 
 else:
   %phi = phi ptr [ %Y, %entry ], [ null, %if ]
   %gep = getelementptr inbounds i8, ptr %phi, i64 12
   call ptr @fn_nonnull_noundef_arg(ptr %gep)
   ret void
 }
 
+define void @test9_gep_inbounds_unknown_null(i1 %X, ptr %Y, i64 %I) {
+; CHECK-LABEL: @test9_gep_inbounds_unknown_null(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, ptr [[Y:%.*]], i64 [[I:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call ptr @fn_nonnull_noundef_arg(ptr [[GEP]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %X, label %if, label %else
+
+if:
+  br label %else
+
+else:
+  %phi = phi ptr [ %Y, %entry ], [ null, %if ]
+  %gep = getelementptr inbounds i8, ptr %phi, i64 %I
+  call ptr @fn_nonnull_noundef_arg(ptr %gep)
+  ret void
+}
 
-define void @test9_gep_inbouds_unknown_null(i1 %X, ptr %Y, i64 %I) {
-; CHECK-LABEL: @test9_gep_inbouds_unknown_null(
+define void @test9_gep_inbounds_unknown_null_defined(i1 %X, ptr %Y, i64 %I) #0 {
+; CHECK-LABEL: @test9_gep_inbounds_unknown_null_defined(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[X:%.*]], ptr null, ptr [[Y:%.*]]
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, ptr [[SPEC_SELECT]], i64 [[I:%.*]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = call ptr @fn_nonnull_noundef_arg(ptr [[GEP]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %X, label %if, label %else
 
 if:
   br label %else
 
 else:
   %phi = phi ptr [ %Y, %entry ], [ null, %if ]
   %gep = getelementptr inbounds i8, ptr %phi, i64 %I
   call ptr @fn_nonnull_noundef_arg(ptr %gep)
   ret void
 }
 
+define void @test9_gep_inbounds_unknown_null_call_noundef(i1 %X, ptr %Y, i64 %I) {
+; CHECK-LABEL: @test9_gep_inbounds_unknown_null_call_noundef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[X:%.*]], ptr null, ptr [[Y:%.*]]
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, ptr [[SPEC_SELECT]], i64 [[I:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = call ptr @fn_noundef_arg(ptr [[GEP]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %X, label %if, label %else
+
+if:
+  br label %else
+
+else:
+  %phi = phi ptr [ %Y, %entry ], [ null, %if ]
+  %gep = getelementptr inbounds i8, ptr %phi, i64 %I
+  call ptr @fn_noundef_arg(ptr %gep)
+  ret void
+}
+
 define void @test9_gep_unknown_null(i1 %X, ptr %Y, i64 %I) {
 ; CHECK-LABEL: @test9_gep_unknown_null(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[X:%.*]], ptr null, ptr [[Y:%.*]]
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr i8, ptr [[SPEC_SELECT]], i64 [[I:%.*]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = call ptr @fn_nonnull_noundef_arg(ptr [[GEP]])
 ; CHECK-NEXT:    ret void
 ;

llvm/test/Transforms/SimplifyCFG/unreachable-eliminate-on-ret.ll

bb2:
   %r = phi ptr [ null, %entry ], [ %x, %bb1 ]
   ret ptr %r
 }
 
 define nonnull noundef ptr @test_ret_ptr_nonnull_noundef_gep_nonzero(i1 %cond, ptr %x) {
 ; CHECK-LABEL: @test_ret_ptr_nonnull_noundef_gep_nonzero(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[COND:%.*]], ptr [[X:%.*]], ptr null
-; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds ptr, ptr [[SPEC_SELECT]], i64 12
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr ptr, ptr [[SPEC_SELECT]], i64 12
+; CHECK-NEXT:    ret ptr [[GEP]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb2
+
+bb2:
+  %phi = phi ptr [ null, %entry ], [ %x, %bb1 ]
+  %gep = getelementptr ptr, ptr %phi, i64 12
+  ret ptr %gep
+}
+
+define nonnull noundef ptr @test_ret_ptr_nonnull_noundef_gep_inbounds_nonzero(i1 %cond, ptr %x) {
+; CHECK-LABEL: @test_ret_ptr_nonnull_noundef_gep_inbounds_nonzero(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @llvm.assume(i1 [[COND:%.*]])
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds ptr, ptr [[X:%.*]], i64 12
 ; CHECK-NEXT:    ret ptr [[GEP]]
 ;
 entry:
   br i1 %cond, label %bb1, label %bb2
 
 bb1:
   br label %bb2