Hi Jakob,<br> I have spent last 4 weeks trying to figure out how to implement<br>Interprocedural Register Allocation. I must admit that I was really<br>overwhelmed with LLVM's codebase while trying to figure this out :)<br>
There is so much to know! I think I have reached a point where I<br>have some sort of basic understanding of what needs to be done,<br>but I need some help from here on. So here is the summary of<br>what I know and for what I need more help.<br>
<br>I see that lib/CodeGen/Passes.cpp adds PrologEpilogInserter (PEI<br>henceforth) pass after the RegAlloc pass. Do I understand correctly<br>that LLVM first performs a given pass on all the functions before<br>moving to the next pass? In order to proceed further with this analysis<br>
and to reduce the number of email exchanges back and forth, I will<br>assume that my understanding is correct for now (branch prediction in<br>real life? :P). Please let me know if I am wrong, I will restart the<br>analysis from this point in the subsequent emails. Assuming this is the<br>
case, as with many things compiler optimizations, this is somewhat<br>opposite to what we want :) So let me start from the beginning of what<br>we want.<br><br>Let us say we want to allocate registers for node X in the call graph.<br>
We want our interprocedural register allocator to have run on all the<br>child nodes of X in the call graph before it starts the register<br>allocation on the given node X itself. We not only need this, but<br>we also want all Callee Saved Registers (CSR henceforth)<br>
information to be available for all the child nodes of X.<br><br>This is because we want to compute the physical registers available<br>for node X as:<br>set(all the physical registers available) - Union over all the<br>
children(X) (set(CSR for the child node)) - Union over all the<br>
children(X) (set(used physical registers including calling<br> convention registers for the child node))<br><br>However in the current implementation CSR info is calculated in the PEI<br>pass which is done after register allocation. I am guessing that this<br>
was because, CSR spill insertion is done in the Prolog and the Epilog<br>in the case when we do not shrink wrap and there was no need to<br>calculate CSR elsewhere and this was the reasonable location to place<br>that calculation. However, we have a need to have the calculation done<br>
in the register allocator now. So IMHO, we should be moving the<br>calculation of CSR out of PEI pass but should save that info to be made<br>available to PEI pass for spill code insertion. If we can actually do<br>this, we should be able to combine this CSR calculation with register<br>
allocation. In fact, unless it is absolutely necessary to keep them<br>separate for modularity or other such reasons, we can merge the PEI pass<br>and the RegAlloc pass together. What are the cases where one uses a<br>RegAlloc pass but not PEI pass?<br>
<br>Another concern is about the re-use of CallGraphSCC pass. I see that in<br>lib/Analysis/IPA/CallGraphSCCPass.cpp's CGPassManager::RunPassOnSCC()<br>method there is this line, Changed |= FPP->runOnFunction(*F); and FPP<br>
is cast to (FPPassManager*). However, if we want to re-use<br>CallGraphSCCPass in CodeGen, shouldn't we be casting FPP to the<br>MachineFunction equivalent and be calling the runOnMachineFunction()<br>method instead? So should we inherit CallGraphSCCPass to create<br>
MachineCallGraphSCCPass like what we do for FunctionPass, and replace<br>all the casts/references to non-machine passes to equivalent machine<br>passes in the overridden methods?<br><br>So given all these things, here is my plan on how to go about<br>
implementing an Interprocedural Register Allocator (IPRA henceforth).<br><br>1. Decide if we have to create MachineCallGraphSCCPass.<br><br>2. If we have to create MachineCallGraphSCCPass, inherit from<br> CallGraphSCCPass and override the methods as required.<br>
<br>3. Create a new IPRA pass which inherits from MachineCallGraphSCCPass<br> or CallGraphPass depending on whether we create<br> MachineCallGraphSCCPass.<br><br>4. Implement a loop in runOnMachineSCC that iterates over the CallGraph<br>
nodes in the bottom-up order:<br> A. For each node, run one of the allocators as chosen by the command<br> line flag or the optimization level required. This can be<br> implemented as an argument to createIPRAPass() method.<br>
B. While running the register allocator for a node, make use of the<br> RegMask from the child nodes to compute the registers available<br> for this node.<br> C. Immediately after the register allocator is run for the node, run<br>
calculateCalleeSavedRegisters() on that node and save that info.<br> I think the current method already saves this info in MFI, so we<br> do not have to do any extra work to save it for later use.<br> D. Update the RegMask for the node so that its parents know what<br>
registers to use.<br><br>5. Since calculateCalleeSavedRegisters() is now part of register<br> allocator, remove it from PEI pass but use that info where required.<br><br>6. Add a command line flag to enable IPRA (turned off by default) and<br>
add the pass to passes.cpp and the non-IPRAs work exactly as they<br> are now from the outside, but calculateCalleeSavedRegisters() is<br> moved to a different place.<br><br>Other things like, not using the RegMask of the child nodes which have<br>
calls to external functions or have function pointers as function<br>parameters should be taken care of.<br><br>Please let me know if this makes any sense at all. Also if you would<br>like to have a quicker turn around time for a conversation, I can login<br>
to LLVM's IRC channel when you have some time or please feel free<br>to ping me on IM (I use this same email ID for GTalk).<br>
<br><br><div class="gmail_quote">On Thu, Oct 4, 2012 at 2:38 PM, Madhusudan C.S <span dir="ltr"><<a href="mailto:madhusudancs@gmail.com" target="_blank">madhusudancs@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Jakob,<br><br><div class="gmail_quote"><div>On Thu, Oct 4, 2012 at 2:31 PM, Jakob Stoklund Olesen <span dir="ltr"><<a href="mailto:stoklund@2pi.dk" target="_blank">stoklund@2pi.dk</a>></span> wrote:<br>
</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"><br><div><div><div>On Oct 4, 2012, at 2:27 PM, "Madhusudan C.S" <<a href="mailto:madhusudancs@gmail.com" target="_blank">madhusudancs@gmail.com</a>> wrote:</div>
<br><blockquote type="cite"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word">
<div>Basically, the PrologEpilogInsertion pass will add a bit mask to MachineModuleInfo describing which registers are clobbered by the function being compiled. Later, when compiling the callers, that bit mask is used to initialize the regmask operands on call instructions.</div>
</div></blockquote><div><br>So the idea is to sidestep from the calling convention a bit if we<br>already know that the called function will not be using all the<br>registers required by the convention and instead use those registers<br>
in the caller?<br></div></div></blockquote><div><br></div></div><div>That's right.</div><div><br><blockquote type="cite"><div class="gmail_quote"><div>If I am understanding this correctly, is this something desirable for<br>
LLVM, even if it is not high priority?</div></div></blockquote><div><br></div></div><div>Yes.</div><div><br><blockquote type="cite"><div class="gmail_quote"><div> Would you guys be Ok if I try<br>to implement this without disturbing the project priorities but with<br>
a little help/guidance?</div></div></blockquote><div><br></div></div><div>Absolutely.</div></div></div></blockquote></div></div><div><br>Great! Thank you very much. Then, I will do some homework on how<br>I plan to implement this, a _very_ rough sketch if not the actual<br>
design, and come back.<br><br>Btw, I just found this <a href="http://optimisticcompilers.blogspot.com/" target="_blank">http://optimisticcompilers.blogspot.com/</a> So<br>I will just take a look at what happened to that project.<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><span><font color="#888888"><div><br></div><div>/jakob</div><div>
<br></div></font></span></div></div>
</blockquote></div><div><div><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Thanks and regards,<br> Madhusudan.C.S<br><br>