Page MenuHomePhabricator

[WebAssembly] Implement tail calls and unify tablegen call classes
ClosedPublic

Authored by tlively on Jun 4 2019, 1:32 PM.

Details

Summary

Implements direct and indirect tail calls enabled by the 'tail-call'
feature. Updates existing call tests and adds new tests including
a binary encoding test.

Diff Detail

Repository
rL LLVM

Event Timeline

tlively created this revision.Jun 4 2019, 1:32 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 4 2019, 1:32 PM
tlively edited the summary of this revision. (Show Details)Jun 4 2019, 1:41 PM

Nice!

  • Does the LLVM guarantee tail calls to be placed in the positions in which they can be really tail calls? Can this property change when we move code around in our backend, so tail calls cannot be executed as tail calls anymore?
  • It seems we need to update the Tail call optimization section in the Code Generator doc too.
llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp
788 ↗(On Diff #203009)
  • Why do we need MVT::Glue?
  • Wouldn't it be better we handle this with the normal call instruction generation flow, rather than treating it as a special case?
llvm/lib/Target/WebAssembly/WebAssemblyInstrCall.td
26 ↗(On Diff #203009)
  • Do vt and rt have to be separate?
  • If they are the same, prefix looks always vt + ., so maybe we don't need prefix anymore?
71 ↗(On Diff #203009)

Probably not related to this CL, but I wonder maybe we should also merge this into a unified CALL instruction when we have calls that return multiple values.

82 ↗(On Diff #203009)
  • Why is the name return call (or ret_call) and not tail call?
  • Are there no tail calls that return values?
82 ↗(On Diff #203009)

Oh I checked the spec and it says return_call. Nevermind the first thing

llvm/lib/Target/WebAssembly/WebAssemblyInstrInfo.td
102 ↗(On Diff #203009)

Nit: stray indentations

llvm/test/CodeGen/WebAssembly/tailcall.ll
2 ↗(On Diff #203009)

It looks like we don't support tail calls in fastisel yet, right?

  • Do we have a plan to support tail calls in fast isel too? Then putting TODO somewhere in the fastisel code would be good.
  • If FAST version here is the same as non-tail version, do we need to check that explicitly in FileCheck before we have the actual fastisel support? The same for call.ll.
14 ↗(On Diff #203009)

How is this musttail supported in fastisel, while we have no support yet? Does that fall back to the normal isel?

30 ↗(On Diff #203009)

Maybe I'm missing something, but can this return_call return a value, while it does not have typed versions?

46 ↗(On Diff #203009)

Nit: Stray space after return_call_indirect, and double spaces between args. The same for other functions below too.

82 ↗(On Diff #203009)

How about adding a test for notail too for coverage?

dschuff added inline comments.Jun 4 2019, 10:48 PM
llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp
651 ↗(On Diff #203009)

Probably should update this error message (e.g. "tail calls aren't enabled")

tlively updated this revision to Diff 203240.Jun 5 2019, 1:26 PM
tlively marked 11 inline comments as done.
  • Fix formatting and error message, add documentation and notail tests
tlively added inline comments.Jun 5 2019, 1:28 PM
llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp
788 ↗(On Diff #203009)

I initially tried to handle this as part of the existing logic, but kept running into assertion failures in the SelectionDAGBuilder. Eventually I just cargo culted what AArch64 was doing for its tail call lowering (including the MVT::Glue) and everything worked. According to MachineValueType.h Glue "glues nodes together during pre-RA sched" so maybe it's for gluing the call to a subsequent return node? I'm not entirely sure. I'll try playing around with this a bit more to see if I can get rid of the glue.

llvm/lib/Target/WebAssembly/WebAssemblyInstrCall.td
26 ↗(On Diff #203009)

yes, for simd. vt is v16i8, v4i32, etc. but rt is always V128.

prefix is actually rt in lowercase, but there is no tablegen for lowercasing a string :(. We could actually clean a lot of SIMD tablegen code up if we could properly manipulate strings, but I'm not sure that would be a welcome tablegen feature.

71 ↗(On Diff #203009)

Yes, something like that is going to need to happen. It will probably be rather tricky, given the rigidity of the SelectionDAG type system.

82 ↗(On Diff #203009)

In wasm, return_call is not just a call that happens to be in a tail position, but actually a return and a call rolled into a single action. So a return_call can be moved by optimizations in any way that a return could be moved.

Since the instruction performs a return, it is impossible for it to produce a value that is consumed in the current context, which is why it is not modeled as returning a value. In Binaryen this is clearer because return_call would have type unreachable.

llvm/test/CodeGen/WebAssembly/tailcall.ll
14 ↗(On Diff #203009)

Yes, musttail causes fastisel to fall back to normal isel. I tried adding fastisel support for tail call but it didn't work out. Maybe I was missing some glue...

30 ↗(On Diff #203009)

It returns a value to the caller of the current function but does not return a value to the current function itself.

46 ↗(On Diff #203009)

The space is not stray, unfortunately. There is a FIXME comment in the instruction printer to remove the leading comma.

I have fixed the double spaces.

aheejin added inline comments.Jun 5 2019, 4:14 PM
llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp
788 ↗(On Diff #203009)

I see. It sounds requiring MVT::Glue actually makes sense in that case. But I still wonder why can't we handle this in the existing logic? Aren't the opcode and MVT::Glue only different things from the normal workflow? And don't we need InTyList as well, as in the normal flow?

llvm/lib/Target/WebAssembly/WebAssemblyInstrCall.td
82 ↗(On Diff #203009)

Hmm, I see. Then I think we'd need isReturn = 1 for these instructions.

llvm/test/CodeGen/WebAssembly/tailcall.ll
2 ↗(On Diff #203009)

ping

14 ↗(On Diff #203009)

Then how about putting a TODO comment in WebAssemblyFastISel.cpp or somewhere?

tlively updated this revision to Diff 203470.Jun 6 2019, 6:06 PM
tlively marked 2 inline comments as done.
  • Add TODO in FastISel, add isReturn attribute, integrate into existing logic flow
tlively marked an inline comment as done.Jun 6 2019, 6:08 PM
tlively added inline comments.
llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp
788 ↗(On Diff #203009)

I integrated the IsTailCall path into the existing logic flow. I think this makes the code more complicated, but perhaps it is less surprising now.

llvm/test/CodeGen/WebAssembly/tailcall.ll
2 ↗(On Diff #203009)

I suppose we should probably support tail calls in FastISel. I started doing that but ran into issues so I gave up. Probably worth another shot in a separate PR. I've added a TODO.

FastISel is not the same as DAG ISel because it lowers optional tail calls to normal calls while DAG ISel lowers them to tail calls. Since there is a difference I thought it worth a test.

dschuff added inline comments.Jun 6 2019, 10:52 PM
llvm/docs/CodeGenerator.rst
2107 ↗(On Diff #203470)

Shouldn't we have the same restrictions on PIC code?
Also, while it seems like va_arg and byval should work, if we're going to promise to optimize those too, we should have some tests.

aheejin added inline comments.Jun 7 2019, 4:03 AM
llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp
790 ↗(On Diff #203470)
  • Sorry, but why should we clear InTys here? I understand that we don't need output types, but should input types different from normal calls?
  • InTys.push_back(MVT::Other); is common for both if and else, so we can hoist it (If we don't need to clear InTys)
tlively marked an inline comment as done.Jun 7 2019, 10:16 AM
tlively added inline comments.
llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp
790 ↗(On Diff #203470)

The terminology here is super confusing, but everything named In* refers to values coming back into the current frame once the call finishes, i.e. the return values. return_call has no return values except for the chain and glue, so InTys gets cleared.

We would need to duplicate the condition for the clear and the glue push if we hoisted the other push, so I don't think it's worth it.

aheejin added inline comments.Jun 7 2019, 11:03 AM
llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp
790 ↗(On Diff #203470)

Oh I see.... I thought InTys is the input parameters, and that was one of the reasons I suggested merging into the existing workflow. Yeah, the benefits of merging look a bit less clear then. If you think the previous code is more clear I think it's good to revert to it. Sorry for my confusion.

tlively marked an inline comment as done.Jun 7 2019, 12:25 PM
tlively added inline comments.
llvm/docs/CodeGenerator.rst
2107 ↗(On Diff #203470)

I'm not totally clear on the details of our PIC code, but any direct or indirect call could be lowered to a tail call, so I'm not sure why there should be a restriction.

I'll add tests for byval, varargs, etc.

sbc100 added inline comments.Jun 7 2019, 2:18 PM
llvm/docs/CodeGenerator.rst
2107 ↗(On Diff #203470)

IIRC PIC shouldn't effect direct calls. It effects indirect calls since function addresses aren't statically known.

tlively updated this revision to Diff 203651.Jun 7 2019, 5:39 PM
  • Restore previous logic, add tests for strange ABIs and prototype mismatches
aheejin added inline comments.Jun 8 2019, 3:26 PM
llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp
795 ↗(On Diff #203651)

Now we have reverted to the previous logic, we don't need RET_CALL here

llvm/test/CodeGen/WebAssembly/tailcall.ll
120 ↗(On Diff #203651)

Not sure what this tests..? The function name is mismatched_prototypes but the prototypes here match. And the comment says musttail requires ... but this is not a musttail but a tail. The same for other methods below.

tlively marked an inline comment as done.Jun 9 2019, 1:09 PM
tlively added inline comments.
llvm/test/CodeGen/WebAssembly/tailcall.ll
120 ↗(On Diff #203651)

The prototypes of the caller and callee do not match. Using musttail here would be an LLVM validation error, but we can still test with tail, and similar for the following tests. I'll clarify the comments.

aheejin added inline comments.Jun 9 2019, 3:40 PM
llvm/test/CodeGen/WebAssembly/tailcall.ll
120 ↗(On Diff #203651)

Sorry, but don't they match..?
Declaration:

declare i32 @baz(i32, i32, i32)

Call:

tail call i32 @baz(i32 0, i32 42, i32 6)
tlively updated this revision to Diff 204232.Jun 12 2019, 1:26 AM
  • Address comments
aheejin accepted this revision.Jun 12 2019, 1:53 AM

LGTM!

llvm/test/CodeGen/WebAssembly/tailcall.ll
120 ↗(On Diff #203651)

Talked offline and turned out I didn't correctly understand what the comment meant

This revision is now accepted and ready to land.Jun 12 2019, 1:53 AM
This revision was automatically updated to reflect the committed changes.