This is an archive of the discontinued LLVM Phabricator instance.

[CFLAA] Add support for field offset in CFLAnders::FunctionInfo
ClosedPublic

Authored by grievejia on Jul 21 2016, 10:45 AM.

Details

Summary

CFLAnders::FunctionInfo used to record, for each value X, what other values Y may-alias it. Such an approach is inadequate if we were to move to a field-sensitive analysis. This patch changes the map type from Value->[Value] to Value->[(Value, Offset)]. In other words, instead of keeping track of "X alias Y", FunctionInfo now understands a more general alias pattern "X alias (Y + FieldOffset)". The strategy of alias query handling gets adjusted accordingly to cope with this change: now CFLAnders can potentially answer "PartialAlias" for certain queries.

Note that only the interfaces of FunctionInfo gets changed in this patch. The analysis body is still oblivious about field offset, therefore no functional change was introduced.

More patches on field-sensitivity will come in the near future.

Diff Detail

Event Timeline

grievejia updated this revision to Diff 64922.Jul 21 2016, 10:45 AM
grievejia retitled this revision from to [CFLAA] Add support for field offset in CFLAnders::FunctionInfo.
grievejia updated this object.
grievejia updated this object.
grievejia added a subscriber: llvm-commits.
grievejia updated this revision to Diff 64923.Jul 21 2016, 10:49 AM

Slight precision improvement.

Thanks for the patch!

lib/Analysis/AliasAnalysisSummary.h
140

Please rebase; it looks like my intuition on your prior patch was only half-correct. ;)

We apparently have a bot that uses clang on Windows, with earlier versions of MS's stdlib. So, LLVM_CONSTEXPR becomes constexpr, and max() still isn't constexpr on that particular bot. My bad.

lib/Analysis/CFLAndersAliasAnalysis.cpp
512

Given that we're using a different comparator than the one we sorted with here, can we add the following above this line, please?

#ifdef EXPENSIVE_CHECKS
assert(std::is_sorted(Itr->second.begin(), Itr->second.end(), /* your comparator here */));
#endif
534

Pick your favorite:

assert(LHSSize <= INT64_MAX)

or

if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX)) return MayAlias;

:)

536

If we care about potential overflow, this may be a good place to put a FIXME, as well.

540

PartialAlias doesn't seem quite right here. PartialAlias is essentially MustAlias (at some offset, as you've noted), and, unless I'm missing something obvious, I think we'd need to do many more checks to prove MustAlias.

(If I *am* wrong, s/MayAlias/MustAlias/, please)

553–554

Given that these checks are relatively cheap, can we put them before our AliasMap checks (which seem potentially more expensive)?

grievejia updated this revision to Diff 65090.Jul 22 2016, 9:25 AM
grievejia edited edge metadata.
grievejia marked 5 inline comments as done.

Rebase and style improvement

lib/Analysis/CFLAndersAliasAnalysis.cpp
540

My original thought was that PartialAlias = MayAlias at nonzero offset.

If PartialAlias = MustAlias at nonzero offset, then we probably don't have anything smarter than MayAlias, since the analysis only handles may info.

george.burgess.iv edited edge metadata.

LGTM -- thanks for the patch!

lib/Analysis/CFLAndersAliasAnalysis.cpp
540

If PartialAlias = MustAlias at nonzero offset, then we probably don't have anything smarter than MayAlias, since the analysis only handles may info

Agreed :)

This revision is now accepted and ready to land.Jul 22 2016, 11:26 AM
This revision was automatically updated to reflect the committed changes.