This is an archive of the discontinued LLVM Phabricator instance.

[LCG] Build an edge abstraction for the LazyCallGraph and use it to differentiate between indirect references to functions an direct calls.
ClosedPublic

Authored by chandlerc on Jan 9 2016, 4:36 PM.

Details

Summary

This doesn't do a whole lot yet other than change the print out produced
by the analysis, but it lays the groundwork for a very major change I'm
working on next: teaching the call graph to actually be a call graph,
modeling *both* the indirect reference graph and the call graph
simultaneously. More details on that in the next patch though.

Here, the biggest qustion I have for reviewers is whether they like the
core interface used by the edge abstraction. Notably, the Edge::Kind
enums end up used broadly in the API of the entire call graph. Better
names or structure for these abstractions would be very interesting.

The rest of this is essentially a bunch of over-engineering that won't be
interesting until the next patch. But this also isolates essentially all of the
churn necessary to introduce the edge abstraction from the very important
behavior change necessary in order to separately model the two graphs. So it
should make review of the subsequent patch a bit easier at the cost of making
this patch seem poorly motivated. ;]

That said, if folks would rather me merge this into the big patch that
makes having this abstraction necessary, I'm happy to do that.

Diff Detail

Repository
rL LLVM

Event Timeline

chandlerc updated this revision to Diff 44416.Jan 9 2016, 4:36 PM
chandlerc retitled this revision from to [LCG] Build an edge abstraction for the LazyCallGraph and use it to differentiate between indirect references to functions an direct calls..
chandlerc updated this object.
chandlerc added a subscriber: llvm-commits.
chandlerc updated this revision to Diff 44424.Jan 10 2016, 2:41 AM

Finish nuking the 'clear' method that I never ended up using. I nuked the declaration but not the definition.

reames accepted this revision.Jan 27 2016, 4:37 PM
reames edited edge metadata.

LGTM w/minor comments. The added abstraction is entirely reasonable.

include/llvm/Analysis/LazyCallGraph.h
109 ↗(On Diff #44424)

Having a class called edge which doesn't encode the source seems mildly confusing. Possibly OutboundEdge? Decidedly minor and optional.

If you make the change suggested, it might be good to pull enum out as a class enum Edge to keep the use sites descriptive. Edge::Ref is more meaningful that OutgoingEdge::Ref to me. Either way, nit, I'd be fine with either.

A bit more detail about the Function/Node and lazy creation might be useful for context on the accessors below.

115 ↗(On Diff #44424)

Minor: doxygen

137 ↗(On Diff #44424)

built

Also, the last half of the comment doesn't parse when reading from the top of the diff? Is this something which needs more explanation or is it obvious from something else in the code?

156 ↗(On Diff #44424)

I'm going to trust you got the double tagging right here. I'm not bothering to look into the implementation to check.

259 ↗(On Diff #44424)

This iterator code is a bit confusing to read through - probably just because I'm not familiar with the base class.

263 ↗(On Diff #44424)

Could this be separated into a helper "advance_to_next_call" or something? Might make the code more obvious.

Also, this looks like this stops on a null edge? Why?

608 ↗(On Diff #44424)

Consistency: tested vs queried four lines apart.

626 ↗(On Diff #44424)

It looks like this can be:
if (auto *Existing = getNode())

return Existing;

Node &M = ...

lib/Analysis/LazyCallGraph.cpp
26 ↗(On Diff #44424)

Why are we excluding edges to declarations? That seems odd to me. (Not directly related to this review and should not block.)

318 ↗(On Diff #44424)

Hm, time for a getNodeRequired()?

This revision is now accepted and ready to land.Jan 27 2016, 4:37 PM
echristo accepted this revision.Jan 28 2016, 5:13 PM
echristo added a reviewer: echristo.
echristo added a subscriber: echristo.

LGTM as well (other than the things Philip brings up inline and one of my own inline).

Thanks!

-eric

lib/Analysis/LazyCallGraph.cpp
74 ↗(On Diff #44424)

s/constant/"direct call" perhaps?

chandlerc marked 5 inline comments as done.Feb 1 2016, 11:40 AM

Thanks both!

Planning to submit soon, but please keep discussing any of the open issues here and I'll make sure to follow up with patches to correct anything. Also lemme know if my resolution isn't really satisfactory.

include/llvm/Analysis/LazyCallGraph.h
109 ↗(On Diff #44424)

Yea, I hear what you're saying here, but I think I'm going to keep this the shorter "edge" for now.

One reason why is that the way you *get* edges is from the source, and I think that will help keep it from being too confusing.

But the comment about more context is very helpful, I'll beef up the comments, but let me know if I get it detailed enough to help.

137 ↗(On Diff #44424)

Yea, I think your context comment above was spot on. Hopefully addressed.

263 ↗(On Diff #44424)

Meh, sure on the refactoring.

It should *continue* on null edges and non-call edges to find the first valid edge? Added to comment.

608 ↗(On Diff #44424)

Tested -> a bool result
Queried -> a non bool result

Anyways, I don't care deeply, happy to make them all say queried...

626 ↗(On Diff #44424)

I mean, it could, it just didn't seem to simplify anything, especially as I'll still need to query P to get the function out.

lib/Analysis/LazyCallGraph.cpp
26 ↗(On Diff #44424)

It is odd, and something I plan to add after we *actually* start modeling call edges correctly. Currently, this patch has us track which edges are calls but do nothing useful with them. Next step is to build useful graph structures with them. Then I plan to add support for declarations and flags indicating when there is a call to a totally unknown function.

74 ↗(On Diff #44424)

Hmm, no, I really do mean constant here? We *don't* add direct calls to the worklist.

318 ↗(On Diff #44424)

Meh, but then it couldn't include the helpful context?

chandlerc marked 3 inline comments as done.Feb 1 2016, 11:45 AM
chandlerc added inline comments.
include/llvm/Analysis/LazyCallGraph.h
263 ↗(On Diff #44424)

Heh. there was a bug here that I had fixed in my next patch. backported the fix. It should have been (!*I || !I->isCall())

This revision was automatically updated to reflect the committed changes.