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
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 > >
On Jun 28, 2010, at 3:19 PM, Eugene Toder wrote:> 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.Actually, the front-end does put nsw there. The nsw gets lost during optimization though. And even when nsw is re-introduced manually, scev-aa loses track of it. These things are theoretically fixable though. scev-aa is still somewhat experimental; it's using ScalarEvolution in a relatively unusual manner, and ScalarEvolution hasn't been specifically tuned this way.> 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.Right; LLVM IR currently lacks a away to represent arbitrary value constraints like that. An odd possibility though is to observe that i is always less than some value on each iteration, and it's only stepping by 1, so it can never wrap.> 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?Yes, something like this sounds theoretically possible. Dan