[llvm-dev] PartialAlias: different start addresses

[Hal Finkel via llvm-dev]

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