[llvm-dev] TBAA for subset of a loaded value (original) (raw)

Hal Finkel via llvm-dev llvm-dev at lists.llvm.org
Mon Apr 10 19:01:30 PDT 2017

On 04/10/2017 08:44 PM, Sanjoy Das wrote:

Hi Keno,

On April 10, 2017 at 6:02:38 PM, Keno Fischer via llvm-dev (llvm-dev at lists.llvm.org) wrote: I'm interested in what we can do about TBAA for loads that the compiler inserts when optimizing loads into smaller loads (e.g. what SROA does). I'm gonna set the stage by using a small C snippet, because I think C has the best-understood implementation of TBAA among the folks on the list. However, I was unable to actually come up with an example where this inhibits optimizations coming from C code. I myself have this problem as a real problem in a non-C frontend, which allows for more stringent AA. With that in mind, consider

void foo(unsigned int *data, int128t *value) { for (int i = 1; i < 100; ++i) {_ _data[i] += (int)*value;_ _}_ _}_ _This will get lowered to something like (pseudo llvm IR here)_ _for.body:_ _%l = load i128, i128* %value, !tbaa !1_ _%t = trunc %l to i32_ _%gep = ..._ _%old = load i32, i32* %gep, !tbaa !2_ _%new = add i32 %t, %old_ _store i32 %new, %gep, !tbaa !2_ _Now, it seems like a perfectly reasonable optimization for the_ _optimizer (though it currently doesn't do that), to fold %l and %t to:_ _%b = bitcast i128* %value to i32*_ _%t = load i32, i32 *%b_ _However, what can we say about the tbaa of %t at this point? With the_ _current semantics, I'm not sure we're allowed to say anything (in this_ _case maybe we're still allowed to say !tbaa !1, but consider what_ _happens for say *value>>32, which we could fold to gep+load). However, that would mean that we lose the information that %value does not alias %data, so e.g. we can't perform LICM anymore. Now, as I said, I couldn't actually get this to be a problem, because C only uses scalar TBAA for rather small values. However, in my frontend, for certain memory access I know that there are no interior pointer, so I emit scalar TBAA for a larger struct. Then SROA comes along and splits it, but it drops the TBAA. So the main points of discussion are: 1) Is there anything we can say about a smaller load created from a TBAA annotated larger load in the current semantics? 2) If not, what is the best way to retain this information. E.g. should we have a TBAA node that says "this access was n bytes into a scalar TBAA of type !1"? I'm not sure if we can do something with the TBAA metadata we have today, but I think there is hope if we're willing to change our TBAA metadata representation. In particular, if we allow access types[0] of TBAA tags to be struct types then we can probably solve the problem. In your case, we'd start with %l tagged with a scalar access type, !i128ty: %l = load i128, i128* %value, !tbaa !{!i128ty, !i128ty, i64 0} %t = trunc %l to i32 which after narrowing would be %l = load i32, i32* %value, !tbaa !{!i128ty, !i32ty, i64 0} %t = trunc %l to i32 and we'd also change !i128ty from a scalar type to a struct type, containing a !i32ty at the appropriate offset. Of course, the loads and stores which mention !i128ty as their access type now have a struct type as their access type, which is why we have to make the generalization I mentioned. [0]: http://llvm.org/docs/LangRef.html#semantics'

As I mentioned a few moments ago, I think we can just propagate the metadata. One thing which it worth pointing out is that, when TBAA checks an access, it does not actually check the access size (our struct path metadata has offsets in it, but we don't really use the sizes in conjunction with those, we're just checking for an offset match up the node hierarchy).

-Hal

-- Sanjoy

I would very much appreciate any guidance on the right approach to this (perfectly willing and planning to code this up myself - but would appreciate discussion on direction). Thanks, Keno

LLVM Developers mailing list llvm-dev at lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory

More information about the llvm-dev mailing list