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

[Finkel, Hal J. 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