<div dir="ltr"><br><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><i><font size="2" face="monospace, monospace"><b>Vivek Pandya</b></font></i><div><br></div></div></div></div></div></div>
<br><div class="gmail_quote">On Wed, May 11, 2016 at 11:19 PM, Matthias Braun <span dir="ltr"><<a href="mailto:matze@braunis.de" target="_blank">matze@braunis.de</a>></span> wrote:<br><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>Yes there is also MachineRegisterInfo::UsedPhysRegMask which should be the union of all regmasks in the function.</div><p style="margin:0px;font-size:13px;line-height:normal;font-family:Hack;color:rgb(235,235,235);background-color:rgb(0,0,0)"></p></div></blockquote><div> </div><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"><p style="margin:0px;font-size:13px;line-height:normal;font-family:Hack;color:rgb(235,235,235);background-color:rgb(0,0,0)">./lib/CodeGen/MIRParser/MIRParser.cpp:  RegInfo.<span style="color:rgb(255,180,197)"><b>setUsedPhysRegMask</b></span>(CalleeSavedRegisterMask.flip());</p><div><blockquote type="cite"><span class=""><div></div></span></blockquote></div></div></blockquote><div>Is this line responsible for setting the UsedPhysMask after codegen for a function? And This will be changed for each function call right ?</div><div>-Vivek </div><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><blockquote type="cite"><span class=""><div>On May 11, 2016, at 10:47 AM, Hal Finkel via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:</div><br></span><div><div style="font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-family:arial,helvetica,sans-serif;font-size:10pt"><br><br><hr><blockquote style="border-left-width:2px;border-left-style:solid;border-left-color:rgb(16,16,255);margin-left:5px;padding-left:5px;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><b>From:<span> </span></b>"Matthias Braun" <<a href="mailto:matze@braunis.de" target="_blank">matze@braunis.de</a>><div><div class="h5"><br><b>To:<span> </span></b>"Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><br><b>Cc:<span> </span></b>"vivek pandya" <<a href="mailto:vivekvpandya@gmail.com" target="_blank">vivekvpandya@gmail.com</a>>, "llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br><b>Sent:<span> </span></b>Wednesday, May 11, 2016 12:46:25 PM<br><b>Subject:<span> </span></b>Re: [llvm-dev] [GSoC 2016] Interprocedural Register Allocation - Introduction and Feedback<br><br><br><div><blockquote><div>On May 11, 2016, at 3:31 AM, Hal Finkel via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:</div><br><div><div style="font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-family:arial,helvetica,sans-serif;font-size:10pt"><br><hr><blockquote style="border-left-width:2px;border-left-style:solid;border-left-color:rgb(16,16,255);margin-left:5px;padding-left:5px;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><b>From:<span> </span></b>"vivek pandya" <<a href="mailto:vivekvpandya@gmail.com" target="_blank">vivekvpandya@gmail.com</a>><br><b>To:<span> </span></b>"Mehdi Amini" <<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a>><br><b>Cc:<span> </span></b>"Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>, "Quentin Colombet" <<a href="mailto:qcolombet@apple.com" target="_blank">qcolombet@apple.com</a>>, "llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>, "Matthias Braun" <<a href="mailto:matze@braunis.de" target="_blank">matze@braunis.de</a>><br><b>Sent:<span> </span></b>Wednesday, May 11, 2016 3:15:03 AM<br><b>Subject:<span> </span></b>Re: [GSoC 2016] Interprocedural Register Allocation - Introduction and Feedback<br><br><div dir="ltr"><br><div class="gmail_extra"><br clear="all"><div><div><div dir="ltr"><div><div dir="ltr"><i><font face="monospace, monospace" size="2"><b>Vivek Pandya</b></font></i><div><br></div></div></div></div></div></div><br><div class="gmail_quote">On Wed, May 11, 2016 at 10:02 AM, vivek pandya<span> </span><span dir="ltr"><<a href="mailto:vivekvpandya@gmail.com" target="_blank">vivekvpandya@gmail.com</a>></span><span> </span>wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br clear="all"><div><div><div dir="ltr"><div><div dir="ltr"><i><font face="monospace, monospace" size="2"><b>Vivek Pandya</b></font></i><div><br></div></div></div></div></div></div><br><div class="gmail_quote"><div><div>On Wed, May 11, 2016 at 9:43 AM, Mehdi Amini<span> </span><span dir="ltr"><<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a>></span><span> </span>wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><br><div><span><blockquote><div>On May 10, 2016, at 6:06 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>> wrote:</div><br><div><div style="font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-family:arial,helvetica,sans-serif;font-size:10pt"><br><br><hr><blockquote style="border-left-width:2px;border-left-style:solid;border-left-color:rgb(16,16,255);margin-left:5px;padding-left:5px;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><b>From:<span> </span></b>"vivek pandya" <<a href="mailto:vivekvpandya@gmail.com" target="_blank">vivekvpandya@gmail.com</a>><br><b>To:<span> </span></b>"llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>, "Tim Amini Golling" <<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a>>, "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><br><b>Cc:<span> </span></b>"Quentin Colombet" <<a href="mailto:qcolombet@apple.com" target="_blank">qcolombet@apple.com</a>><br><b>Sent:<span> </span></b>Tuesday, May 10, 2016 2:59:16 PM<br><b>Subject:<span> </span></b>[GSoC 2016] Interprocedural Register Allocation - Introduction and Feedback<br><br><div dir="ltr"><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">Hello LLVM Community,<br></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica;min-height:14px"><br></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">Sorry for delay as I was busy in final exams.</div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica;min-height:14px"><br></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">I am Vivek from India. Thanks for choosing my proposal for Interprocedural Register Allocation (IPRA) in LLVM. Mehdi Amini and Hal Finkel will be mentoring me for this project.</div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica;min-height:14px"><br></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">IPRA can reduce code size and runtime of programs by allocating register across the module and procedure boundaries.</div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica;min-height:14px"><br></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">I have identified some old but effective research work on this area.</div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">I want community's feedback for feasibility of these approach and I am targeting to implement two of them during this project.</div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica;min-height:14px"><br></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">Here is list of the papers, I have read first two papers and I would like to discuss those approach first, I will read other two paper then initiate discussion for them as well. All I want is to find out a concrete implementation plan before 23 May, 2016 and for that I need community's help.</div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica;min-height:14px"><br></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">1) Compile time ----- Minimizing register usage penalty at procedure calls -<span> </span><a href="http://dl.acm.org/citation.cfm?id=53999" target="_blank">http://dl.acm.org/citation.cfm?id=53999</a></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">====================================================================In this approach intra-procedural register allocation is used as base but machine code generation order is bottom up traversal of call graph and inter-procedural effect is achieved by propagating register usage information of callee function to caller (i.e child to parent in CallGraph) so that caller can use different registers than callee and can save load store cost at procedure call, this is not trivial as it seems due to recursive calls, library function usage etc. Also for upper region of the graph in this technique available number of registers might become zero in that case it should fall back to normal load store at procedure call. Apart from these difficulties other difficulties have been identified please follow this mail-chain<span> </span><a href="https://groups.google.com/d/topic/llvm-dev/HOYAXv3m1LY/discussion" target="_blank">https://groups.google.com/d/topic/llvm-dev/HOYAXv3m1LY/discussion</a></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">My mentor has already provided me a patch that alters code generation order as per bottom up call graph traversal, I am working from that point now. Any other help/suggestion is always welcomed.</div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica;min-height:14px"><br></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">2) Link time ----- Global register allocation at link time -<span> </span><a href="http://dl.acm.org/citation.cfm?id=989415" target="_blank">http://dl.acm.org/citation.cfm?id=989415</a></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">====================================================================In this particular approach (sort of true IPRA) registers will be reallocated (this optimization will be optional if turned off still code will be compiled as per intra-procedural allocation) at link time. Here modules are first complied as per normal compilation but the object code is annotated with details so that linker can build call graph and also calculate usage information at link time. Compiler also write hints in object code that if particular variable is allocated in some other register ( due to new allocation) then how the code should be changed? Thus linker can use these information to decide which variables (global) need to be in same register through out the program execution and also according to register usage information in call graph which procedure will not be active simultaneously so that locals for that procedures can be in same registers with out load store at procedure calls. </div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">For these particular method help me to analyze feasibility: </div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">1) Can llvm collects following information at module level in MachineIR? list of procedures in module, list of locals in procedures, list of procedures that a particular procedure can call, and a list of the variables this procedure references. Each entry in the last two lists includes an estimate of the number of times the procedure is called or the variable is referenced in each execution of this procedure </div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">2) Can llvm write informative commands to object files?</div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">3) Can LTO is capable of leveraging those commands?<span> </span><br></div></div></blockquote>In terms of scoping the project for the summer, I definitely recommend that you focus on (1) first. If you finish that, we can certainly move on to other things.</div></div></blockquote><div><br></div></span><div>I'll add +1 here, but I already wrote the same thing on IRC when discussing with Vivek. True IPRA without a proper MachineModule infrastructure won't be doable in my opinion (even with such infrastructure, it may not be trivial in LLVM in general).</div><span><br><blockquote><div><div style="font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-family:arial,helvetica,sans-serif;font-size:10pt">Regarding link time, note that any such a design would likely look much different than in David Wall's paper however, because our LTO re-codegens everything anyway. The paper says, "Finally, it keeps us honest as designers of the system; once we postpone anything until link time, the temptation is great to postpone everything, ..." - Well, we've long-since succumb to that temptation when we LTO. C'est la vie.<br></div></div></blockquote><div><br></div></span><div>+1 as well, our LTO will benefit naturally from the leaf-to-root information propagation. ThinLTO will be more challenging/interesting though!</div><span><blockquote><div><div style="font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-family:arial,helvetica,sans-serif;font-size:10pt"><blockquote style="border-left-width:2px;border-left-style:solid;border-left-color:rgb(16,16,255);margin-left:5px;padding-left:5px;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><div dir="ltr"><p style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica"></p><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica">For the first part a mechanism similar to MachineModulePass would be desirable but that may not be possible during this project, but if we can make some sort of smaller version of that to suit our purpose.</div></div></blockquote>I don't think we need to make any kind of MachineModulePass to make this work. Once we alter the visitation order based on the CGSCC iteration scheme, we can keep state in-between functions in the pre-existing hacky way (using static members of the relevant function passes).<br></div></div></blockquote><div><span style="font-size:13px"></span></div></span></div></div></blockquote></div></div><span><div> <span style="font-size:13px">Sorry my mistake here by first part I mean 1) requirement in the link time approach.</span></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><div></div></div></div></blockquote><div> </div></span><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><div>I also don't see where/why we need a MachineModule(Pass) for the CGSCC scheme, that said I'd rather avoid using a function pass with static members, if we can have a ModuleAnalysis that is bookkeeping the results for functions in the module and queries by the register allocator somehow.</div><span><div>Matthias/Quentin may have other inputs on this aspect.</div></span></div></div></blockquote></div></div></div></blockquote><div> </div><div>@Hal do you mean to add a simple MachineFunction pass that will just operate on register allocated function and prepare a BitVector to indicate which register is being used by MachineFunction, and then use this pass as analysis pass (i.e just simply return static BitVector for clobbered register when register allocation for next function begins. This part is not much clear to me) this thing can be done by scheduling a pass post register allocation in lib/CodeGen/Passes.cpp</div><div><div><br></div><div>void TargetPassConfig::addMachinePasses() {</div><div>. </div><div>.</div><div>.</div><div>  // Run pre-ra passes.</div><div>  addPreRegAlloc();</div><div><br></div><div>  // Run register allocation and passes that are tightly coupled with it,</div><div>  // including phi elimination and scheduling.</div><div>  if (getOptimizeRegAlloc())</div><div>    addOptimizedRegAlloc(createRegAllocPass(true));</div><div>  else</div><div>    addFastRegAlloc(createRegAllocPass(false));</div><div><br></div><div>  // Run post-ra passes.</div><div>  addPostRegAlloc();</div></div><div>// Adding a new pass here which keeps register mask information across function calls.</div><div>.</div><div>.</div><div>.</div><div>}</div><div><br></div><div>But this also requires current register allocators to use this information in someway because RegMaskBits in LiveIntervalAnalysis.cpp is not static across calls. I mean I am not clear for how to propagate static info to Intra-procedural Register allocators (if possible without disturbing their code )</div></div></div></div></blockquote>First, my hope is that we won't need to change the register allocators, as such, in order to make use of this information. Instead, we'll simply be able to alter the register masks generated for the call instructions. These masks will indicate fewer clobbers than might otherwise be present based on the ABI because of information gathered during the codegen of the callee. These masks are generally constructed by target based on the calling convention. The PowerPC backend, for example, looks like this:<br><br>  // Add a register mask operand representing the call-preserved registers.<br>  const TargetRegisterInfo *TRI = Subtarget.getRegisterInfo();<br>  const uint32_t *Mask =<br>      TRI->getCallPreservedMask(DAG.getMachineFunction(), CallConv);<br>  assert(Mask && "Missing call preserved mask for calling convention");<br>  Ops.push_back(DAG.getRegisterMask(Mask));<br><br>but it can be more complicated. If you look for uses of 'getRegisterMask' in Target/*/*ISelLowering.cpp, you'll see what I mean. Regardless, the code ends up calling some method is the targets TargetRegisterInfo subclass. These methods generally look something like this:<br><br>const uint32_t *<br>PPCRegisterInfo::getCallPreservedMask(const MachineFunction &MF,<br>                                      CallingConv::ID CC) const {<br>  const PPCSubtarget &Subtarget = MF.getSubtarget<PPCSubtarget>();<br>  ...<br>  return TM.isPPC64() ? (Subtarget.hasAltivec() ? CSR_SVR464_Altivec_RegMask<br>                                                : CSR_SVR464_RegMask)<br>                      : (Subtarget.hasAltivec() ? CSR_SVR432_Altivec_RegMask<br>                                                : CSR_SVR432_RegMask);<br>}<br><br>In any case, the fundamental idea here is that, when someone calls getCallPreservedMask in order to set the regmask on a call, we might not have to use the CC at all. Instead, if we've already codegened the function, we might use a cache of 'exact' register masks computed during codegen of the potential callees instead.<br><br>In order to do this, I think we'll need to provide a function callable from the target's getCallPreservedMask implementation, which can return such an 'exact' regmask when available. I think we need to do it this way for two reasons:<br><br> 1. Not all of the target code calls getCallPreservedMask, but sometimes calls other similar target-specific functions (e.g. getTLSCallPreservedMask).<br> 2. The targets need to opt-in to this behavior because only the target can know that all register uses are really tagged correctly post "pre-emit".<br><br>Because the target is free to introduce uses of registers at essentially any time, we need to do the scanning for used registers after the "pre-emit" passes run. This can be done by scheduling some simple register-use scanning pass after the call to addPreEmitPass in lib/CodeGen/Passes.cpp.<br></div></div></blockquote><div>MachineRegister maintains linked lists with defs/uses for each register so you can determine whether a specific register is used or not without scanning.</div></div></div></div></blockquote><div><div class="h5">Does this include regmask-clobbered registers?<br><br> -Hal<br><blockquote style="border-left-width:2px;border-left-style:solid;border-left-color:rgb(16,16,255);margin-left:5px;padding-left:5px;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><div><div></div><div><br></div><div>- Matthias</div></div><br></blockquote><br><br><br>--<span> </span><br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></div></div><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">_______________________________________________</span><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">LLVM Developers mailing list</span><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><a href="mailto:llvm-dev@lists.llvm.org" style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">llvm-dev@lists.llvm.org</a><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></div></blockquote></div><br></div></blockquote></div><br></div></div>