<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Mar 24, 2021, at 15:16, Johannes Doerfert via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta charset="UTF-8" class=""><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">On 3/24/21 9:06 AM, Clement Courbet wrote:</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">On Wed, Mar 24, 2021 at 2:20 PM Johannes Doerfert <<br class=""><a href="mailto:johannesdoerfert@gmail.com" class="">johannesdoerfert@gmail.com</a>> wrote:<br class=""><br class=""><blockquote type="cite" class="">I really like encoding more (range) information in the IR,<br class="">more thoughts inlined.<br class=""><br class="">On 3/24/21 4:14 AM, Clement Courbet via llvm-dev wrote:<br class=""><blockquote type="cite" class="">Hi everyone,<br class=""><br class="">tl;dr: I would like to teach clang to output range metadata so that LLVM<br class="">can do better alias analysis. I have a proposal as D99248<br class=""><<a href="https://reviews.llvm.org/D99248" class="">https://reviews.llvm.org/D99248</a>> (clang part) and D99247<br class=""><<a href="https://reviews.llvm.org/D99247" class="">https://reviews.llvm.org/D99247</a>> (llvm part). But there are other<br class=""></blockquote>possible<br class=""><blockquote type="cite" class="">options that I'm detailing below.<br class=""><br class="">Consider the following code, adapted from brotli<br class=""><<a href="https://en.wikipedia.org/wiki/Brotli" class="">https://en.wikipedia.org/wiki/Brotli</a>>:<br class=""><br class="">```<br class=""><br class="">struct Histogram {<br class=""><br class=""> int values[256];<br class=""><br class=""> int total;<br class=""><br class="">};<br class=""><br class="">Histogram DoIt(const int* image, int size) {<br class=""><br class=""> Histogram histogram;<br class=""><br class=""> for (int i = 0; i < size; ++i) {<br class=""><br class=""> ++histogram.values[image[i]]; // (A)<br class=""><br class=""> ++histogram.total; // (B)<br class=""><br class=""> }<br class=""><br class=""> return histogram;<br class=""><br class="">}<br class="">```<br class=""><br class="">In this code, the compiler does not know anything about the values of<br class="">images[i], so it assumes that 256 is a possible value for it. In that<br class=""></blockquote>case,<br class=""><blockquote type="cite" class="">(A) would change the value of histogram.total, so (B) has to load, add<br class=""></blockquote>one<br class=""><blockquote type="cite" class="">and store [godbolt <<a href="https://godbolt.org/z/KxE343" class="">https://godbolt.org/z/KxE343</a>>].<br class=""><br class="">Fortunately, C/C++ has a rule that it is invalid (actually, UB) to use<br class="">values to form a pointer to total and dereference it. What valid C/C++<br class=""></blockquote>code<br class=""><blockquote type="cite" class="">is allowed to do with values is:<br class=""> - Form any pointer in [values, values + 256].<br class=""> - Form and dereference any pointer in [values, values + 256)<br class=""><br class="">Note that the LLVM memory model is much laxer than that of C/C++. It has<br class=""></blockquote>no<br class=""><blockquote type="cite" class="">notion of types. In particular, given an LLVM aggregate definition:<br class=""><br class="">```<br class="">%struct.S = type { [42 x i32], i32, i32 }<br class="">```<br class=""><br class="">It is perfectly valid to use an address derived from a GEP(0,0,%i) [gep<br class="">reference] representing indexing into the [42 x i32] array to load the<br class=""></blockquote>i32<br class=""><blockquote type="cite" class="">member at index 2. It is also valid for %i to be 43 (though not 44 if an<br class="">inbound GEP is used).<br class="">So clang has to give LLVM more information about the C/C++ rules.<br class=""><br class="">*IR representation:*<br class="">LLVM has several ways of representing ranges of values:<br class=""> - *!range* metadata can be attached to integer call and load<br class=""></blockquote>instructions<br class=""><blockquote type="cite" class="">to indicate the allowed range of values of the result. LLVM's<br class=""></blockquote>ValueTracking<br class=""><blockquote type="cite" class="">provides a function for querying the range for any llvm::Variable.<br class=""> - The *llvm.assume* intrinsic takes a boolean condition that can also<br class=""></blockquote>be<br class=""><blockquote type="cite" class="">used by ValueTracking to infer range of values.<br class=""> - The *inrange* attribute of GEP can be used to indicate C-like<br class=""></blockquote>semantics<br class=""><blockquote type="cite" class="">for the structure field marked with the inrange attribute. It can only be<br class="">used for GEP constantexprs (ie.e. GEPs defined inline), but not for<br class="">standalone GEPs defining instructions. relevant discussion<br class=""><<a href="https://reviews.llvm.org/D22793?id=65626#inline-194653" class="">https://reviews.llvm.org/D22793?id=65626#inline-194653</a>>.<br class=""><br class="">Alternatives:<br class="">*(1) *Annotate each array subscript index value with a range, e.g.:<br class="">```<br class="">%i = i64 …<br class="">%ri = call i64 @llvm.annotation.i64(%index), !range !0<br class="">%gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0,<br class=""></blockquote>i32<br class=""><blockquote type="cite" class="">%ri<br class="">...<br class="">!0 = !{i64 0, i64 42}<br class="">```<br class="">*(2) *(variant of 1) relax the constraint that !range metadata can only<br class=""></blockquote>be<br class=""><blockquote type="cite" class="">set on call and load instructions, and set the !range metadata on the<br class=""></blockquote>index<br class=""><blockquote type="cite" class="">expression. We still need annotations for function parameters though:<br class="">```<br class="">%i = i64 … , !range !0<br class="">%gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0,<br class=""></blockquote>i32<br class=""><blockquote type="cite" class="">%i<br class="">...<br class="">!0 = !{i64 0, i64 42}<br class="">```<br class="">This is slightly more compact.<br class=""><br class="">*(3)* Same as (1), with llvm.assume. This feels inferior to annotations.<br class="">*(4)* Extend inrange to non-constantexprs GEPs. It is unclear how this<br class=""></blockquote>will<br class=""><blockquote type="cite" class="">interfere with optimizations.<br class=""></blockquote>I would very much like not to introduce another way to encode<br class="">assumptions other than `llvm.assume`. If you want to avoid the extra<br class="">instructions, use `llvm.assume(i1 true) ["range"(%val, %lb, %ub)]`,<br class="">which is in line with our move towards operand bundle use.<br class=""><br class=""></blockquote>Thanks, I did not know about that. I've just tried it but it appears that<br class="">tags have to be attribute names, and `!range` is not a valid attribute,<br class="">it's a metadata node. Is there a way to encode this ?<br class=""></blockquote><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">We need to get rid of that assertion. There are other non-attributes</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">to be used in assume operand bundles in the (near) future, so the this</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">work has to be done anyway.</span><br class=""></div></blockquote><br class=""></div><div><br class=""></div><div>+1 on trying to use assume, rather than adding another way. </div><div><br class=""></div><div>But are value ranges special for assumes, so that we need to handle them in a bundle? Is that just so we can easier skip ‘artificial’ assume users?</div><div><br class=""></div><div>Cheers,</div><div>Florian</div></body></html>