Page MenuHomePhabricator

[Attributor] Deduce "willreturn" function attribute
ClosedPublic

Authored by uenoku on Jun 8 2019, 7:18 AM.

Details

Summary

Deduce the "willreturn" attribute for functions.

For now, intrinsics are not willreturn. More annotation will be done in another patch.

Diff Detail

Event Timeline

uenoku created this revision.Jun 8 2019, 7:18 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 8 2019, 7:18 AM
uenoku added a comment.Jun 8 2019, 7:31 AM

The current algorithm can deduce only for very simple cases.

  • A function doesn't have any loop.
  • A function doesn't have any recursion.

I'll work on allowing some loops next.

Can you clang format the code?

What about the test changes?

llvm/lib/Transforms/IPO/Attributor.cpp
1037

Please create an AAWillReturn interface in the header so it is easier to query the attribute.

1095

for (BasicBlock *SuccBB : successors(BB)) {

1098

No braces around return

uenoku updated this revision to Diff 203721.Jun 8 2019, 11:54 PM

Address comments and add test change.

uenoku marked 3 inline comments as done.Jun 8 2019, 11:57 PM

Can you clang format the code?

I always clang format before submitting a patch.
Is there something wrong?

Can you clang format the code?

I always clang format before submitting a patch.
Is there something wrong?

I forgot why I thought it was not formatted. Forget that comment.

Last comments wrt class placement.

llvm/lib/Transforms/IPO/Attributor.cpp
1037

Now I would split this again into:
struct AAWillReturn : public AbstractAttribute that lives in the header
and
struct AAWillReturnImpl : public AAWillReturn, BooleanState that lives here.
The idea is that the AAWillReturn is exposed to everybody and AAWillReturnImpl has the code shared between all AAWillReturn deductions. It is, for example, reasonable to have a call site deduction at some point.

1045

assumed and known mixed up in the comments.

1056

I think it might make sense to use the same spelling in the assumed case as we use for the attr.

uenoku updated this revision to Diff 203760.EditedJun 9 2019, 5:46 PM

Address comments

uenoku marked 3 inline comments as done.Jun 9 2019, 5:47 PM
jdoerfert accepted this revision.EditedJun 9 2019, 6:03 PM

Declare isKnownWillReturn and isAssumedWillReturn in the base class. Then place the base class in the header. Otherwise, LGTM.

(Can you also make the dependences explicit so I know when I can commit these things, use the edit related revisions button).

This revision is now accepted and ready to land.Jun 9 2019, 6:03 PM
uenoku updated this revision to Diff 203763.Jun 9 2019, 7:27 PM

Add declarations in base class.

The current algorithm can deduce only for very simple cases.

  • A function doesn't have any loop.
  • A function doesn't have any recursion.

What about functions that exit the program, throw an exception, or longjmp?

llvm/lib/Transforms/IPO/Attributor.cpp
1109

Loop is commonly assumed to mean "natural loop", where there is one block (the header) which dominates the other blocks in the loop (the loop body). What you're looking for here is a more general thing called a cycle (equivalent to looking for a backedge). That also explains why you need your own function and can't reuse LoopInfo.

1115–1120

FYI, with effort, this could be pushed to be more efficient. df_iterator maintains its own copy of Visited, and it does its own scan over the successors of the block, neither of which need to be done twice. Unfortunately the fix is not entirely simple.

The current algorithm can deduce only for very simple cases.

  • A function doesn't have any loop.
  • A function doesn't have any recursion.

What about functions that exit the program, throw an exception, or longjmp?

I know I just posted, but I think I figured out the right rule. The rule you want is a) doesn't have a cycle b) all calls have willreturn. A function with no calls (and no cycles) can have willreturn, and a function that calls only willreturn functions (and no cycles) can have willreturn. That's assuming you don't mind a function being both willreturn and noreturn at the same time (a function that ends in unreachable). I think we just accept that, there's no point trying to prove any code free from undefined behaviour.

If I'm right, this patch doesn't need to depend on norecurse.

The current algorithm can deduce only for very simple cases.

  • A function doesn't have any loop.
  • A function doesn't have any recursion.

What about functions that exit the program, throw an exception, or longjmp?

That was an oversight in the comment but not the code, I think. There are tests for calls and exceptions. The former may prevent willreturn the latter doesn't (as of D62801). This way, willreturn is orthogonal to nothrow.

I know I just posted, but I think I figured out the right rule. The rule you want is a) doesn't have a cycle b) all calls have willreturn. A function with no calls (and no cycles) can have willreturn, and a function that calls only willreturn functions (and no cycles) can have willreturn. That's assuming you don't mind a function being both willreturn and noreturn at the same time (a function that ends in unreachable). I think we just accept that, there's no point trying to prove any code free from undefined behaviour.

If I'm right, this patch doesn't need to depend on norecurse.

Strictly speaking, it doesn't. But for now, that makes it much simpler. If you only make sure calls are optimistically willreturn you get willreturn for a potential endless recursion. That is, a function that might, depending on the input, recurse forever or not. Now, norecurse is actually "too strong" but that is fine for now.

llvm/lib/Transforms/IPO/Attributor.cpp
1115–1120

Let's not optimize it preemptively. I'll run it through LLVM-TS and SPEC2006 before I commit it anyway, if there is a change in compile or runtime I'll report it back.

uenoku added a comment.EditedJun 9 2019, 9:57 PM

The current algorithm can deduce only for very simple cases.

  • A function doesn't have any loop.
  • A function doesn't have any recursion.

What about functions that exit the program, throw an exception, or longjmp?

  • longjump shouldn't be "willreturn" but I've found that the current implementation might deduce "willreturn" (llvm.eh.sjlj.longjmp is intrinsic but it has noreturn).

I'll fix it to check noreturn.

llvm/lib/Transforms/IPO/Attributor.cpp
1109

Loop is commonly assumed to mean "natural loop", where there is one block (the header) which dominates the other blocks in the loop (the loop body). What you're looking for here is a more general thing called a cycle (equivalent to looking for a backedge).

OK, I rename it.

That also explains why you need your own function and can't reuse LoopInfo.

LoopInfo doesn't contain an irreducible loop (maybe endless loop) so I check the cycle manually for now.
I'm going to use LoopInfo to check (i) whether a function has an irreducible loop and (ii) whether all loops are guaranteed to terminate.

uenoku updated this revision to Diff 203774.Jun 9 2019, 10:53 PM
  • Rename "Loop" to "Cycle".
  • Prohibit noreturn intrinsic (ex. longjump) and add longjump test.
  • Check AANoReturnFunction
jdoerfert added inline comments.Jun 10 2019, 7:18 AM
llvm/lib/Transforms/IPO/Attributor.cpp
1109

I'm going to use LoopInfo to check (i) whether a function has an irreducible loop and (ii) whether all loops are guaranteed to terminate.

Keep it this way for now, LoopInfo will currently not simplify things

uenoku updated this revision to Diff 204213.Jun 11 2019, 8:49 PM

Fix patch.

@nicholas If you want to discuss any of this further, please say so.

llvm/lib/Transforms/IPO/Attributor.cpp
1037

Could you move this struct to the header file please?

1177

I'd argue: Either do not check for noreturn at all, which I would have initially thought we do, or do it explicitly for this function but not the callees. That way, the function which is noreturn is not willreturn and callers will no be able to get willreturn. However, once willreturn is deduced, noreturn should be irrelevant (IMHO), maybe contradicting.

llvm/test/Transforms/FunctionAttrs/will-return.ll
1

since you renamed the attribute you should think about renaming the file as well ;)

uenoku updated this revision to Diff 204425.Jun 12 2019, 10:51 PM

Address comments

uenoku marked 2 inline comments as done.Jun 12 2019, 10:54 PM
uenoku marked an inline comment as done.Jun 12 2019, 11:03 PM
uenoku added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
1177

I agree with you.

nicholas added inline comments.Jun 13 2019, 1:36 PM
llvm/lib/Transforms/IPO/Attributor.cpp
1115–1120

I doubt human-written code will trigger slow compile times in this path, but I bet it could happen with machine generated code. Just leave a TODO noting how it could be more efficient.

jdoerfert added inline comments.Jun 13 2019, 3:27 PM
llvm/lib/Transforms/IPO/Attributor.cpp
1115–1120

Agreed, to all of it. We will most likely see various "compile time problems" once we add more and more functionality (and actually turn it on), so keeping a record of fixes is very useful. @uenoku Can you add such a comment.

uenoku updated this revision to Diff 204674.Jun 13 2019, 5:28 PM

Add TODO.

uenoku updated this revision to Diff 205505.Jun 18 2019, 10:36 PM

Remove nofree.

uenoku updated this revision to Diff 206597.Jun 26 2019, 12:20 AM

Use enum attribute.

jdoerfert requested changes to this revision.Jul 5 2019, 7:52 PM
jdoerfert added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
492

I think we should be cautious and not mark intrinsics as willreturn in the update method but instead do it explicitly as such in the Intrinsics.td file.

Also, drop the braces around single statements.

llvm/test/Transforms/FunctionAttrs/willreturn.ll
2

Explicitly activate the attributor.

This revision now requires changes to proceed.Jul 5 2019, 7:52 PM
uenoku updated this revision to Diff 209227.EditedJul 11 2019, 8:19 AM
uenoku edited the summary of this revision. (Show Details)

Annotate "willreturn" in Intrinsics.td and add related test changes.

@jdoerfert
In the current implementation, updateImpl depends on AANoRecurseFunction. However, norecurse patch is abandoned and what should I do?

@jdoerfert
In the current implementation, updateImpl depends on AANoRecurseFunction. However, norecurse patch is abandoned and what should I do?

Take the AANoRecurse abstract attribute interface (no implementation) and add it to this patch. That will not improve the results but will make it work once we derive it.

uenoku updated this revision to Diff 209568.Jul 12 2019, 12:50 PM

Rebase and add NoRecurse interface. check-all passed.

For some intrinsics, I can not judge whether it is allowed to mark willreturn. I want to hear an opinion.

  • Standard C libray: especially memcpy, memmove, memset

For some intrinsics, I can not judge whether it is allowed to mark willreturn. I want to hear an opinion.

  • Standard C libray: especially memcpy, memmove, memset

Can we do the following:

  • Commit this with conservative intrinsic handling. That is, without all the intrinsics marking stuff.
  • Open another patch for the marking stuff as you have it now in here.

Basically, split the patch in two and commit the first part assuming the comments in (https://reviews.llvm.org/D63046#1572140) have been addressed.

To answer your question: memcpy, memmove, memset are willreturn

For some intrinsics, I can not judge whether it is allowed to mark willreturn. I want to hear an opinion.

  • Standard C libray: especially memcpy, memmove, memset

Can we do the following:

  • Commit this with conservative intrinsic handling. That is, without all the intrinsics marking stuff.
  • Open another patch for the marking stuff as you have it now in here. Basically, split the patch in two and commit the first part assuming the comments in (https://reviews.llvm.org/D63046#1572140) have been addressed.

    To answer your question: memcpy, memmove, memset are willreturn

OK, I'll split a patch for mem*or other stuff.
In my opinion, the annotation in this patch is enough conservative (I annotated to arithmetic function and debugging function). Is there any problem with this annotation?

uenoku updated this revision to Diff 209850.Jul 15 2019, 7:05 AM

Remove annotation for now.

uenoku updated this revision to Diff 210324.Jul 17 2019, 7:52 AM
uenoku edited the summary of this revision. (Show Details)

Rebase.

This revision was not accepted when it landed; it landed in state Needs Review.Jul 17 2019, 8:15 AM
Closed by commit rL366335: [Attributor] Deduce "willreturn" function attribute (authored by uenoku, committed by ). · Explain Why
This revision was automatically updated to reflect the committed changes.
nikic added a subscriber: nikic.Jul 27 2019, 7:35 AM
nikic added inline comments.
llvm/trunk/lib/Transforms/IPO/Attributor.cpp
1284 ↗(On Diff #210334)

In line with isGuaranteedToTransferExecutionToSuccessor(), isn't it also necessary to check for volatile memory operations, which may trap?

uenoku added inline comments.Jul 27 2019, 6:57 PM
llvm/trunk/lib/Transforms/IPO/Attributor.cpp
1284 ↗(On Diff #210334)

In D53184, it is clarified in LangRef that volatile memory operations wouldn't trap. Therefore, in my opinion, we need to fix rather isGuaranteedToTransferExecutionToSuccessor, isn't it?

nikic added inline comments.Jul 28 2019, 1:39 AM
llvm/trunk/lib/Transforms/IPO/Attributor.cpp
1284 ↗(On Diff #210334)

Thanks for pointing that out! In that case indeed the implementation of guaranteed-to-transfer should be changed. Especially the paragraph

The compiler may assume execution will continue after a volatile operation,
so operations which modify memory or may have undefined behavior can be
hoisted past a volatile operation.

seems pretty clear on this point -- this not only precludes trapping, but also a volatile MMIO operation that hangs forever.

uenoku added inline comments.Jul 28 2019, 2:32 AM
llvm/trunk/lib/Transforms/IPO/Attributor.cpp
1284 ↗(On Diff #210334)

Btw AtomicCmpXchgInst are checked in isGuaranteedToTransfer.. whether the instruction is volatile. However, I think in some cases AtomicCmpXchgInst never return so we need to fix also isGuaranteedToTransfer.. in this point. For the same reason, AtomicCmpXchgInst should be checked in willreturn deduction.

uenoku added inline comments.Jul 28 2019, 4:03 AM
llvm/trunk/lib/Transforms/IPO/Attributor.cpp
1284 ↗(On Diff #210334)

Above was a misunderstanding of me about AtomicCmpXchgInst. Please ignore.