Nuno Lopes via llvm-dev
2017-Jul-14 21:37 UTC
[llvm-dev] PartialAlias: different start addresses
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. Thanks, Nuno -----Original Message----- From: Daniel Berlin Sent: Friday, July 14, 2017 9:25 PM To: Hal Finkel Cc: Davide Italiano ; Nuno Lopes ; LLVMdev Subject: Re: [llvm-dev] PartialAlias: different start addresses Yeah, we definitely don't implement this, and i'm not sure why we would. The best guess i can come up with is that it's really attempting to say something like 1 = *A+4 (size 4) 2 = *A (size 8) load from 2 PartialAlias 1 (not MustAlias) Which is conservative but correct, and meant to ensure alias(1, 2) == alias(2, 1) That would match with our definition of MustAlias, which would not allow 2 MustAlias 1 either. There isn't really a good set of consistent answers between most compilers when the sizes are different but memory addresses overlap. IE it seems reasonable to say that a load of 2 MustAlias 1 but a load of 1 PartialAlias 2. It also seems reasonable to declare these both PartialAlias. In any case, our current implementation, from what i remember (i didn't trace *every* path), says: if MemoryLocations are same size: may if no idea must if the same partial if we can prove overlap If MemoryLocations are different sizes: may if no idea partial if overlap never must On Fri, Jul 14, 2017 at 1:06 PM, Hal Finkel via llvm-dev <llvm-dev at lists.llvm.org> wrote: On 07/14/2017 03:00 PM, Davide Italiano via llvm-dev wrote: On Fri, Jul 14, 2017 at 12:50 PM, Nuno Lopes via llvm-dev <llvm-dev at lists.llvm.org> wrote: Hi, I going through the alias analysis documentation (http://llvm.org/docs/AliasAnalysis.html) and noticed the following in the definition of PartialAlias: " The PartialAlias response is used when the two memory objects are known to be overlapping in some way, but *do not start at the same address*. " Is it really required that the objects do no start at the same address? if that's the case the AA algorithm would need to prove that. I'm asking this because: 1) This condition seems very strict and I don't think it's met in a few places I found by manual inspection If I read the definition correctly, at least our Andersens' AA implementation violates it. see: AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { if (LocA.Ptr == LocB.Ptr) return LocA.Size == LocB.Size ? MustAlias : PartialAlias; (i.e. the two objects are overlapping here *and* start at the same address). I've never noticed that part of the definition myself. I'm fairly certain that's not what we actually implement. -Hal
Hal Finkel via llvm-dev
2017-Jul-14 21:47 UTC
[llvm-dev] 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 ;) -Hal> > Thanks, > Nuno > > > -----Original Message----- From: Daniel Berlin > Sent: Friday, July 14, 2017 9:25 PM > To: Hal Finkel > Cc: Davide Italiano ; Nuno Lopes ; LLVMdev > Subject: Re: [llvm-dev] PartialAlias: different start addresses > > > Yeah, we definitely don't implement this, and i'm not sure why we would. > The best guess i can come up with is that it's really attempting to > say something like > > 1 = *A+4 (size 4) > 2 = *A (size 8) > > load from 2 PartialAlias 1 (not MustAlias) > > Which is conservative but correct, and meant to ensure alias(1, 2) == > alias(2, 1) > > That would match with our definition of MustAlias, which would not > allow 2 MustAlias 1 either. > > There isn't really a good set of consistent answers between most > compilers when the sizes are different but memory addresses overlap. > > IE it seems reasonable to say that a load of 2 MustAlias 1 but a load > of 1 PartialAlias 2. It also seems reasonable to declare these both > PartialAlias. > > In any case, our current implementation, from what i remember (i > didn't trace *every* path), says: > > if MemoryLocations are same size: > may if no idea > must if the same > partial if we can prove overlap > > If MemoryLocations are different sizes: > may if no idea > partial if overlap > never must > > > > > On Fri, Jul 14, 2017 at 1:06 PM, Hal Finkel via llvm-dev > <llvm-dev at lists.llvm.org> wrote: > > > On 07/14/2017 03:00 PM, Davide Italiano via llvm-dev wrote: > On Fri, Jul 14, 2017 at 12:50 PM, Nuno Lopes via llvm-dev > <llvm-dev at lists.llvm.org> wrote: > Hi, > > I going through the alias analysis documentation > (http://llvm.org/docs/AliasAnalysis.html) and noticed the following in > the > definition of PartialAlias: > " > The PartialAlias response is used when the two memory objects are > known to > be overlapping in some way, but *do not start at the same address*. > " > > Is it really required that the objects do no start at the same > address? if > that's the case the AA algorithm would need to prove that. > I'm asking this because: > 1) This condition seems very strict and I don't think it's met in a few > places I found by manual inspection > If I read the definition correctly, at least our Andersens' AA > implementation violates it. > see: > > AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA, > const MemoryLocation &LocB) { > if (LocA.Ptr == LocB.Ptr) > return LocA.Size == LocB.Size ? MustAlias : PartialAlias; > > > (i.e. the two objects are overlapping here *and* start at the same > address). > > I've never noticed that part of the definition myself. I'm fairly > certain that's not what we actually implement. > > -Hal-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory
Nuno Lopes via llvm-dev
2017-Jul-15 09:51 UTC
[llvm-dev] 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.