llvm dev - Jul 2017 - PartialAlias: different start addresses

On Sat, Jul 15, 2017 at 5:35 AM, Hal Finkel <hfinkel at anl.gov> wrote:
>
> On 07/15/2017 04:51 AM, Nuno Lopes wrote:
>
>> 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 ;)
>>>
>>
>> It's true that the CFL AAs have this code:
>> if (LocA.Ptr == LocB.Ptr)
>>  return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
>>
>>
>> I grepped for clients of MustAlias:
>> ~/llvm/lib/Transforms $ grep -Rl MustAlias .
>> ./ObjCARC/ObjCARCOpts.cpp
>> ./ObjCARC/ProvenanceAnalysis.cpp
>> ./Scalar/DeadStoreElimination.cpp
>> ./Scalar/GVN.cpp
>> ./Scalar/LICM.cpp
>> ./Scalar/LoopVersioningLICM.cpp
>> ./Scalar/MemCpyOptimizer.cpp
>> ./Scalar/MergedLoadStoreMotion.cpp
>> ./Scalar/NewGVN.cpp
>> ./Utils/VNCoercion.cpp
>>
>> I glanced over all the uses in these files and I couldn't find any
usage
>> that requires sizes to match.  Actually most clients check access sizes
>> themselves. Most don't need equal sizes, just need one to be
smaller than
>> the other.
>>
>
Does aliasing actually check both ways?
Otherwise, alias (A, B) will give different results than alias (B, A).
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170715/0511141d/attachment.html>

>On 07/15/2017 04:51 AM, Nuno Lopes wrote:
>>> 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 ;)
>>
>> It's true that the CFL AAs have this code:
>> if (LocA.Ptr == LocB.Ptr)
>>  return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
>>
>>
>> I grepped for clients of MustAlias:
>> ~/llvm/lib/Transforms $ grep -Rl MustAlias .
>> ./ObjCARC/ObjCARCOpts.cpp
>> ./ObjCARC/ProvenanceAnalysis.cpp
>> ./Scalar/DeadStoreElimination.cpp
>> ./Scalar/GVN.cpp
>> ./Scalar/LICM.cpp
>> ./Scalar/LoopVersioningLICM.cpp
>> ./Scalar/MemCpyOptimizer.cpp
>> ./Scalar/MergedLoadStoreMotion.cpp
>> ./Scalar/NewGVN.cpp
>> ./Utils/VNCoercion.cpp
>>
>> I glanced over all the uses in these files and I couldn't find any
>> usage that requires sizes to match.  Actually most clients check
>> access sizes themselves. Most don't need equal sizes, just need one
to
>> be smaller than the other.
>
> Does aliasing actually check both ways?
> Otherwise, alias (A, B) will give different results than alias (B, A).
Sorry for the delay.
I'm not sure I understood what you wrote, sorry.  What you wrote is true in 
general, but I don't see how MustAlias in particular is worse than the other
AA results.  And how not enforcing that access sizes are equal changes 
things with respect to commutativity either.  Maybe I completely missed your 
point..

Nuno

On Sun, Jul 16, 2017, 12:45 PM Nuno Lopes <nunoplopes at sapo.pt> wrote:
> >On 07/15/2017 04:51 AM, Nuno Lopes wrote:
> >>> 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
;)
> >>
> >> It's true that the CFL AAs have this code:
> >> if (LocA.Ptr == LocB.Ptr)
> >>  return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
> >>
> >>
> >> I grepped for clients of MustAlias:
> >> ~/llvm/lib/Transforms $ grep -Rl MustAlias .
> >> ./ObjCARC/ObjCARCOpts.cpp
> >> ./ObjCARC/ProvenanceAnalysis.cpp
> >> ./Scalar/DeadStoreElimination.cpp
> >> ./Scalar/GVN.cpp
> >> ./Scalar/LICM.cpp
> >> ./Scalar/LoopVersioningLICM.cpp
> >> ./Scalar/MemCpyOptimizer.cpp
> >> ./Scalar/MergedLoadStoreMotion.cpp
> >> ./Scalar/NewGVN.cpp
> >> ./Utils/VNCoercion.cpp
> >>
> >> I glanced over all the uses in these files and I couldn't find
any
> >> usage that requires sizes to match.  Actually most clients check
> >> access sizes themselves. Most don't need equal sizes, just
need one to
> >> be smaller than the other.
> >
> > Does aliasing actually check both ways?
> > Otherwise, alias (A, B) will give different results than alias (B, A).
>
> Sorry for the delay.
> I'm not sure I understood what you wrote, sorry.  What you wrote is
true in
> general, but I don't see how MustAlias in particular is worse than the
> other
> AA results.

Historically, in llvm, we have guaranteed that alias(a, b) ==alias(b, a)

If it does:

If start (a) == start (b)
  If size(b) < size(a)
      Return mustalias
  Return may or partial

It will give different answers for alias(a, b) and alias (b, a)

Hence my question about whether it checked whether *either* was smaller, or
just in one direction.

  And how not enforcing that access sizes are equal
changes
> things with respect to commutativity either.  Maybe I completely missed
> your
> point..
>
> Nuno
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170716/4a3f9770/attachment.html>