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

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