<div class="gmail_quote">On Tue, Oct 18, 2011 at 4:31 PM, Jakob Stoklund Olesen <span dir="ltr"><<a href="mailto:stoklund@2pi.dk">stoklund@2pi.dk</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"><br><div><div class="im"><div>On Oct 18, 2011, at 3:07 PM, Chandler Carruth wrote:</div><br></div><blockquote type="cite"><div class="gmail_quote"><div class="im">On Tue, Oct 18, 2011 at 2:59 PM, Cameron Zwarich <span dir="ltr"><<a href="mailto:zwarich@apple.com" target="_blank">zwarich@apple.com</a>></span> wrote:<br>
</div><div class="im"><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>I think this should really live as a CodeGen pass. Is there any good reason to make it an IR pass?</div></blockquote><div><br></div><div>So, as it happens, I was *completely* wrong here. CodeGen correctly preserves the ordering of blocks from IR, *unless* it can do folding, etc.</div>
</div></div></blockquote><div><br></div><div>That's right. However, the CFG changes quite a bit during CodeGen.</div><div><br></div><div>Switches can be lowered into branch trees, multiple passes can split critical edges, and then there is taildup and tailmerge.</div>
<div><br></div><div>An IR code layout algorithm simply doesn't know the final CFG.</div></div></div></blockquote><div><br></div><div>To be clear, I don't disagree with any of this. =] However, my rough experiments thus far (hoping to have real benchmark data soon) seem to indicate that just giving a baseline ordering of block to the CodeGen layer </div>
<div> </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 class="im"><div><br></div><blockquote type="cite"><div class="gmail_quote">
<div>As for why it should be an IR pass, mostly because once the selection dag runs through the code, we can never recover all of the freedom we have at the IR level. To start with, splicing MBBs around requires known about the terminators (which we only some of the time do), and it requires re-writing them a touch to account for the different fall-through pattern. To make matters worse, at this point we don't have the nicely analyzable 'switch' terminator (I think), and so the existing MBB placement code just bails on non-branch-exit blocks.</div>
</div></blockquote><div><br></div></div><div>Those are all the wrong reasons for not doing the right thing.</div></div></div></blockquote><div><br></div><div>Sorry, I'm not trying to do the wrong thing because of this... Currently, it feels like a trade-off in terms of cost/benefit. It's not yet clear to me that the benefit of doing this analysis in the CodeGen layer outweighs the cost and I was trying to clarify what the costs I perceive are.</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><span style="background-color: transparent; ">Some basic blocks are glued together and must be placed next to each other. That situation can be recognized by "MBB->canFallThrough() && TII->AnalyzeBranch(MBB..)".</span></div>
<div><br></div><div>Treat glued-together blocks as super-blocks, and everything should be as breezy as IR.</div></div></div></blockquote><div><br></div><div>But that's just the thing -- a primary goal of this pass would be to *change* the fall-through pattern. Currently, that can be done very easily, although to a limited extent, by changing the IR which enters the selection dag.</div>
<div><br></div><div>Maybe what we need is to have this pass at both layers? Then the codegen layer can work on the glued-together blocks to check for (and correct) any inappropriate CFG changes made in the intervening passes?</div>
<div><br></div><div>Also, it's still not clear to me how to analyze switches in CodeGen, but that's likely my lack of having read the appropriate interfaces thoroughly.</div></div>