[llvm-dev] InstCombine GEP

[Nuno Lopes via llvm-dev]

>>> Also, BasicAA has the following rule, with constants c1 and c2, and 
>>> arbitrary values x, y:
>>> a[x][c1] no-alias a[y][c2] if:
>>> the distance between c1 and c2 is sufficient to guarantee that the 
>>> accesses will be disjoint due to ending up in different array slots.
>>> For this rule it's important to know what's the size of each array 
>>> element. This information is lost if GEPs are flattened.
>>
>> Do you mean to say that in LLVM IR we will conclude ptr0 and ptr1 don't 
>> alias:
>>
>>   int a[4][4];
>>   ptr0 = &a[x][3];
>>   ptr1 = &a[y][7];
>>
>> If so, that doesn't match my understanding -- I was under the
>> impression that in LLVM IR x = 2, y = 1 will give us must-alias
>> between ptr0 and ptr1.
>
> No, in this case it won't conclude no-alias, since 3 % 4 == 7 % 4.  LLVM 
> is not that aggressive in exploiting UB.  Anyway, concluding no-alias here 
> was only possible if the GEP index had the inrange attribute.
>
> The example is more like this:
>   int a[4][5];
>   p = &a[x][0];
>   q = &a[y][1];
>
> With access sizes sp, sq, respectively:
> If the access size through p ends before q (q >= sp) and the access 
> through q doesn't go beyond the array limit (sq <= 5*sizeof(int) - 
> 1*sizeof(int)), then it's no-alias.
>
> By flattening a GEP, you lose the information of the size of the each of 
> array/struct constituents. Hence this proof rule doesn't apply and you 
> would get may-alias for the example above.

Let me rephrase this last bit: I agree with you that if the GEP has no 
inrage attributes then there's no logical loss of information: a GEP is 
simply a bunch of arithmetic operations and nothing else can be inferred 
from the types.
However, the BasicAA code that I mentioned above wouldn't kick in (as far as 
I understand).  It would be possible to extend it to handle the flattened 
GEP case, though.  There's already a bit of code that analyses linear 
expressions, but I don't think it go as far as needed to handle the case 
above.

Nuno