llvm dev - Jul 2017 - PartialAlias: different start addresses

> 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.

BTW, Basic AA doesn't check for size either:
if (isValueEqualInPotentialCycles(V1, V2))
  return MustAlias;

bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
                                                  const Value *V2) {
  if (V != V2)
    return false;

  const Instruction *Inst = dyn_cast<Instruction>(V);
  if (!Inst)
    return true;
(...)
}

So if V1==V2, BasicAA will yield MustAlias.

I couldn't find any evidence that access sizes must be equal for 2 pointers 
to be MustAlias.  Unless someone can prove that statement wrong, we have to 
conclude that CFL* AAs are being too conservative by yielding PartialMatch 
when sizes don't match.

Nuno

P.S.: This is not to say that SCEV AA hasn't bugs: I think I found one by 
inspection; I've asked a colleague to review and will report it soon.  Not 
sure there's an easy fix for it, though.

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.
>
> BTW, Basic AA doesn't check for size either:
> if (isValueEqualInPotentialCycles(V1, V2))
>  return MustAlias;
>
> bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
>                                                  const Value *V2) {
>  if (V != V2)
>    return false;
>
>  const Instruction *Inst = dyn_cast<Instruction>(V);
>  if (!Inst)
>    return true;
> (...)
> }
>
> So if V1==V2, BasicAA will yield MustAlias.
>
> I couldn't find any evidence that access sizes must be equal for 2 
> pointers to be MustAlias.  Unless someone can prove that statement 
> wrong, we have to conclude that CFL* AAs are being too conservative by 
> yielding PartialMatch when sizes don't match.
Thanks for looking at this. In that case, I see no reason for the 
restriction. Please do post patches to clean all of this up.
>
> Nuno
>
> P.S.: This is not to say that SCEV AA hasn't bugs: I think I found one 
> by inspection; I've asked a colleague to review and will report it 
> soon.  Not sure there's an easy fix for it, though.
Good, thanks!

  -Hal

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

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>