Page MenuHomePhabricator

[FunctionAttrs] Infer willreturn for functions without loops
ClosedPublic

Authored by nikic on Wed, Jan 13, 1:48 PM.

Details

Summary

If a function doesn't contain loops and does not call non-willreturn functions, then it is willreturn. Handling of the loop case is left as an exercise to the reader ;)

I think this should give us enough inference to move forward with D94106.

Diff Detail

Event Timeline

nikic created this revision.Wed, Jan 13, 1:48 PM
nikic requested review of this revision.Wed, Jan 13, 1:48 PM
Herald added a project: Restricted Project. · View Herald TranscriptWed, Jan 13, 1:48 PM

I still think we should check to enable a light-attributor run in the beginning of the pipeline. The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

lib/Transforms/IPO/FunctionAttrs.cpp
1443 ↗(On Diff #316507)

I never used this function. Does it handle irreducible control flow properly? Maybe we want a test just to be sure.

nikic updated this revision to Diff 316682.Thu, Jan 14, 9:29 AM

Add test for infinite recursion and irreducible flow.

nikic added a comment.Thu, Jan 14, 9:42 AM

I still think we should check to enable a light-attributor run in the beginning of the pipeline.

I was hoping to get the willreturn-related bugs fixed in time for LLVM 12, so sticking to the existing infrastructure seems like the safer bet :) It probably makes more sense to enable the attributor after branching rather than before.

The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

I thought about this, but I don't think that we can use an optimistic fixpoint here without some much more sophisticated analysis. Just naively assuming "willreturn until proven otherwise" will incorrectly mark infinite recursion as willreturn:

; Not willreturn.
define void @willreturn_recursion() {
  tail call void @willreturn_recursion()
  ret void
}

Without mustprogress, I believe that function is well-defined (or at least with musttail it's well-defined for sure). Inferring willreturn for a non-trivial SCC (without mustprogress) would require proving that the recursion is finite. And as the current code doesn't even handle finite loops, this is a bit out of scope...

lib/Transforms/IPO/FunctionAttrs.cpp
1443 ↗(On Diff #316507)

I believe it will just pick some possible choice of backedges for the irreducible case, which is good enough for this purpose. I've added a test.

fhahn added inline comments.Thu, Jan 14, 9:50 AM
lib/Transforms/IPO/FunctionAttrs.cpp
1441 ↗(On Diff #316682)

We do not really need to find all back edges, wouldn't it be sufficient to just traverse the CFG and exit once we found a cycle?

1447 ↗(On Diff #316682)

You could use the instruction() iterator range to directly iterate over all instructions, e.g.

return all_of(instructions(F), [](const Instruction &I){
  const auto *CB = dyn_cast<CallBase>(&I);
  return !CB || CB->hasFnAttr(Attribute::WillReturn);
});
nikic updated this revision to Diff 316693.Thu, Jan 14, 9:56 AM

Use all_of(instructions(F)).

nikic marked an inline comment as done.Thu, Jan 14, 10:00 AM
nikic added inline comments.
lib/Transforms/IPO/FunctionAttrs.cpp
1441 ↗(On Diff #316682)

I don't think FindFunctionBackedges is expensive enough to warrant reimplementing it here. Note that just keeping a visited set doesn't cut it, as that would detect any join point. You need to perform a DFS search, and doing that non-recursively is ugly enough that I'd rather not repeat it.

jdoerfert added a comment.EditedThu, Jan 14, 10:06 AM

EDIT: I'm fine with this patch, FWIW.

I still think we should check to enable a light-attributor run in the beginning of the pipeline.

I was hoping to get the willreturn-related bugs fixed in time for LLVM 12, so sticking to the existing infrastructure seems like the safer bet :) It probably makes more sense to enable the attributor after branching rather than before.

Fair. As I said, we can enable it in a restricted, lightweight mode first. Could you remind me which bugs?

The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

I thought about this, but I don't think that we can use an optimistic fixpoint here without some much more sophisticated analysis. Just naively assuming "willreturn until proven otherwise" will incorrectly mark infinite recursion as willreturn:

; Not willreturn.
define void @willreturn_recursion() {
  tail call void @willreturn_recursion()
  ret void
}

So, I run this through the Attributor: https://opt.godbolt.org/z/TqsK86
Not what we were looking for, so here is the non-trivial version: https://opt.godbolt.org/z/rbeedM

Without mustprogress, I believe that function is well-defined (or at least with musttail it's well-defined for sure). Inferring willreturn for a non-trivial SCC (without mustprogress) would require proving that the recursion is finite. And as the current code doesn't even handle finite loops, this is a bit out of scope...

I don't disagree. My concern is that we should add more sophisitcated the logic in the Attributor instead. We had some initial patches wrt. finite loops, but I don't think they went in.

EDIT: I'm fine with this patch, FWIW.

I still think we should check to enable a light-attributor run in the beginning of the pipeline.

I was hoping to get the willreturn-related bugs fixed in time for LLVM 12, so sticking to the existing infrastructure seems like the safer bet :) It probably makes more sense to enable the attributor after branching rather than before.

Fair. As I said, we can enable it in a restricted, lightweight mode first. Could you remind me which bugs?

D94106 fixes the important one, though isGuaranteedToTransferExecutionToSuccessor is also buggy for languages without forward progress. Functions with infinite loops getting optimized away is the number one Rust miscompile by quite a margin...

The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

I thought about this, but I don't think that we can use an optimistic fixpoint here without some much more sophisticated analysis. Just naively assuming "willreturn until proven otherwise" will incorrectly mark infinite recursion as willreturn:

; Not willreturn.
define void @willreturn_recursion() {
  tail call void @willreturn_recursion()
  ret void
}

So, I run this through the Attributor: https://opt.godbolt.org/z/TqsK86
Not what we were looking for, so here is the non-trivial version: https://opt.godbolt.org/z/rbeedM

Just to make sure we're on the same page, both of those would be bugs in attributor right? The first one shouldn't be unreachable, and the second one shouldn't be willreturn, at least not without more information than is contained in that IR.

lib/Transforms/IPO/FunctionAttrs.cpp
1441 ↗(On Diff #316682)

I ran some tests to check the compile-time impact. For this patch as-is: https://llvm-compile-time-tracker.com/compare.php?from=17fb21f875f4aaf6ad2cf9499cb75d76588167f2&to=335a834be8fe9a571fdbeea1262989c704ba91cf&stat=instructions There is a 0.1% regression. However, if I comment out the setWillReturn call, I get: http://llvm-compile-time-tracker.com/compare.php?from=17fb21f875f4aaf6ad2cf9499cb75d76588167f2&to=1b9a75cff1543e5ca29dea0dd56b111312901d98&stat=instructions So it seems that the impact here is due to second-order effects. The FindFunctionBackedges call itself doesn't appear to be problematic.

EDIT: I'm fine with this patch, FWIW.

I still think we should check to enable a light-attributor run in the beginning of the pipeline.

I was hoping to get the willreturn-related bugs fixed in time for LLVM 12, so sticking to the existing infrastructure seems like the safer bet :) It probably makes more sense to enable the attributor after branching rather than before.

Fair. As I said, we can enable it in a restricted, lightweight mode first. Could you remind me which bugs?

D94106 fixes the important one, though isGuaranteedToTransferExecutionToSuccessor is also buggy for languages without forward progress. Functions with infinite loops getting optimized away is the number one Rust miscompile by quite a margin...

Right. We should not delete non-mustprogress non-side-effect calls. Probably requires changes in a few more places.

The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

I thought about this, but I don't think that we can use an optimistic fixpoint here without some much more sophisticated analysis. Just naively assuming "willreturn until proven otherwise" will incorrectly mark infinite recursion as willreturn:

; Not willreturn.
define void @willreturn_recursion() {
  tail call void @willreturn_recursion()
  ret void
}

So, I run this through the Attributor: https://opt.godbolt.org/z/TqsK86
Not what we were looking for, so here is the non-trivial version: https://opt.godbolt.org/z/rbeedM

Just to make sure we're on the same page, both of those would be bugs in attributor right? The first one shouldn't be unreachable, and the second one shouldn't be willreturn, at least not without more information than is contained in that IR.

I agree for the first one. Mustprogress is missing for unreachable to correct. The second one is correct, or am I missing something?

nikic added a comment.Thu, Jan 14, 2:57 PM

The logic seems sound, could be improved since this does initialize the fixpoint computation with a pessimistic starting value. One comment below, the rest is OK for merging.

I thought about this, but I don't think that we can use an optimistic fixpoint here without some much more sophisticated analysis. Just naively assuming "willreturn until proven otherwise" will incorrectly mark infinite recursion as willreturn:

; Not willreturn.
define void @willreturn_recursion() {
  tail call void @willreturn_recursion()
  ret void
}

So, I run this through the Attributor: https://opt.godbolt.org/z/TqsK86
Not what we were looking for, so here is the non-trivial version: https://opt.godbolt.org/z/rbeedM

Just to make sure we're on the same page, both of those would be bugs in attributor right? The first one shouldn't be unreachable, and the second one shouldn't be willreturn, at least not without more information than is contained in that IR.

I agree for the first one. Mustprogress is missing for unreachable to correct. The second one is correct, or am I missing something?

Nope, the second one is indeed correct, I misread the output. Sorry for the noise!

nikic added a comment.Wed, Jan 20, 2:32 PM

Any further concerns for this change?

This revision is now accepted and ready to land.Wed, Jan 20, 9:09 PM
nikic added inline comments.Thu, Jan 21, 11:35 AM
lib/Transforms/IPO/FunctionAttrs.cpp
1441 ↗(On Diff #316682)

I've looked a bit closer into what causes the compile-time regression, and apparently it is the setWillReturn() call itself. Adding an attribute is quite expensive (we create AttributeBuilders for the original attributes and the new attribute, merge them, reconstruct an attribute set from that, look up the interned set...) Something that can be optimized, but otherwise not related to this patch.

Herald added a project: Restricted Project. · View Herald TranscriptThu, Jan 21, 11:44 AM