[SimplifyCFG] Check if the return instruction causes undefined behavior

[DianQK]

Summary

This should fix https://github.com/rust-lang/rust/issues/107681.

Return undefined to a noundef return value is undefined.

Example:

define noundef i32 @test_ret_noundef(i1 %cond) {
entry:
  br i1 %cond, label %bb1, label %bb2
bb1:
  br label %bb2
bb2:
  %r = phi i32 [ undef, %entry ], [ 1, %bb1 ]
  ret i32 %r
}

[DianQK]

Fix the undefined ptr case

[DianQK]

Fix test cases

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7137

This requires both nonnull and noundef.

[DianQK]

Add nonnull and noundef.

[DianQK]

Fix typo.

[nikic]

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

38

Please also add a test with just nonnull to show that it doesn't fold.

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7137

Thanks for the review. According to the LangRef manual, is it a convention to pair nonnull with noundef?

[DianQK]

Add the use case with only nonnull.

[nikic]

LGTM, but please precommit the tests. (Or if you don't have commit access, let me know which Name <email> to use.)

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7137

nonnull by itself only converts the return value to poison. noundef converts poison into IUB. Frontends will generally place both attributes.

[DianQK]

Thank you for your review and answer. I have commit access. After https://reviews.llvm.org/B214570 succeeds, I will rebase the commit and run ninja check-all once locally to confirm it is correct.

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7138

Not sure whether that's the cause of the sanitizer failures, but I just realized that we're missing a check for !PtrValueMayBeModified here -- this is not a provenance based fold, so it must be exactly the null pointer.

[DianQK]

check !PtrValueMayBeModified.

[DianQK]

According to https://github.com/google/sanitizers/wiki/SanitizerBotReproduceBuild, I can reproduce the issue locally. But this build is taking too long, and I'm still verifying the sanitizer checks after the fix.

[DianQK]

Another thing I'm curious about is why all the gep zero have been removed in the llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll file at the 8979ae42769e529b0f6fce3268492ffb49bd54b9.

-  %phi = phi i8* [ %Y, %entry ], [ null, %if ]
-  %gep = getelementptr inbounds i8, i8* %phi, i64 0
-  call i8* @fn_nonnull_noundef_arg(i8* %gep)
+  %phi = phi ptr [ %Y, %entry ], [ null, %if ]
+  call ptr @fn_nonnull_noundef_arg(ptr %phi)

[nikic]

LGTM

In D144319#4137514, @DianQK wrote:

According to https://github.com/google/sanitizers/wiki/SanitizerBotReproduceBuild, I can reproduce the issue locally. But this build is taking too long, and I'm still verifying the sanitizer checks after the fix.

It's probably fine to just recommit and keep an eye on the buildbot.

In D144319#4137515, @DianQK wrote:

Another thing I'm curious about is why all the gep zero have been removed in the llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll file at the 8979ae42769e529b0f6fce3268492ffb49bd54b9.

With opaque pointers zero-index GEPs can no longer occur in canonical IR, so they get dropped to test a more realistic input.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7124

As a side note, I'm pretty sure this was supposed to read !GEP->isInBounds() && !GEP->hasAllZeroIndices(), the current check doesn't make a lot of sense.

[DianQK]

Sad, it still looks like it failed.

[xbolva00]

So maybe there is a real UB which is now exploited by stronger optimizations…

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7135

if the result value is not used - is it?

check line 7172, it requires nonnnull+noundef for similar case.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7135

(please ignore, was in draft)

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7124

After addressing the current problem, I cloud to try to refactor this part.

7135

I checked the test/Refactor/Extract/ObjCProperty.m case. The DeadArgumentElimination pass will change define internal noundef zeroext i1 @...SelectionFinder12TraverseStmt... to define fastcc void @...SelectionFinder12TraverseStmt....
So if no return value is used, returning undefined values does not appear to be undefined behavior.

Now, finding a sound solution was a bit difficult for me, but I will address it in this direction.

(More study time may be required.)

Thanks.

7138

I found the DeadArgumentElimination pass will change define internal noundef zeroext i1 @...SelectionFinder12TraverseStmt... to define fastcc void @...SelectionFinder12TraverseStmt.... Then the if (isa<UndefValue>(C) && HasNoUndefAttr) return true; statement is no longer a sound decision.

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7138

Not sure I understand. Once the return type is changed to void there is no longer a noundef attribute (or return instruction operand, for that matter).

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7138

Yes, I think so. This DeadArgumentElimination pass only handles internal functions, we can add a non-internal function check. It should be safe because any pass should not change the attributes and types of the non-internal function. But I'm not sure yet if this will change under LTO.

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7138

Sorry, I still don't get what the DeadArgumentElimination pass has to do with this. Before DAE runs, we have a noundef return value and if this optimization triggers, presumably an undef value is being returned from it on some path. This is UB even if the return value is actually unused and can be eliminated by DAE.

Can you share a more complete IR sample?

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7138

You can try this IR, this content can be very complex and I haven't made a simplified example yet.

The function is define internal noundef zeroext i1 @_ZN12_GLOBAL__N_118ASTSelectionFinder12TraverseStmtEPN5clang4StmtE from https://github.com/llvm/llvm-project/blob/main/clang/lib/Tooling/Refactoring/ASTSelection.cpp#L112.

To make the content simpler, I manually deleted https://github.com/llvm/llvm-project/blob/main/clang/lib/Tooling/Refactoring/ASTSelection.cpp#L122-L128.

ASTSelection.ll.zip1 MBDownload

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7138

The DAE changes the function to define internal fastcc void @_ZN12_GLOBAL__N_118ASTSelectionFinder12TraverseStmtEPN5clang4StmtE, also it changes the return instruction.
The return value of this function no longer requires noundef, or more precisely, no return value (a void).
Now it looks like these two optimizations are in conflict, one requiring the return value noundef and one removing noundef.

Sorry I haven't found a more precise explanation.
The current local buildbot_bootstrap_asan.sh test looks fine.

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7138

Thanks for the IR. I believe I understand the problem now. IPSCCP replaces return values with undef, but does not drop the noundef attribute. I'll work on a patch...

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7138

Patch: https://reviews.llvm.org/D144461

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

7138

Wow, thank you for giving the right solution!
I tested test/Refactor/Extract/ObjCProperty.m, which was fine.

Maybe next I should learn what all the LLVM passes are doing.

[Mordante]

After a recent update of Clang in the libc+++ precommit CI I see consistent failures of 4 tests in our no exception build
https://buildkite.com/llvm-project/libcxx-ci/builds/20704#0186e44d-63c5-414e-ba9d-9771804b7c4f

I've bisected the issue to this patch, reverting the .cpp changes on HEAD fixes the build.

Would it be possible to fix this issue quickly, if not can you revert this patch?

[xbolva00]

In D144319#4203982, @Mordante wrote:

After a recent update of Clang in the libc+++ precommit CI I see consistent failures of 4 tests in our no exception build
https://buildkite.com/llvm-project/libcxx-ci/builds/20704#0186e44d-63c5-414e-ba9d-9771804b7c4f

I've bisected the issue to this patch, reverting the .cpp changes on HEAD fixes the build.

Would it be possible to fix this issue quickly, if not can you revert this patch?

Are you sure there is no UB in your code?

[DianQK]

Would it be possible to fix this issue quickly, if not can you revert this patch?

As @xbolva00 mentioned, if you're sure your code doesn't have UB, you can revert my commit first.
Can you provide libc++ related commits? Only 564ed0b?
I can investigate tomorrow when I wake up.

[DianQK]

If you are not so sure, you are free to revert my commit. ^_^

[Mordante]

In D144319#4204004, @DianQK wrote:

Would it be possible to fix this issue quickly, if not can you revert this patch?

As @xbolva00 mentioned, if you're sure your code doesn't have UB, you can revert my commit first.
Can you provide libc++ related commits? Only 564ed0b?
I can investigate tomorrow when I wake up.

Tomorrow is fine by me.

Here is one of the test files failing. This only fails when exceptions are disabled in libc++ and libc++-abi.

libcxx/test/std/language.support/support.dynamic/new.delete/new.delete.array/new_align_val_t_nothrow.pass.cpp

I don't directly see anything undefined behaviour. Note in the failures the asserts are not triggered so if
allocating the large amount of memory would succeed there would a message in the CI log.

[DianQK]

@Mordante Please check patch D146379. Some test cases fail, but I tried to explain this UB.

[Mordante]

I've updated the libc++ CI and it's fixed now, thanks!

[DianQK]

In D144319#4213682, @Mordante wrote:

I've updated the libc++ CI and it's fixed now, thanks!

Great, but I'm curious how the fix is working?
It still seems to fail in my local tests.

[nikic]

@Mordante @ldionne What is the current progress on fixing the libcxx issue?

If this cannot be resolved quickly, I'd ask you to disable the relevant libcxx CI configuration so this change can be reapplied.

[ldionne]

In D144319#4289608, @nikic wrote:

@Mordante @ldionne What is the current progress on fixing the libcxx issue?

If this cannot be resolved quickly, I'd ask you to disable the relevant libcxx CI configuration so this change can be reapplied.

This is the patch: https://reviews.llvm.org/D150610. This is going to require some discussion cause it's a breaking change that might have some non-trivial impact.

[DianQK]

Is there any progress on D150610? @ldionne
I'm worrying about the possibility of these progresses being stalled or lost due to https://discourse.llvm.org/t/update-on-github-pull-requests/71540.

[DianQK]

Track this issue at https://github.com/llvm/llvm-project/issues/60717.

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())
           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))
       return passingValueIsAlwaysUndefined(V, BC, PtrValueMayBeModified);
 
     // Load from null is undefined.
     if (LoadInst *LI = dyn_cast<LoadInst>(Use))
       if (!LI->isVolatile())
         return !NullPointerIsDefined(LI->getFunction(),

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S < %s | FileCheck %s
+
+define noundef i32 @test_ret_noundef(i1 %cond) {
+; CHECK-LABEL: @test_ret_noundef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb2
+
+bb2:
+  %r = phi i32 [ undef, %entry ], [ 1, %bb1 ]
+  ret i32 %r
+}
+
+define i32 @test_ret(i1 %cond) {
+; CHECK-LABEL: @test_ret(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[COND:%.*]], i32 1, i32 undef
+; CHECK-NEXT:    ret i32 [[SPEC_SELECT]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb2
+
+bb2:
+  %r = phi i32 [ undef, %entry ], [ 1, %bb1 ]
+  ret i32 %r
+}
+
+define nonnull noundef ptr @test_ret_ptr_nonnull_noundef(i1 %cond, ptr %x) {
+; CHECK-LABEL: @test_ret_ptr_nonnull_noundef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @llvm.assume(i1 [[COND:%.*]])
+; CHECK-NEXT:    ret ptr [[X:%.*]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb2
+
+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:    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 inbounds ptr, ptr %phi, i64 12
+  ret ptr %gep
+}
+
+define nonnull ptr @test_ret_ptr_nonnull(i1 %cond, ptr %x) {
+; CHECK-LABEL: @test_ret_ptr_nonnull(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[COND:%.*]], ptr [[X:%.*]], ptr null
+; CHECK-NEXT:    ret ptr [[SPEC_SELECT]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb2
+
+bb2:
+  %r = phi ptr [ null, %entry ], [ %x, %bb1 ]
+  ret ptr %r
+}
+
+define noundef ptr @test_ret_ptr_noundef(i1 %cond, ptr %x) {
+; CHECK-LABEL: @test_ret_ptr_noundef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[COND:%.*]], ptr [[X:%.*]], ptr null
+; CHECK-NEXT:    ret ptr [[SPEC_SELECT]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb2
+
+bb2:
+  %r = phi ptr [ null, %entry ], [ %x, %bb1 ]
+  ret ptr %r
+}
+
+define ptr @test_ret_ptr(i1 %cond, ptr %x) {
+; CHECK-LABEL: @test_ret_ptr(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[COND:%.*]], ptr [[X:%.*]], ptr null
+; CHECK-NEXT:    ret ptr [[SPEC_SELECT]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb2
+
+bb2:
+  %r = phi ptr [ null, %entry ], [ %x, %bb1 ]
+  ret ptr %r
+}