[llvm-dev] valid BasicAA behavior?

[Chawla, Pankaj via llvm-dev]

Hi Michael,

>> There seems to be a bug in DI, see Felipe's answer.
Maybe I missed something. There seems to be no resolution to the problem. How can DA fix this without help from alias analysis?


>> Since aliasPHI looks for any incoming value contradicting the NoAlias assumption, it would be equivalant to always return MayAlias.
I pasted the code snippet below with some extra comments. 
The merge is still happening with NoAlias. Only the cached query is set to MayAlias to detect the cycle during recursion.

     AliasResult Alias = NoAlias;
      AliasResult OrigAliasResult;
      {
        // Limited lifetime iterator invalidated by the aliasCheck call below.
        auto CacheIt = AAQI.AliasCache.find(Locs);
        assert((CacheIt != AAQI.AliasCache.end()) &&
               "There must exist an entry for the phi node");
        OrigAliasResult = CacheIt->second;
        CacheIt->second = NoAlias;                        // modify this to PNSize == MemoryLocation::UnknownSize ? MayAlias : NoAlias
      }

      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
        AliasResult ThisAlias =
            aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo,
                       PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
                       V2Size, V2AAInfo, AAQI);
        Alias = MergeAliasResults(ThisAlias, Alias);         //Merge happens with NoAlias
        if (Alias == MayAlias)
          break;
      }

I accept that this is a workaround but this could help DA for with this problem. A good solution might be to add an explicit interface to alias analysis which is conservatively correct for DA.

-Pankaj

-----Original Message-----
From: Michael Kruse <llvmdev at meinersbur.de> 
Sent: Wednesday, March 18, 2020 9:12 AM
To: Chawla, Pankaj <pankaj.chawla at intel.com>
Cc: Kruse, Michael <michael.kruse at anl.gov>; Finkel, Hal J. <hfinkel at anl.gov>; Hiroshi Yamauchi <yamauchi at google.com>; llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] valid BasicAA behavior?

Am Di., 17. März 2020 um 16:56 Uhr schrieb Chawla, Pankaj via llvm-dev
<llvm-dev at lists.llvm.org>:
> All I am expecting from DA is a direction vector containing (*).

There seems to be a bug in DI, see Felipe's answer.


> I think the main problem is that currently there is no exact way DA can query AliasAnalysis in a ‘conservatively correct’ manner.
>
> Using UnknownSize seems to be an approximate solution (workaround).

Passing an unknown size is conservatively correct. That is, it must be correct for any possible size.

Yes, we could be better if we know all the array elements that are accessed. Unfortunately it is also difficult, e.g. because the access range depends on `n`, ie is non-constant. The AA interface doesn't even allow querying for non-constant sizes.


> How do you guys feel about setting the initial cached result as MayAlias instead of NoAlias if the query is performed for UnknownSize?
>
> If during alias query recursion we hit the same phi query again, we will return a conservative ‘MayAlias’ knowing that we have hit a cycle (loop).

Since aliasPHI looks for any incoming value contradicting the NoAlias assumption, it would be equivalant to always return MayAlias.


Michael