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

[Hal Finkel via llvm-dev]

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