[Local] Treat calls that may not return as being alive (WIP).

[fhahn]

Summary

With the addition of the willreturn attribute, functions that may
not return (e.g. due to an infinite loop) are well defined, if they are
not marked as willreturn.

This patch updates wouldInstructionBeTriviallyDead to not consider
calls that may not return as dead, unless they are in willreturn
functions.

[nikic]

llvm/include/llvm/IR/InstrTypes.h

1763

This isn't right, MustProgress does not guarantee that the function returns. I'd suggest to take a look at the logic in isGuaranteedToTransferExecutionToSuccessor() (which should be replaced as well).

[nikic]

Happy to see this issue finally fixed :)

I think the general approach here should be more along the lines of infering WillReturn inside FuncAttrs, and then just checking the WillReturn attribute here. Especially for languages which have no forward-progress guarantee it is important that WillReturn actually gets inferred somewhere, otherwise intrinsics will be the only thing that set the attribute.

[jdoerfert]

llvm/include/llvm/IR/InstrTypes.h

1763

willreturn || (mustprogress && readnone)

1763

Maybe readonly is sufficient given that volatile/atomic read accesses are considered writes, right?

[jdoerfert]

In D94106#2480220, @nikic wrote:

Happy to see this issue finally fixed :)

I think the general approach here should be more along the lines of infering WillReturn inside FuncAttrs, and then just checking the WillReturn attribute here. Especially for languages which have no forward-progress guarantee it is important that WillReturn actually gets inferred somewhere, otherwise intrinsics will be the only thing that set the attribute.

Maybe if we turn on the attributor for a few selected attributes only?

[fhahn]

In D94106#2480229, @jdoerfert wrote:

In D94106#2480220, @nikic wrote:

Happy to see this issue finally fixed :)

I think the general approach here should be more along the lines of infering WillReturn inside FuncAttrs, and then just checking the WillReturn attribute here. Especially for languages which have no forward-progress guarantee it is important that WillReturn actually gets inferred somewhere, otherwise intrinsics will be the only thing that set the attribute.

Maybe if we turn on the attributor for a few selected attributes only?

I think it would be good to approach this incrementally. So start with gradually making the behavior 'more' correct than it is at the moment, while not regressing on performance. Treating functions without side effects without mustprogress as 'alive' seems like a relatively safe thing to do as a start.

We should also improve the inference, but to make progress it might be be desirable to not predicate one on the other to start with. I realize that having good-enough inference to start with is the more principled approach and I am not sure if the desire to make progress outweighs that in the case at hand.

llvm/include/llvm/IR/InstrTypes.h

1763

That's a good point, in general we need to be more careful.

Though perhaps using mustprogress as an initial proxy to enable/disable this altogether would be helpful to limit the fallout at least a little bit during the transition, not here but at the use in Local.cpp. instructions there are only considered dead if there are no side-effects at all to start with.

[nikic]

In D94106#2480348, @fhahn wrote:

In D94106#2480229, @jdoerfert wrote:

In D94106#2480220, @nikic wrote:

Happy to see this issue finally fixed :)

I think the general approach here should be more along the lines of infering WillReturn inside FuncAttrs, and then just checking the WillReturn attribute here. Especially for languages which have no forward-progress guarantee it is important that WillReturn actually gets inferred somewhere, otherwise intrinsics will be the only thing that set the attribute.

Maybe if we turn on the attributor for a few selected attributes only?

I think it would be good to approach this incrementally. So start with gradually making the behavior 'more' correct than it is at the moment, while not regressing on performance. Treating functions without side effects without mustprogress as 'alive' seems like a relatively safe thing to do as a start.

We should also improve the inference, but to make progress it might be be desirable to not predicate one on the other to start with. I realize that having good-enough inference to start with is the more principled approach and I am not sure if the desire to make progress outweighs that in the case at hand.

I like incremental improvements, but I don't think this really qualifies. What you are doing here is not making the behavior more correct while not regressing performance -- you are making it more correct while not regressing performance for languages with a forward-progress guarantee. What's likely going to happen is that this lands because it works well enough for C++, and then the remaining and technically harder part gets forgotten...

It would be okay if you say that this optimization just isn't very valuable in the first place and we can switch it to only checking WillReturn, delay the actual inference of WillReturn in more places until a later time, and eat any regressions that fall out in the meantime because correctness is more important than performance. But I don't think that directly coupling it to MustProgress in this way is a good idea.

[jdoerfert]

FWIW, my comment was aimed at inference of willreturn, we can have that right now (basically) if we enable a "lightweight" attributor pass.

llvm/include/llvm/IR/InstrTypes.h

1763

mustprogress alone doesn't imply willreturn, why would we benefit from assuming it would. The deduction of willreturn in the attributor uses mustprogress with D94125.
I'd be more inclined to just look for willreturn and run the deduction early.

llvm/lib/Transforms/Utils/Local.cpp

428

Nit: move the comment before the if or use braces.

I->getFunction()

[fhahn]

In D94106#2480386, @nikic wrote:

In D94106#2480348, @fhahn wrote:

In D94106#2480229, @jdoerfert wrote:

In D94106#2480220, @nikic wrote:

Happy to see this issue finally fixed :)

I think the general approach here should be more along the lines of infering WillReturn inside FuncAttrs, and then just checking the WillReturn attribute here. Especially for languages which have no forward-progress guarantee it is important that WillReturn actually gets inferred somewhere, otherwise intrinsics will be the only thing that set the attribute.

Maybe if we turn on the attributor for a few selected attributes only?

I think it would be good to approach this incrementally. So start with gradually making the behavior 'more' correct than it is at the moment, while not regressing on performance. Treating functions without side effects without mustprogress as 'alive' seems like a relatively safe thing to do as a start.

We should also improve the inference, but to make progress it might be be desirable to not predicate one on the other to start with. I realize that having good-enough inference to start with is the more principled approach and I am not sure if the desire to make progress outweighs that in the case at hand.

I like incremental improvements, but I don't think this really qualifies. What you are doing here is not making the behavior more correct while not regressing performance -- you are making it more correct while not regressing performance for languages with a forward-progress guarantee. What's likely going to happen is that this lands because it works well enough for C++, and then the remaining and technically harder part gets forgotten...

There should be almost no impact for C++ (because all readnone functions should also be mustprogress -> willreturn), but there will be some impact to different languages (C). I don't think C++ performance is the only language for which performance regressions will block a patch. We have several large C benchmarks in our internal tracking for example and in general we report regression upstream and consider them reason for reverting. As for other languages, ideally they would closely track main to be able to spot & flag issues ASAP.

In any case, I went ahead and update this to use willreturn directly as suggested. There are a few pending patches that add willreturn in a few key places. With those, I think it should be very similar to the original patch, but split up properly. This is probably the best we can do to start with. In terms of performance impact, I expect the impact to be low for optimization levels with aggressive inlining.

There are still a few intrinsics that require adding willreturn for the tests to pass. Some updates related to that are included in the patch, but I can split them off. Once we are happy with the patch, I'll send a heads-up to llvm-dev, to let people know they should make sure willreturn is added, if possible, to intrinsics for their targets and frontend languages.

[jdoerfert]

FTR, this is the "corresponding" Attributor patch: D94743

[nikic]

The new direction of the patch looks good to me. And yes, I would prefer it if the intrinsic attribute updates were split off into a separate patch.

llvm/include/llvm/IR/Intrinsics.td

1192 ↗

(On Diff #316928)

Wow, coro.alloc and coro.free are some seriously misleading function names.

llvm/include/llvm/IR/IntrinsicsARM.td

374 ↗

(On Diff #316928)

Any reason not to use DefaultAttrsIntrinsic for these?

llvm/lib/Transforms/Utils/Local.cpp

425

Why does this check for willreturn on the calling function as well? It's not wrong, but it's also not clear to me under what circumstances the extra check would be useful.

[nikic]

llvm/lib/Transforms/Utils/Local.cpp

425

What do you think about making this condition if (!CB->willReturn() && !isa<IntrinsicInst>(CB)), with a FIXME to drop the intrinsic check later? That avoids the need to block this on intrinsic updates for now, but should be enough to avoid practical miscompiles.

[jdoerfert]

llvm/lib/Transforms/Utils/Local.cpp

425

I'm not against this but just FTR, most target independent intrinsics have been updated (IIRC). We should ping target owners to do the same for their intrinsics, such as @fhahn did for aarch64.

[fhahn]

llvm/lib/Transforms/Utils/Local.cpp

425

That sounds like a good idea. There are just too many intrinsics to update. I started updating X86 but did not have a chance to finish that yet. I'll update the patch.

[fhahn]

add escape hatch for intrinsics as suggested for now

[nikic]

This LGTM apart from the attributor test changes -- @jdoerfert Could you please check if those make sense?

llvm/test/Transforms/InstSimplify/ConstProp/math-1.ll

16 ↗

(On Diff #318646)

The changes to math-1.ll and math-2.ll are unnecessary and probably wrong -- I assume these wildcards are there to paper over some issues in platform-dependent trig accuracy.

[fhahn]

Add braces.

[fhahn]

llvm/lib/Transforms/Utils/Local.cpp

425

Why does this check for willreturn on the calling function as well? It's not wrong, but it's also not clear to me under what circumstances the extra check would be useful.

I think there could be situations where the called function is cannot be willreturn, because there are some paths that do not return. But when it is called in this particular function, only the will return path will be executed? I guess we could instead also add will return at all call-sites (but not the function itself)

I'm not saying this will happen at the moment in practice, but it seems at least conceivable in the future, e.g. if frontends are more aggressively using willreturn directly.

428

Braces finally added.

[jdoerfert]

Can we add something along the lines of the commit message for D95260

In languages where infinite side-effect free loops are undefined behavior, willreturn is inferred from readnone+mustprogress by D94502. Such languages should see no regressions from this change. For languages where infinite loops are well-defined, D94633 infers willreturn for straight-line code.

In D94106#2516777, @nikic wrote:

This LGTM apart from the attributor test changes -- @jdoerfert Could you please check if those make sense?

I assume you run the test update script, which should be OK. I double checked and it seems sensible, though the Attributor must be thought about this separately to avoid it removing such calls, that's on my plate.

[nikic]

llvm/lib/Transforms/Utils/Local.cpp

425

Why does this check for willreturn on the calling function as well? It's not wrong, but it's also not clear to me under what circumstances the extra check would be useful.

I think there could be situations where the called function is cannot be willreturn, because there are some paths that do not return. But when it is called in this particular function, only the will return path will be executed? I guess we could instead also add will return at all call-sites (but not the function itself)

I'm not saying this will happen at the moment in practice, but it seems at least conceivable in the future, e.g. if frontends are more aggressively using willreturn directly.

Right, I'd say that in this case the right thing to do is annotate the call-site. I believe that the Attributor also does inference in that direction (while FuncAttrs does not). If this is not needed to prevent a regression right now, then I would drop the check, as it's logically not the right place to do it. It should be handled by attribute inference.

[fhahn]

Undo changes in InstSimplify/ConstProp/math-* files.

[nikic]

llvm/lib/Transforms/Utils/Local.cpp

425

To add one more note to this: This kind of reasoning is applicable to most attributes. For example, we could replace the !I->mayHaveSideEffects() call below with something to the effect of !I->mayHaveSideEffects() && !I->getFunction()->mayHaveSideEffects(), and generally do this for many other call-site attribute checks. But I don't think we want to do that generally, and for that reason also don't think we should do that here.

[fhahn]

llvm/lib/Transforms/Utils/Local.cpp

425

I mostly added it out of caution, but there are no binary changes without it (on MultiSource &SPEC). I'll drop it, let's see if there are any regressions.