[llvm-dev] PartialAlias: different start addresses

[Nuno Lopes via llvm-dev]

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.

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