[llvm-dev] PartialAlias: different start addresses

[Hal Finkel via llvm-dev]

On 07/14/2017 04:37 PM, Nuno Lopes wrote:
> Thank you all for your replies.
> So here seems to be an agreement that the documentation for 
> PartialAlias is incorrect.
>
> Daniel: now you got me wondering about MustAlias. This is what the 
> docs say:
> "The MustAlias response may only be returned if the two memory objects 
> are *guaranteed to always start at exactly the same location*"
>
> This statement is regardless of the access sizes.  For example, in 
> SCEV AA:
> // If they evaluate to the same expression, it's a MustAlias.
> if (AS == BS)
>  return MustAlias;
>
> AS/BS are scev expressions for the pointers. So no check for the 
> access size.
>
> So, does must needs to check for access sizes?  If so, SCEV AA is 
> buggy and the documentation needs tweaking.

I'm under the impression that there is code that depends on the size 
check, but I don't trust my recollection in this regard. SCEV AA is 
known to cause miscompiles, IIRC, maybe you just found out why ;)

  -Hal

>
> Thanks,
> Nuno
>
>
> -----Original Message----- From: Daniel Berlin
> Sent: Friday, July 14, 2017 9:25 PM
> To: Hal Finkel
> Cc: Davide Italiano ; Nuno Lopes ; LLVMdev
> Subject: Re: [llvm-dev] PartialAlias: different start addresses
>
>
> Yeah, we definitely don't implement this, and i'm not sure why we would.
> The best guess i can come up with is that it's really attempting to 
> say something like
>
> 1 = *A+4 (size 4)
> 2 = *A (size 8)
>
> load from 2 PartialAlias 1 (not MustAlias)
>
> Which is conservative but correct, and meant to ensure alias(1, 2) == 
> alias(2, 1)
>
> That would match with our definition of MustAlias, which would not 
> allow 2 MustAlias 1 either.
>
> There isn't really a good set of consistent answers between most 
> compilers when the sizes are different but memory addresses overlap.
>
> IE it seems reasonable to say that a load of 2 MustAlias 1 but a load 
> of 1 PartialAlias 2. It also seems reasonable to declare these both 
> PartialAlias.
>
> In any case, our current implementation, from what i remember (i 
> didn't trace *every* path), says:
>
> if MemoryLocations are same size:
> may if no idea
> must if the same
> partial if we can prove overlap
>
> If MemoryLocations are different sizes:
> may if no idea
> partial if overlap
> never must
>
>
>
>
> On Fri, Jul 14, 2017 at 1:06 PM, Hal Finkel via llvm-dev 
> <llvm-dev at lists.llvm.org> wrote:
>
>
> On 07/14/2017 03:00 PM, Davide Italiano via llvm-dev wrote:
> On Fri, Jul 14, 2017 at 12:50 PM, Nuno Lopes via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> Hi,
>
> I going through the alias analysis documentation
> (http://llvm.org/docs/AliasAnalysis.html) and noticed the following in 
> the
> definition of PartialAlias:
> "
> The PartialAlias response is used when the two memory objects are 
> known to
> be overlapping in some way, but *do not start at the same address*.
> "
>
> Is it really required that the objects do no start at the same 
> address?  if
> that's the case the AA algorithm would need to prove that.
> I'm asking this because:
> 1) This condition seems very strict and I don't think it's met in a few
> places I found by manual inspection
> If I read the definition correctly, at least our Andersens' AA
> implementation violates it.
> see:
>
> AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
>                                      const MemoryLocation &LocB) {
>   if (LocA.Ptr == LocB.Ptr)
>     return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
>
>
> (i.e. the two objects are overlapping here *and* start at the same 
> address).
>
> I've never noticed that part of the definition myself. I'm fairly 
> certain that's not what we actually implement.
>
> -Hal

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory