This is an archive of the discontinued LLVM Phabricator instance.

[SimplifyLibCalls] propagate tail flags on CallInsts
ClosedPublic

Authored by nickdesaulniers on Aug 10 2021, 4:33 PM.

Details

Summary

I noticed we weren't propagating tail flags on calls when
FortifiedLibCallSimplifier.optimizeCall() was replacing calls to runtime
checked calls to the non-checked routines (when safe to do so). Make
sure to check this before replacing the original calls!

Also, avoid any libcall transforms when notail/musttail is present.

PR46734

Diff Detail

Event Timeline

nickdesaulniers requested review of this revision.Aug 10 2021, 4:33 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 10 2021, 4:33 PM
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
3089

There's another call site of FortifiedLibCallSimplifier.optimizeCall. Perhaps it would be better to sink this check into that method? Thoughts?

  • check in FortifiedLibCallSimplifier::optimizeCall

FWIW, this was the test case I was looking at that triggered this: https://godbolt.org/z/864jvY5nr.

nickdesaulniers retitled this revision from [SimplifyLibCalls] propagate tail flag on FORITIFY calls to [SimplifyLibCalls] propagate tail flag on FORTIFY calls.Aug 11 2021, 11:36 AM

FYI https://reviews.llvm.org/D89249

This your patch looks more promising.

FYI https://reviews.llvm.org/D89249

This your patch looks more promising.

Ah! Also, I only do this for the FortifiedLibCallSimplifier::optimizeCall, maybe I should do this for the vanilla LibCallSimplifier as well?

On a sort-of-related note, should we avoid optimizing musttail and/or notail calls here?

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
3560

This isn't the right call in some cases, I think. For example, for memmove, this is the operand to the memmove, not the memmove itself.

On a sort-of-related note, should we avoid optimizing musttail and/or notail calls here?

RE: notail:
Not necessary. If we have a notail call, we transform it, but we don't add tail so nothing to see here.

RE: musttail:
Probably; if I replace a musttail with a non-musttail call, that's kind of the same problem I'm trying to fix here with tail. Though when I try that, I get an error I don't yet understand:

cannot guarantee tail call due to mismatched parameter counts
  %ret = musttail call i32 @__vsprintf_chk(i8* %dst, i32 0, i64 -1, i8* %src, %struct.__va_list_tag* null)

huh?

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
3560

Yeah, I don't quite understand not returning the newly constructed call instruction. Does that mean that the call to replaceAllUsesWith on line 3041 wont actually insert the new call instruction, or rather replace the old instruction?

So this fixes https://bugs.llvm.org/show_bug.cgi?id=46734

It does not (yet, but could+should), probably because of the case that @efriedma describes above. I may want to do:

if (CI->isTailCall())
      SimplifiedCI->setTailCall();

within each optimize* method.

xbolva00 added inline comments.Aug 12 2021, 2:06 PM
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
3560

memmove/fortified memmove returns a pointer, llvm.memmove and friends return “void”

efriedma added inline comments.Aug 12 2021, 2:08 PM
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
3560

The code at line 3041 is probably not working as intended, yes.

Actually, I'm not sure what that code is trying to do; not sure why we don't want to just let the instcombine worklist do its normal thing.

nickdesaulniers retitled this revision from [SimplifyLibCalls] propagate tail flag on FORTIFY calls to [SimplifyLibCalls] propagate tail flag on FORITIFY calls.
  • add lots of tests, and fixes for those tests
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
3560

Ah, looks like there's seperate test files for a few of these.

  • memcpy_chk-1.ll, memcpy_chk-2.ll
  • memset_chk-1.ll, memset_chk-2.ll
  • stpcpy_chk-1.ll
  • strcpy_chk-64.ll, strcpy_chk-2.ll

Also, in https://bugs.llvm.org/show_bug.cgi?id=46734, it looks like whatever converts calls to __memcpy_chk to @llvm.memcpy.p0i8.p0i8.i64 is also dropping these!!!

Oh god, it's endemic to the non-chk/vanilla LibCallSimplifier, too! Should I litter the code with these, or should we consider running TailCallElim immediately after LibcallSimplifier?

or should we consider running TailCallElim immediately after LibcallSimplifier?

Sorry, I guess that would be s/LibcallSimplifier/instcombine.

TODO: of the three cases reported in https://bugs.llvm.org/show_bug.cgi?id=46734, this still missed the memmove case.

nickdesaulniers edited the summary of this revision. (Show Details)Aug 12 2021, 7:39 PM

or should we consider running TailCallElim immediately after LibcallSimplifier?

Yeah, would be great ro insert it after loop idiom pass.

  • memmove, mempcpy
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
3311–3313

if this pattern of:

  1. set attributes from new to old
  2. remove type incompatible attributes
  3. copy over tail flag (maybe musttail)

Then perhaps this should be a helper function; copyAttributesFlags(const CallInst *From, CallInst *To)? Though I'd like @efriedma 's input on this approach of redoing work another pass does, vs inserting another run of TailCallElim after instcombine?

On a sort-of-related note, should we avoid optimizing musttail and/or notail calls here?

Yes, looks like

New->setTailCallKind(Old.getTailCallKind()); would be better.

nickdesaulniers retitled this revision from [SimplifyLibCalls] propagate tail flag on FORITIFY calls to [SimplifyLibCalls] propagate tail/musttail/notail flags on CallInsts.
  • rebase, rewrite approach w/helper, add flag propagation everywhere

Nice approach, +1.

nickdesaulniers marked 3 inline comments as done.Oct 4 2021, 4:08 PM

@xbolva00 you've made 28 of the last 100 commits to llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp; I think that means you own it now. Is that +1 a formal accept of the patch or are we waiting on additional review?

If possible, @efriedma should take a look as well.

nickdesaulniers removed a subscriber: efriedma.
jdoerfert added inline comments.Oct 11 2021, 3:11 PM
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
634

Mostly this makes sense but doesn't this violate tail properties now? The old call result was return but it is not anymore.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
634

perhaps we should be avoiding libcall transforms that don't return the new CallInst if the CallInst to be replaced is marked musttail? Let me add musttail tests.

xbolva00 added inline comments.Oct 11 2021, 3:33 PM
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
634

You mean eg musttail on strncpy?

Well yeah, but anyway there are many other libcall simplifications which break “musttail” contract (so if CI is musttail, we should not perform some simplifications).

But yeah, now with propagated tail kind, some IR verifier or backend may fail.

Nick, can you try it please?

nickdesaulniers marked 2 inline comments as done.
nickdesaulniers edited the summary of this revision. (Show Details)
  • avoid transforms when musttail and not replacing a call with a new call, add 11 new musttail tests
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
634

Yeah, there's 11 cases that I'm updating from Diff 377048. I will write 11 new tests, too.

jdoerfert accepted this revision.Oct 12 2021, 10:54 AM

LG, with some missing checks that can be added for the final version.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
1152

Musttail check for this one?

1368

Also not allowed to be musttail.

1633

copy flags only if not musstail or we actually return "this Sqrt".

2610

Musttail check?

2652

Musttail check?

3364

make it return copyFlags so it's easy to see this doesn't need a guard.

This revision is now accepted and ready to land.Oct 12 2021, 10:54 AM

If we replace musttail CI with non-CI or CI without musttail, maybe we should have an assert somewhere to detect this issue for new libcall simplifications

nickdesaulniers planned changes to this revision.Oct 12 2021, 12:54 PM
nickdesaulniers added inline comments.
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
1152

oof, and the case above it, too.

1195

missing musttail

nickdesaulniers marked 6 inline comments as done.
  • add more musttail guards, a musttail assert, 18 new tests
This revision is now accepted and ready to land.Oct 12 2021, 3:25 PM

If we replace musttail CI with non-CI or CI without musttail, maybe we should have an assert somewhere to detect this issue for new libcall simplifications

Done. PTAL @ asserts added to InstCombinerImpl::tryOptimizeCall in llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
1633

This case is tricky. Please review my changes here and to llvm/test/Transforms/InstCombine/pow-1.ll carefully. I think I have it right though, since the below transforms replace the call to pow with non-CallInsts, while above are CallInsts.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2489–2491

Thinking about this overnight...if this is the one place where replacement occurs, then why don't I just copy over the tail call kind here, rather than use the adapter in multiple locations in LibCallSimplifier? As I've already demonstrating, this approach is error prone; perhaps I could "do the work" here. Then we wouldn't need the asserts here, and this becomes a smaller change. Let me give that a shot and see if there's something I'm missing here as to why that can't be done.

xbolva00 added inline comments.Oct 13 2021, 10:32 AM
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2489–2491

This is what was the idea of https://reviews.llvm.org/D89249 but check @efriedma 's comment. First point is problematic.

For second and third:

"A lot of combines create calls, but return some other value."

I think this is not a issue. We simply fail to preserve this info, but what is problematic .. musttail. I still think if CI->isMustTailCall() == true, than we should throw away NewCI if NewCI is not a CallInst.

"For the floating-point routines, we probably want to add "tail" unconditionally."

Yeah, probably okay and can be here. Not sure how to correctly detect it, maybe TLI.has(rountine) && rountine->getType() is FP?

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
1155

Is it worth it at all?

I would just bail out libcall simplifier for musttail CIs

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2489–2491

I think this is not a issue. We simply fail to preserve this info, but what is problematic .. musttail. I still think if CI->isMustTailCall() == true, than we should throw away NewCI if NewCI is not a CallInst.

I agree. Let me comment on D89249; after spending too much time looking into this, I think that is the right approach. With some modifications to D89249, I think we should land that, then I'll rebase all these tests I've added onto that. Sound good?

xbolva00 added inline comments.Oct 13 2021, 10:51 AM
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2489–2491

Yeah,, this approach sounds better.

nickdesaulniers planned changes to this revision.Oct 13 2021, 5:23 PM
efriedma added inline comments.Oct 18 2021, 11:10 AM
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2494

I don't understand this assertion. There are two possibilities for simplification:

  1. We replace a call with some existing value.
  2. We replace a call with another new call.

For (1), this assertion doesn't make sense: we don't have a call. For (2), we probably can't safely do the replacement in general; musttail has a bunch of restrictions, and the replacement call might not satisfy them.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
1155

I agree; musttail calls should be rare enough that it isn't a big deal to just skip libcall simplification completely

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2494

These asserts were added in response to https://reviews.llvm.org/D107872#3059254. I think they do make sense, from the perspective of guarding against musttail calls being transformed.

If the old call is musttail, and the recommended replacement is not also musttail, assert that the suggestion is probably broken.

It is anomalous if a must tail call was simplified to a value. (1)

It is anomalous if a must tail call was simplified to a new call that's also not must tail.

Though if we just avoid the call to Simplifier.optimizeCall above if CI is must tail, then these asserts become impossible and can be removed.

llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
1155

So just completely skipping the call to LibCallSimplifier::optimizeCall from InstCombinerImpl::tryOptimizeCall if the call is must tail? That's going to require me to rewrite a lot of the newly added test cases here; please confirm we're in mutual understanding before I go and make such invasive changes to this patch.

efriedma added inline comments.Oct 25 2021, 10:54 AM
llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp
1155

Yes, this.

  • skip musttail calls and update musttail tests, add asserts, fix a few floating point cases
This revision is now accepted and ready to land.Oct 25 2021, 3:52 PM
nickdesaulniers marked 6 inline comments as done.Oct 25 2021, 3:54 PM

Ok, rather than a bunch of checks for musttail, I've centralized it to one place (ie. skipping libcall simplifications for musttail). I keep the manual checks, and add an assert to hopefull catch any new transforms that accidentally drop the tail and notail flags.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2475–2477

There's probably a better way to express/word this. @efriedma please let me know what to replace here.

efriedma added inline comments.Nov 1 2021, 2:44 PM
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2475–2477

I'd probably say "Skip optimizing musttail calls so LibCallSimplifier::optimizeCall doesn't have to preserve those invariants."

Actually, to be on the safe side, probably best to also skip optimizing notail calls... I'm not what "notail" actually means on a libcall, if anything, but might as well be conservative.

2494

I still think the assertion doesn't make sense.

In the "We replace a call with some existing value" case, consider, for example, memcpy. We have an optimization that transforms memcpy->llvm.memcpy. llvm.memcpy, doesn't have a return value, though, so we emit an llvm.memcpy, and return the value of the first operand. This operand may or may not be a call, and that call may or may not be a tail call.

nickdesaulniers retitled this revision from [SimplifyLibCalls] propagate tail/musttail/notail flags on CallInsts to [SimplifyLibCalls] propagate tail flags on CallInsts.
nickdesaulniers edited the summary of this revision. (Show Details)
  • rebase, avoid notail, update comment and description
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2494

For the case you describe, With will not be the CallInst to llvm.memcpy; it will be the destination operand of the original call to memcpy, so the dyn_cast will return nullptr. Thus the assertion is not checked at runtime for the case you describe.

The assertion is only checked when we replace a CallInst with another CallInst (with the new CallInst being what's returned from the call to LibCallSimplifier::optimizeCall).

To me, the assertion is a guard for future changes to LibCallSimplifier to ensure copyFlags is done safely in a manner that is done throughout this diff.

nickdesaulniers marked an inline comment as done.Nov 1 2021, 3:11 PM

bumping for review (@efriedma ).

bumping for review (@efriedma ).

efriedma added inline comments.Nov 16 2021, 1:02 PM
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2494

it will be the destination operand of the original call to memcpy

Yes.

so the dyn_cast will return nullptr

I'm not following; is there some reason the destination can't be an instruction?

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2494

so the dyn_cast will return nullptr

I'm not following; is there some reason the destination can't be an instruction?

It might be an Instruction, but not necessarily a CallInst. The dyn_cast is testing whether the returned Value is a CallInst and only checking that the tail call kind flag was propagate in that case. In all other cases of different Values returned, the assertion is not checked.


Or are you saying that the first operand to a call to memcpy could itself be a CallInst? Is that valid/possible to do in IR? ie.

%bar = call i8* memcpy(call i8* @foo(), i8* %src, i64 %n)

This operand may or may not be a call, and that call may or may not be a tail call.

I guess I'm curious how can the first operand be a call? Perhaps:

%dest = call i8* @foo()
%bar = call i8* @memcpy(i8* %dest, i8* %src, i64 %n)

Does that mean that %dest is a CallInst? If yes, then I indeed should remove the assert, but can you please confirm for me?

efriedma added inline comments.Nov 16 2021, 1:56 PM
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2494

In the following, %dest is a CallInst, yes.

%dest = call i8* @foo()
%bar = call i8* @memcpy(i8* %dest, i8* %src, i64 %n)
nickdesaulniers marked 3 inline comments as done.
  • add test case of CallInst first param to memcpy and remove assertion, as per @efriedma
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
2494

Ok, let me add that as a test case, and drop the assertion. PTAL

bumping for review (@efriedma ).

bumping for review (@efriedma or anyone else; I plan to land this next Monday if there's no further feedback).