This is an archive of the discontinued LLVM Phabricator instance.

[SimplifyCFG] Check if the return instruction causes undefined behavior
ClosedPublic

Authored by DianQK on Feb 17 2023, 6:56 PM.

Details

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
}

Diff Detail

Event Timeline

DianQK created this revision.Feb 17 2023, 6:56 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 17 2023, 6:56 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
DianQK requested review of this revision.Feb 17 2023, 6:56 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 17 2023, 6:56 PM
DianQK edited the summary of this revision. (Show Details)Feb 17 2023, 6:59 PM
DianQK added reviewers: xbolva00, nikic, jdoerfert, aqjune.
DianQK edited the summary of this revision. (Show Details)Feb 17 2023, 7:15 PM
DianQK updated this revision to Diff 498558.Feb 17 2023, 8:10 PM

Fix the undefined ptr case

DianQK updated this revision to Diff 498564.Feb 17 2023, 11:14 PM

Fix test cases

nikic added inline comments.Feb 18 2023, 5:47 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
7137

This requires both nonnull and noundef.

DianQK updated this revision to Diff 498583.Feb 18 2023, 5:56 AM

Add nonnull and noundef.

DianQK updated this revision to Diff 498584.Feb 18 2023, 5:59 AM
DianQK marked an inline comment as done.

Fix typo.

nikic added inline comments.Feb 18 2023, 6:02 AM
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 added inline comments.Feb 18 2023, 6:04 AM
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 updated this revision to Diff 498585.Feb 18 2023, 6:07 AM

Add the use case with only nonnull.

DianQK marked an inline comment as done.Feb 18 2023, 6:08 AM
nikic accepted this revision.Feb 18 2023, 6:10 AM

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

This revision is now accepted and ready to land.Feb 18 2023, 6:10 AM
nikic added inline comments.Feb 18 2023, 6:10 AM
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 marked an inline comment as done.Feb 18 2023, 6:21 AM

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.

vitalybuka reopened this revision.Feb 18 2023, 12:25 PM
This revision is now accepted and ready to land.Feb 18 2023, 12:25 PM
nikic requested changes to this revision.Feb 18 2023, 12:39 PM
nikic added inline comments.
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.

This revision now requires changes to proceed.Feb 18 2023, 12:39 PM
DianQK updated this revision to Diff 498661.Feb 19 2023, 1:49 AM

check !PtrValueMayBeModified.

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.

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 accepted this revision.Feb 19 2023, 3:26 AM

LGTM

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.

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.

This revision is now accepted and ready to land.Feb 19 2023, 3:26 AM
DianQK reopened this revision.Feb 19 2023, 5:03 AM

Sad, it still looks like it failed.

This revision is now accepted and ready to land.Feb 19 2023, 5:03 AM

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 added inline comments.Feb 19 2023, 5:21 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
7135

(please ignore, was in draft)

DianQK added inline comments.Feb 20 2023, 7:47 AM
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 added inline comments.Feb 20 2023, 8:04 AM
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 marked an inline comment as done.Feb 20 2023, 5:31 PM
DianQK added inline comments.
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 added inline comments.Feb 20 2023, 11:21 PM
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 added inline comments.Feb 21 2023, 12:41 AM
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.

DianQK added inline comments.Feb 21 2023, 1:06 AM
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 added inline comments.Feb 21 2023, 1:26 AM
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 added inline comments.Feb 21 2023, 2:04 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
7138
DianQK added inline comments.Feb 21 2023, 5:08 AM
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.

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?

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?

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.

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

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.

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

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

DianQK added a comment.EditedMar 22 2023, 3:29 PM

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 added a subscriber: ldionne.Apr 22 2023, 3:39 AM

@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.

@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 reopened this revision.Jul 21 2023, 8:09 PM

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.

This revision is now accepted and ready to land.Jul 21 2023, 8:09 PM