llvm dev - May 2015 - [LLVMdev] MemoryDependenceAnalysis reports dependencies between NoAlias pointers

Thanks Daniel,

I'll do a debug build of LLVM (I guess that'll teach me) and step
through it as soon as I'll find a power outlet.

I'm calling getDependency on the load instruction, and it returns the store
instruction. Suspiciously enough, calling invalidateCachedPointerInfo on
load->getPointerOperand() does not cause my AA pass to be called again when I
use getDependency (or is that not what I needed to do?).

I joined the .ll that shows the relevant function as it gets to my pass (memdep
is a function pass, right?). Ultimately, my goal is to find out when loads from
address space 0 depend on calls. Given my usage pattern, I can overlook
non-local dependencies.

Félix

-------------- next part --------------
A non-text attachment was scrubbed...
Name: memdepprob.ll
Type: application/octet-stream
Size: 3627 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150521/31abf2d3/attachment.obj>
-------------- next part --------------

> Le 2015-05-21 à 14:53:44, Daniel Berlin <dberlin at dberlin.org> a
écrit :
> 
> On Thu, May 21, 2015 at 11:37 AM, Félix Cloutier <felixcca at
yahoo.ca> wrote:
>> Hi all,
>> 
>> I have a custom alias analysis pass that enforces that pointers from
different address spaces do not alias, and I'm using
MemoryDependenceAnalysis to, well, figure out dependence analysis.
>> 
>> The AA pass is extremely simple, it only checks the address space of
pointers, returns NoAlias if they're different, and delegates otherwise. It
is the last alias analysis pass added to my PassManager (basically, after
BasicAA only). As far as I can check with breakpoints and logging, it appears to
work as intended. MemoryDependenceAnalysis often appears in the call stack when
my alias method is called, and it does return NoAlias appropriately.
>> 
>> However, in another custom module pass that I have, I'm observing
that MemDep reports dependences between loads and stores of pointers to
different address spaces, despite my AA pass. For instance, an AA request
against these parameters returns NoAlias:
>> 
>>  %7 = inttoptr i64 %4 to i64 addrspace(1)*
>>  %9 = getelementptr inbounds %struct.mystruct, %struct.mystruct* %0,
i64 0, i32 7, i32 0
>> 
>> But then, memdep suggests that there is a clobber dependency between
these two instructions:
>> 
>>  %10 = load i64, i64* %9, align 8
>>  store i64 %6, i64 addrspace(1)* %7, align 8
>> 
> 
> 
>> I would expect that since the locations cannot alias, the load cannot
depend on the store. When used from my module pass, >MemoryDependenceAnalysis
never ends up calling my AA pass, but I would imagine that this is because GVN
or some other pass already did all the >queries that I do and that they are
cached.
> 
> First, you should step through memdep and see exactly what is going on.
> You can invalidate the memdep cache if you need to for these pointers,
> which should cause your AA to be called.
> 
> Second, a bit more info is needed.
> 
> On which of these pointers and what memdep functions are you calling?
> 
> (and can you attach the full .ll file?)
> 
> 
> Note that memorydependence's main client is GVN, and they have a
> pretty incestuous relationship.
> 
> So the API may not give you what you really want in some cases.
> For example, iit will return load-load clobbers in noalias cases
> sometimes so that gvn can use them for load widening, etc.
> 
> But it's not at all clear that you are hitting one of these cases.

On Thu, May 21, 2015 at 1:31 PM, Félix Cloutier <felixcca at yahoo.ca>
wrote:
> Thanks Daniel,
>
> I'll do a debug build of LLVM (I guess that'll teach me) and step
through it as soon as I'll find a power outlet.
>
> I'm calling getDependency on the load instruction, and it returns the
store instruction. Suspiciously enough, calling invalidateCachedPointerInfo on
load->getPointerOperand() does not cause my AA pass to be called again when I
use getDependency (or is that not what I needed to do?).
No, that should do it.
I would step through and see what is happening.
>
> I joined the .ll that shows the relevant function as it gets to my pass
(memdep is a function pass, right?). Ultimately, my goal is to find out when
loads from address space 0 depend on calls.
> Given my usage pattern, I can overlook non-local dependencies.
Interesting. FWIW, memory ssa will make this easier (and i'm just
getting back to adding a ton of tests for it after having my time
eaten for a while. It should go in in a few weeks).
http://reviews.llvm.org/D7864

You would just look at loads, and the immediate definition of the
MemoryUse on the load will tell you whether it is dependent on a call
or not
if it's a call, it's dependent on that call. If it's something else,
A. It is not dependent on any  calls in between that thing and your load
B. It's killed by that something else, regardless of whether any call
before it would also kill it :)

> Félix
>
>
>
>
>> Le 2015-05-21 à 14:53:44, Daniel Berlin <dberlin at dberlin.org>
a écrit :
>>
>> On Thu, May 21, 2015 at 11:37 AM, Félix Cloutier <felixcca at
yahoo.ca> wrote:
>>> Hi all,
>>>
>>> I have a custom alias analysis pass that enforces that pointers
from different address spaces do not alias, and I'm using
MemoryDependenceAnalysis to, well, figure out dependence analysis.
>>>
>>> The AA pass is extremely simple, it only checks the address space
of pointers, returns NoAlias if they're different, and delegates otherwise.
It is the last alias analysis pass added to my PassManager (basically, after
BasicAA only). As far as I can check with breakpoints and logging, it appears to
work as intended. MemoryDependenceAnalysis often appears in the call stack when
my alias method is called, and it does return NoAlias appropriately.
>>>
>>> However, in another custom module pass that I have, I'm
observing that MemDep reports dependences between loads and stores of pointers
to different address spaces, despite my AA pass. For instance, an AA request
against these parameters returns NoAlias:
>>>
>>>  %7 = inttoptr i64 %4 to i64 addrspace(1)*
>>>  %9 = getelementptr inbounds %struct.mystruct, %struct.mystruct*
%0, i64 0, i32 7, i32 0
>>>
>>> But then, memdep suggests that there is a clobber dependency
between these two instructions:
>>>
>>>  %10 = load i64, i64* %9, align 8
>>>  store i64 %6, i64 addrspace(1)* %7, align 8
>>>
>>
>>
>>> I would expect that since the locations cannot alias, the load
cannot depend on the store. When used from my module pass,
>MemoryDependenceAnalysis never ends up calling my AA pass, but I would
imagine that this is because GVN or some other pass already did all the
>queries that I do and that they are cached.
>>
>> First, you should step through memdep and see exactly what is going on.
>> You can invalidate the memdep cache if you need to for these pointers,
>> which should cause your AA to be called.
>>
>> Second, a bit more info is needed.
>>
>> On which of these pointers and what memdep functions are you calling?
>>
>> (and can you attach the full .ll file?)
>>
>>
>> Note that memorydependence's main client is GVN, and they have a
>> pretty incestuous relationship.
>>
>> So the API may not give you what you really want in some cases.
>> For example, iit will return load-load clobbers in noalias cases
>> sometimes so that gvn can use them for load widening, etc.
>>
>> But it's not at all clear that you are hitting one of these cases.
>
>

> Le 2015-05-21 à 17:19:25, Daniel Berlin <dberlin at dberlin.org> a
écrit :
> 
> Interesting. FWIW, memory ssa will make this easier (and i'm just
> getting back to adding a ton of tests for it after having my time
> eaten for a while. It should go in in a few weeks).
> http://reviews.llvm.org/D7864
> 
> You would just look at loads, and the immediate definition of the
> MemoryUse on the load will tell you whether it is dependent on a call
> or not
> if it's a call, it's dependent on that call. If it's something
else,
> A. It is not dependent on any  calls in between that thing and your load
> B. It's killed by that something else, regardless of whether any call
> before it would also kill it :)
This is extremely relevant to what I'm doing. I was using MemDep because
that's what came closest to memory SSA. I think I'll grab the patch
right away.

I'm still pretty new to LLVM and just starting to figure things out, and
this is just a hobby thing (no corporate resources to back my project), but if
you would like feedback, I can probably give some.

Félix
>>> Le 2015-05-21 à 14:53:44, Daniel Berlin <dberlin at
dberlin.org> a écrit :
>>> 
>>> On Thu, May 21, 2015 at 11:37 AM, Félix Cloutier <felixcca at
yahoo.ca> wrote:
>>>> Hi all,
>>>> 
>>>> I have a custom alias analysis pass that enforces that pointers
from different address spaces do not alias, and I'm using
MemoryDependenceAnalysis to, well, figure out dependence analysis.
>>>> 
>>>> The AA pass is extremely simple, it only checks the address
space of pointers, returns NoAlias if they're different, and delegates
otherwise. It is the last alias analysis pass added to my PassManager
(basically, after BasicAA only). As far as I can check with breakpoints and
logging, it appears to work as intended. MemoryDependenceAnalysis often appears
in the call stack when my alias method is called, and it does return NoAlias
appropriately.
>>>> 
>>>> However, in another custom module pass that I have, I'm
observing that MemDep reports dependences between loads and stores of pointers
to different address spaces, despite my AA pass. For instance, an AA request
against these parameters returns NoAlias:
>>>> 
>>>> %7 = inttoptr i64 %4 to i64 addrspace(1)*
>>>> %9 = getelementptr inbounds %struct.mystruct, %struct.mystruct*
%0, i64 0, i32 7, i32 0
>>>> 
>>>> But then, memdep suggests that there is a clobber dependency
between these two instructions:
>>>> 
>>>> %10 = load i64, i64* %9, align 8
>>>> store i64 %6, i64 addrspace(1)* %7, align 8
>>>> 
>>> 
>>> 
>>>> I would expect that since the locations cannot alias, the load
cannot depend on the store. When used from my module pass,
>MemoryDependenceAnalysis never ends up calling my AA pass, but I would
imagine that this is because GVN or some other pass already did all the
>queries that I do and that they are cached.
>>> 
>>> First, you should step through memdep and see exactly what is going
on.
>>> You can invalidate the memdep cache if you need to for these
pointers,
>>> which should cause your AA to be called.
>>> 
>>> Second, a bit more info is needed.
>>> 
>>> On which of these pointers and what memdep functions are you
calling?
>>> 
>>> (and can you attach the full .ll file?)
>>> 
>>> 
>>> Note that memorydependence's main client is GVN, and they have
a
>>> pretty incestuous relationship.
>>> 
>>> So the API may not give you what you really want in some cases.
>>> For example, iit will return load-load clobbers in noalias cases
>>> sometimes so that gvn can use them for load widening, etc.
>>> 
>>> But it's not at all clear that you are hitting one of these
cases.
>> 
>>