<div class="gmail_quote">On Fri, Oct 21, 2011 at 6:17 PM, Andrew Trick <span dir="ltr"><<a href="mailto:atrick@apple.com">atrick@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div style="word-wrap:break-word"><div><div class="im"><div>On Oct 20, 2011, at 11:53 PM, Chandler Carruth wrote:</div><blockquote type="cite"><div class="gmail_quote">On Thu, Oct 20, 2011 at 10:53 AM, Jakob Stoklund Olesen <span dir="ltr"><<a href="mailto:stoklund@2pi.dk" target="_blank">stoklund@2pi.dk</a>></span> wrote:<blockquote class="gmail_quote" style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-color:rgb(204, 204, 204);border-left-style:solid;padding-left:1ex">
<div>
On Oct 20, 2011, at 9:56 AM, Chandler Carruth wrote:<br>
<br>
> A new patch is attached that is *much* less of a rough draft. Sorry for any confusion due to the early state of the patch.<br>
<br>
</div>Thanks, Chandler. This is great stuff.<br>
<div><br>
> Still, I never intended this to be on-by-default at first. This is a starting point, that I hope can be improved into something that is on-by-default eventually, but I'll be the first to say it's almost certainly not ready for that just yet.<br>
<br>
</div>I would like to see this go in ASAP under a flag. I prefer to see development as commits rather than a series of updated patches.</blockquote></div></blockquote></div>...<br><blockquote type="cite"><div class="gmail_quote">
<div class="im"><div>Awesome, same way I feel. Checked in as r142641. I've got some generic cleanup I'll go ahead and commit to it over the next few days.</div></div><div class="im"><div>Done, and in progress. SHould have the loop alignment stuff cloned right away, and then i'll start looking at the loop structure issues. I'll probably have some questions for you and/or andy about exactly how that should work, whether CodePlacementOpt is doing the right thing, etc.</div>
</div></div>
</blockquote></div><br><div><div>Your work looks good and there's talk of making this the default</div><div>layout pass. So let's figure out the goals and requirements. We agree</div><div>that preserving "structure" of the CFG is important in the absence of</div>
<div>profile information to the contrary. This is important for performance</div><div>stability in the presence of imperfect profile data and unbiased</div><div>branches. But it's also important for the sanity of fellow compiler</div>
<div>engineers and anyone debugging the disassembly. We can define</div><div>structure very simply by saying that we want contiguous loops and</div><div>topologically ordered regions within a loop. Those are not the</div>
<div>strongest constraints. We could still end up with strangely shuffled</div><div>code, but they are easy constraints to define.</div><div><br></div><div>Once you decide to break these constraints, you have effectively</div>
<div>designated the offending paths as "cold". It's up to you how to</div><div>decide which paths are cold. You'll need some threshold based on</div><div>confidence in the profile, and we can measure the effectiveness of</div>
<div>your heuristics and add more over time. The key point is that the</div><div>layout algorithm needs to make an explicit binary decision at some</div><div>point to violate the natural structure of the CFG.</div><div><br>
</div><div>I don't care much about how you layout the cold chains as long as they</div><div>are not interleaved with the rest of the code, thus breaking the</div><div>topological ordering and forcing extra branches. In practice, this</div>
<div>means they get their own little Siberia after the function return,</div><div>effectively splitting the function into two sections. However, the</div><div>notion of "coldness" is really relative to the current loop head. So</div>
<div>you may layout a nice contiguous, topologically ordered inner loop,</div><div>then determine the whole thing is cold relative to its outer loop, so</div><div>send the whole thing packing to Siberia. That's exactly what we</div>
<div>want. The loop itself is sane, but doesn't get in the way of hotter</div><div>enclosing code.</div><div><br></div><div>Even within the constraints imposed by CFG structure, you can reduce</div><div>the likelihood of taken branches. Here you can employ any</div>
<div>profile-based or static heuristics with lower confidence, because the</div><div>resulting layout will be reasonably good either way. This will still</div><div>do a great job in the absence of accurate profile information, builtin</div>
<div>expect, or very strong static heuristics (e.g. landing pads are cold).</div><div><br></div><div>This is where the algorithm gets interesting and you can be creative,</div><div>but I'll give you a rough idea so we're on the same page:</div>
<div><br></div><div>1) Visit each loop independently inside-out.</div><div><br></div><div>2) Construct chains of blocks within the loop. Here the "entry" chain</div><div> is the loop header, or function entry. You can probably represent</div>
<div> each already laid out inner loop as a single chain. The graph of</div><div> chains within a loop is *acyclic* except for irreducible control</div><div> flow, which doesn't have any structure to preserve anyway. There's</div>
<div> no need to compute SCCs.</div><div><br></div><div>3) Stop constructing the chain at a CFG merge. Chaining past a merge</div><div> would immediately violate topological ordering, which is only ok if</div><div> other predecessors of the merge have been designated "cold".</div>
<div><br></div><div>4) Splice the chains together, preserving topological order. Assigning</div><div> each block to a DFS reverse-post-order number provides a nice</div><div> ordering that is easy to compare or sort.</div>
</div></div></blockquote><div><br></div><div>FYI, I'm still working on the details, and the code is a complete hack, but I have a big chunk of this working now. =] The more precise strategy I implemented follows your suggestion very closely. I've got lots more ideas to layer on top of this, but this is my first stab at providing a better underpinning.</div>
<div><br></div><div>First, it walks all loops in the function from the inside out just as you describe. =] Really like this, it's a very nice model to use.</div><div><br></div><div>For each loop, after having walked all sub-loops, it walks forward across all the blocks in the loop. For each block not part of a chain, it creates a single-block chain. If the block has more than one predecessor (I think this is what you were after w/ a "merge point"?), we're done. If the block is the start of the chain it belongs to, and if it is the most likely of the in-loop successors of the previous block, and that previous block is the tail of its chain, we merge its chain to the previous block's chain. This should only form chains which are valid in the existing topological ordering within a loop, and don't cross loop boundaries or cross incoming branches.</div>
<div><br></div><div>Then we traverse the BB graph in RPO, and for each block look up its chain. The first time we encounter a chain, we splice it into the function.</div><div><br></div><div>I think this satisfies your desire to preserve the structural components of the CFG? If not, I'd love to understand where I've deviated / what I've misunderstood.</div>
<div><br></div><div>It already makes some minimal use of the probabilities to select which topology-preserving fall-through options to prefer. I'm also going to tie-break with the existing layout. I've not started to really integrate it with probabilities though, I wanted to get something that fit the constraint model you're looking for first, and had clean traversal semantics.</div>
<div><br></div><div>I'll clean the patch up and mail it out tomorrow. The implementation gets tremendously simpler by A) using the loop info, and B) exclusively walking forward over the blocks. The first simplified the traversal greatly, and the second made it easy to just store pointers to basic blocks for the chains rather than moving blocks around in the function itself. That gets rid of a bunch of other code, and the most bug-prone of the other code. So all in all, I like where this is going.</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div style="word-wrap:break-word"><div><div><br></div><div>Let me give you a little example to think about:</div>
<div><br></div><div>A:</div><div> br B(80%), C(20%)</div><div>B:</div><div> br D</div><div>C:</div><div> br D(90%), E(10%)</div><div>D:</div><div> br F</div><div>E:</div><div> br F</div><div>F:</div><div> ret</div><div>
<br></div><div>This is a fine topological sort but bad layout based on expected</div><div>branch probability (even with low confidence in the profile).</div><div><br></div><div>The only good layout that preserves topological ordering is:</div>
<div>A, B, C, E, D, F</div><div><br></div><div>.8 * 1 branch + .18 * 2 branches + .02 * 2 branches</div><div><br></div><div>This approach likely covers the existing functionality of</div><div>CodePlacement, which attempts to keep loops contiguous.</div>
<div>You will probably need to do the loop tail adjustment that</div><div>CodePlacement currently does as a special case.</div><div>(Shift the tail of the loop to precede its header, resulting in</div><div>a fall-through loop test.)</div>
<div><br></div><div>We can discuss the design more, but you may want to think about it and</div><div>come with your own design first.</div><div><br></div><div>Finally, we need some way to validate the design and verify the</div>
<div>implementation. Weighted statistics will be very useful here, similar</div><div>to those that Jakob used in the register allocator. For example:</div><div><br></div><div>For each nonadjacent edge:</div><div> TakenBranchFrequency += frequency(Edge)</div>
<div><br></div><div>This metric will prefer the most "extreme" layout because it assumes</div><div>perfect accuracy of block frequencies. It would be nice to look at the</div><div>same metric computed from skewed branch probabilities to see how</div>
<div>sensitive it is to small shifts in branch behavior.</div><div><br></div><div>Taken branch frequency is the most obvious, but doesn't completely</div><div>capture locality. You could also measure distance jumped fairly</div>
<div>easily, also weighted by edge frequency.</div><div><br></div><div>It might be useful to gather these stats as late as possible to take</div><div>into consideration the final impact of layout, including the effect on</div>
<div>any later passes.</div></div><div><br></div><div>-Andy</div></div></blockquote></div><br>