[LLVMdev] Strange pointer aliasing behaviour

[Eugene Toder]

I think scev-aa does not succeed on the original example, because
front ends do not put "nsw" on signed addition, so according to llvm
rules addition can overflow and i can be < 0.
Also, if original example used unsigned type (e.g. size_t, which is
very common), I don't think ir can express the fact that i is
guaranted to be >= 0.

Another line of reasoning is that if
sizeof(i)*8+log2(sizeof(_data[0])) > address_size_in_bits, overflowing
i requires going out of bounds when storing to _data[i] (because
address space can't contain objects large enough). Can this be used
for alias analysis?

Eugene

On Mon, Jun 28, 2010 at 7:46 PM, Dan Gohman <gohman at apple.com> wrote:
>
> On Jun 27, 2010, at 2:26 PM, Eugene Toder wrote:
>
>> Hi Dan,
>>
>> Are you referring to my reasoning for why _length and _data[i] do not
>> alias?
>
> No, I was referring to the discussion of C99 6.7.2.1, 6.5.6,
> 6.2.6, and so on.
>
>> I don't think this needs TBAA or any "strict" aliasing rules.
>> All that sufficient is 1) assumption about struct layout:
>> offsetof(_length) < offsetof(_data) 2) assumption that i >= 0.
>> My understanding is that 1) is guaranteed by llvm rules and 2) by C
>> rules, however I'm not sure how to express C rules in llvm IR. For
>> signed types "nsw" flag on arithmetic seems close, if I understand the
>> description of trap values.
>
> Right; this is the second of the two approaches Eli originally
> suggested. For this approach, the IR is already sufficient to
> allow the optimizer to prove that i >=0 and to subsequently prove
> that the relevant pointers don't alias.
>
> BasicAA doesn't have any logic related to proving either
> i >= 0, or that _length and _data don't alias even if
> it somehow knew i >= 0. It could be taught both of those
> things, if someone were interested.
>
> SCEV-AA does have logic related to proving that i >= 0, but
> it happens to fail in this testcase; I haven't investigated it
> in detail. It also has logic for proving that _length and _data
> don't alias if i >= 0. However, SCEV-AA is not enabled by default.
>
>> For unsigned types arithmetic is fine, but
>> we probably need "unsigned" flag in getelementptr to signal that
>> offset is treated as unsigned.
>>
>> In fact, as Takumi pointed out, if you add an extra comparison to
>> ensure 2) SCEV can already optimize the loop.
>> Or am I missing something?
>
> With that extra comparison, SCEV-AA succeeds in proving that
> i >=0, and this shows it can do everything else from there.
>
> Dan
>
>