This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by xbolva00 on Jan 6 2021, 9:14 AM.

Details

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);


}

Diff Detail

Event Timeline

xbolva00 created this revision.Jan 6 2021, 9:14 AM
xbolva00 requested review of this revision.Jan 6 2021, 9:14 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 6 2021, 9:14 AM
xbolva00 edited the summary of this revision. (Show Details)Jan 6 2021, 9:30 AM
nikic added a subscriber: aqjune.
nikic added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6602

Why llvm::?

6604

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

test missing?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6604

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

xbolva00 added inline comments.Jan 6 2021, 12:06 PM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6604

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 added a comment.Jan 6 2021, 6:25 PM

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 updated this revision to Diff 315082.Jan 7 2021, 2:59 AM

Restrict to nonnull+noundef.
Handle GEPs.

xbolva00 marked 2 inline comments as done.Jan 7 2021, 3:00 AM
xbolva00 added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6602

We have the variable "Use" already here.

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 updated this revision to Diff 315085.Jan 7 2021, 3:15 AM
xbolva00 added inline comments.Jan 7 2021, 3:32 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6603

Or just continue if I is GEP?

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 updated this revision to Diff 315165.Jan 7 2021, 9:21 AM

Avoid optimization if inner instruction is GEP.
Added test.

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?

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 added inline comments.Jan 7 2021, 9:31 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6604

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
278

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

lebedev.ri added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6595–6596

And what if C is actually undef?

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 added inline comments.Jan 7 2021, 9:39 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6595–6596

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

I will add a testcase.

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

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6595–6596

noundef undef -> instant UB

xbolva00 updated this revision to Diff 315177.Jan 7 2021, 10:31 AM

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

Is this something what you propose, @nikic ?

nikic added inline comments.Jan 12 2021, 9:32 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
1348

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

6610

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

xbolva00 updated this revision to Diff 316197.Jan 12 2021, 12:17 PM

Simplified implementation.

xbolva00 marked an inline comment as done.Jan 12 2021, 12:17 PM
xbolva00 added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6610

Yes, simplier. Thanks

xbolva00 retitled this revision from [SimplifyCFG] Optimize CFG when null is passed to a function with nonnull argument. to [SimplifyCFG] Optimize CFG when null is passed to a function with nonnull argument.Jan 15 2021, 9:55 AM
xbolva00 marked an inline comment as done.

Any comments from @jdoerfert / @nikic ?

jdoerfert accepted this revision.Jan 15 2021, 10:19 AM

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
6548

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–6575

/* IsUndef... */ true

6601
llvm/test/Transforms/SimplifyCFG/UnreachableEliminate.ll
209

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

This revision is now accepted and ready to land.Jan 15 2021, 10:19 AM
xbolva00 updated this revision to Diff 317028.Jan 15 2021, 11:08 AM

Addressed review comments.

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

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6571–6575

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 added inline comments.Jan 15 2021, 12:14 PM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6595–6596

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

xbolva00 updated this revision to Diff 317048.Jan 15 2021, 12:40 PM

Addressed review comments

xbolva00 added inline comments.Jan 15 2021, 12:41 PM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6571–6575

Thanks, applied in new patch.

6595–6596

Ops, fixed.

Added test for this case.

DianQK added a subscriber: DianQK.Feb 18 2023, 6:03 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 18 2023, 6:03 PM
Herald added a subscriber: StephenFan. · View Herald Transcript