[LLVMdev] Strange pointer aliasing behaviour

[Dan Gohman]

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