This is an archive of the discontinued LLVM Phabricator instance.

[CFLAA] Simplify CFLGraphBuilder by removing InstantiatedRelations and InstantiatedAttrs
ClosedPublic

Authored by grievejia on Jul 6 2016, 6:57 PM.

Details

Summary

This is a code cleanup patch. No functionality change is introduced. It concludes the efforts of moving all information from the auxiliary data structures in CFLGraphBuilder into the constructed CFLGraph.

To achieve the aforementioned goal, I changed the node type of CFLGraph from Value* to (Value*, DerefLevel) pair. With the change of node type, CFLGraph is now able to represent concepts like "derference value x 3 times", therefore it doesn't need InstantiatedRelations and InstantiatedAttrs any more to hold the information we get from interprocedural analysis.

Another change I made to the CFLGraph is that I tried to group together all nodes that share the same Value*. Also, there's no need to explicit store Reference/Dereference edges because we know that it is always going to be the case that there exists a reference edge from (X, I) to (X, I-1) and a dereference edge form (X, I) to (X, I+1). For the purpose of consistency we disallow any other forms of reference/dereference edges. As a result, walking through a dereference chain becomes a fairly easy job (which is useful for implementing CFLAnders). I'm not satisfied with the API to perform the walkthrough, but I can't come up with a better alternative without making things less efficient.

The patch deprecates our previous hacks on StratifiedSets: noteAttributeBelow() and addBelowWith() is no longer needed, as we can take care of it at CFLGraph level. It also reveals another problem hidden in StratifiedSets::mergeDirect(): when it tries to merge two sets and neither set has anything up/below it, the attributes of those two sets won't get merged. Not sure if this is intentional or not. I added a line there to make sure the attribute merge is guaranteed.

Diff Detail

Event Timeline

grievejia updated this revision to Diff 63010.Jul 6 2016, 6:57 PM
grievejia retitled this revision from to [CFLAA] Simplify CFLGraphBuilder by removing InstantiatedRelations and InstantiatedAttrs.
grievejia updated this object.
grievejia updated this object.
grievejia updated this object.
grievejia added a subscriber: llvm-commits.
grievejia updated this object.Jul 6 2016, 6:59 PM
grievejia updated this revision to Diff 63076.Jul 7 2016, 8:18 AM

Changed the offset type from Optional<int> to int

grievejia updated this revision to Diff 63253.Jul 8 2016, 10:24 AM

Changed CFLGraph from bidirectional to unidirectional since the former doesn't seem to buy us that much.

As always, thanks for the patch!

lib/Analysis/CFLGraph.h
42

Can you talk about the purpose of Offset, please? It looks like it's unused, and only ever has a value of 0. Will this change in the future, or am I missing something?

54

Redundant private

62

Can this just be Levels.resize(Level+1)?

89

Please merge this with the condition above

97

This, too

164

Is there a reason we have separate sets for globals vs constants?

192

Why can't we just say if (!Graph.addNode({Val, 0}) return; (here and for the CExpr case)?

194

It looks like addNode(Foo) + addAttr(Foo, A) is a common pattern. Maybe we could either add a WithAttrs param (or whatever) to addNode, or make an addNodeWithAttrs method, so we don't need to do redundant lookups?

209

If Val turns out to be a global or constant expression, it seems mildly redundant to add it (or see that we've already added it) in checkGlobalOrCExpr, then try to re-add it below.

Also, given its uses, I think addGlobalOrCExpr may be a better name. :)

218

And here

221

And here

392

Is there a case where we add non-pointer types to the graph? If not, can we either add assert(isPointerTy) to addNode, or add this logic into addNode?

It looks like it's really easy to miss a type check at the moment. :/

lib/Analysis/CFLSteensAliasAnalysis.cpp
203

s/mapping/Mapping

grievejia marked 13 inline comments as done.Jul 11 2016, 2:52 PM
grievejia added inline comments.
lib/Analysis/CFLGraph.h
42

It is intended for future usage.

But I think you had a point that it's confusing to put an unused field here. Let me remove it for now and add it back in a separate patch.

grievejia updated this revision to Diff 63587.Jul 11 2016, 2:56 PM
grievejia edited edge metadata.
grievejia marked an inline comment as done.

Style fixes.

george.burgess.iv edited edge metadata.

LGTM after a few more nits. Thanks again!

lib/Analysis/CFLGraph.h
111

s/changed/Changed/ (aren't naming conventions fun?)

203–205

Please remove this function

513

Please swap this to addNode(value, attr)

517

This, too

This revision is now accepted and ready to land.Jul 11 2016, 3:21 PM
grievejia updated this revision to Diff 63602.Jul 11 2016, 3:44 PM
grievejia edited edge metadata.
grievejia marked 4 inline comments as done.

More style fixes

As always, thanks for the comments!

This revision was automatically updated to reflect the committed changes.