[AliasAnalysis] Fix a bug in alias analysis interaction with CSE w/ memorySSA

[haoranxu510]

Summary

I noticed that clang miscompiled a C code generated from brainfxxk-to-C transpiler
(https://godbolt.org/z/676Grr), under -O1 or higher, a loop is wrongly optimized
into a dead loop.

After investigation, it turned out that the cause of the issue is that CSE w/
memorySSA transformation pass wrongly eliminated a --(*ptr) in the loop using
the result of another --(*ptr) outside the loop, without realizing that *ptr
may have been modified by the loop.

By bisecting the git history, it turned out that the bug was introduced by D59315.
The said diff seems to be a refactoring diff, however, it seems like the author
accidentally removed two lines of logic in refactoring, resulting in the bug.

I added the two lines back. While it solves the correctness issue, I'm not certain
on the performance implications of this change, since by clearing the AAQI after
each alias query, perhaps we would lose most of the gain from batching AA queries.

During the investigation, I also noticed that the author forgot to change a few
places to use his new API, however, I'm not sure if it is a correctness issue
or not.

[lebedev.ri]

Needs a test

[haoranxu510]

In D89991#2349360, @lebedev.ri wrote:

Needs a test

Hi Roman,

Thanks for your comment!
I'm new to LLVM, can you explain what test would be needed? So currently I have the C code snippet that is miscompiled before this diff and works after this diff, however, the snippet is ~100KB. Do you think it is OK to add a test like that?
I don't know the internals of LLVM so I don't know how I can construct a not-end-to-end failing case.

[asbirlea]

I checked in the changes adding AAQI as authored by you.
The change clearing the cache is not right, as discussed on llvm-dev, so I think this patch is not obsolete.

[haoranxu510]

Thanks!

llvm/lib/Analysis/AliasAnalysis.cpp

 //==- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation --==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (onlyAccessesArgPointees(MRB) || onlyAccessesInaccessibleOrArgMem(MRB)) {
     // Logical & between other AA analyses and argument analysis.
     Result = intersectModRef(Result, AllArgsMask);
     // If only MustAlias found above, set Must bit.
     Result = IsMustAlias ? setMust(Result) : clearMust(Result);
   }
 
   // If Loc is a constant memory location, the call definitely could not
   // modify the memory location.
-  if (isModSet(Result) && pointsToConstantMemory(Loc, /*OrLocal*/ false))
+  if (isModSet(Result) && pointsToConstantMemory(Loc, AAQI, /*OrLocal*/ false))
     Result = clearMod(Result);
 
   return Result;
 }
 
 ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
                                     const CallBase *Call2) {
   AAQueryInfo AAQIP;
for (auto I = Call2->arg_begin(), E = Call2->arg_end(); I != E; ++I) {
       ModRefInfo ArgMask = ModRefInfo::NoModRef;
       if (isModSet(ArgModRefC2))
         ArgMask = ModRefInfo::ModRef;
       else if (isRefSet(ArgModRefC2))
         ArgMask = ModRefInfo::Mod;
 
       // ModRefC1 indicates what Call1 might do to Call2ArgLoc, and we use
       // above ArgMask to update dependence info.
-      ModRefInfo ModRefC1 = getModRefInfo(Call1, Call2ArgLoc);
+      ModRefInfo ModRefC1 = getModRefInfo(Call1, Call2ArgLoc, AAQI);
       ArgMask = intersectModRef(ArgMask, ModRefC1);
 
       // Conservatively clear IsMustAlias unless only MustAlias is found.
       IsMustAlias &= isMustSet(ModRefC1);
 
       R = intersectModRef(unionModRef(R, ArgMask), Result);
       if (R == Result) {
         // On early exit, not all args were checked, cannot set Must.
for (auto I = Call1->arg_begin(), E = Call1->arg_end(); I != E; ++I) {
       unsigned Call1ArgIdx = std::distance(Call1->arg_begin(), I);
       auto Call1ArgLoc =
           MemoryLocation::getForArgument(Call1, Call1ArgIdx, TLI);
 
       // ArgModRefC1 indicates what Call1 might do to Call1ArgLoc; if Call1
       // might Mod Call1ArgLoc, then we care about either a Mod or a Ref by
       // Call2. If Call1 might Ref, then we care only about a Mod by Call2.
       ModRefInfo ArgModRefC1 = getArgModRefInfo(Call1, Call1ArgIdx);
-      ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc);
+      ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc, AAQI);
       if ((isModSet(ArgModRefC1) && isModOrRefSet(ModRefC2)) ||
           (isRefSet(ArgModRefC1) && isModSet(ModRefC2)))
         R = intersectModRef(unionModRef(R, ArgModRefC1), Result);
 
       // Conservatively clear IsMustAlias unless only MustAlias is found.
       IsMustAlias &= isMustSet(ModRefC2);
 
       if (R == Result) {

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 //===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
 
   CacheIt = AAQI.AliasCache.find(AAQueryInfo::LocPair(LocB, LocA));
   if (CacheIt != AAQI.AliasCache.end())
     return CacheIt->second;
 
   AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
                                  LocB.Size, LocB.AATags, AAQI);
 
+  AAQI.AliasCache.shrink_and_clear();
+  AAQI.IsCapturedCache.shrink_and_clear();
   VisitedPhiBBs.clear();
   return Alias;
 }
 
 /// Checks to see if the specified callsite can clobber the specified memory
 /// object.
 ///
 /// Since we only look at local properties of this function, we really can't