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

[Hal Finkel via llvm-dev]

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