This is an archive of the discontinued LLVM Phabricator instance.

[LCG] Add the necessary functionality to the LazyCallGraph to support inlining.
ClosedPublic

Authored by chandlerc on Sep 5 2016, 12:59 AM.

Details

Summary

The basic inlining operation makes the following changes to the call graph:

  1. Add edges that were previously transitive edges. This is always trivial and this patch gives the LCG helper methods to make this more convenient.
  2. Remove the inlined edge. We had existing support for this, but it contained bugs that needed to be fixed. Testing in the same pattern as the inliner exposes these bugs very nicely.
  3. Delete a function when it becomes dead because it is internal and all calls have been inlined. The LCG had no support at all for this operation, so this adds that support.

Two unittests have been added that exercise this specific mutation pattern to
the call graph. They were extremely effective in uncovering bugs. Sadly,
a large fraction of the code here is just to implement those unit tests, but
I think they're paying for themselves. =]

This was split out of a patch that actually uses the routines to implement
inlining in the new pass manager. I'll send it out next, I just wanted to
isolate (with unit tests) the logic that was entirely within the LCG.

Depends on D24219

Diff Detail

Repository
rL LLVM

Event Timeline

chandlerc updated this revision to Diff 70306.Sep 5 2016, 12:59 AM
chandlerc retitled this revision from to [LCG] Add the necessary functionality to the LazyCallGraph to support inlining..
chandlerc updated this object.
chandlerc added a reviewer: sanjoy.
chandlerc added a subscriber: llvm-commits.
eastig added a subscriber: eastig.Sep 5 2016, 7:33 AM
sanjoy edited edge metadata.Sep 7 2016, 11:48 PM

Hi Chandler,

I've not yet had a chance to look at this in detail, so I only have some superficial comments inline. However, I don't (yet! :) ) believe you when you say that inlining only does the three trivial transforms you outlined above. Because InlineFunction does some basic simplification I think it can introduce new SCCs. For instance, if I run opt -always-inline (and nothing else) on

define void @f(void()* %p) alwaysinline {
  call void %p()
  ret void
}

define void @g() {
  call void @f(void()* @h)
  ret void
}

define void @h() {
  call void @g()
  ret void
}

I get

; ModuleID = 'inl.ll'
source_filename = "inl.ll"

; Function Attrs: alwaysinline
define void @f(void ()* %p) #0 {
  call void %p()
  ret void
}

define void @g() {
  call void @h()
  ret void
}

define void @h() {
  call void @g()
  ret void
}

attributes #0 = { alwaysinline }

That is, we form a new SCC containing @g and @h.

lib/Analysis/LazyCallGraph.cpp
1215 ↗(On Diff #70306)

Nit: spelling of sequnece

1302 ↗(On Diff #70306)

Can we put this logic inside connectRefSCC ?

1413 ↗(On Diff #70306)

llvm::find?

1496 ↗(On Diff #70306)

Nit: s/fine/find/

sanjoy requested changes to this revision.Sep 7 2016, 11:48 PM
sanjoy edited edge metadata.

"Marking as read"

This revision now requires changes to proceed.Sep 7 2016, 11:48 PM

Hi Chandler,

I've not yet had a chance to look at this in detail, so I only have some superficial comments inline. However, I don't (yet! :) ) believe you when you say that inlining only does the three trivial transforms you outlined above. Because InlineFunction does some basic simplification I think it can introduce new SCCs. For instance, if I run opt -always-inline (and nothing else) on

define void @f(void()* %p) alwaysinline {
  call void %p()
  ret void
}

define void @g() {
  call void @f(void()* @h)
  ret void
}

define void @h() {
  call void @g()
  ret void
}

I get

; ModuleID = 'inl.ll'
source_filename = "inl.ll"

; Function Attrs: alwaysinline
define void @f(void ()* %p) #0 {
  call void %p()
  ret void
}

define void @g() {
  call void @h()
  ret void
}

define void @h() {
  call void @g()
  ret void
}

attributes #0 = { alwaysinline }

That is, we form a new SCC containing @g and @h.

Thanks for the example! I hadn't really thought a lot about devirtualization happening during the simplification, but of course it can easily happen as you show here.

I stand by my claim that this patch tests the *basic* graph updates necessary for inlining. ;] This is a bit more than "just" inlining, not that our APIs make that visible to the caller in any useful way.

I'll add this as a high-level test case for the inliner port patch and update it to take this into account. That may in turn motivate more unittests of the core LCG functionality, but even if so I'd prefer to put those extra tests in a separate patch if that's OK?

chandlerc updated this revision to Diff 72447.Sep 26 2016, 1:22 AM
chandlerc edited edge metadata.

Rebase and ping...

chandlerc updated this revision to Diff 72449.Sep 26 2016, 1:46 AM
chandlerc marked 3 inline comments as done.
chandlerc edited edge metadata.

Update to address some specific comments I missed previously, sorry about that.
Nothing really substantive though. Mostly using llvm's "find" that accepts
a range.

Sorry I missed the inline comments at first, addressed all but one and responded to that one below.

lib/Analysis/LazyCallGraph.cpp
1302 ↗(On Diff #70306)

We already do related things in connectRefSCC, but there are callers to that which don't need to do the re-analysis?

sanjoy accepted this revision.Sep 29 2016, 10:23 PM
sanjoy edited edge metadata.

lgtm with some comments inline

Ignore the comment with . as the body -- for some reason phabricator refused to delete a stale comment.

include/llvm/Analysis/LazyCallGraph.h
736 ↗(On Diff #72449)

I'd drop the "strictly" (here and below). (Or clarify "strictly" as opposed to what?).

908 ↗(On Diff #72449)

s/an SCC/a maximal SCC/, to make things 100% obvious.

Same for RefSCC

lib/Analysis/LazyCallGraph.cpp
1340 ↗(On Diff #72449)

If we're inserting a call edge and &TargetRC == this then I think we should assert that the target SCC is equal to or a descendent of the source SCC.

Actually, perhaps we should assert the target SCC is equal to or a descendent of the source SCC whenever we're inserting a call edge (i.e. without regards to whether &TargetRC == this). That'll be partially redundant with TargetRC.isDescendantOf(*this) below, but I think that's fine.

1408 ↗(On Diff #72449)

How about recursive functions? It seems reasonable to want to all removeDeadFunction on them too.

1413 ↗(On Diff #72449)

Any reason why you can't compact the EntryEdges vector here (i.e. swap the last element with the EII->second th element, pop the last element and update EntryIndexMap)?

1425 ↗(On Diff #72449)

.

1434 ↗(On Diff #72449)

s/necesasry/necessary/

1440 ↗(On Diff #72449)

llvm::all_of

This revision is now accepted and ready to land.Sep 29 2016, 10:23 PM
chandlerc marked 5 inline comments as done.Oct 11 2016, 11:58 PM

Thanks again for the review! Committing shortly and will make two follow-ups to address the comments that seem separable (either needing more utility code unrelated to this patch, and/or needing more tests).

lib/Analysis/LazyCallGraph.cpp
1340 ↗(On Diff #72449)

We don't have any utility code for checking if an SCC is a descendent of another SCC in the call graph, so writing these assertions is very verbose right now. So I'll plan add it in a follow-up with some utility code.

1408 ↗(On Diff #72449)

Interesting. I mean, yes, it does. And yet the caller I wanted to call this has this exact check before calling it.

But I agree that it seems like a meaningless restriction at *this* layer of the API.

I've left a FIXME here for now as I'd like to add this in a follow-up commit with its own test case.

1413 ↗(On Diff #72449)

It would make the iteration order dependent on the particular mutation order which seems ... unfortunate.

If the sparseness ever becomes an issue here, I'd like to add an ADT that handles this generically when growing the vector.

This revision was automatically updated to reflect the committed changes.