<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Mon, Sep 24, 2018 at 10:07 PM Chris Lattner <<a href="mailto:clattner@nondot.org">clattner@nondot.org</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">> On Sep 24, 2018, at 9:54 PM, Chris Lattner <<a href="mailto:clattner@nondot.org" target="_blank">clattner@nondot.org</a>> wrote:<br>
>> I think we have consensus that we should go forward with this. Would anyone mind formally stamping it in phab? So far everyone understandably has said "makes sense to me, but I don't consider myself to have authority to stamp this.”<br>
> <br>
> Hi Reid,<br>
> <br>
> I have significant concerns with this patch. I’d really appreciate it if you could address the discussion feedback here before just plowing forward with such an invasive change to the core IR.<br></blockquote><div><br></div><div>Sorry for that, I'm at a conference and I'm trying to push this along in the background without doing any real work on it. I've convinced myself it's the right change, and that's enough to make me impatient.</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">
> Have you done any memory use analysis or compile time impact analysis of this change? Have you consider the algorithm I mentioned? I am not motivated by your rationale above, and I think it will be a huge step forward and effectively define away the problem.<br>
<br>
To be clear, I’m a superfan of your work and agree that “automatic invalidation and simplification” are good goals. I’d just love to see more analysis of the situation before burning space on this extra field.<br>
<br>
For example, it would be very interesting to see what the typical distribution of local dominance queries actually are. You could take your patch here and have it instrument the “Instruction::comesBefore” method to log the distance between the instruction numbers to a file and generate a histogram of them. My bet is that the vast vast vast majority of them will be small (and I’d guess a HUGE number of them have a distance of +1/-1, whose query can be resolved without computing a numbering in the first place).<br>
<br>
Can you do that experiment and report back, e.g. on the SemaChecking.cpp testcase?<br></blockquote><div><br></div><div>Fair enough. I made a patch to do that, and uploaded it here: <a href="https://reviews.llvm.org/D52510">https://reviews.llvm.org/D52510</a></div><div>I put it into a spreadsheet and made a histogram here: <a href="https://goo.gl/AMLBt7">https://goo.gl/AMLBt7</a></div><div>I grouped the typical query distances into natural log buckets, and the table is small enough to paste here:</div><div><br></div><div><div>distance<span style="white-space:pre"> </span>freq</div><div>1-2<span style="white-space:pre"> </span>3707</div><div>2-7<span style="white-space:pre"> </span>5622</div><div>7-20<span style="white-space:pre"> </span>25764</div><div>20-54<span style="white-space:pre"> </span>1726</div><div>54-148<span style="white-space:pre"> </span>2052</div><div>148-403<span style="white-space:pre"> </span>4462</div><div>403-1096<span style="white-space:pre"> </span>8423</div><div>1096-2980<span style="white-space:pre"> </span>20487</div><div>2980-8103<span style="white-space:pre"> </span>34930</div><div>8103-22026<span style="white-space:pre"> </span>63759</div><div>22026-59874<span style="white-space:pre"> </span>41729</div></div><div><br>I think the table shows that local dominance queries are, at least for SemaChecking.cpp, not clustered around small distances. The average query is somewhere out around 11,000 instructions apart.</div><div><br></div><div>One thing to note is that the code in question isn't using DominatorTree::dominates. That was identified as a hotspot, so it's using OrderedBasicBlock, but it's not caching it at a high enough level to avoid quadratic behavior. Raising it up isn't easy, hence this patch.</div><div><br></div><div>Sanjoy also wanted more data and suggested that I re-run the max RSS during full LTO of llc experiment that I did when I removed the vptr from Value. I went ahead and did that on the review, but it's not on the dev list, so it may not have enough visibility. I found that the<span style="color:rgb(0,0,0);font-family:"Segoe UI","Segoe UI Emoji","Segoe UI Symbol",Lato,"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:13px"> </span><span style="color:rgb(0,0,0);font-family:"Segoe UI","Segoe UI Emoji","Segoe UI Symbol",Lato,"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:13px">max RSS before the patch was 4816464 kb, and after, 4867836 kb. That's an increase of 1.06%, or in absolute terms, ~50MB of memory spent on instruction positions during full LTO of llc.</span></div><div><span style="color:rgb(0,0,0);font-family:"Segoe UI","Segoe UI Emoji","Segoe UI Symbol",Lato,"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:13px"><br></span></div><div><span style="color:rgb(0,0,0);font-family:"Segoe UI","Segoe UI Emoji","Segoe UI Symbol",Lato,"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:13px">I think Sanjoy's bit-stealing suggestion is a worthwhile alternative to growing Instruction, but I really think we should analyze it from the position of, is the complexity of bit-stealing from Parent worth it to shrink Instruction?</span></div><div><span style="color:rgb(0,0,0);font-family:"Segoe UI","Segoe UI Emoji","Segoe UI Symbol",Lato,"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:13px"><br></span></div><div><span style="color:rgb(0,0,0);font-family:"Segoe UI","Segoe UI Emoji","Segoe UI Symbol",Lato,"Helvetica Neue",Helvetica,Arial,sans-serif;font-size:13px">Anyway, hopefully this looks compelling. I'll put some of it in the patch description before landing.</span></div></div></div></div></div></div>