Page MenuHomePhabricator

Split tailcallelim into tailcallmark and tailcallelim
AcceptedPublic

Authored by uenoku on Mar 30 2019, 9:40 AM.

Details

Summary

Currently, tailcallelim does
(1) mark call instruction as "tail" if possible
(2) eliminate tail call and generate loops

Like memcpyopt, some passes add call instruction but these calls are not marked as tail[1]. So it is better to add (1) after such passes.

I split tailcallelim into tailcallmark and tailcallelim.

tailcallmark - only for marking function calls as "tail".
tailcallelim - does what old tailcalleim did except for marking the calls.

[1]https://reviews.llvm.org/D59534

Diff Detail

Event Timeline

uenoku created this revision.Mar 30 2019, 9:40 AM
lebedev.ri added inline comments.
include/llvm/Transforms/Scalar/TailCallMarking.h
2

License blurb missing

lib/Transforms/Scalar/TailCallMarking.cpp
9

Might be a good idea to add a comment here as to what this does

lib/Transforms/Scalar/TailRecursionElimination.cpp
531

block

uenoku updated this revision to Diff 192982.EditedMar 30 2019, 10:04 AM

Add license blurb

uenoku updated this revision to Diff 192983.Mar 30 2019, 10:08 AM
uenoku marked an inline comment as done.

Add description

efriedma added inline comments.Apr 1 2019, 11:20 AM
lib/Transforms/Scalar/TailRecursionElimination.cpp
536

There's a helper in llvm/ADT/DepthFirstIterator.h which can automatically handle all the boilerplate for iterating over all the reachable blocks in a function.

nicholas added inline comments.
lib/Transforms/Scalar/TailCallMarking.cpp
2

Fix ruler, it's too short.

lib/Transforms/Scalar/TailRecursionElimination.cpp
530–539

"areAllCallsTailCalls"? "allCallsAreTail"? "allCallsHaveTail"? Or the inverse, "hasAnyNonTailCall"?

uenoku updated this revision to Diff 193293.Apr 2 2019, 8:13 AM
uenoku marked 2 inline comments as done.

use DepthFirstIterator and rename

I might have missed some earlier discussion but how does this solve the problem? Also, I assume the problem is still PR41047, correct?

lib/Transforms/Scalar/TailCallMarking.cpp
14

I would have "just" created the second pass in the original TailRecursionElimination.cpp file but separating it is fine too. (One benefit would have been a much smaller diff ;))

uenoku marked 3 inline comments as done.Apr 2 2019, 10:24 PM
This comment was removed by uenoku.
lib/Transforms/Scalar/TailRecursionElimination.cpp
531

Sorry, could you tell me what this means?

Yes, the problem is PR41047. Inserting tailcallmark after memcpyopt would solve this problem.

Will you have a plan to make Attributor mark "tail"? If so, I think it is better to leave marking to Attributor.

nicholas added inline comments.Apr 2 2019, 10:28 PM
lib/Transforms/Scalar/TailRecursionElimination.cpp
531

There's a typo in the comment, "blcok" should read "block".

uenoku updated this revision to Diff 193434.Apr 2 2019, 10:37 PM
uenoku marked an inline comment as done.

Fix typo.

uenoku added inline comments.Apr 2 2019, 10:37 PM
lib/Transforms/Scalar/TailRecursionElimination.cpp
531

Oh, Thanks.

Yes, the problem is PR41047. Inserting tailcallmark after memcpyopt would solve this problem.

Will you have a plan to make Attributor mark "tail"? If so, I think it is better to leave marking to Attributor.

My main point is that you did not move tailcallmark after memcpyopt, correct?

If we want to change how/when tail is deduced is a separate discussion I guess. Keeping the existing deduction is the right thing for the patch.

uenoku added a comment.EditedApr 3 2019, 7:42 PM

Yes, tailcallmark is not moved after memcpyopt in this patch.
I was going to make another patch for this change.

So this patch only split the pass and there is nothing to be changed in results.

jdoerfert accepted this revision.Apr 3 2019, 10:16 PM

Yes, tailcallmark is not moved after memcpyopt in this patch.
I was going to make another patch for this change.

So this patch only split the pass and there is nothing to be changed in results.

Fair point.

Except for the things I noted in the comments, this LGTM.

lib/Transforms/Scalar/TailRecursionElimination.cpp
528

Function behavior descriptions go usually above the function (3 x /). See canMoveAboveCall below for an example.

531

Please use BasicBlock and Instruction instead of auto, it is not helping to hide the type.

536

I'd remove the braces around a single return stmt.

This revision is now accepted and ready to land.Apr 3 2019, 10:16 PM
uenoku updated this revision to Diff 193662.Apr 3 2019, 11:28 PM
uenoku marked an inline comment as done.

Remove auto and brace

uenoku marked 4 inline comments as done.Apr 3 2019, 11:29 PM
uenoku added a comment.Apr 4 2019, 6:51 PM

I don't have commit access. Would you commit?

I don't have commit access. Would you commit?

I'm running the tests now, will commit if all is good.

I don't have commit access. Would you commit?

I'm running the tests now, will commit if all is good.

I see these failures:

LLVM :: Other/opt-O2-pipeline.ll
LLVM :: Other/opt-O3-pipeline.ll
LLVM :: Other/opt-Os-pipeline.ll
LLVM :: Transforms/TailCallElim/ackermann.ll
LLVM :: Transforms/TailCallElim/dup_tail.ll

Please build LLVM with assertions and fix the tests.

jdoerfert requested changes to this revision.Apr 5 2019, 12:20 PM
This revision now requires changes to proceed.Apr 5 2019, 12:20 PM
uenoku updated this revision to Diff 194012.Apr 6 2019, 4:33 AM

Fix testcases

lebedev.ri added inline comments.Apr 6 2019, 5:03 AM
test/Other/opt-O3-pipeline.ll
90–101

This looks weird.
Does Tail Call Marking discard/does not preserve those analysises?

jdoerfert requested changes to this revision.Apr 7 2019, 11:02 PM
jdoerfert added inline comments.
test/Other/opt-O3-pipeline.ll
90–101

Good catch. It probably doesn't preserve but should. (Not only those)

This revision now requires changes to proceed.Apr 7 2019, 11:02 PM

(Probably should be using setPreservesCFG().)

uenoku updated this revision to Diff 194345.Apr 9 2019, 8:37 AM

Set preserved Analysis and fix testcases.

uenoku marked an inline comment as done.Apr 9 2019, 8:43 AM
uenoku added inline comments.
test/Other/opt-O3-pipeline.ll
90–101

I cannot be sure whether preserved Analysis are enough.
Is there missing analysis?

jdoerfert added inline comments.Apr 15 2019, 10:04 AM
test/Other/opt-O3-pipeline.ll
90–101

Optimization Remark Emitter seems to be recomputed, you should "preserve" that one as well.

uenoku updated this revision to Diff 195333.Apr 16 2019, 1:41 AM

Add preservedAnalysis

uenoku marked an inline comment as done.Apr 16 2019, 1:42 AM
uenoku updated this revision to Diff 195337.Apr 16 2019, 1:47 AM

Remove wrong file

I inlined a question. Also, did you run the tests with assertions enabled?

test/Other/opt-Os-pipeline.ll
80

Why do the analysis appear here? I would have expected them to be somewhere on the left as well.

Btw. please submit patches with *all* the context so I can see more than 3 lines if I want.

uenoku updated this revision to Diff 195672.Apr 17 2019, 9:49 PM

Make AA preserved.

uenoku marked an inline comment as done.Apr 17 2019, 9:57 PM
uenoku marked an inline comment as done.
uenoku added inline comments.
test/Other/opt-Os-pipeline.ll
80

You are right. AA should be preserved.

I submit a patch with all the context. I am sorry to have inconvenienced you.

uenoku updated this revision to Diff 195674.Apr 17 2019, 10:18 PM

I didn't added files. Fix it.

Yes, I ran the tests with assertions enabled. check-llvm and check-clang have passed.

jdoerfert accepted this revision.Apr 29 2019, 7:43 PM

Yes, I ran the tests with assertions enabled. check-llvm and check-clang have passed.

I'll need to run it (probably at the end of this week) and assuming that works out I'll submit it (= LGTM).

This revision is now accepted and ready to land.Apr 29 2019, 7:43 PM