llvm dev - Dec 2018 - AliasAnalysis does not look though a memcpy

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

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

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