Daniel Berlin via llvm-dev
2017-Jul-15 14:01 UTC
[llvm-dev] 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>
Nuno Lopes via llvm-dev
2017-Jul-16 19:45 UTC
[llvm-dev] PartialAlias: different start addresses
>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
Daniel Berlin via llvm-dev
2017-Jul-16 20:27 UTC
[llvm-dev] PartialAlias: different start addresses
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>