This is an archive of the discontinued LLVM Phabricator instance.

[CFLAA] Include externally-visible memory aliasing information in function summaries
ClosedPublic

Authored by grievejia on Jun 20 2016, 3:14 PM.

Details

Summary

CFLAA's support for interprocedural analysis was rather limited. For each function argument/return value, it only records whether if the given value is somehow related (i.e. can be obtained through assignments/reference/derefence) to other argument/return values. If the relation is found, an assignment edge is added (i.e. merge the two values into the same StratifiedSet). For example, if it sees a call instruction like this:

call void @f(i32** %x, i32* %y)

and if function @f is defined like this:

define void @f(%i32** %a, i32* %b) {
  store i32* %b, i32** %a
  ret void
}

Then the analysis will try to say, at the callsite, that %x and %y are aliases. However, doing interprocedural analysis in this way is neither sound nor precise. It is imprecise because it is obvious that callee @f does not do anything to make its arguments alias each other, yet the analysis conclude that they may. It is unsound because if we add another instruction after the callsite:

%z = load i32*, i32** %x

, the analysis will not be able to detect %z and %y may-alias each other.

It seems to me that the core issue here is that our function summaries are not detailed enough to provide adequate information to the caller. Given a function @f, we can't just say "the first argument is somehow related to the second argument, but yeah we don't know exactly what the relationship is". What we really want instead is something more concrete, such as "the first argument is related to the second argument, and here's the relationship: the dereference of the first argument may-alias with the second argument". Summaries in the latter form give precise instructions on how to deal with actual arguments/actual return value at the callsite where the summary is instantiated.

This patch implements the idea illustrated in the last paragraph. Previously, the "RetParamRelation" struct inside FunctionInfo only includes related-pairs of parameters/return values. Now we refine the pairs by extending each parameters/return values with an additional DerefLevel N, which allows us to represent things like "derefrence the first argument N times". For instance, for the function @f mentioned before we will put [(param0, DerefLevel = 1), (param1, DerefLevel=0)] into the summary. At callsite where this summary is instantiated, we will create a new StratifiedSet below the set of %x, and merge it with the StratifiedSet of %y. To support this kind of operation where the DerefLevels of both elements of the pair are non-zero, a new interface to StratifiedSetBuilder needs to be added.

I've also changed the algorithm we used to generate function summaries. Here is how we checked whether two parameters %a and %b are related in the past:

  • Find the StratifiedSet that %a belongs to
  • Find all StratifiedSets that come above %a, and see if %b is in there
  • Find all StratifiedSets that come below %a, and see if %b is in there

The algorithm is correct but if we were to do this for all pairs of parameters, it becomes O(n^2). Here is the approach I used in this patch:

  • Declare a hashmap that maps from StratifiedSets to lists of parameters
  • Scan the parameter list. For each parameter p, get the corresponding StratifiedSets s, and add (s->p) to the hashmap
  • Scan the hashmap. For each StratifiedSet, if the mapped list has more than one element, then we know that every parameters in the list alias every other one

I think my approach should do less work and has a linear complexity (I could be wrong about this, though). One drawback of this approach (or at least in the way I'm doing it) is that we may end up with redundant items in the summary. Take @f as an example again: the summary not only contains the aforementioned entry [(param0, DerefLevel = 1), (param1, DerefLevel=0)] , we may end up with another entry [(param0, DerefLevel = 2), (param1, DerefLevel=1)] as well. The second entry is redundant here because it can be implied from the first entry. That being said, the issue does not affect soundness, and it may be fixable, so I am not very concerned about it.

With this patch ready, I am finally able to remove some xfailed test cases I introduced in an earlier patch. There are still two xfailed left untouched, since fixing them requires me putting even more information (e.g. which InterfaceValue(s) may be tagged with AttrUnknown) into the summary. They will be handled by subsequent patches.

Diff Detail

Repository
rL LLVM

Event Timeline

grievejia updated this revision to Diff 61307.Jun 20 2016, 3:14 PM
grievejia retitled this revision from to [CFLAA] Include externally-visible memory aliasing information in function summaries.
grievejia updated this object.
grievejia added a subscriber: llvm-commits.

Woohoo bugfixes! Thanks for the patch.

lib/Analysis/CFLAliasAnalysis.cpp
747 ↗(On Diff #61307)

FWIW, MSVC2013 didn't like templating on a local (yes, even though said local was const. I can't wait until we bump passed 2013), so I had to change this code a bit. Please rebase. :)

755 ↗(On Diff #61307)

This still seems n^2-ish in some cases, which I believe ultimately makes this algorithm n^3 time, and n^2 storage. Imagine we have:

void foo(int **a, int ***b, int ****c) {
  *c = b;
  *b = a;
  int *d = *a;
}

That would give us one "chain" of

a
^
b
^
c
^
d

When scanning these, it looks like we'll add 4 entries for a, 3 entries for b, and 2 for c. It also looks like we may end up with 6 entries in cases like:

void foo(int ***a, int ***b) {
  int **ad = *a;
  int *add = *ad;
  int **bd = *b;
  int *bdd = *bd;
}

When I think we shouldn't have more than 2 (or 4, depending on how we want to handle attributes).

Assuming I'm not missing something, I think we can improve on this. AIUI, given two stratifiedset chains:

a
^
b  e
^  ^
c  f
^  ^
d  g
   ^
   h

Adding an assignment edge between b and e (or c and f, or d and g) produces the same result as adding assignment edges between all of the aforementioned pairs.

If this is correct, we can knock down the time+space complexity a bit, I think. The rough idea I have for how to do this is:

  • Build a map, M, of StratifiedIndex -> vector<Value *>, where each vector is the list of Args/Return values that are in that StratifiedSet
  • For each element, E, in the above map:
    • Add entries to RetParamRelations that represent assignment between E.second[0] and E.second[1..E.second.size()] (**)
    • For each set index S below E.first:
      • If we don't find a mapping in M for S, try the next lower set.
      • Otherwise, given said mapping, M', for a set N levels below E, add an entry that represents N levels of dereference between E.second[0] and M'.second[0] in RetParamRelations.

(** If you want, you can probably do this when building the map, and just make the map a StratifiedIndex -> Value* map. I realized this after writing the above, and am lazy :) )

With this, it looks like we'll end up with a linear number of entries (worst-case; best case, we'll have 0), and we'll end up walking N*M StratifiedSets total (N = number of args/returns, M = max(chain length))

758 ↗(On Diff #61307)

I don't care either way, but if you want to just use [&] for captures in the future, you're welcome to. :)

764 ↗(On Diff #61307)

Nit: if (!Link.hasBelow()) break; seems cleaner to me

784 ↗(On Diff #61307)

for (auto *V : RetVals)?

785 ↗(On Diff #61307)

Can we assert that RetVals[I] is a pointer here? I realize that it's only meant to hold values of pointer type, but that isn't exactly locally obvious IMO. :)

792 ↗(On Diff #61307)

Nit: Mapping

792 ↗(On Diff #61307)

It looks like there are cases where this won't add the correct StratifiedAttrs to sets. Consider:

int **g;
void foo(int **a) {
  *a = *g;
}

void bar() {
  int *p, *p2;
  *g = p2;

  int **a = &p;
  foo(a);
  // p and p2 now alias
}

Because there's only arg and no return values when analyzing foo, Interfaces.size() will never be > 1, so we'll end up with no RetParamRelations. We need to somehow apply the attributes from the set containing a in foo to the set containing a in bar, though.

799 ↗(On Diff #61307)

Looks like RetParamRelations will hold n^2 elements, because InterfaceMap holds n^2 elements.

863 ↗(On Diff #61307)

Looks like we do a linear walk of StratifiedSet chains for every iteration of this loop, so this might be n^3ish overall, assuming RetParamRelations contains n^2 elements?

grievejia added inline comments.Jun 21 2016, 4:04 PM
lib/Analysis/CFLAliasAnalysis.cpp
755 ↗(On Diff #61307)

Well, I'm not convinced that the current algorithm has an n^2 complexity. I think the complexity should be O(m*n), where m is the max chain length, even without your enhancement. You are right that m can sometimes be greater or equal to n, which essentially makes it O(n^2). However, normally I wouldn't expect m to be greater than 3 in most cases (at least I myself rarely write functions that handle pointers of >3 depth). So I would say m can almost be treated as a constant term.

I do agree that the algorithm can be improved in the way you described. If I understand correctly, you are suggesting that the InterfaceMap population algorithm should be executed in a "breadth-first" manner rather than a "depth-first" manner, since the former allows us to detect redundant entries earlier hence we can just shortcut exit if redundancies were found.

I'll try to change the codes as you suggested. Thanks for the comment!

758 ↗(On Diff #61307)

Won't [&] unnecessarily capture things we don't need in the closure?

792 ↗(On Diff #61307)

That's the reason why there are still two xfail test cases, and that's the reason why I mentioned in the description section that more work need to be done here :)

I think almost all StratifiedAttr in the callee's graph is useless to the caller, except for AttrUnknown. The summary should also include a list of InterfaceValues that must be tagged with AttrUnknown. However, we currently tag all nodes below formal parameters "AttrUnknown", so doing what I suggested before would unnecessarily tag too many "AttrUnknown"s in the caller. I think we may need to introduce another StratifiedAttr here just to distinguish between "things below parameters, which are known by the caller" and "things that are truly unknown, such as globals or inttoptr".

Anyway, whatever we do, that's going to be the story for the next patch :)

grievejia added inline comments.Jun 21 2016, 4:09 PM
lib/Analysis/CFLAliasAnalysis.cpp
792 ↗(On Diff #61307)

After a second thought, maybe AttrEscaped is useful to the caller as well...

lib/Analysis/CFLAliasAnalysis.cpp
755 ↗(On Diff #61307)

at least I myself rarely write functions that handle pointers of >3 depth

FWIW, RetVals[I]->getType() goes through 3 levels of indirection, since RetVals is a reference to a vector of pointers. :)

However, normally I wouldn't expect m to be greater than 3 in most cases

I'd buy that both m and n are generally going to stay < 8 for the vast majority of real-world code, yeah.

the InterfaceMap population algorithm should be executed in a "breadth-first" manner rather than a "depth-first"

Sounds correct to me.

758 ↗(On Diff #61307)

I thought that initially, too -- the answer is apparently "nope". Only things that you actually use in the lambda need to be captured; if you like to read standardese, 5.1.2p12 (and bits around there) may be interesting to you.

792 ↗(On Diff #61307)

AttrGlobal would probably be useful, too. As would AttrUnknown under any sets tagged with AttrGlobal. :)

grievejia marked an inline comment as done.Jun 22 2016, 10:27 AM
grievejia added inline comments.
lib/Analysis/CFLAliasAnalysis.cpp
755 ↗(On Diff #61307)

Now that I think about it, I'm not so sure if skipping shortcut exit is a safe option. My concern is a case like this:

a
^
b  < d
^
c

, where two parameters both belongs to set b, yet their dereferences belongs to set c and d, resp. If this is possible (which I assume highly likely since otherwise the analysis becomes indistinguishable from Steensgard), then "A and B aliases implies *A and *B also aliases" is going to be a false statement.

grievejia updated this revision to Diff 61569.Jun 22 2016, 10:28 AM
grievejia edited edge metadata.

Style update

lib/Analysis/CFLAliasAnalysis.cpp
760 ↗(On Diff #61569)

Currently, we unify stratifiedsets both upwards and downwards -- the reason behind this is "that's how I interpreted the paper when I wrote StratifiedSets." :P

If you want to fix that, then feel free. And yeah, if we do change stratifiedsets to that model, then my proposed approach is broken.

grievejia added inline comments.Jun 22 2016, 12:11 PM
lib/Analysis/CFLAliasAnalysis.cpp
760 ↗(On Diff #61569)

I'll probably kick off another discussion on the topic of unifying strategy: its impact on performance can be very, very big...

grievejia updated this revision to Diff 61585.Jun 22 2016, 12:23 PM

Added early exit in summary construction.

grievejia updated this revision to Diff 61626.Jun 22 2016, 4:32 PM

Another minor style update

george.burgess.iv edited edge metadata.

LGTM -- will commit tomorrow.

Thanks for the patch!

This revision is now accepted and ready to land.Jun 22 2016, 9:56 PM
This revision was automatically updated to reflect the committed changes.