Page MenuHomePhabricator

[LCG] Update and expand comments to properly document the design motivation, tradeoffs, and constraints.
Needs ReviewPublic

Authored by chandlerc on Jul 13 2016, 1:52 AM.

Details

Summary

This is essentially attempting to embed the living document parts of
a design document into the doxygen comments for the analysis. I can
separate these docs into a restructured text file, but personally
I prefer keeping it as close to the code as possible.

The first section here outlines the high-level motivation, constraints,
and resulting tradeoffs of the design. These are expressed in the
file-level comment as they don't *directly* pertain to the API itself.

The second section is the class comment that tries to give a more
comprehensive but still high-level description of the implementation
strategy for the design.

This doesn't (yet) update the mutation API comments. I'd like to do that
too, but I think its a bit lower priority and I want to try to draw some
ASCII-art diagrams to go with it which will take a while. I didn't want
the higher level stuff to wait on that.

The only really big section of a traditional design document that isn't
really covered here are detailed discussions of the alternatives
considered. I'm open to suggestions about whether that's really useful,
and where within this it would be useful. My personal inclination is to
discuss status, process, and alternatives in commit logs rather than
code, but I'm happy to talk about other places where such discussion can
live.

Also, thanks to Daniel Jasper who provided a ton of informal review for
me as someone who had no idea what any of this did to make sure I wasn't
assuming too much.

Diff Detail

Event Timeline

chandlerc updated this revision to Diff 63783.Jul 13 2016, 1:52 AM
chandlerc retitled this revision from to [LCG] Update and expand comments to properly document the design motivation, tradeoffs, and constraints..
chandlerc updated this object.
chandlerc added a subscriber: llvm-commits.
silvas edited edge metadata.Jul 13 2016, 2:41 AM

Some initial comments.

include/llvm/Analysis/LazyCallGraph.h
35

Something like outlining will also add new nodes. You may want to mention that somewhere.

117

You may want to clarify the exact sense in which "potential" is meant here. The types of edges in a traditional call graph could also be considered as "potential".

Maybe one wording could be "current direct calls" and "references to other functions that might be turned into 'current direct calls' during static optimization"

138–146

You may want to spell out what you mean by "pruned" here (or is this common terminology I'm unaware of?). Since you define the exact circumstances in which an edge exists, I'm not sure that there's much benefit to saying "pruned" here though.

140

Is the "call" graph not a subgraph of the "reference" graph? If it isn't, you probably want to show a concrete example of a situation where it isn't.

148–149

small nit: this should probably be "escaped into external global variables"

153

Does this sentence mean it uses two implementations? That it uses one which is both straight-forward and lazy? I don't see what "straight-forward" adds to this sentence nor how an implementation of Tarjan's algorithm that is lazy can be considered "straight-forward". Is there a specific thing you're trying to communicate?

172

Tarjan's algorithm per se doesn't deal with updates and so saying that the updates are handled with"using straightforward versions of Tarjan's SCC finding algorithm" doesn't provide much information. Could you maybe give a concrete explanation? E.g. that you perform a DFS from ... reusing the LowLink's that have already been computed in such and such a way. Then you can draw parallels to Tarjan's algorithm.

174

Could you elaborate here about what "impacted" / "potentially impacted" means for the various kinds of updates?

chandlerc updated this revision to Diff 64097.Jul 15 2016, 12:13 AM
chandlerc marked 2 inline comments as done.
chandlerc edited edge metadata.

Update with various improvements including based on code review.

chandlerc updated this revision to Diff 64098.Jul 15 2016, 12:21 AM

Fix another typo.

davidxl added inline comments.Jul 15 2016, 10:31 AM
include/llvm/Analysis/LazyCallGraph.h
49

Perhaps describing how this is handled (with an example?)

60

Perhaps add an example here to show 'this is accomplished by ..'

72

This depends how secondary order constraints are formed (i.e., reference edges to potential targets are originated from callers of indirect calls or from constructor methods that reference vtables etc). Perhaps an example to demonstrate this?

136

This does not seem precise. The SCC nodes in RefGraph does not necessarily form a DAG (only RefSCCs), there can be cycles.

142

Is Laziness essential to the algorithm? If not, we don't need to emphasize it here -- just a footnote at the end should be enough.

150

Perhaps just define 'roots' as those callgraph nodes that can potentially called by external functions without body of IR that are available to the compilation.

167

Probably needs more description of updates : various scenarios (small example) and description on how each scenario is handled.

sanjoy resigned from this revision.Jun 24 2017, 12:41 PM

Inactive, as far as I can tell.

silvas resigned from this revision.Mar 25 2020, 6:27 PM