<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Mar 24, 2021 at 2:20 PM Johannes Doerfert <<a href="mailto:johannesdoerfert@gmail.com" target="_blank">johannesdoerfert@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I really like encoding more (range) information in the IR,<br>
more thoughts inlined.<br>
<br>
On 3/24/21 4:14 AM, Clement Courbet via llvm-dev wrote:<br>
> Hi everyone,<br>
><br>
> tl;dr: I would like to teach clang to output range metadata so that LLVM<br>
> can do better alias analysis. I have a proposal as D99248<br>
> <<a href="https://reviews.llvm.org/D99248" rel="noreferrer" target="_blank">https://reviews.llvm.org/D99248</a>> (clang part) and D99247<br>
> <<a href="https://reviews.llvm.org/D99247" rel="noreferrer" target="_blank">https://reviews.llvm.org/D99247</a>> (llvm part). But there are other possible<br>
> options that I'm detailing below.<br>
><br>
> Consider the following code, adapted from brotli<br>
> <<a href="https://en.wikipedia.org/wiki/Brotli" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/Brotli</a>>:<br>
><br>
> ```<br>
><br>
> struct Histogram {<br>
><br>
> int values[256];<br>
><br>
> int total;<br>
><br>
> };<br>
><br>
> Histogram DoIt(const int* image, int size) {<br>
><br>
> Histogram histogram;<br>
><br>
> for (int i = 0; i < size; ++i) {<br>
><br>
> ++histogram.values[image[i]]; // (A)<br>
><br>
> ++histogram.total; // (B)<br>
><br>
> }<br>
><br>
> return histogram;<br>
><br>
> }<br>
> ```<br>
><br>
> In this code, the compiler does not know anything about the values of<br>
> images[i], so it assumes that 256 is a possible value for it. In that case,<br>
> (A) would change the value of histogram.total, so (B) has to load, add one<br>
> and store [godbolt <<a href="https://godbolt.org/z/KxE343" rel="noreferrer" target="_blank">https://godbolt.org/z/KxE343</a>>].<br>
><br>
> Fortunately, C/C++ has a rule that it is invalid (actually, UB) to use<br>
> values to form a pointer to total and dereference it. What valid C/C++ code<br>
> is allowed to do with values is:<br>
> - Form any pointer in [values, values + 256].<br>
> - Form and dereference any pointer in [values, values + 256)<br>
><br>
> Note that the LLVM memory model is much laxer than that of C/C++. It has no<br>
> notion of types. In particular, given an LLVM aggregate definition:<br>
><br>
> ```<br>
> %struct.S = type { [42 x i32], i32, i32 }<br>
> ```<br>
><br>
> It is perfectly valid to use an address derived from a GEP(0,0,%i) [gep<br>
> reference] representing indexing into the [42 x i32] array to load the i32<br>
> member at index 2. It is also valid for %i to be 43 (though not 44 if an<br>
> inbound GEP is used).<br>
> So clang has to give LLVM more information about the C/C++ rules.<br>
><br>
> *IR representation:*<br>
> LLVM has several ways of representing ranges of values:<br>
> - *!range* metadata can be attached to integer call and load instructions<br>
> to indicate the allowed range of values of the result. LLVM's ValueTracking<br>
> provides a function for querying the range for any llvm::Variable.<br>
> - The *llvm.assume* intrinsic takes a boolean condition that can also be<br>
> used by ValueTracking to infer range of values.<br>
> - The *inrange* attribute of GEP can be used to indicate C-like semantics<br>
> for the structure field marked with the inrange attribute. It can only be<br>
> used for GEP constantexprs (ie.e. GEPs defined inline), but not for<br>
> standalone GEPs defining instructions. relevant discussion<br>
> <<a href="https://reviews.llvm.org/D22793?id=65626#inline-194653" rel="noreferrer" target="_blank">https://reviews.llvm.org/D22793?id=65626#inline-194653</a>>.<br>
><br>
> Alternatives:<br>
> *(1) *Annotate each array subscript index value with a range, e.g.:<br>
> ```<br>
> %i = i64 …<br>
> %ri = call i64 @llvm.annotation.i64(%index), !range !0<br>
> %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0, i32<br>
> %ri<br>
> ...<br>
> !0 = !{i64 0, i64 42}<br>
> ```<br>
> *(2) *(variant of 1) relax the constraint that !range metadata can only be<br>
> set on call and load instructions, and set the !range metadata on the index<br>
> expression. We still need annotations for function parameters though:<br>
> ```<br>
> %i = i64 … , !range !0<br>
> %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0, i32<br>
> %i<br>
> ...<br>
> !0 = !{i64 0, i64 42}<br>
> ```<br>
> This is slightly more compact.<br>
><br>
> *(3)* Same as (1), with llvm.assume. This feels inferior to annotations.<br>
> *(4)* Extend inrange to non-constantexprs GEPs. It is unclear how this will<br>
> interfere with optimizations.<br>
<br>
I would very much like not to introduce another way to encode<br>
assumptions other than `llvm.assume`. If you want to avoid the extra<br>
instructions, use `llvm.assume(i1 true) ["range"(%val, %lb, %ub)]`,<br>
which is in line with our move towards operand bundle use.<br></blockquote><div><br></div><div>Thanks, I did not know about that. I've just tried it but it appears that tags have to be attribute names, and `!range` is not a valid attribute, it's a metadata node. Is there a way to encode this ?</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
SCEV should be thought about this (as well), unsure what the problem<br>
is you describe below. If BasicAA needs to know, sure.<br></blockquote><div><br></div><div>scev-aa already knows how to use range information. If we add a !range metadata in clang right now and use SCEV, there is nothing to do on the LLVM side. My point was that scev-aa is not enabled in the default pipeline, so we might as well teach BasicAA about this cheap case.</div><div><br></div><div>Actually I think it makes sense to teach BasicAA about range information anyway (D99247) given that it could already be useful in cases like:</div><div><br></div><div>```</div><div><div><div style="background-color:rgb(255,255,254);font-family:"Consolas, ""><div style="color:rgb(0,0,0)"><span style="color:rgb(0,0,255)">define</span> <span style="color:rgb(0,128,128)">dso_local</span> <span style="color:rgb(0,128,128)">void</span> <span style="color:rgb(0,128,128)">@DoIt</span>(<span style="color:rgb(0,128,128)">%struct.Histogram</span>* <span style="color:rgb(0,128,128)">noalias</span> <span style="color:rgb(0,128,128)">nocapture</span> <span style="color:rgb(0,128,128)">sret</span>(<span style="color:rgb(0,128,128)">%struct.Histogram</span>) <span style="color:rgb(0,128,128)">align</span> <span style="color:rgb(9,134,88)">4</span> <span style="color:rgb(205,49,49)">%</span><span style="color:rgb(9,134,88)">0</span>, <span style="color:rgb(0,128,128)">i32</span> <span style="color:rgb(205,49,49)">%</span><span style="color:rgb(9,134,88)">1</span>, <b><span style="color:rgb(0,128,128)">i8</span> <span style="color:rgb(0,128,128)">zeroext</span> <span style="color:rgb(205,49,49)">%</span><span style="color:rgb(9,134,88)">2</span></b>) <span style="color:rgb(0,128,128)">local_unnamed_addr</span> <span style="color:rgb(9,134,88)">#0</span> {</div><div><font color="#cd3131">...</font></div><div style="color:rgb(0,0,0)"><b><span style="color:rgb(205,49,49)">%6</span> <span style="color:rgb(205,49,49)">=</span> <span style="color:rgb(0,0,255)">zext</span> <span style="color:rgb(0,128,128)">i8</span> <span style="color:rgb(205,49,49)">%</span><span style="color:rgb(9,134,88)">2</span> <span style="color:rgb(0,128,128)">to</span> <span style="color:rgb(0,128,128)">i64</span></b></div><div style="color:rgb(0,0,0)"><span style="color:rgb(205,49,49)">%7</span> <span style="color:rgb(205,49,49)">=</span> <span style="color:rgb(0,0,255)">getelementptr</span> <span style="color:rgb(0,128,128)">inbounds</span> <span style="color:rgb(0,128,128)">%struct.Histogram</span>, <span style="color:rgb(0,128,128)">%struct.Histogram</span>* <span style="color:rgb(205,49,49)">%</span><span style="color:rgb(9,134,88)">0</span>, <span style="color:rgb(0,128,128)">i64</span> <span style="color:rgb(9,134,88)">0</span>, <span style="color:rgb(0,128,128)">i32</span> <span style="color:rgb(9,134,88)">0</span>, <b><span style="color:rgb(0,128,128)">i64</span> <span style="color:rgb(205,49,49)">%</span><span style="color:rgb(9,134,88)">6</span></b></div><div style="color:rgb(0,0,0)"><span style="color:rgb(9,134,88)">```</span></div></div></div><div><br></div></div><div>Where ValueTracking could easily deduce that %6 is in [0,255].</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
~ Johannes<br>
<br>
<br>
><br>
> *On the clang side*:<br>
> The clang part is quite trivial as the infrastructure is already in place<br>
> to emit dynamic ubsan guards: D99248 <<a href="https://reviews.llvm.org/D99248" rel="noreferrer" target="_blank">https://reviews.llvm.org/D99248</a>><br>
><br>
> *On the LLVM Side:*<br>
> Alternatives:<br>
> *(A)* - (annotation or assume options) Simply enable scev-aa which knows<br>
> how to handle value ranges in general. IIUC it's not enabled in clang<br>
> because it has issues with invalidation when code changes, and is therefore<br>
> not cacheable. This makes it too slow to be practical.<br>
> *(B) *- (annotation or assume options) Teach BasicAA to honor !range<br>
> metadata (D99247 <<a href="https://reviews.llvm.org/D99247" rel="noreferrer" target="_blank">https://reviews.llvm.org/D99247</a>>)<br>
> *(C)* - (inrange option) Teach BasicAA to honor inrange attributes of GEP.<br>
><br>
> I was leaning towards (1) and (B) because:<br>
> - BasicAA already has basic support for value range analysis<br>
> (zero/nonzero), this is a small and natural extension.<br>
> - The BasicAA improvement already benefits some existing code (as<br>
> evidenced by the test changes in D99247 <<a href="https://reviews.llvm.org/D99247" rel="noreferrer" target="_blank">https://reviews.llvm.org/D99247</a>>)<br>
> - Using range metadata rather than the `inrange` attribute means that<br>
> BasicAA will automatically benefit from improvements in value tracking in<br>
> the future.<br>
><br>
> Opinions ?<br>
><br>
><br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
> <a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div></div>