[llvm-dev] Question about Alias Analysis with restrict keyword

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

[llvm-dev] Question about Alias Analysis with restrict keyword

Bruce Hoult via llvm-dev
Hello All,

I have met a case with restrict keyword and I have a question about it.
Let's look at a simple example.

char buf[4];

void test(char *restrict a, char *restrict b, int count) {
   for (unsigned i = 0; i < count; i++) {
     *a = *b;
     a++;
     b++;
     buf[i] = i;
   }
}

I think there are no aliasing among pointers such as 'a', 'b' and 'buf'
because of the restrict keyword.

The IR snippet with '-O1' is as following:

@buf = common local_unnamed_addr global [4 x i8] zeroinitializer, align 1

; Function Attrs: norecurse nounwind uwtable
define void @test(i8* noalias nocapture, i8* noalias nocapture readonly,
i32) local_unnamed_addr #0 {
   %4 = icmp eq i32 %2, 0
   br i1 %4, label %7, label %5

; <label>:5:                                      ; preds = %3
   %6 = zext i32 %2 to i64
   br label %8

; <label>:7:                                      ; preds = %8, %3
   ret void

; <label>:8:                                      ; preds = %8, %5
   %9 = phi i64 [ 0, %5 ], [ %17, %8 ]
   %10 = phi i8* [ %0, %5 ], [ %13, %8 ]
   %11 = phi i8* [ %1, %5 ], [ %14, %8 ]
   %12 = load i8, i8* %11, align 1, !tbaa !2
   store i8 %12, i8* %10, align 1, !tbaa !2
   %13 = getelementptr inbounds i8, i8* %10, i64 1
   %14 = getelementptr inbounds i8, i8* %11, i64 1
   %15 = trunc i64 %9 to i8
   %16 = getelementptr inbounds [4 x i8], [4 x i8]* @buf, i64 0, i64 %9
   store i8 %15, i8* %16, align 1, !tbaa !2
   %17 = add nuw nsw i64 %9, 1
   %18 = icmp eq i64 %17, %6
   br i1 %18, label %7, label %8
}

As you can see, there are noalias attribute with arguments and we can
expect the alias analysis will consider them.

The Alias Set is as below.

Alias sets for function 'test':
Alias Set Tracker: 2 alias sets for 3 pointer values.
   AliasSet[0x4a1e3a0, 3] may alias, Mod/Ref   Pointers: (i8* %11, 1),
(i8* %10, 1), (i8* %16, 1)
   AliasSet[0x4a1e440, 1] must alias, Mod        forwarding to 0x4a1e3a0

Alias analysis returns 'May- alias' for above code. When I look at the
alias analysis code, below code causes may-alias.

On BasicAAResult::aliasGEP()

1297     // Check to see if these two pointers are related by the
getelementptr
1298     // instruction.  If one pointer is a GEP with a non-zero index
of the other
1299     // pointer, we know they cannot alias.
1300
1301     // If both accesses are unknown size, we can't do anything
useful here.
1302     if (V1Size == MemoryLocation::UnknownSize &&
1303         V2Size == MemoryLocation::UnknownSize)
1304       return MayAlias;
1305
1306     AliasResult R = aliasCheck(UnderlyingV1,
MemoryLocation::UnknownSize,
1307                                AAMDNodes(), V2,
MemoryLocation::UnknownSize,
1308                                V2AAInfo, nullptr, UnderlyingV2);

On line 1306, we can see the V1Size and V2Size are set up with
"MemoryLocation::UnknownSize" and it causes may-alias. On line 1302 and
1033, there are checking code for "MemoryLocation::UnknownSize"... I am
not sure whether it is bug or not... Can someone let me know why it
passes "MemoryLocation::UnknownSize" please? If I missed something,
please let me know.

Thanks,

JinGu Kang

_______________________________________________
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] Question about Alias Analysis with restrict keyword

Bruce Hoult via llvm-dev
On 6/18/2018 8:16 AM, [hidden email] wrote:

>
> On BasicAAResult::aliasGEP()
>
> 1297     // Check to see if these two pointers are related by the
> getelementptr
> 1298     // instruction.  If one pointer is a GEP with a non-zero
> index of the other
> 1299     // pointer, we know they cannot alias.
> 1300
> 1301     // If both accesses are unknown size, we can't do anything
> useful here.
> 1302     if (V1Size == MemoryLocation::UnknownSize &&
> 1303         V2Size == MemoryLocation::UnknownSize)
> 1304       return MayAlias;

The check for UnknownSize is here because it's impossible to
disambiguate the offsets of two pointers which both have unknown size,
so the rest of BasicAAResult::aliasGEP can't do anything useful.

> 1305
> 1306     AliasResult R = aliasCheck(UnderlyingV1,
> MemoryLocation::UnknownSize,
> 1307                                AAMDNodes(), V2,
> MemoryLocation::UnknownSize,
> 1308                                V2AAInfo, nullptr, UnderlyingV2);
>
> On line 1306, we can see the V1Size and V2Size are set up with
> "MemoryLocation::UnknownSize" and it causes may-alias. On line 1302
> and 1033, there are checking code for "MemoryLocation::UnknownSize"...
> I am not sure whether it is bug or not... Can someone let me know why
> it passes "MemoryLocation::UnknownSize" please? If I missed something,
> please let me know.
>

UnderlyingV1 is the base of the GEP.  So this is asking whether the base
of the GEP aliases V2.  It uses UnknownSize because the offset is
unknown; it can't tell which bytes are accessed, so it's using an
approximation instead.

We could theoretically try to be a bit more clever here if the size is
known and the GEP offset is constant: we could instead pass
V1Size+GEP1BaseOffset.  Not sure that would have much effect in
practice, though.

-Eli

--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project

_______________________________________________
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] Question about Alias Analysis with restrict keyword

Bruce Hoult via llvm-dev
Hi Eli,

I appreciate your good comments. It is very helpful.

Thanks again,

JinGu Kang


On 18/06/18 23:17, Friedman, Eli wrote:

> On 6/18/2018 8:16 AM, [hidden email] wrote:
>>
>> On BasicAAResult::aliasGEP()
>>
>> 1297     // Check to see if these two pointers are related by the
>> getelementptr
>> 1298     // instruction.  If one pointer is a GEP with a non-zero
>> index of the other
>> 1299     // pointer, we know they cannot alias.
>> 1300
>> 1301     // If both accesses are unknown size, we can't do anything
>> useful here.
>> 1302     if (V1Size == MemoryLocation::UnknownSize &&
>> 1303         V2Size == MemoryLocation::UnknownSize)
>> 1304       return MayAlias;
>
> The check for UnknownSize is here because it's impossible to
> disambiguate the offsets of two pointers which both have unknown size,
> so the rest of BasicAAResult::aliasGEP can't do anything useful.
>
>> 1305
>> 1306     AliasResult R = aliasCheck(UnderlyingV1,
>> MemoryLocation::UnknownSize,
>> 1307                                AAMDNodes(), V2,
>> MemoryLocation::UnknownSize,
>> 1308                                V2AAInfo, nullptr, UnderlyingV2);
>>
>> On line 1306, we can see the V1Size and V2Size are set up with
>> "MemoryLocation::UnknownSize" and it causes may-alias. On line 1302
>> and 1033, there are checking code for
>> "MemoryLocation::UnknownSize"... I am not sure whether it is bug or
>> not... Can someone let me know why it passes
>> "MemoryLocation::UnknownSize" please? If I missed something, please
>> let me know.
>>
>
> UnderlyingV1 is the base of the GEP.  So this is asking whether the
> base of the GEP aliases V2.  It uses UnknownSize because the offset is
> unknown; it can't tell which bytes are accessed, so it's using an
> approximation instead.
>
> We could theoretically try to be a bit more clever here if the size is
> known and the GEP offset is constant: we could instead pass
> V1Size+GEP1BaseOffset.  Not sure that would have much effect in
> practice, though.
>
> -Eli
>

--
JINGU KANG
Software Engineer, Compilers
Codeplay Software Ltd
Level C Argyle House, 3 Lady Lawson Street, Edinburgh, United Kingdom, EH3 9DR
Tel: +44 (0)131 466 0503
Website: http://www.codeplay.com
Twitter: https://twitter.com/codeplaysoft

This email and any attachments may contain confidential and /or privileged information and is for use by the addressee only. If you are not the intended recipient, please notify Codeplay Software Ltd immediately and delete the message from your computer. You may not copy or forward it, or use or disclose its contents to any other person. Any views or other information in this message which do not relate to our business are not authorized by Codeplay software Ltd, nor does this message form part of any contract unless so stated.
As internet communications are capable of data corruption Codeplay Software Ltd does not accept any responsibility for any changes made to this message after it was sent. Please note that Codeplay Software Ltd does not accept any liability or responsibility for viruses and it is your responsibility to scan any attachments.
Company registered in England and Wales, number: 04567874
Registered office: Regent House, 316 Beulah Hill, London, United Kingdom, SE19 3HF

_______________________________________________
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] Question about Alias Analysis with restrict keyword

Bruce Hoult via llvm-dev
Ah, the recursive phi and gep caused the may-alias... Eli made my brain
re-work. Thank you very much! To be sure, If we add "-basicaa-recphi"
option, the example does not generate may-alias with restrict keyword.


On 19/06/18 10:33, [hidden email] via llvm-dev wrote:

> Hi Eli,
>
> I appreciate your good comments. It is very helpful.
>
> Thanks again,
>
> JinGu Kang
>
>
> On 18/06/18 23:17, Friedman, Eli wrote:
>> On 6/18/2018 8:16 AM, [hidden email] wrote:
>>>
>>> On BasicAAResult::aliasGEP()
>>>
>>> 1297     // Check to see if these two pointers are related by the
>>> getelementptr
>>> 1298     // instruction.  If one pointer is a GEP with a non-zero
>>> index of the other
>>> 1299     // pointer, we know they cannot alias.
>>> 1300
>>> 1301     // If both accesses are unknown size, we can't do anything
>>> useful here.
>>> 1302     if (V1Size == MemoryLocation::UnknownSize &&
>>> 1303         V2Size == MemoryLocation::UnknownSize)
>>> 1304       return MayAlias;
>>
>> The check for UnknownSize is here because it's impossible to
>> disambiguate the offsets of two pointers which both have unknown
>> size, so the rest of BasicAAResult::aliasGEP can't do anything useful.
>>
>>> 1305
>>> 1306     AliasResult R = aliasCheck(UnderlyingV1,
>>> MemoryLocation::UnknownSize,
>>> 1307                                AAMDNodes(), V2,
>>> MemoryLocation::UnknownSize,
>>> 1308                                V2AAInfo, nullptr, UnderlyingV2);
>>>
>>> On line 1306, we can see the V1Size and V2Size are set up with
>>> "MemoryLocation::UnknownSize" and it causes may-alias. On line 1302
>>> and 1033, there are checking code for
>>> "MemoryLocation::UnknownSize"... I am not sure whether it is bug or
>>> not... Can someone let me know why it passes
>>> "MemoryLocation::UnknownSize" please? If I missed something, please
>>> let me know.
>>>
>>
>> UnderlyingV1 is the base of the GEP.  So this is asking whether the
>> base of the GEP aliases V2.  It uses UnknownSize because the offset
>> is unknown; it can't tell which bytes are accessed, so it's using an
>> approximation instead.
>>
>> We could theoretically try to be a bit more clever here if the size
>> is known and the GEP offset is constant: we could instead pass
>> V1Size+GEP1BaseOffset.  Not sure that would have much effect in
>> practice, though.
>>
>> -Eli
>>
>

--
JINGU KANG
Software Engineer, Compilers
Codeplay Software Ltd
Level C Argyle House, 3 Lady Lawson Street, Edinburgh, United Kingdom, EH3 9DR
Tel: +44 (0)131 466 0503
Website: http://www.codeplay.com
Twitter: https://twitter.com/codeplaysoft

This email and any attachments may contain confidential and /or privileged information and is for use by the addressee only. If you are not the intended recipient, please notify Codeplay Software Ltd immediately and delete the message from your computer. You may not copy or forward it, or use or disclose its contents to any other person. Any views or other information in this message which do not relate to our business are not authorized by Codeplay software Ltd, nor does this message form part of any contract unless so stated.
As internet communications are capable of data corruption Codeplay Software Ltd does not accept any responsibility for any changes made to this message after it was sent. Please note that Codeplay Software Ltd does not accept any liability or responsibility for viruses and it is your responsibility to scan any attachments.
Company registered in England and Wales, number: 04567874
Registered office: Regent House, 316 Beulah Hill, London, United Kingdom, SE19 3HF

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