search for: mustalia

...m a bit confused about some of the corner cases. Suppose we had something like this std::vector<int> A(100); > int* x,y; > x=&A[0]; > for(int i=0; i<100; i++) { > y=&A[i]; > *y=*x; > x=&A[i+1]; > } > Would the load and store instructions be MustAlias? I think what it boils down to is the distinction between static instructions and dynamic instructions and how they are handled by alias analysis. I originally interpreted MustAlias as saying /all/ dynamic instructions A must alias with /all/ dynamic instructions B. However, you're saying t...

...vm.org/docs/AliasAnalysis.html>, The MayAlias response is used whenever the two pointers might refer to the > same object. > > 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. > > The MustAlias response may only be returned if the two memory objects are > guaranteed to always start at exactly the same location. A MustAlias > response implies that the pointers compare equal. > Reading this, it seems the "MustAlias" result is exceptionally strong. Consider this loop st...

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

...;>>>>>> 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*" >>&g...

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

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

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

...; > #include <cstdlib> > int main(int c, char** argv) { > int* A=(int*)malloc(100*sizeof(int)); > > if(c>1) { > for(int i=0; i<5; i++) { > A[i]=5; > } > } else { > A[1]=5; > } > printf("%d\n",A[4]); > free(A); > } > MustAlias? Because whenever they are executed, they do alias. Or MayAlias? Jeremy On Wed, Aug 13, 2014 at 7:31 PM, Daniel Berlin <dberlin at dberlin.org> wrote: > On Wed, Aug 13, 2014 at 2:52 PM, Jeremy Salwen <jeremysalwen at gmail.com> > wrote: > > Thanks Daniel! > > &g...

...st 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 > _______________________________________________ &...

...ifically, what do we expect "must alias" to mean in practice? Consider a simple example: load i64, i64* %p %p.i32 = bitcast i64* %p to i32* load i32, i32* %p.i32 Given two memory locations which describe the two memory accesses of these loads, do we expect that alias analysis returns MustAlias?  That is, when we have two accesses to the same pointer, but *different* sizes, does that result in MustAlias? (Just to be clear, MayAlias is clearly a valid answer.  I'm really asking if we can legally return MustAlias for these.) I would have said up until recently, that the correct re...

...Value* point to the same DSNode, they 'may-alias'. If two Value* point to different DSNode, they 'not-alias'. However, is it possible to know whether two Value* 'must-alias'? I checked the AliasAnalysis interface before it was removed from DSA, the interface never returns MustAlias results. I guess it may not be possible to get 'MustAlias' results from DSA. Will it be possible to modify the DSA code so that every heap DSNode tracks all possible malloc() calls it comes from? Thanks for your help. Best regards, Zhixuan Yang -------------- next part -------------- A...

...int to different DSNode, they > 'not-alias'. However, is it possible to know whether two Value* > 'must-alias'? No. DSA does not track must-alias information. > > I checked the AliasAnalysis interface before it was removed from DSA, > the interface never returns MustAlias results. I guess it may not be > possible to get 'MustAlias' results from DSA. Will it be possible to > modify the DSA code so that every heap DSNode tracks all possible > malloc() calls it comes from? Interesting question. You could add a "Must-Alias" flag that is...

...39;t a pointer. So the interpretation of "A" having only one outbound edge (to "B") is a little ambiguous. It means "'A' definitely points to 'B', or 'A' doesn't hold a valid pointer." This makes it hard for the algorithm to ever return a MustAlias result. If the graph has just two edges, "A-->C" and "B-->C", then the most precise answer it could give for "alias(A,B)" would be "MustAlias or NoAlias, I'm not sure which". AFAIK, with the current interface I'd have to return "MayAlia...

...as sets with anything (we happen to assign the int _value_ we obtain from pointer `x` by dereferencing it `*x`, but that bears no relevance to aliasing here). Perhaps this can help illustrate the scenario (assuming the URL doesn't get mangled): http://www.pythontutor.com/cpp.html#code=void%20MUSTALIAS%28void%20*p,%20void%20*q%29%20%7B%7D%0A%0Aint%20main%28%29%7B%0A%0A%20%20int%20**a,%20*b,%20*x%20,c%3B%0A%20%20c%20%3D%2010%3B%0A%20%20a%20%3D%20%26b%3B%0A%20%20b%20%3D%20%26c%3B%0A%20%20x%20%3D%20*a%3B%0A%20%20int%20y%20%3D%20*x%3B%0A%20%20MUSTALIAS%28x,%26c%29%3B%0A%20%20MUSTALIAS%28x,b%29%3B%0A...

...ction calls. > And how to interpret that we have "2 must alias responses"? Where > does it come from? And why do we have "0 may alias response"? I > would expect to have at least "4 may alias responses" as well? No, "MayAlias" and "MustAlias" are distinct elements in the lattice, cf. https://llvm.org/docs/AliasAnalysis.html#must-may-or-no There's a good explanation of the alias analysis queries and responses in the following talk (particularly the part starting with "AA Query" around the 22 min. mark): “Pointers,...

...t;>> >>> if(c>1) { >>> for(int i=0; i<5; i++) { >>> A[i]=5; >>> } >>> } else { >>> A[1]=5; >>> } >>> printf("%d\n",A[4]); >>> free(A); >>> } >> >> > >> MustAlias? Because whenever they are executed, they do alias. Or MayAlias? > Since you seem to be having trouble going all the way down the rabbit > hole here, let me take a different approach. > > In this example, A[i] is not an LLVM location or value *. > You will never see A[i] in the LL...

...the result type of various AA, including TBAA. I would expect that the result of the complete alias analysis includes both the information on whether given accesses alias and, as a separate element, whether they are allowed to alias by the rules of the language. Then we may have combinations like (MustAlias, AllowedAlias) that seem to be the common case and combinations like (MustAlias, NotAllowedAlias) that I would expect to a) generate the breaks-alias-rules kind of warnings and b) proceed further as any other MustAlias case. The latter combination is what I would expect for illegal type puns, for...

...rocedural analysis (the local analysi>s will be the most precise but will have many Incomplete DSNodes; the Bottom-Up and Top-Down propagate information up and down the call graph but will cause further DSNode merging). Thanks for your clarification. I agree with you. Even if we implemented a MustAlias interface in DSA, it will be too weak. >It may be that you will need a more accurate points-to analysis algorithm for your work. In fact, my task can be solved in a simpler (while less elegant) way. If I want to find pointers must-alias with a malloc() call, I can create a new variable sto...

...move calls, so we'd never really care about > must-alias for promotion". I was just pointing out other things move calls > any may want to know. > > If you want an example where the must-alias part would matter: > > *a = something > foo(a) > b = *a > > If foo mustalias a (and only a) not only can you move foo with a, you can > actually clone foo here, change it to be pass-by-value, and promote the > argument inside of it (if you wanted to). > > So you can use this info to, for example, do interprocedural promotion. > > >> Are we instead l...

Dear John, > When you say "must be allocated," you mean it must have been allocated via a call to a heap allocator (e.g., malloc(), calloc(), etc), correct? Yes, I mean heap allocators. In fact, I'm implementing the idea of the ICSE 2015 paper Safe Memory-Leak Fixing for C Programs. > Also, are you performing intra-procedural or inter-procedural data-flow analysis?