[llvm-dev] AliasAnalysis does not look though a memcpy

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

[llvm-dev] AliasAnalysis does not look though a memcpy

Alberto Barbaro via llvm-dev
Hi,

I'm trying to get AA results for two pointers, but it seems that AA
cannot look though a memcpy. For example:

    define dso_local spir_func void @fun() {
    entry:
      ; Store an address of `var'
      %var = alloca i32, align 4
      store i32 42, i32* %var, align 4
      %var.addr = alloca i32*, align 8
      store i32* %var, i32** %var.addr, align 8

      ; Memcpy `var.addr' to `var.addr.tmp'
      %var.addr.tmp = alloca i32*, align 8
      %0 = bitcast i32** %var.addr.tmp to i8*
      %1 = bitcast i32** %var.addr to i8*
      call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %0, i8* align 8 %1, i64 8, i1 false)

      ; Load a copy of `var'
      %var.tmp = load i32*, i32** %var.addr.tmp
      %should.be.42 = load i32, i32* %var.tmp
      ret void
    }

    ; Function Attrs: argmemonly nounwind
    declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1) #1
    attributes #1 = { argmemonly nounwind }

I run it with opt, and get the following:

    $ opt -basicaa -print-alias-sets memcpy.ll -disable-output
    Alias sets for function 'fun':
    Alias Set Tracker: 3 alias sets for 6 pointer values.
      AliasSet[0x5b5df0, 2] may alias, Mod/Ref   Pointers: (i32* %var, LocationSize::precise(4)), (i32* %var.tmp, LocationSize::precise(4))
      AliasSet[0x5b5e90, 2] must alias, Mod/Ref   Pointers: (i32** %var.addr, LocationSize::precise(8)), (i8* %1, LocationSize::precise(8))
      AliasSet[0x5b7390, 2] must alias, Mod/Ref   Pointers: (i8* %0, LocationSize::precise(8)), (i32** %var.addr.tmp, LocationSize::precise(8))

So AA says that %var and %var.tmp "may alias", but I'd expect to get a
"must alias". What can be done to determine that %var and %var.tmp are
actually the same pointer in this case?

--
Andrew

--------------------------------------------------------------------
Joint Stock Company Intel A/O
Registered legal address: Krylatsky Hills Business Park,
17 Krylatskaya Str., Bldg 4, Moscow 121614,
Russian Federation

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] AliasAnalysis does not look though a memcpy

Alberto Barbaro via llvm-dev
> Hi,
>
> I'm trying to get AA results for two pointers, but it seems that AA
> cannot look though a memcpy. For example:
>
>     define dso_local spir_func void @fun() {
>     entry:
>       ; Store an address of `var'
>       %var = alloca i32, align 4
>       store i32 42, i32* %var, align 4
>       %var.addr = alloca i32*, align 8
>       store i32* %var, i32** %var.addr, align 8
>
>       ; Memcpy `var.addr' to `var.addr.tmp'
>       %var.addr.tmp = alloca i32*, align 8
>       %0 = bitcast i32** %var.addr.tmp to i8*
>       %1 = bitcast i32** %var.addr to i8*
>       call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %0, i8* align 8 %1, i64 8, i1 false)
>
>       ; Load a copy of `var'
>       %var.tmp = load i32*, i32** %var.addr.tmp
>       %should.be.42 = load i32, i32* %var.tmp
>       ret void
>     }
>
>     ; Function Attrs: argmemonly nounwind
>     declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1) #1
>     attributes #1 = { argmemonly nounwind }
>
> I run it with opt, and get the following:
>
>     $ opt -basicaa -print-alias-sets memcpy.ll -disable-output
>     Alias sets for function 'fun':
>     Alias Set Tracker: 3 alias sets for 6 pointer values.
>       AliasSet[0x5b5df0, 2] may alias, Mod/Ref   Pointers: (i32* %var, LocationSize::precise(4)), (i32* %var.tmp, LocationSize::precise(4))
>       AliasSet[0x5b5e90, 2] must alias, Mod/Ref   Pointers: (i32** %var.addr, LocationSize::precise(8)), (i8* %1, LocationSize::precise(8))
>       AliasSet[0x5b7390, 2] must alias, Mod/Ref   Pointers: (i8* %0, LocationSize::precise(8)), (i32** %var.addr.tmp, LocationSize::precise(8))
>
> So AA says that %var and %var.tmp "may alias", but I'd expect to get a
> "must alias". What can be done to determine that %var and %var.tmp are
> actually the same pointer in this case?

Can anyone suggest how to get the expected results from AA?

InstCombiner and other LLVM passes can probably remove a memcpy and make
IR a lot easier for AA, but I'd like to get the analysis working for
not-optimized IR as well.

--
Andrew

--------------------------------------------------------------------
Joint Stock Company Intel A/O
Registered legal address: Krylatsky Hills Business Park,
17 Krylatskaya Str., Bldg 4, Moscow 121614,
Russian Federation

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] AliasAnalysis does not look though a memcpy

Alberto Barbaro via llvm-dev
On 12/5/18 9:51 AM, Andrew Savonichev via llvm-dev wrote:

>> Hi,
>>
>> I'm trying to get AA results for two pointers, but it seems that AA
>> cannot look though a memcpy. For example:
>>
>>     define dso_local spir_func void @fun() {
>>     entry:
>>       ; Store an address of `var'
>>       %var = alloca i32, align 4
>>       store i32 42, i32* %var, align 4
>>       %var.addr = alloca i32*, align 8
>>       store i32* %var, i32** %var.addr, align 8
>>
>>       ; Memcpy `var.addr' to `var.addr.tmp'
>>       %var.addr.tmp = alloca i32*, align 8
>>       %0 = bitcast i32** %var.addr.tmp to i8*
>>       %1 = bitcast i32** %var.addr to i8*
>>       call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %0, i8* align 8 %1, i64 8, i1 false)
>>
>>       ; Load a copy of `var'
>>       %var.tmp = load i32*, i32** %var.addr.tmp
>>       %should.be.42 = load i32, i32* %var.tmp
>>       ret void
>>     }
>>
>>     ; Function Attrs: argmemonly nounwind
>>     declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1) #1
>>     attributes #1 = { argmemonly nounwind }
>>
>> I run it with opt, and get the following:
>>
>>     $ opt -basicaa -print-alias-sets memcpy.ll -disable-output
>>     Alias sets for function 'fun':
>>     Alias Set Tracker: 3 alias sets for 6 pointer values.
>>       AliasSet[0x5b5df0, 2] may alias, Mod/Ref   Pointers: (i32* %var, LocationSize::precise(4)), (i32* %var.tmp, LocationSize::precise(4))
>>       AliasSet[0x5b5e90, 2] must alias, Mod/Ref   Pointers: (i32** %var.addr, LocationSize::precise(8)), (i8* %1, LocationSize::precise(8))
>>       AliasSet[0x5b7390, 2] must alias, Mod/Ref   Pointers: (i8* %0, LocationSize::precise(8)), (i32** %var.addr.tmp, LocationSize::precise(8))
>>
>> So AA says that %var and %var.tmp "may alias", but I'd expect to get a
>> "must alias". What can be done to determine that %var and %var.tmp are
>> actually the same pointer in this case?
> Can anyone suggest how to get the expected results from AA?
>
> InstCombiner and other LLVM passes can probably remove a memcpy and make
> IR a lot easier for AA, but I'd like to get the analysis working for
> not-optimized IR as well.

Hi, Andrew,

To be clear, you'd like BasicAA to look back, not just trough the
memcpy, but also through the loads and stores of the addresses? BasicAA
currently doesn't do any of that under the presumption that, once SROA,
InstCombine, etc. do promotion and simplification, AA will be able to
understand the rest. Can you say more about the use case?

Thanks,

Hal

>
--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] AliasAnalysis does not look though a memcpy

Alberto Barbaro via llvm-dev
> On 12/5/18 9:51 AM, Andrew Savonichev via llvm-dev wrote:
>>> Hi,
>>>
>>> I'm trying to get AA results for two pointers, but it seems that AA
>>> cannot look though a memcpy. For example:
>>>
>>>     define dso_local spir_func void @fun() {
>>>     entry:
>>>       ; Store an address of `var'
>>>       %var = alloca i32, align 4
>>>       store i32 42, i32* %var, align 4
>>>       %var.addr = alloca i32*, align 8
>>>       store i32* %var, i32** %var.addr, align 8
>>>
>>>       ; Memcpy `var.addr' to `var.addr.tmp'
>>>       %var.addr.tmp = alloca i32*, align 8
>>>       %0 = bitcast i32** %var.addr.tmp to i8*
>>>       %1 = bitcast i32** %var.addr to i8*
>>>       call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %0, i8* align 8 %1, i64 8, i1 false)
>>>
>>>       ; Load a copy of `var'
>>>       %var.tmp = load i32*, i32** %var.addr.tmp
>>>       %should.be.42 = load i32, i32* %var.tmp
>>>       ret void
>>>     }
>>>
>>>     ; Function Attrs: argmemonly nounwind
>>>     declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1) #1
>>>     attributes #1 = { argmemonly nounwind }
>>>
>>> I run it with opt, and get the following:
>>>
>>>     $ opt -basicaa -print-alias-sets memcpy.ll -disable-output
>>>     Alias sets for function 'fun':
>>>     Alias Set Tracker: 3 alias sets for 6 pointer values.
>>>       AliasSet[0x5b5df0, 2] may alias, Mod/Ref   Pointers: (i32* %var, LocationSize::precise(4)), (i32* %var.tmp, LocationSize::precise(4))
>>>       AliasSet[0x5b5e90, 2] must alias, Mod/Ref   Pointers: (i32** %var.addr, LocationSize::precise(8)), (i8* %1, LocationSize::precise(8))
>>>       AliasSet[0x5b7390, 2] must alias, Mod/Ref   Pointers: (i8* %0, LocationSize::precise(8)), (i32** %var.addr.tmp, LocationSize::precise(8))
>>>
>>> So AA says that %var and %var.tmp "may alias", but I'd expect to get a
>>> "must alias". What can be done to determine that %var and %var.tmp are
>>> actually the same pointer in this case?
>> Can anyone suggest how to get the expected results from AA?
>>
>> InstCombiner and other LLVM passes can probably remove a memcpy and make
>> IR a lot easier for AA, but I'd like to get the analysis working for
>> not-optimized IR as well.
>
> Hi, Andrew,
>
> To be clear, you'd like BasicAA to look back, not just trough the
> memcpy, but also through the loads and stores of the addresses?

Yes, exactly. I was mostly concerned about memcpy, but you're right,
loads/stores of addresses seems to have the same issue.

> BasicAA currently doesn't do any of that under the presumption that,
> once SROA, InstCombine, etc. do promotion and simplification, AA will
> be able to understand the rest.

That is what I thought. Thanks for the confirmation.

> Can you say more about the use case?

OpenCL C has a notion of Generic Address Space (GAS), allowing you to
cast a pointer from any (named) address space to a GAS pointer. Then you
can use this GAS pointer instead of a named AS pointer. Compiler is
responsible to infer the original address space of a GAS pointer when it
is actually used (for load/store), otherwise this is a compilation
error.

So I'm trying to follow a pointer from a point of origin
(i.e. addrspacecast private ptr -> generic ptr) and look through a
sequence of bitcasts, GEPs, function calls and pointer copies through
memory. AliasAnalysis and MemDepAnalysis give me all the required
information to do intraprocedural analysis, except for the memcpy case
that I raised in this thread.

Since a failure to infer an address space means a compilation error, I'm
trying to get this analysis working for debug builds, where we do not
run InstCombine and other aggressive optimizations.

--
Andrew

--------------------------------------------------------------------
Joint Stock Company Intel A/O
Registered legal address: Krylatsky Hills Business Park,
17 Krylatskaya Str., Bldg 4, Moscow 121614,
Russian Federation

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] AliasAnalysis does not look though a memcpy

Alberto Barbaro via llvm-dev
On 12/5/18 2:14 PM, Andrew Savonichev wrote:

>> On 12/5/18 9:51 AM, Andrew Savonichev via llvm-dev wrote:
>>>> Hi,
>>>>
>>>> I'm trying to get AA results for two pointers, but it seems that AA
>>>> cannot look though a memcpy. For example:
>>>>
>>>>     define dso_local spir_func void @fun() {
>>>>     entry:
>>>>       ; Store an address of `var'
>>>>       %var = alloca i32, align 4
>>>>       store i32 42, i32* %var, align 4
>>>>       %var.addr = alloca i32*, align 8
>>>>       store i32* %var, i32** %var.addr, align 8
>>>>
>>>>       ; Memcpy `var.addr' to `var.addr.tmp'
>>>>       %var.addr.tmp = alloca i32*, align 8
>>>>       %0 = bitcast i32** %var.addr.tmp to i8*
>>>>       %1 = bitcast i32** %var.addr to i8*
>>>>       call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %0, i8* align 8 %1, i64 8, i1 false)
>>>>
>>>>       ; Load a copy of `var'
>>>>       %var.tmp = load i32*, i32** %var.addr.tmp
>>>>       %should.be.42 = load i32, i32* %var.tmp
>>>>       ret void
>>>>     }
>>>>
>>>>     ; Function Attrs: argmemonly nounwind
>>>>     declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1) #1
>>>>     attributes #1 = { argmemonly nounwind }
>>>>
>>>> I run it with opt, and get the following:
>>>>
>>>>     $ opt -basicaa -print-alias-sets memcpy.ll -disable-output
>>>>     Alias sets for function 'fun':
>>>>     Alias Set Tracker: 3 alias sets for 6 pointer values.
>>>>       AliasSet[0x5b5df0, 2] may alias, Mod/Ref   Pointers: (i32* %var, LocationSize::precise(4)), (i32* %var.tmp, LocationSize::precise(4))
>>>>       AliasSet[0x5b5e90, 2] must alias, Mod/Ref   Pointers: (i32** %var.addr, LocationSize::precise(8)), (i8* %1, LocationSize::precise(8))
>>>>       AliasSet[0x5b7390, 2] must alias, Mod/Ref   Pointers: (i8* %0, LocationSize::precise(8)), (i32** %var.addr.tmp, LocationSize::precise(8))
>>>>
>>>> So AA says that %var and %var.tmp "may alias", but I'd expect to get a
>>>> "must alias". What can be done to determine that %var and %var.tmp are
>>>> actually the same pointer in this case?
>>> Can anyone suggest how to get the expected results from AA?
>>>
>>> InstCombiner and other LLVM passes can probably remove a memcpy and make
>>> IR a lot easier for AA, but I'd like to get the analysis working for
>>> not-optimized IR as well.
>> Hi, Andrew,
>>
>> To be clear, you'd like BasicAA to look back, not just trough the
>> memcpy, but also through the loads and stores of the addresses?
> Yes, exactly. I was mostly concerned about memcpy, but you're right,
> loads/stores of addresses seems to have the same issue.

We've not generally seen a need to put this kind of logic into BasicAA,
and even if we were motivated to do so, we'd need to be very careful
about compile-time impact.

>
>> BasicAA currently doesn't do any of that under the presumption that,
>> once SROA, InstCombine, etc. do promotion and simplification, AA will
>> be able to understand the rest.
> That is what I thought. Thanks for the confirmation.
>
>> Can you say more about the use case?
> OpenCL C has a notion of Generic Address Space (GAS), allowing you to
> cast a pointer from any (named) address space to a GAS pointer. Then you
> can use this GAS pointer instead of a named AS pointer. Compiler is
> responsible to infer the original address space of a GAS pointer when it
> is actually used (for load/store), otherwise this is a compilation
> error.

That seems scary :-) -- Can this inference not be done syntactically in
Clang?

 -Hal

>
> So I'm trying to follow a pointer from a point of origin
> (i.e. addrspacecast private ptr -> generic ptr) and look through a
> sequence of bitcasts, GEPs, function calls and pointer copies through
> memory. AliasAnalysis and MemDepAnalysis give me all the required
> information to do intraprocedural analysis, except for the memcpy case
> that I raised in this thread.
>
> Since a failure to infer an address space means a compilation error, I'm
> trying to get this analysis working for debug builds, where we do not
> run InstCombine and other aggressive optimizations.
>
--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] AliasAnalysis does not look though a memcpy

Alberto Barbaro via llvm-dev
Finkel, Hal J. writes:

> On 12/5/18 2:14 PM, Andrew Savonichev wrote:
>>> On 12/5/18 9:51 AM, Andrew Savonichev via llvm-dev wrote:
>>>>> Hi,
>>>>>
>>>>> I'm trying to get AA results for two pointers, but it seems that AA
>>>>> cannot look though a memcpy. For example:
>>>>>
>>>>>     define dso_local spir_func void @fun() {
>>>>>     entry:
>>>>>       ; Store an address of `var'
>>>>>       %var = alloca i32, align 4
>>>>>       store i32 42, i32* %var, align 4
>>>>>       %var.addr = alloca i32*, align 8
>>>>>       store i32* %var, i32** %var.addr, align 8
>>>>>
>>>>>       ; Memcpy `var.addr' to `var.addr.tmp'
>>>>>       %var.addr.tmp = alloca i32*, align 8
>>>>>       %0 = bitcast i32** %var.addr.tmp to i8*
>>>>>       %1 = bitcast i32** %var.addr to i8*
>>>>>       call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %0, i8* align 8 %1, i64 8, i1 false)
>>>>>
>>>>>       ; Load a copy of `var'
>>>>>       %var.tmp = load i32*, i32** %var.addr.tmp
>>>>>       %should.be.42 = load i32, i32* %var.tmp
>>>>>       ret void
>>>>>     }
>>>>>
>>>>>     ; Function Attrs: argmemonly nounwind
>>>>>     declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1) #1
>>>>>     attributes #1 = { argmemonly nounwind }
>>>>>
>>>>> I run it with opt, and get the following:
>>>>>
>>>>>     $ opt -basicaa -print-alias-sets memcpy.ll -disable-output
>>>>>     Alias sets for function 'fun':
>>>>>     Alias Set Tracker: 3 alias sets for 6 pointer values.
>>>>>       AliasSet[0x5b5df0, 2] may alias, Mod/Ref   Pointers: (i32* %var, LocationSize::precise(4)), (i32* %var.tmp, LocationSize::precise(4))
>>>>>       AliasSet[0x5b5e90, 2] must alias, Mod/Ref   Pointers: (i32** %var.addr, LocationSize::precise(8)), (i8* %1, LocationSize::precise(8))
>>>>>       AliasSet[0x5b7390, 2] must alias, Mod/Ref   Pointers: (i8* %0, LocationSize::precise(8)), (i32** %var.addr.tmp, LocationSize::precise(8))
>>>>>
>>>>> So AA says that %var and %var.tmp "may alias", but I'd expect to get a
>>>>> "must alias". What can be done to determine that %var and %var.tmp are
>>>>> actually the same pointer in this case?
>>>> Can anyone suggest how to get the expected results from AA?
>>>>
>>>> InstCombiner and other LLVM passes can probably remove a memcpy and make
>>>> IR a lot easier for AA, but I'd like to get the analysis working for
>>>> not-optimized IR as well.
>>> Hi, Andrew,
>>>
>>> To be clear, you'd like BasicAA to look back, not just trough the
>>> memcpy, but also through the loads and stores of the addresses?
>>>
>> Yes, exactly. I was mostly concerned about memcpy, but you're right,
>> loads/stores of addresses seems to have the same issue.
>
> We've not generally seen a need to put this kind of logic into BasicAA,
> and even if we were motivated to do so, we'd need to be very careful
> about compile-time impact.
>

Understood. I assume that the best way to ensure that is to add this
logic into a new AA.

>>> BasicAA currently doesn't do any of that under the presumption that,
>>> once SROA, InstCombine, etc. do promotion and simplification, AA will
>>> be able to understand the rest.
>> That is what I thought. Thanks for the confirmation.
>>
>>> Can you say more about the use case?
>> OpenCL C has a notion of Generic Address Space (GAS), allowing you to
>> cast a pointer from any (named) address space to a GAS pointer. Then you
>> can use this GAS pointer instead of a named AS pointer. Compiler is
>> responsible to infer the original address space of a GAS pointer when it
>> is actually used (for load/store), otherwise this is a compilation
>> error.
>
> That seems scary :-) -- Can this inference not be done syntactically in
> Clang?
>

From a frontend perspective, a GAS pointer is just a pointer:

  void foo(int *p, int *q) { *p = 42; *q = 43; };

Until Clang reaches a call site, it has no idea about real address
spaces of `p' and `q'. When we do reach a call site, `foo()' can already
be CodeGen'ed, so we can't really change anything.

>> So I'm trying to follow a pointer from a point of origin
>> (i.e. addrspacecast private ptr -> generic ptr) and look through a
>> sequence of bitcasts, GEPs, function calls and pointer copies through
>> memory. AliasAnalysis and MemDepAnalysis give me all the required
>> information to do intraprocedural analysis, except for the memcpy case
>> that I raised in this thread.
>>
>> Since a failure to infer an address space means a compilation error, I'm
>> trying to get this analysis working for debug builds, where we do not
>> run InstCombine and other aggressive optimizations.
>>

--
Andrew

--------------------------------------------------------------------
Joint Stock Company Intel A/O
Registered legal address: Krylatsky Hills Business Park,
17 Krylatskaya Str., Bldg 4, Moscow 121614,
Russian Federation

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] AliasAnalysis does not look though a memcpy

Alberto Barbaro via llvm-dev

On 12/6/18 8:33 AM, Andrew Savonichev wrote:

> Finkel, Hal J. writes:
>> On 12/5/18 2:14 PM, Andrew Savonichev wrote:
>>>> On 12/5/18 9:51 AM, Andrew Savonichev via llvm-dev wrote:
>>>>>> Hi,
>>>>>>
>>>>>> I'm trying to get AA results for two pointers, but it seems that AA
>>>>>> cannot look though a memcpy. For example:
>>>>>>
>>>>>>     define dso_local spir_func void @fun() {
>>>>>>     entry:
>>>>>>       ; Store an address of `var'
>>>>>>       %var = alloca i32, align 4
>>>>>>       store i32 42, i32* %var, align 4
>>>>>>       %var.addr = alloca i32*, align 8
>>>>>>       store i32* %var, i32** %var.addr, align 8
>>>>>>
>>>>>>       ; Memcpy `var.addr' to `var.addr.tmp'
>>>>>>       %var.addr.tmp = alloca i32*, align 8
>>>>>>       %0 = bitcast i32** %var.addr.tmp to i8*
>>>>>>       %1 = bitcast i32** %var.addr to i8*
>>>>>>       call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %0, i8* align 8 %1, i64 8, i1 false)
>>>>>>
>>>>>>       ; Load a copy of `var'
>>>>>>       %var.tmp = load i32*, i32** %var.addr.tmp
>>>>>>       %should.be.42 = load i32, i32* %var.tmp
>>>>>>       ret void
>>>>>>     }
>>>>>>
>>>>>>     ; Function Attrs: argmemonly nounwind
>>>>>>     declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1) #1
>>>>>>     attributes #1 = { argmemonly nounwind }
>>>>>>
>>>>>> I run it with opt, and get the following:
>>>>>>
>>>>>>     $ opt -basicaa -print-alias-sets memcpy.ll -disable-output
>>>>>>     Alias sets for function 'fun':
>>>>>>     Alias Set Tracker: 3 alias sets for 6 pointer values.
>>>>>>       AliasSet[0x5b5df0, 2] may alias, Mod/Ref   Pointers: (i32* %var, LocationSize::precise(4)), (i32* %var.tmp, LocationSize::precise(4))
>>>>>>       AliasSet[0x5b5e90, 2] must alias, Mod/Ref   Pointers: (i32** %var.addr, LocationSize::precise(8)), (i8* %1, LocationSize::precise(8))
>>>>>>       AliasSet[0x5b7390, 2] must alias, Mod/Ref   Pointers: (i8* %0, LocationSize::precise(8)), (i32** %var.addr.tmp, LocationSize::precise(8))
>>>>>>
>>>>>> So AA says that %var and %var.tmp "may alias", but I'd expect to get a
>>>>>> "must alias". What can be done to determine that %var and %var.tmp are
>>>>>> actually the same pointer in this case?
>>>>> Can anyone suggest how to get the expected results from AA?
>>>>>
>>>>> InstCombiner and other LLVM passes can probably remove a memcpy and make
>>>>> IR a lot easier for AA, but I'd like to get the analysis working for
>>>>> not-optimized IR as well.
>>>> Hi, Andrew,
>>>>
>>>> To be clear, you'd like BasicAA to look back, not just trough the
>>>> memcpy, but also through the loads and stores of the addresses?
>>>>
>>> Yes, exactly. I was mostly concerned about memcpy, but you're right,
>>> loads/stores of addresses seems to have the same issue.
>> We've not generally seen a need to put this kind of logic into BasicAA,
>> and even if we were motivated to do so, we'd need to be very careful
>> about compile-time impact.
>>
> Understood. I assume that the best way to ensure that is to add this
> logic into a new AA.
>
>>>> BasicAA currently doesn't do any of that under the presumption that,
>>>> once SROA, InstCombine, etc. do promotion and simplification, AA will
>>>> be able to understand the rest.
>>> That is what I thought. Thanks for the confirmation.
>>>
>>>> Can you say more about the use case?
>>> OpenCL C has a notion of Generic Address Space (GAS), allowing you to
>>> cast a pointer from any (named) address space to a GAS pointer. Then you
>>> can use this GAS pointer instead of a named AS pointer. Compiler is
>>> responsible to infer the original address space of a GAS pointer when it
>>> is actually used (for load/store), otherwise this is a compilation
>>> error.
>> That seems scary :-) -- Can this inference not be done syntactically in
>> Clang?
>>
> From a frontend perspective, a GAS pointer is just a pointer:
>
>   void foo(int *p, int *q) { *p = 42; *q = 43; };
>
> Until Clang reaches a call site, it has no idea about real address
> spaces of `p' and `q'. When we do reach a call site, `foo()' can already
> be CodeGen'ed, so we can't really change anything.

Is this supposed to work like template instantiation? Are you guaranteed
to only get one (unique) set of address spaces for the function arguments?

We can change the order that functions are emitted in Clang if necessary.

 -Hal

>
>>> So I'm trying to follow a pointer from a point of origin
>>> (i.e. addrspacecast private ptr -> generic ptr) and look through a
>>> sequence of bitcasts, GEPs, function calls and pointer copies through
>>> memory. AliasAnalysis and MemDepAnalysis give me all the required
>>> information to do intraprocedural analysis, except for the memcpy case
>>> that I raised in this thread.
>>>
>>> Since a failure to infer an address space means a compilation error, I'm
>>> trying to get this analysis working for debug builds, where we do not
>>> run InstCombine and other aggressive optimizations.
>>>
--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] AliasAnalysis does not look though a memcpy

Alberto Barbaro via llvm-dev
Finkel, Hal J. writes:

> On 12/6/18 8:33 AM, Andrew Savonichev wrote:
>> Finkel, Hal J. writes:
>>> On 12/5/18 2:14 PM, Andrew Savonichev wrote:
>>>>> On 12/5/18 9:51 AM, Andrew Savonichev via llvm-dev wrote:
>>>>>>> Hi,
>>>>>>>
>>>>>>> I'm trying to get AA results for two pointers, but it seems that AA
>>>>>>> cannot look though a memcpy. For example:
>>>>>>>
>>>>>>>     define dso_local spir_func void @fun() {
>>>>>>>     entry:
>>>>>>>       ; Store an address of `var'
>>>>>>>       %var = alloca i32, align 4
>>>>>>>       store i32 42, i32* %var, align 4
>>>>>>>       %var.addr = alloca i32*, align 8
>>>>>>>       store i32* %var, i32** %var.addr, align 8
>>>>>>>
>>>>>>>       ; Memcpy `var.addr' to `var.addr.tmp'
>>>>>>>       %var.addr.tmp = alloca i32*, align 8
>>>>>>>       %0 = bitcast i32** %var.addr.tmp to i8*
>>>>>>>       %1 = bitcast i32** %var.addr to i8*
>>>>>>>       call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %0, i8* align 8 %1, i64 8, i1 false)
>>>>>>>
>>>>>>>       ; Load a copy of `var'
>>>>>>>       %var.tmp = load i32*, i32** %var.addr.tmp
>>>>>>>       %should.be.42 = load i32, i32* %var.tmp
>>>>>>>       ret void
>>>>>>>     }
>>>>>>>
>>>>>>>     ; Function Attrs: argmemonly nounwind
>>>>>>>     declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1) #1
>>>>>>>     attributes #1 = { argmemonly nounwind }
>>>>>>>
>>>>>>> I run it with opt, and get the following:
>>>>>>>
>>>>>>>     $ opt -basicaa -print-alias-sets memcpy.ll -disable-output
>>>>>>>     Alias sets for function 'fun':
>>>>>>>     Alias Set Tracker: 3 alias sets for 6 pointer values.
>>>>>>>       AliasSet[0x5b5df0, 2] may alias, Mod/Ref   Pointers: (i32* %var, LocationSize::precise(4)), (i32* %var.tmp, LocationSize::precise(4))
>>>>>>>       AliasSet[0x5b5e90, 2] must alias, Mod/Ref   Pointers: (i32** %var.addr, LocationSize::precise(8)), (i8* %1, LocationSize::precise(8))
>>>>>>>       AliasSet[0x5b7390, 2] must alias, Mod/Ref   Pointers: (i8* %0, LocationSize::precise(8)), (i32** %var.addr.tmp, LocationSize::precise(8))
>>>>>>>
>>>>>>> So AA says that %var and %var.tmp "may alias", but I'd expect to get a
>>>>>>> "must alias". What can be done to determine that %var and %var.tmp are
>>>>>>> actually the same pointer in this case?
>>>>>> Can anyone suggest how to get the expected results from AA?
>>>>>>
>>>>>> InstCombiner and other LLVM passes can probably remove a memcpy and make
>>>>>> IR a lot easier for AA, but I'd like to get the analysis working for
>>>>>> not-optimized IR as well.
>>>>> Hi, Andrew,
>>>>>
>>>>> To be clear, you'd like BasicAA to look back, not just trough the
>>>>> memcpy, but also through the loads and stores of the addresses?
>>>>>
>>>> Yes, exactly. I was mostly concerned about memcpy, but you're right,
>>>> loads/stores of addresses seems to have the same issue.
>>> We've not generally seen a need to put this kind of logic into BasicAA,
>>> and even if we were motivated to do so, we'd need to be very careful
>>> about compile-time impact.
>>>
>> Understood. I assume that the best way to ensure that is to add this
>> logic into a new AA.
>>
>>>>> BasicAA currently doesn't do any of that under the presumption that,
>>>>> once SROA, InstCombine, etc. do promotion and simplification, AA will
>>>>> be able to understand the rest.
>>>> That is what I thought. Thanks for the confirmation.
>>>>
>>>>> Can you say more about the use case?
>>>> OpenCL C has a notion of Generic Address Space (GAS), allowing you to
>>>> cast a pointer from any (named) address space to a GAS pointer. Then you
>>>> can use this GAS pointer instead of a named AS pointer. Compiler is
>>>> responsible to infer the original address space of a GAS pointer when it
>>>> is actually used (for load/store), otherwise this is a compilation
>>>> error.
>>> That seems scary :-) -- Can this inference not be done syntactically in
>>> Clang?
>>>
>> From a frontend perspective, a GAS pointer is just a pointer:
>>
>>   void foo(int *p, int *q) { *p = 42; *q = 43; };
>>
>> Until Clang reaches a call site, it has no idea about real address
>> spaces of `p' and `q'. When we do reach a call site, `foo()' can already
>> be CodeGen'ed, so we can't really change anything.
>
> Is this supposed to work like template instantiation? Are you guaranteed
> to only get one (unique) set of address spaces for the function
> arguments?
>

Yes, just like in C++ template, if `foo' is called with different sets
of address spaces, a compiler have to create different function
instantiations for each set.

>
> We can change the order that functions are emitted in Clang if necessary.
>

I haven't thought this is actually configurable. I'd really appreciate
if you can give me a pointer on how to do this.

>>>> So I'm trying to follow a pointer from a point of origin
>>>> (i.e. addrspacecast private ptr -> generic ptr) and look through a
>>>> sequence of bitcasts, GEPs, function calls and pointer copies through
>>>> memory. AliasAnalysis and MemDepAnalysis give me all the required
>>>> information to do intraprocedural analysis, except for the memcpy case
>>>> that I raised in this thread.
>>>>
>>>> Since a failure to infer an address space means a compilation error, I'm
>>>> trying to get this analysis working for debug builds, where we do not
>>>> run InstCombine and other aggressive optimizations.
>>>>

--
Andrew

--------------------------------------------------------------------
Joint Stock Company Intel A/O
Registered legal address: Krylatsky Hills Business Park,
17 Krylatskaya Str., Bldg 4, Moscow 121614,
Russian Federation

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev