Page MenuHomePhabricator

Teach the inliner how to preserve musttail invariants
ClosedPublic

Authored by rnk on Apr 24 2014, 1:36 PM.

Diff Detail

Repository
rL LLVM

Event Timeline

rnk updated this revision to Diff 8816.Apr 24 2014, 1:36 PM
rnk retitled this revision from to Teach the inliner how to preserve musttail invariants.
rnk added a reviewer: chandlerc.
rnk added a subscriber: Unknown Object (MLST).
rnk added a reviewer: nicholas.
chandlerc added inline comments.May 6 2014, 11:43 AM
lib/IR/Instructions.cpp
327 ↗(On Diff #8816)

Please commit this separately with a separate test? Maybe a unittest?

lib/Transforms/Utils/InlineFunction.cpp
483 ↗(On Diff #8816)

This is called in a context that needs it to not go truly linear... And it doesn't. I almost want to call it 'isImmediatelyPrecededByMustTailCall', but the bitcast thing makes that a lie. Maybe just some comments?

687–690 ↗(On Diff #8816)

I assume the after cases should have "h"? Actually, shouldn't these be "f -> g -> f" => "f -> f"?

692–693 ↗(On Diff #8816)

I would sink this comment to the loop body.

744–745 ↗(On Diff #8816)

Do all of the passes using lifetime markers know this?

It might be useful to separate this into its own patch with its own test case.

795 ↗(On Diff #8816)

You say "should" but then "assert" below. I think the should is correct though...

804 ↗(On Diff #8816)

So, I don't think you can *always* assert. What about a musttail call to a function that just happens to return the result of a non-musttail call? Above, you set the flag if any call is musttail, so it seems you should just continue if this call site isn't a musttail.

Similarly, I don't think you can assert that there will be a callinst here.

rnk added inline comments.May 6 2014, 1:56 PM
lib/IR/Instructions.cpp
327 ↗(On Diff #8816)

Done.

lib/Transforms/Utils/InlineFunction.cpp
483 ↗(On Diff #8816)

Comments sound good to me.

687–690 ↗(On Diff #8816)

Yeah. Let's go with f -> g -> f. That's the example described in the paragraph above. The reader can extrapolate a larger cyclical call graph.

692–693 ↗(On Diff #8816)

done

744–745 ↗(On Diff #8816)

Sure. I'll split this into a followup patch to highlight the test case that fails without it. It fixes the byval and dynalloca test cases.

795 ↗(On Diff #8816)

The assert was correct. I reworked this to be simpler.

804 ↗(On Diff #8816)

We are looping over the second partition here, i.e. returns that are preceded by musttail. So, all of these things have to be true, or there are bugs in isPrecededByMustTailCall.

It sounds like this was confusing, so I'll restructure it without partition. That was silly.

rnk updated this revision to Diff 9130.May 6 2014, 1:57 PM
  • review
  • split out lifetime.end change and test cases
chandlerc edited edge metadata.May 6 2014, 2:04 PM

Ok, this makes more sense now. Thahnks for the clue-bat.

I want to ruminate on the bit about not needing stackrestore. I think I believe you, but I don't fully understand why yet and I would like to. But below are some easy comments to just clean up code.

lib/Transforms/Utils/InlineFunction.cpp
697 ↗(On Diff #9130)

nit: invert and use continue to reduce indentation

794 ↗(On Diff #9130)

nit: as above, invert and continue to reduce indentation.

795–800 ↗(On Diff #9130)

Rather than duplicating isPrecededByMustTailCall, make that function getPrecedingMustTailCallInst or some such, and have it return null when there is no call? That should make this loop simplify quite a bit.

rnk updated this revision to Diff 9136.May 6 2014, 2:32 PM
rnk edited edge metadata.
  • reduce indentation
  • return the preceding musttail call
lib/Transforms/Utils/InlineFunction.cpp
697 ↗(On Diff #9130)

done

794 ↗(On Diff #9130)

done

795–800 ↗(On Diff #9130)

Sure. It helps a bit, but I have to get the bitcast instr so I can erase it.

Sorry for continually getting distracted here. I think this is essentially fine. Feel free to submit whenever, and we can figure out the comments and the confusing parts as we go. I don't think there is anything wrong here.

lib/Transforms/Utils/InlineFunction.cpp
482–483 ↗(On Diff #9136)

Stale comment.

694–705 ↗(On Diff #9136)

Would it make sense to sink this comment down to the TailCallKind bit below?

780–784 ↗(On Diff #9136)

It's really surprising to me that this applies to *all* dynamic allocas rather than just to inalloca arguments... Maybe I'm just missing the point, but I'd appreciate a comment clarifying why this makes sense.

Is there a test case that covers this? I can't tell if some of the CHECK-NEXT ones actually cover this case.

chandlerc accepted this revision.May 15 2014, 10:09 AM
chandlerc edited edge metadata.

(and actually mork it as LGTM in phab...)

This revision is now accepted and ready to land.May 15 2014, 10:09 AM
rnk added a comment.May 15 2014, 1:13 PM

Thanks, committing. I'll update the follow-on, http://reviews.llvm.org/D3630, in a sec.

lib/Transforms/Utils/InlineFunction.cpp
482–483 ↗(On Diff #9136)

fixed

694–705 ↗(On Diff #9136)

Seems reasonable.

780–784 ↗(On Diff #9136)

I'm not really following.

Here's what could happen when inlining this fragment:

%a = alloca i8, i32 %n
call void @use_a(i8* %a)
musttail call void @bar()
ret void

Without this change, after inlining, we get this:

%sp = call i8* @llvm.stacksave()
%a = alloca i8, i32 %n
call void @use_a(i8* %a)
musttail call void @bar()
call void @llvm.stackrestore(i8*)
ret void

First, this fails musttail verification, because now the musttail call isn't in tail position.

The stackrestore is completely redundant with the ret. Unlike other rets, this ret is going to remain in the inlined function. It isn't removed later and merged back into the normal control flow.

Would it make more sense to reframe the comment to talk about the fact that this ret isn't going a way and stackrestore before ret is pointless? The way I think about it is that we just did a musttail call which already did the work of clearing the stack, so there's no reason to restore the stack.

Anyway, this should have been split into the @lifetime.end change, because it's covered by those tests. I'll go do that.

rnk closed this revision.May 19 2014, 7:24 AM
rnk updated this revision to Diff 9564.

Closed by commit rL208910 (authored by @rnk).