llvm dev - Jun 2018 - One more Question about handling pointer with restrict keyword on Alias Analysis

Hi All,

I have a question about handling pointer on Alias Analysis. Let's look 
at simple code snippet.

struct element {
   char fieldA;
   char fieldB;
};

char c;

void test(int idx, struct element *restrict *restrict buf1,
           struct element *restrict *restrict buf2) {
   struct element *a = buf1[idx];
   struct element *b = buf2[idx];

   a->fieldA = b->fieldB;

   c++;

   a->fieldA = b->fieldB | 1;
}

The IR snippet is as following:

%struct.element = type { i8, i8 }

@c = common local_unnamed_addr global i8 0, align 1

define void @test(i32, %struct.element** noalias nocapture readonly, 
%struct.element** noalias nocapture readonly) local_unnamed_addr #0 {
   %4 = sext i32 %0 to i64
   %5 = getelementptr inbounds %struct.element*, %struct.element** %1, 
i64 %4
   %6 = load %struct.element*, %struct.element** %5, align 8, !tbaa !2
   %7 = getelementptr inbounds %struct.element*, %struct.element** %2, 
i64 %4
   %8 = load %struct.element*, %struct.element** %7, align 8, !tbaa !2
   %9 = getelementptr inbounds %struct.element, %struct.element* %8, i64 
0, i32 1
   %10 = load i8, i8* %9, align 1, !tbaa !6
   %11 = getelementptr inbounds %struct.element, %struct.element* %6, 
i64 0, i32 0
   store i8 %10, i8* %11, align 1, !tbaa !8
   %12 = load i8, i8* @c, align 1, !tbaa !9
   %13 = add i8 %12, 1
   store i8 %13, i8* @c, align 1, !tbaa !9
   %14 = or i8 %10, 1
   store i8 %14, i8* %11, align 1, !tbaa !8
   ret void
}

The result of AliasSet is as below.

Alias sets for function 'test':
Alias Set Tracker: 4 alias sets for 5 pointer values.
   AliasSet[0x64ac600, 1] must alias, Ref       Pointers: 
(%struct.element** %5, 8)
   AliasSet[0x64aa990, 1] must alias, Ref       Pointers: 
(%struct.element** %7, 8)
   AliasSet[0x64ab320, 1] must alias, Ref       Pointers: (i8* %9, 1)
   AliasSet[0x64ac800, 2] may alias, Mod/Ref   Pointers: (i8* %11, 1), 
(i8* @c, 1)

As you can see, there is 'May-Alias' between %11 and @c. I think we 
could say 'No-Alias' between them because of the restrict keyword. It 
seems the basicAA does not go through 'load' instruction with its 
recursive way and GetUnderlyingObject. I am not sure why it does not 
always go though it. Is there something illegal to do it? Could someone 
let me know it please? If I missed something, please let me know.

Thanks,

JinGu Kang

[+Jeroen]

Hi, JinGu,

Yes. The underlying problem here is that we don't really do anything
with the nested restrict pointer qualifications. This is the same
problem, in some sense, as handling restrict-qualified local variables.
I've proposed a scheme based on an @llvm.noalias intrinsic to handle
this, and there's still some iteration on how to do this without
penalizing the optimizer too much (because the intrinsic would need to
be opaque, essentially, so it can get it the way at times). If you're
interested in helping with this, that would be good.

 -Hal

On 06/28/2018 10:27 AM, jingu at codeplay.com wrote:
> Hi All,
>
> I have a question about handling pointer on Alias Analysis. Let's look
> at simple code snippet.
>
> struct element {
>   char fieldA;
>   char fieldB;
> };
>
> char c;
>
> void test(int idx, struct element *restrict *restrict buf1,
>           struct element *restrict *restrict buf2) {
>   struct element *a = buf1[idx];
>   struct element *b = buf2[idx];
>
>   a->fieldA = b->fieldB;
>
>   c++;
>
>   a->fieldA = b->fieldB | 1;
> }
>
> The IR snippet is as following:
>
> %struct.element = type { i8, i8 }
>
> @c = common local_unnamed_addr global i8 0, align 1
>
> define void @test(i32, %struct.element** noalias nocapture readonly,
> %struct.element** noalias nocapture readonly) local_unnamed_addr #0 {
>   %4 = sext i32 %0 to i64
>   %5 = getelementptr inbounds %struct.element*, %struct.element** %1,
> i64 %4
>   %6 = load %struct.element*, %struct.element** %5, align 8, !tbaa !2
>   %7 = getelementptr inbounds %struct.element*, %struct.element** %2,
> i64 %4
>   %8 = load %struct.element*, %struct.element** %7, align 8, !tbaa !2
>   %9 = getelementptr inbounds %struct.element, %struct.element* %8,
> i64 0, i32 1
>   %10 = load i8, i8* %9, align 1, !tbaa !6
>   %11 = getelementptr inbounds %struct.element, %struct.element* %6,
> i64 0, i32 0
>   store i8 %10, i8* %11, align 1, !tbaa !8
>   %12 = load i8, i8* @c, align 1, !tbaa !9
>   %13 = add i8 %12, 1
>   store i8 %13, i8* @c, align 1, !tbaa !9
>   %14 = or i8 %10, 1
>   store i8 %14, i8* %11, align 1, !tbaa !8
>   ret void
> }
>
> The result of AliasSet is as below.
>
> Alias sets for function 'test':
> Alias Set Tracker: 4 alias sets for 5 pointer values.
>   AliasSet[0x64ac600, 1] must alias, Ref       Pointers:
> (%struct.element** %5, 8)
>   AliasSet[0x64aa990, 1] must alias, Ref       Pointers:
> (%struct.element** %7, 8)
>   AliasSet[0x64ab320, 1] must alias, Ref       Pointers: (i8* %9, 1)
>   AliasSet[0x64ac800, 2] may alias, Mod/Ref   Pointers: (i8* %11, 1),
> (i8* @c, 1)
>
> As you can see, there is 'May-Alias' between %11 and @c. I think we
> could say 'No-Alias' between them because of the restrict keyword.
It
> seems the basicAA does not go through 'load' instruction with its
> recursive way and GetUnderlyingObject. I am not sure why it does not
> always go though it. Is there something illegal to do it? Could
> someone let me know it please? If I missed something, please let me know.
>
> Thanks,
>
> JinGu Kang
>
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory