This is an archive of the discontinued LLVM Phabricator instance.

[CFLAA] Summarize interprocedural aliasing information instead of recomputing it at callsite
ClosedPublic

Authored by grievejia on Jun 17 2016, 10:02 AM.

Details

Summary

The primary goal of this patch is to put parameters/return value aliasing info of each function to its summary. Those info used to get computed at each callsite where the function gets invoked. If the said function gets invoked many times, we may end up with lots of redundant computations.

This patch is almost functionality-preserving, except that I've changed the criteria of marking a function f external from "f->hasLocalLinkage()" to "f->isInterposable()". I think the former is overly conservative since it only handles functions with internal or private linkage type, yet all we want for non-external functions is that they can't be overwritten while linking. If my thought turns out to be wrong, I'm happy to switch it back.

I've also made struct type CFLAAResult::FunctionInfo public. The reason is that I want a static free-function buildFunctionInfo() as well as GetEdgeVisitor::tryInterproceduralAnalysis() to access the FunctionInfo struct. I acknowledge that this is not neat, and I'm happy to be told a cleaner solution.

Finally, various test cases on interprocedural analysis were added. Unfortunately, some of them showed that our current handling of function calls/returns is very buggy. For now I've marked those tests as XFAIL, and subsequent patches will primarily focus on removing the XFAILs gradually.

Diff Detail

Event Timeline

grievejia updated this revision to Diff 61106.Jun 17 2016, 10:02 AM
grievejia retitled this revision from to [CFLAA] Summarize interprocedural aliasing information instead of recomputing it at callsite.
grievejia updated this object.
grievejia added a subscriber: llvm-commits.
mgrang added a subscriber: mgrang.Jun 17 2016, 11:51 AM
mgrang added inline comments.
lib/Analysis/CFLAliasAnalysis.cpp
71

Period needed at end of comment.

80–90

Period needed at end of comment.

120

Period needed at end of comment.

grievejia updated this revision to Diff 61139.Jun 17 2016, 3:10 PM
grievejia marked 3 inline comments as done.

Comment style fixes.

Also, the "f->isInterposable()" change was reverted. It will be put into a separate patch

grievejia updated this revision to Diff 61260.Jun 20 2016, 9:36 AM

Make FunctionInfo private to CFLAAResult again by putting all the work that buildFunctionInfo() does into the constructor of FunctionInfo().

Also, I just found out that I need to xfail another test case due to the restrictiveness of hasLocalLinkage().

Thanks for the patch, and for adding all of the tests! :)

Looks good with a handful of nits.

lib/Analysis/CFLAliasAnalysis.cpp
394

Please add a comment explaining why this check exists.

430

Please add a comment to the effect of "FromVal and ToVal should already exist in the graph, so we can add this edge directly"

748

Nit: Remove these braces, please.

(Braces on the loop are fine IMO)

754

Nit: Reserve RetVals.size() elements ahead of time, please

766

Nit: /// -> //

778

If you want to simplify things a bit, Optional<T> has an implicit conversion to bool, so you can do if (getIndexRelation(...)) RetParamRelations.push_back(...);.

Entirely up to you, though.

test/Analysis/CFLAliasAnalysis/basic-interproc.ll
1–2

Nit: Please wrap comments at 80 chars, here and elsewhere.

(It's fine to leave the run lines at > 80 chars if you'd like)

grievejia added inline comments.Jun 20 2016, 1:24 PM
lib/Analysis/CFLAliasAnalysis.cpp
394

It used to be "if (Fn->arg_size() == CS.arg_size()) return false", and I thought I asked you for justifications some time ago... I just kept what was there and relaxed it a little bit.

778

Thanks for the note.

I am aware of that. The reason I invoked hasValue() is consistency: I saw "XXX.hasValue()" at several other places in the same file.

test/Analysis/CFLAliasAnalysis/basic-interproc.ll
1–2

Oops sorry about that. My editor auto-wrap long comments for C++ source files (thanks to clang-format), but I forgot it didn't do the same thing for .ll files :(

grievejia updated this revision to Diff 61298.Jun 20 2016, 1:35 PM
grievejia edited edge metadata.
grievejia marked 6 inline comments as done.

Style fixes.

lib/Analysis/CFLAliasAnalysis.cpp
394

I thought I asked you for justifications some time ago

You did :)

IIRC, the best I could offer you was "we somehow devirtualized the function pointer to N different functions, and their arities didn't match up." Given that that's the best explanation we have (and if we ever do anything fancy with indirect calls, it's probably going to be the resolver's job to ensure that the potential callee makes sense to call), I'm tempted to turn this into an assert, rather than guarding against this case without knowing why. You can blame me if it ends up breaking anything. :)

It also looks like this change would also make us do interprocedural analysis on variadic functions -- I think that should be fine, but can we have a test for that, please? If it helps, here's a link to vararg stuff: http://llvm.org/docs/LangRef.html#variable-argument-handling-intrinsics

434

Please add a period at the end of the comment.

778

WFM

test/Analysis/CFLAliasAnalysis/interproc-ret-arg.ll
8

80 chars, please

grievejia added inline comments.Jun 20 2016, 3:34 PM
lib/Analysis/CFLAliasAnalysis.cpp
394

Regarding variadic functions:

AFAIK, the LLVM va_arg instruction is mostly dead, at least on platforms I commonly use. The docs are outdated w.r.t. this issue. Clang handles C/C++ variadic functions in a highly platform-dependent manner, and it generally try to avoid emitting any va_arg instructions (you can verify this on your machine).

My point is that variadic function is a complex thing to support and I'm not sure this simple change will buy us that much.

grievejia updated this revision to Diff 61314.Jun 20 2016, 3:39 PM
grievejia marked 2 inline comments as done.

More style fixes

lib/Analysis/CFLAliasAnalysis.cpp
394

My point is that variadic function is a complex thing to support and I'm not sure this simple change will buy us that much

If we don't want to support interprocedural analysis on varargs functions, that's perfectly fine with me. My point is that relaxing this check to if (param_size() > arg_size()) return false; allows variadic functions (that were given more than zero args in their arg pack) to be analyzed interprocedurally. If we don't want to support that, we should either explicitly ask the callee if it takes an arg pack (and fail if it does), or we should un-loosen this check. :)

grievejia added inline comments.Jun 20 2016, 3:51 PM
lib/Analysis/CFLAliasAnalysis.cpp
394

My point is that relaxing this check to if (param_size() > arg_size()) return false; allows variadic functions (that were given more than zero args in their arg pack) to be analyzed interprocedurally.

It won't. See line 392 :)

george.burgess.iv edited edge metadata.

LGTM -- will commit. Thanks again.

lib/Analysis/CFLAliasAnalysis.cpp
394

...Right. I'm dumb. Sorry about that. :)

This revision is now accepted and ready to land.Jun 20 2016, 3:55 PM
This revision was automatically updated to reflect the committed changes.
lib/Analysis/CFLAliasAnalysis.cpp