llvm dev - Jun 2018 - One more No-alias case on Alias analysis

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


-------------- next part --------------
A non-text attachment was scrubbed...
Name: alias.diff
Type: text/x-patch
Size: 2215 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180611/156e7c79/attachment.bin>

Oops, there is a typo on diff file. getLoBits(0) -->getLoBits(1)

On 11 Jun 2018, 18:06, at 18:06, "jingu at codeplay.com via llvm-dev"
<llvm-dev at lists.llvm.org> 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
>llvm-dev at lists.llvm.org
>http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180611/39202bbf/attachment.html>

On 6/11/2018 10:06 AM, jingu at codeplay.com 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

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, jingu at codeplay.com 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180612/77d93ba5/attachment.html>

On 06/11/2018 02:33 PM, Friedman, Eli via llvm-dev
wrote:
> On 6/11/2018 10:06 AM, jingu at codeplay.com 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