<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 14, 2016 at 4:48 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi all,<br>
<br>
It looks like the key controversial point is the bit about the extra<br>
control dependence on loads and stores[0]. Generally the consensus is<br>
that (please chime if you think otherwise) it is not reasonable to<br>
make the safety (or semantics) of a load instruction depend on the<br>
type it is loading. Introducing such a thing would involve changing<br>
the IR semantics in a fundamental way, and therefore has a high bar<br>
for acceptance.<br>
<br>
Here is a summary of the alternative solutions that were proposed here<br>
and on IRC (thanks Chandler, Andy, Eli!):<br>
<br>
1. Model loads and stores of GC references as intrinsic calls: add<br>
llvm.gc_load, llvm.gc_store intrinsics, and optimize them as loads<br>
and stores whenever appropriate and legal.<br>
<br>
2. Introduce a flag on load and stores that either<br>
a. Denotes a "gc_safety" control dependence.<br>
b. Denotes a "blackbox_safety" control dependence. In this case<br>
we will probably have some optional metadata on loads and<br>
stores to indicate that the control dependence is actually on<br>
GC safety.<br>
<br>
As a starting point, LLVM will conservatively not speculate such<br>
loads and stores; and will leave open the potential to upstream<br>
logic that will have a more precise sense of when these loads and<br>
stores are safe to speculate.<br></blockquote><div><br></div><div>I think you need to define what you mean by control dependence here. If you mean speculation, you should say speculation :)</div><div>As you describe below, it is not enough to simply not speculate them. You also are saying you don't want to change the conditions on which they execute.</div><div>That is very different from speculation.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
3. Introduce a general way to denote control dependence on loads and<br>
stores. This can be helpful to LLVM in general, and will let us<br>
basically implement a more precise version of (2).<br></blockquote><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
<br>
<br>
[0]: I may have (incorrectly) mentioned otherwise on IRC, but we need<br>
to model safety properties of stores as well, to avoid transforms<br>
like:<br>
<br>
%x = malloc() ;; known thread local<br>
if (cond_0) {<br>
store GCREF %val to %x<br>
}<br>
if (cond_1) {<br>
store i64 %val to %x<br>
}<br>
<br>
to<br>
<br>
%x = malloc() ;; known thread local<br>
if (cond_0 || cond_1) {<br>
store GCREF %val to %x ;; This "speculative" store is bad<br>
if (cond_1) {<br>
store i64 %val to %x<br>
}<br>
}<br>
</blockquote></div><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">FWIW: This raises one of the same issues we have now with may-throw, which is that, if all you have is a flag on the instruction, now you have to look at every instruction in every block to know whether a *CFG* transform is correct.</div><div class="gmail_extra"><br></div><div class="gmail_extra">That means any pass that wants to just touch the CFG can't do so without also looking at the instruction stream. It will also make a bunch of things currently O(N), O(N^2) (see the sets of patches fixing may-throw places, and extrapolate to more places).</div><div class="gmail_extra"><br></div><div class="gmail_extra">This is theoretically fixable in each pass by taking a single pass over the instruction stream and marking which blocks have these instructions, etc, and then using that info.</div><div class="gmail_extra"><br></div><div class="gmail_extra">But we shouldn't have to do that in each pass, especially if they just want to make CFG manipulations.</div><div class="gmail_extra"><br></div><div class="gmail_extra">The TL;DR I would really like to see this also made a BB level flag that says whether the block contains instructions with unknown control dependences (or really, 1 bb level flag for each attribute you introduce) .</div><div class="gmail_extra"> I don't think this is terribly difficult, and at the very least, will keep us from having to look at every instruction in the block in the common case that there is nothing in the block to worry about ;)<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Also note that these CFG transforms will also now need post-dominance info in a bunch of cases to sanely determine if they are changing the control dependence structure.</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Let me ask another question:</div><div class="gmail_extra"><br></div><div class="gmail_extra">Given</div><div class="gmail_extra"><br class=""> %x = malloc() ;; known thread local<br> if (cond_0) {<br> store GCREF %val to %x<br> }<br> if (cond_1) {<br> store i64 %val to %x<br> }<br></div><div class="gmail_extra">Assume i can prove cond0 and cond1 the same.</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">I change this to:<br> %x = malloc() ;; known thread local<br> if (cond_0) {<br> store i64 %val to %x</div><div class="gmail_extra"> store GCREF %val to %x</div><div class="gmail_extra"> }<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Is this okay to happen?</div><div class="gmail_extra"><div class="gmail_extra">Note that i did not actually change the control dependence of it by the normal definition of control dependence.</div><div class="gmail_extra"><br></div><div class="gmail_extra">But you can end up "hoisting" or "sinking" instructions by moving every other instruction :)</div><div class="gmail_extra"><br></div><div class="gmail_extra">Is that okay, or are they really barriers as well (like may throw), in which case, they probably need some real representation in control flow if you want to make most algorithms O(N) (you can get away with the bb level flags if you are willing to make some algorithms N^2 in cases where these things exist).</div><div class="gmail_extra"> </div><div class="gmail_extra"><br></div></div></div>