<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Aug 16, 2011, at 2:08 AM, Ghassan Shobaki wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div><div style="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt; position: static; z-index: auto; "><div><span class="Apple-style-span" style="font-family: 'times new roman', 'new york', times, serif; ">I know that phase ordering is a non-trivial problem that does not have a perfect solution (like most compiler optimization problems!), but I wonder why LLVM runs such passes between scheduling and allocation. One would expect a register pressure reduction pass to be placed as close as possible to the register allocation pass.</span></div></div></div></blockquote><div><br></div><div>Since SelectionDAG is a graph and MachineInstr is linear, some kind of scheduling needs to take place when converting the intermediate representation.</div><div><br></div><div>We are looking at placing a scheduler between coalescing and register allocation. There are complications such as keeping the LiveIntervals data structure updated, and dealing with code that is no longer in SSA form.</div><div><br></div><div>Compile time is also a major concern. Out-of-order processors don't benefit much from ILP scheduling except in special cases, so it is not clear that an extra scheduler is worth the compile time. That depends on the target machine, of course.</div><br><blockquote type="cite"><div><div style="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt; position: static; z-index: auto; "><div><span class="Apple-style-span" style="font-family: 'times new roman', 'new york', times, serif; "> Ideally, you would like to have an integrated algorithm that does allocation and scheduling simultaneously, but such an integrated
solution is usually not implemented due to its complexity. So, my questions are:</span></div><div style="font-family: arial,helvetica,sans-serif; font-size: 12pt;"><div style="font-family: times new roman,new york,times,serif; font-size: 12pt;"><div id="yiv1595100037"><div><div>(1) CSE naturally tends to increase reg pressure. Is there any particular reason for doing CSE between scheduling and allocation instead of doing it, say before scheduling?<br></div></div></div></div></div></div></div></blockquote><div><br></div><div>CSE and LICM are generally performed on the LLVM IR before instruction selection. The late passes exist to exploit opportunities created by instruction selection.</div><div><br></div><div>SelectionDAG is a per-block data structure, so these global passes must run on the MachineInstr representation.</div><br><blockquote type="cite"><div><div style="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt; position: static; z-index: auto; "><div style="font-family: arial,helvetica,sans-serif; font-size: 12pt;"><div style="font-family: times new roman,new york,times,serif; font-size: 12pt;"><div id="yiv1595100037"><div><div>(2) How easy will it be to change the phase ordering in LLVM without breaking things? Where is the phase ordering done? How do we know if there are dependencies among certain phases?<br></div></div></div></div></div></div></div></blockquote><div><br></div><div>You cannot reorder passes that work on different intermediate representations.</div><div><br></div><blockquote type="cite"><div><div style="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt; position: static; z-index: auto; "><div style="font-family: arial,helvetica,sans-serif; font-size: 12pt;"><div style="font-family: times new roman,new york,times,serif; font-size: 12pt;"><div id="yiv1595100037"><div><div>>These DAG nodes are also used to copy to/from physical registers before and after calls.</div><div>>Virtual registers defined by PHI instructions will also appear as CopyFromReg operands.</div><br>Ghassan: So, is there a way to distinguish the ones that represent live-in and live-out regs?<br></div></div></div></div></div></div></blockquote><div><br></div><div>Look for virtual registers.</div><div><br></div><div>/jakob</div><div><br></div></div></body></html>