Thanks for all of the comments Andy and Jakob. 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.<div><br></div><div>Also, many many thanks to Jakob for his explanation of how the branches between MBBs should be handled, and Andy, Jim, and Eric who helped answer my questions on IRC when I ran into stumbling blocks. Also, Nick, who shoulder surfed and helped with a lot of the tricky debugging. The previous patch had some... very annoying to track down bugs. =]<br>
<div><br></div><div>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.</div>
<div><br></div><div>I'm more hopeful that we can delete the existing block placement pass, and direct anyone interested in profile file guided stuff to write a simple pass to load profiles into metadata. I suspect this pass is already superior to that one.</div>
<div><br></div><div>Responses to some comments inline:</div><div><br><div class="gmail_quote">On Wed, Oct 19, 2011 at 6:48 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 class="im">On Oct 19, 2011, at 7:56 AM, Jakob Stoklund Olesen wrote:<br>
</div><div class="im">>> This is still *very* much a rough draft, but it's probably better to review that the previous patch. One big caveat, I know I have an iteration bug in here somewhere that is inf-looping. Just ran out of steam debugging it, will pick it back up again later today to shake it out.<br>

><br>
</div><div class="im">> Some random notes:<br>
><br>
> - Please add a description of the algorithm.<br></div></blockquote><div><br></div><div>There is more described now in various comments, but I'm going to work on an overview in the file comments. Not done yet, but wanted to get it back out for review in a more polished state.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">
> - Please add a comment to the BlockChain class.<br></div></blockquote><div><br></div><div>Done.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">
> - Use a separate anonymous namespace per class, and don't indent for the namespace.<br></div></blockquote><div><br></div><div>Done.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">
><br>
</div>...<br>
<div class="im">> Note that MachineFunction::iterator decays into an MBB pointer, so you can say FI->canFallThrough() and AnalyzeBranch(*FI...)<br></div></blockquote><div><br></div><div>I'm aware, but there were a few weird places where it didn't happen, and 'From' seemed like a more readable name anyways... Lemme know if you'd really rather I use the iterator everywhere.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">
><br>
> +      WeightedEdge WE = { BaseFrequency * MBPI->getEdgeProbability(From, To),<br>
><br>
> Did we add API for this computation? We intended to add a function that computes this and saturates on overflow etc.<br>
<br>
</div>Overflow is handled transparently in the overloaded BlockFrequency::operator*(BranchProbability). But you could use the existing API anyway by adding a helper to MachineBlockFrequencyInfo calling BlockFrequencyImpl::getEdgeFreq(Src,Dst).<br>
</blockquote><div><br></div><div>Yea, this should be handled by the BlockFrequency object correctly here, but if you'd rather see the helper I can add that. Was just keeping this patch more focused on the pass.</div><div>
<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im"><br>
>> Still, for the test cases that don't tickle the iteration bug, it generates beautiful, well laid out code. =]<br>
><br>
> I am sure others have strong opinions about the algorithm ;-)<br>
<br>
</div>I may be one of those others ;-). Although handling SCCs (loops) probably saves Chandler's design from going too far off the rails. I don't remember that being in the published algorithm.<br></blockquote><div>
<br></div><div>It definitely isn't. The published algorithm is very hand-wave-y about exactly how you select between chains when there isn't an obvious ordering.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<div class="im">> I would like to see a more explicit handling of loop layout. There is a tradeoff between entering the loop with a branch, and having the exit block last. It is not clear to me that this algorithm handles that properly.<br>
</div></blockquote><div><br></div><div>Keep in mind that the SCCs are across block *chains*. Most of the loops I saw formed a single chain with back edges, and so would be laid out exactly as they came into this pass, modulo fallthrough branches that for some reason we have probability information that says aren't likely to be taken. That said, I haven't done a thorough investigation of this... See below...</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">
<br>
</div>How do you ensure that BlockChains start at loop headers?<br>
<br>
How do you ensure that loop exits are laid out following the loop body, especially in the presence of critical edges?<br></blockquote><div><br></div><div>These are really interesting questions. I'm not sure how to answer them. Is this something we could continue to iterate on? Maybe you could point me at how to dig into these issues?</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>
Why not layout blocks according to MachineLoopInfo? The SCC abstraction seems overly generic and unnecessary.<br></blockquote><div><br></div><div>I'm not sure -- the SCCs here are often at a much coarser granualarity than those in the MBB graph. If anything, it might be good to use MachineLoopInfo to force loops into a single pre-laid-out chain; but I haven't looked at that pass yet. I'm interested in adding this kind of special and careful logic to the pass though, and making it much more loop-structure-aware.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">When you merge chains, why don't you delete the edge between the chains?<br></blockquote><div><br></div>
<div>No good reason. The edges were a wart on the entire design. They're gone now, and we just use the BB -> successor list -> block-to-chain mapping sequence to deduce edges when needed.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Why do you run profile guided block layout after the existing CodePlacementOpt? Shouldn't it be the other way around so that CodePlacementOpt can cleanup loops, which BlockPlacement2 doesn't handle well?</blockquote>
<div><br></div><div>Yep, I just slapped it in there for testing. I've put it immediately before the CodePlacementOpt pass, but I know very little about the other passes. Let me know if there is a better home for it.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> I think the answer is that BlockPlacement2 actually depends on loops being laid out sensibly before running, but that needs to be explained.<br>
</blockquote><div><br></div><div>Essentially, yes. How should we document it? Does that change if we teach it to explicitly use some of the loop analysis passes?</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<div class="im">> Be careful about placing too much trust in the behavior of branch probabilities. They go out of whack when they saturate.<br>
><br>
> Second, you should handle blocks that can never fall through (indirect branches from jump tables). There is no need to try to place their successors.<br>
<br>
</div>Please put this under some flag for now. Enabling it by default opens up a whole set of issues that are premature to discuss. Until the overall code layout strategy is more coherent, people will only want to enable profile guided layout when they have complete profile info, or really need to take full advantage of builtin expect. If you're not one of those people, you'll want to leave this disabled to avoid unnecessary misery when debugging generated disassembly, and reduce the number of places that codegen makes semi-random decisions that perturb the code.<br>
</blockquote><div><br></div><div>Couldn't agree more. The goal is to get something started.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Otherwise, the code looks nice! Good comments.</blockquote>
<div><br></div><div>Thanks! Please let me know both what needs to be done to get this first version checked in, and what the important next steps are.</div><div><br></div><div>On my end, I'm working on getting some benchmark numbers next. </div>
</div></div></div>