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>
Hal Finkel via llvm-dev
2017-Jul-16 20:35 UTC
[llvm-dev] PartialAlias: different start addresses
On 07/16/2017 03:27 PM, Daniel Berlin wrote:> > > On Sun, Jul 16, 2017, 12:45 PM Nuno Lopes <nunoplopes at sapo.pt > <mailto: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)We should continue to do so. Thanks again, Hal> > 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 >-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170716/327c74be/attachment.html>
Daniel Berlin via llvm-dev
2017-Jul-16 21:13 UTC
[llvm-dev] PartialAlias: different start addresses
Meant to send this to the list: Agreed, but we are getting it wrong somewhere, I just tried to bootstrap with an assert that this happened, and enabling a bunch of aa's, and it asserts. I'll debug. On Sun, Jul 16, 2017, 1:35 PM Hal Finkel <hfinkel at anl.gov> wrote:> > On 07/16/2017 03:27 PM, Daniel Berlin wrote: > > > > 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) > > > We should continue to do so. > > Thanks again, > Hal > > > > 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 >> >> > -- > Hal Finkel > Lead, Compiler Technology and Programming Languages > Leadership Computing Facility > Argonne National Laboratory > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170716/ec69f837/attachment.html>
Nuno Lopes via llvm-dev
2017-Jul-16 21:34 UTC
[llvm-dev] PartialAlias: different start addresses
>> On Sun, Jul 16, 2017, 12:45 PM Nuno Lopes 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)Wait, but the size check is done in the clients, not in AA. AA only does (according to my understanding): If start (a) == start (b) Return mustalias Return may or partial Nuno
Daniel Berlin via llvm-dev
2017-Jul-16 21:58 UTC
[llvm-dev] PartialAlias: different start addresses
On Sun, Jul 16, 2017 at 2:34 PM, Nuno Lopes <nunoplopes at sapo.pt> wrote:> On Sun, Jul 16, 2017, 12:45 PM Nuno Lopes 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) >> > > Wait, but the size check is done in the clients, not in AA. > AA only does (according to my understanding): > > If start (a) == start (b) > Return mustalias > Return may or partial > >That seems ... wrong to me, but i haven't thought very hard about it. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170716/b74c5bb8/attachment.html>