[llvm-dev] One more No-alias case on Alias analysis

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

[llvm-dev] One more No-alias case on Alias analysis

Tim Northover via llvm-dev
Hello All,

I have met one may-alias case from llvm's alias analysis. The code
snippet is as following:

char buf[4];

void test (int idx) {
char *a = &buf[3 - idx];
char *b = &buf[idx];
*a = 1;
*b = 2;
}

I can see below output from alias set tracker for above code snippet.

Alias sets for function 'test':
Alias Set Tracker: 1 alias sets for 2 pointer values.
   AliasSet[0x53d8070, 2] may alias, Mod       Pointers: (i8* %arrayidx,
1), (i8* %arrayidx2, 1)

As you can see on above code snippet, the 'a' and 'b' are not aliased. I
think if we have following offset form, we can say No-alias between them.

offset1 = odd_number - index

offset2 = index

I have implemented simple code for it and the output is as following:

Alias sets for function 'test':
Alias Set Tracker: 2 alias sets for 2 pointer values.
   AliasSet[0x541a070, 1] must alias, Mod       Pointers: (i8* %arrayidx, 1)
   AliasSet[0x541cc00, 1] must alias, Mod       Pointers: (i8*
%arrayidx2, 1)

How do you think about this? Is it legal for current alias analysis or
not? I have attached the diff file as reference. 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

alias.diff (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] One more No-alias case on Alias analysis

Tim Northover via llvm-dev
Oops, there is a typo on diff file. getLoBits(0) -->getLoBits(1)
On 11 Jun 2018, at 18:06, "[hidden email] via llvm-dev" <[hidden email]> wrote:
Hello All,

I have met one may-alias case from llvm's alias analysis. The code
snippet is as following:

char buf[4];

void test (int idx) {
char *a = &buf[3 - idx];
char *b = &buf[idx];
*a = 1;
*b = 2;
}

I can see below output from alias set tracker for above code snippet.

Alias sets for function 'test':
Alias Set Tracker: 1 alias sets for 2 pointer values.
  AliasSet[0x53d8070, 2] may alias, Mod       Pointers: (i8* %arrayidx,
1), (i8* %arrayidx2, 1)

As you can see on above code snippet, the 'a' and 'b' are not aliased. I
think if we have following offset form, we can say No-alias between them.

offset1 = odd_number - index

offset2 = index

I have implemented simple code for it and the output is as following:

Alias sets for function 'test':
Alias Set Tracker: 2 alias sets for 2 pointer values.
  AliasSet[0x541a070, 1] must alias, Mod       Pointers: (i8* %arrayidx, 1)
  AliasSet[0x541cc00, 1] must alias, Mod       Pointers: (i8*
%arrayidx2, 1)

How do you think about this? Is it legal for current alias analysis or
not? I have attached the diff file as reference. 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

_______________________________________________
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] One more No-alias case on Alias analysis

Tim Northover via llvm-dev
In reply to this post by Tim Northover via llvm-dev
On 6/11/2018 10:06 AM, [hidden email] via llvm-dev wrote:

> Hello All,
>
> I have met one may-alias case from llvm's alias analysis. The code
> snippet is as following:
>
> char buf[4];
>
> void test (int idx) {
> char *a = &buf[3 - idx];
> char *b = &buf[idx];
> *a = 1;
> *b = 2;
> }
>
> I can see below output from alias set tracker for above code snippet.
>
> Alias sets for function 'test':
> Alias Set Tracker: 1 alias sets for 2 pointer values.
>   AliasSet[0x53d8070, 2] may alias, Mod       Pointers: (i8*
> %arrayidx, 1), (i8* %arrayidx2, 1)
>
> As you can see on above code snippet, the 'a' and 'b' are not aliased.
> I think if we have following offset form, we can say No-alias between
> them.
>
> offset1 = odd_number - index
>
> offset2 = index
>
> I have implemented simple code for it and the output is as following:
>
> Alias sets for function 'test':
> Alias Set Tracker: 2 alias sets for 2 pointer values.
>   AliasSet[0x541a070, 1] must alias, Mod       Pointers: (i8*
> %arrayidx, 1)
>   AliasSet[0x541cc00, 1] must alias, Mod       Pointers: (i8*
> %arrayidx2, 1)
>
> How do you think about this? Is it legal for current alias analysis or
> not? I have attached the diff file as reference. If I missed
> something, please let me know.

The concept works. I'm not sure your patch handles all the edge cases
correctly, at first glance.  (If you want a full review, please post on
Phabricator.)

-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] One more No-alias case on Alias analysis

Tim Northover via llvm-dev

Thanks Eli for kind comment. I have created the review on Phabricator. https://reviews.llvm.org/D48066 Please review it.

Kind regards,

JinGu Kang


On 11/06/18 20:33, Friedman, Eli wrote:
On 6/11/2018 10:06 AM, [hidden email] via llvm-dev wrote:
Hello All,

I have met one may-alias case from llvm's alias analysis. The code snippet is as following:

char buf[4];

void test (int idx) {
char *a = &buf[3 - idx];
char *b = &buf[idx];
*a = 1;
*b = 2;
}

I can see below output from alias set tracker for above code snippet.

Alias sets for function 'test':
Alias Set Tracker: 1 alias sets for 2 pointer values.
  AliasSet[0x53d8070, 2] may alias, Mod       Pointers: (i8* %arrayidx, 1), (i8* %arrayidx2, 1)

As you can see on above code snippet, the 'a' and 'b' are not aliased. I think if we have following offset form, we can say No-alias between them.

offset1 = odd_number - index

offset2 = index

I have implemented simple code for it and the output is as following:

Alias sets for function 'test':
Alias Set Tracker: 2 alias sets for 2 pointer values.
  AliasSet[0x541a070, 1] must alias, Mod       Pointers: (i8* %arrayidx, 1)
  AliasSet[0x541cc00, 1] must alias, Mod       Pointers: (i8* %arrayidx2, 1)

How do you think about this? Is it legal for current alias analysis or not? I have attached the diff file as reference. If I missed something, please let me know.

The concept works. I'm not sure your patch handles all the edge cases correctly, at first glance.  (If you want a full review, please post on Phabricator.)

-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] One more No-alias case on Alias analysis

Tim Northover via llvm-dev
In reply to this post by Tim Northover via llvm-dev

On 06/11/2018 02:33 PM, Friedman, Eli via llvm-dev wrote:

> On 6/11/2018 10:06 AM, [hidden email] via llvm-dev wrote:
>> Hello All,
>>
>> I have met one may-alias case from llvm's alias analysis. The code
>> snippet is as following:
>>
>> char buf[4];
>>
>> void test (int idx) {
>> char *a = &buf[3 - idx];
>> char *b = &buf[idx];
>> *a = 1;
>> *b = 2;
>> }
>>
>> I can see below output from alias set tracker for above code snippet.
>>
>> Alias sets for function 'test':
>> Alias Set Tracker: 1 alias sets for 2 pointer values.
>>   AliasSet[0x53d8070, 2] may alias, Mod       Pointers: (i8*
>> %arrayidx, 1), (i8* %arrayidx2, 1)
>>
>> As you can see on above code snippet, the 'a' and 'b' are not
>> aliased. I think if we have following offset form, we can say
>> No-alias between them.
>>
>> offset1 = odd_number - index
>>
>> offset2 = index
>>
>> I have implemented simple code for it and the output is as following:
>>
>> Alias sets for function 'test':
>> Alias Set Tracker: 2 alias sets for 2 pointer values.
>>   AliasSet[0x541a070, 1] must alias, Mod       Pointers: (i8*
>> %arrayidx, 1)
>>   AliasSet[0x541cc00, 1] must alias, Mod       Pointers: (i8*
>> %arrayidx2, 1)
>>
>> How do you think about this? Is it legal for current alias analysis
>> or not? I have attached the diff file as reference. If I missed
>> something, please let me know.
>
> The concept works. I'm not sure your patch handles all the edge cases
> correctly, at first glance.  (If you want a full review, please post
> on Phabricator.)

+1

In your example, we have:

3 - idx == idx => 3 == 2*idx

and you've generalized this slightly to make this:

(odd number) == 2*idx

which makes sense. I think that we can go further looking at:

n == 2*idx

and, calling computeKnownBits on n and idx, then asking whether:

knownZeros(n) == (knownZeros(idx) << 1) | 1 and
knownOnes(n) == knownOnes(idx) << 1

(please note the comment in aliasSameBasePointerGEPs regarding avoiding
PR32314)

also, if we have more than one array access, we can have:

n - idx == m - idx

then we have:

n-m == 2*idx

and so we can check:

knownZeros(n-m) == (knownZeros(idx) << 1) | 1 and
knownOnes(n-m) == knownOnes(idx) << 1

Sadly, we don't have a good API to do the knownBits check on the
subtraction of non-constants, but you only need the constants in your
case, and we can leave the more-general case for future work.

Thanks again,
Hal

>
> -Eli
> 8

--
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] One more No-alias case on Alias analysis

Tim Northover via llvm-dev
Thanks Hal for good comment!

It seems the 'computeKnownBits' does not handle non-constant values well.

For example,

define void @test(i32 %idx) {
entry:
   %sub = sub nsw i32 3, %idx

It fails to get Zero and One from %idx.

I agree with using 'computeKnowBits' to check odd number. If I missed
something, please let me know.

Thanks,

JinGu Kang


On 12/06/18 11:17, Hal Finkel wrote:

> On 06/11/2018 02:33 PM, Friedman, Eli via llvm-dev wrote:
>> On 6/11/2018 10:06 AM, [hidden email] via llvm-dev wrote:
>>> Hello All,
>>>
>>> I have met one may-alias case from llvm's alias analysis. The code
>>> snippet is as following:
>>>
>>> char buf[4];
>>>
>>> void test (int idx) {
>>> char *a = &buf[3 - idx];
>>> char *b = &buf[idx];
>>> *a = 1;
>>> *b = 2;
>>> }
>>>
>>> I can see below output from alias set tracker for above code snippet.
>>>
>>> Alias sets for function 'test':
>>> Alias Set Tracker: 1 alias sets for 2 pointer values.
>>>    AliasSet[0x53d8070, 2] may alias, Mod       Pointers: (i8*
>>> %arrayidx, 1), (i8* %arrayidx2, 1)
>>>
>>> As you can see on above code snippet, the 'a' and 'b' are not
>>> aliased. I think if we have following offset form, we can say
>>> No-alias between them.
>>>
>>> offset1 = odd_number - index
>>>
>>> offset2 = index
>>>
>>> I have implemented simple code for it and the output is as following:
>>>
>>> Alias sets for function 'test':
>>> Alias Set Tracker: 2 alias sets for 2 pointer values.
>>>    AliasSet[0x541a070, 1] must alias, Mod       Pointers: (i8*
>>> %arrayidx, 1)
>>>    AliasSet[0x541cc00, 1] must alias, Mod       Pointers: (i8*
>>> %arrayidx2, 1)
>>>
>>> How do you think about this? Is it legal for current alias analysis
>>> or not? I have attached the diff file as reference. If I missed
>>> something, please let me know.
>> The concept works. I'm not sure your patch handles all the edge cases
>> correctly, at first glance.  (If you want a full review, please post
>> on Phabricator.)
> +1
>
> In your example, we have:
>
> 3 - idx == idx => 3 == 2*idx
>
> and you've generalized this slightly to make this:
>
> (odd number) == 2*idx
>
> which makes sense. I think that we can go further looking at:
>
> n == 2*idx
>
> and, calling computeKnownBits on n and idx, then asking whether:
>
> knownZeros(n) == (knownZeros(idx) << 1) | 1 and
> knownOnes(n) == knownOnes(idx) << 1
>
> (please note the comment in aliasSameBasePointerGEPs regarding avoiding
> PR32314)
>
> also, if we have more than one array access, we can have:
>
> n - idx == m - idx
>
> then we have:
>
> n-m == 2*idx
>
> and so we can check:
>
> knownZeros(n-m) == (knownZeros(idx) << 1) | 1 and
> knownOnes(n-m) == knownOnes(idx) << 1
>
> Sadly, we don't have a good API to do the knownBits check on the
> subtraction of non-constants, but you only need the constants in your
> case, and we can leave the more-general case for future work.
>
> Thanks again,
> Hal
>
>> -Eli
>> 8

--
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] One more No-alias case on Alias analysis

Tim Northover via llvm-dev

On 06/12/2018 07:41 AM, [hidden email] wrote:

> Thanks Hal for good comment!
>
> It seems the 'computeKnownBits' does not handle non-constant values well.
>
> For example,
>
> define void @test(i32 %idx) {
> entry:
>   %sub = sub nsw i32 3, %idx
>
> It fails to get Zero and One from %idx.
>
> I agree with using 'computeKnowBits' to check odd number. If I missed
> something, please let me know.

We'll move this to the code-review thread.

 -Hal

>
> Thanks,
>
> JinGu Kang
>
>
> On 12/06/18 11:17, Hal Finkel wrote:
>> On 06/11/2018 02:33 PM, Friedman, Eli via llvm-dev wrote:
>>> On 6/11/2018 10:06 AM, [hidden email] via llvm-dev wrote:
>>>> Hello All,
>>>>
>>>> I have met one may-alias case from llvm's alias analysis. The code
>>>> snippet is as following:
>>>>
>>>> char buf[4];
>>>>
>>>> void test (int idx) {
>>>> char *a = &buf[3 - idx];
>>>> char *b = &buf[idx];
>>>> *a = 1;
>>>> *b = 2;
>>>> }
>>>>
>>>> I can see below output from alias set tracker for above code snippet.
>>>>
>>>> Alias sets for function 'test':
>>>> Alias Set Tracker: 1 alias sets for 2 pointer values.
>>>>    AliasSet[0x53d8070, 2] may alias, Mod       Pointers: (i8*
>>>> %arrayidx, 1), (i8* %arrayidx2, 1)
>>>>
>>>> As you can see on above code snippet, the 'a' and 'b' are not
>>>> aliased. I think if we have following offset form, we can say
>>>> No-alias between them.
>>>>
>>>> offset1 = odd_number - index
>>>>
>>>> offset2 = index
>>>>
>>>> I have implemented simple code for it and the output is as following:
>>>>
>>>> Alias sets for function 'test':
>>>> Alias Set Tracker: 2 alias sets for 2 pointer values.
>>>>    AliasSet[0x541a070, 1] must alias, Mod       Pointers: (i8*
>>>> %arrayidx, 1)
>>>>    AliasSet[0x541cc00, 1] must alias, Mod       Pointers: (i8*
>>>> %arrayidx2, 1)
>>>>
>>>> How do you think about this? Is it legal for current alias analysis
>>>> or not? I have attached the diff file as reference. If I missed
>>>> something, please let me know.
>>> The concept works. I'm not sure your patch handles all the edge cases
>>> correctly, at first glance.  (If you want a full review, please post
>>> on Phabricator.)
>> +1
>>
>> In your example, we have:
>>
>> 3 - idx == idx => 3 == 2*idx
>>
>> and you've generalized this slightly to make this:
>>
>> (odd number) == 2*idx
>>
>> which makes sense. I think that we can go further looking at:
>>
>> n == 2*idx
>>
>> and, calling computeKnownBits on n and idx, then asking whether:
>>
>> knownZeros(n) == (knownZeros(idx) << 1) | 1 and
>> knownOnes(n) == knownOnes(idx) << 1
>>
>> (please note the comment in aliasSameBasePointerGEPs regarding avoiding
>> PR32314)
>>
>> also, if we have more than one array access, we can have:
>>
>> n - idx == m - idx
>>
>> then we have:
>>
>> n-m == 2*idx
>>
>> and so we can check:
>>
>> knownZeros(n-m) == (knownZeros(idx) << 1) | 1 and
>> knownOnes(n-m) == knownOnes(idx) << 1
>>
>> Sadly, we don't have a good API to do the knownBits check on the
>> subtraction of non-constants, but you only need the constants in your
>> case, and we can leave the more-general case for future work.
>>
>> Thanks again,
>> Hal
>>
>>> -Eli
>>> 8
>

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