<html><head></head><body bgcolor="#FFFFFF"><div><br></div><div>On Oct 23, 2011, at 1:11 AM, Chandler Carruth <<a href="mailto:chandlerc@google.com">chandlerc@google.com</a>> wrote:<br><br></div><blockquote type="cite"><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; ">Let me give you a little example to think about:</span></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></div></blockquote><div><br></div><div>I made a test case out of this, and I think it works. It's a bit confusing at it just replaces branches to F with ret. That removes the edge from D to F, and makes the following ordering also viable: A, B, C, D, E. That's the ordering it chooses, and it also duplicates D up into B instead of branching from B to D. :: shrug ::. It looks pretty good to me though. =]</div>
<div><br></div></blockquote><br><div></div><div>Great. I didn't expect it to work as test case without tweaking. The case when no blocks get folded or tail duped is interesting. You'll have to disable those codegen optimizations or just add blocks and instructions until they're defeated.</div><div><br></div><div>Andy </div></body></html>