Page MenuHomePhabricator

[AA][NFC] Convert AliasResult to class containing offset for PartialAlias case.
ClosedPublic

Authored by dfukalov on Mar 16 2021, 9:13 AM.

Details

Summary

Add an ability to store Offset between partially aliased location. Use this
storage within returned ResultAlias instead of caching it in AAQueryInfo.

Diff Detail

Event Timeline

dfukalov created this revision.Mar 16 2021, 9:13 AM
dfukalov requested review of this revision.Mar 16 2021, 9:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 16 2021, 9:13 AM
dfukalov added inline comments.Mar 16 2021, 9:17 AM
llvm/include/llvm/Analysis/MemorySSA.h
304

Perhaps AliasResult should be replaced with AliasResult::Result here and in similar places in MemorySSA? @nikic, @asbirlea, what do you think?

nikic added inline comments.Mar 16 2021, 9:45 AM
llvm/include/llvm/Analysis/AliasAnalysis.h
111

Why does this ctor only initialize HasOffset?

124

I believe this is isInt<OffsetBits>(NewOffset).

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1094

aliasCheck() performs location swapping as well. I think now you need to adjust it to negate the offset if a swapped location is used.

dfukalov updated this revision to Diff 331255.Mar 17 2021, 6:16 AM

Addressed comments.

dfukalov marked 3 inline comments as done.Mar 17 2021, 6:25 AM

@nikic thanks for review, and what do you think about Optional<AliasResult> - should it be refactored to Optional<AliasResult::Result> in MemorySSA?
Or, possibly, will this module use PartialAlias offsets?

llvm/include/llvm/Analysis/AliasAnalysis.h
111

Yes, it was incorrect, we should no get an uninitialized Alias field.

124

Thanks for hint!

@nikic, could you check this patch through the compiler-tracker, please?

llvm/include/llvm/Analysis/MemorySSA.h
304

Yes. Unless we have a usecase of using the PartialAlias in MemorySSA, I don't think we should have the overhead of creating new class instances for all aliasing result kept in optimized memory accesses.

dfukalov marked 2 inline comments as done.Mar 17 2021, 4:36 PM
dfukalov added inline comments.
llvm/include/llvm/Analysis/MemorySSA.h
304

Actually I thought about pretty ugly compositions like AliasResult(AliasResult::MayAlias). They are caused by Optional<AliasResult>. And speaking of running compiler on x86, IMHO AliasResult class overhead is not significant, at least if it is stored in Optional<>.

dfukalov added inline comments.Mar 18 2021, 2:37 AM
llvm/include/llvm/Analysis/MemorySSA.h
304


I've attached diff with a substitution with using AliasRes = AliasResult::Result. If this option is ok, I'll update the review' patch.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1549

Doesn't this swap the cached result? I think the intention here was to only return a swapped result, no?

1573

I think we shouldn't be swapping here, as we computed the result already in swapped order.

dfukalov updated this revision to Diff 331668.Mar 18 2021, 1:07 PM
dfukalov marked an inline comment as done.
  • Fixed swapping already cached result.
  • Result bit field size set to 8 bits, Offset field initialized with zero.

I see there you experimented with 8 bits for Result and zero init for Offset field - I agree it's a good ideas.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1549

Yes, you're right, I didn't notice it modifies cache. Thanks!

1573

Result we've just put into cache is computed by aliasCheckRecursive(V1, ..., V2) with original order, but Entry was found as AAQI.AliasCache.find(Locs) for sorted pair. So here we should save the Swapped result into cache.

I ran additional tests: perf impact of the patch and perf impact of the reverting it. Here is the "cumulative" (commit patch and revert it back) difference.

Some of tests didn't get back to original values and generated noise comparable with shown average perf drop of the patch. E.g. CMakeFiles/lencod.dir/image.c.o compilation slowed down by 1.79%, but after reverting it got back by 1.28% only. CMakeFiles/lencod.dir/nalucommon.c.o slowed by 0.20% and after reverting it slowed down again by enormous 1.29%...

Then I ran image.c.o compilation locally under perf and valgrind. Perf said new compiler slowed down, but valgrind reported tiny speedup.
Btw, both of them reported second topmost self-consuming function
DenseMapBase::LookupBucketFor() mostly called from DenseMapBase::try_emplace(std::pair<> const&, AAQueryInfo::CacheEntry&&) and BasicAAResult::aliasCheck().
But again, valgrind said it became faster, perf - slower...

IMHO all of these results say that the reported impact is not significant.
What do you think?

@nikic, @asbirlea would you please review the patch?
It blocks GVN related D95543.

I'm running some additional tests for this patch.
Could you rebase the GVN dependent patch so I get some testing done in parallel?

I was not sure this patch will be landed so left GVN patch based on previous already landed (cached) offset storage.

Could you rebase the GVN dependent patch so I get some testing done in parallel?

Yes, sure, do you need rebase it on this change or even on updated main branch + this change?

asbirlea accepted this revision.Apr 8 2021, 10:33 PM

This is good to go from my side.

This revision is now accepted and ready to land.Apr 8 2021, 10:33 PM
nikic added a comment.Apr 9 2021, 12:34 AM

Possibly MergeAliasResults should preserve the offset when merging two PartialAlias with the same offset?

llvm/include/llvm/Analysis/AliasAnalysis.h
93

I'd rename this to something like Type or Kind.

140

I think the AliasResult printing code should be adjusted to also print the PartialAlias offset. This will allow us to test this functionality using normal -aa-eval tests, instead of unit tests. That should be a great deal simpler when testing more complex cases.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1114

Now that the offset is part of the result, I *think* the VisitedPhiBBs check is not needed anymore, but I'm not entirely sure.

This revision was landed with ongoing or failed builds.Apr 9 2021, 3:26 AM
This revision was automatically updated to reflect the committed changes.

@nikic, I didn't notice your comments before push, will address your comments in different patch.

dfukalov added inline comments.Apr 13 2021, 9:59 AM
llvm/include/llvm/Analysis/AliasAnalysis.h
140

There is an issue with printing offset in -aa-eval: it prints two (aliased) values sorted lexicographically.
So the printed offset may have wrong sign regarding printed pair of values. I'm not sure how it should be printed to avoid confusion in tests... Do you have any ideas?

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1114

Actually I added this check because of comment you asked about in D95543.

nikic added inline comments.Apr 13 2021, 10:25 AM
llvm/include/llvm/Analysis/AliasAnalysis.h
140

Would just calling swap() on the AliasResult if the values are swapped not work?

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1114

I think these are different issues. The comment refers to phi translation performed by MDA and GVN. BasicAA itself does not perform phi translation.

Here, VisitedPhiBBs should already implicit take effect, in that returning PartialAlias here requires that the GEP base pointers are MustAlias. They will only be MustAlias if they pass the phi cycle reachability check. So the VisitedPhiBBs are important for the recursive check on the base pointers, but there shouldn't be a need to check it here.