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

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

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

On 06/12/2018 07:41 AM, jingu at codeplay.com 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, 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