<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On May 24, 2016, at 9:17 PM, vivek pandya <<a href="mailto:vivekvpandya@gmail.com" class="">vivekvpandya@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="">Dear Mentors,</div><div class=""><br class=""></div><div class="">Please help me to understand our plan to implement Interprocedural Register allocator by propogating register usage info. While writing this mail I am considering all previous discussion over llvm-dev and IRC. </div><div class=""><br class=""></div><div class="">1) A MachineFunction pass to be executed POST-RA to collect the information about the used Registers.</div><div class="">2) An Immutable pass which will store reg usage info collected by previous pass and return it whenever queried.</div><div class="">3) A Target specific MachineFucntion pass that will use the register usage info for available for call instrction to <span class="" style="white-space:pre"> </span>achive IPRA. This pass should run at PRE-RA.</div><div class=""><br class=""></div><div class="">Relation among above passes:</div><div class=""><br class=""></div><div class="">1) pass will store info to 2) pass as well use info for call instruction found while processing.</div><div class=""><br class=""></div><div class="">3) pass only requires to query information from 2) pass.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Questions</div><div class="">=========</div><div class=""><br class=""></div><div class=""> Which pass is responsible for load/store of callee saved register, at the begining of each function call? And how does it uses RegMask of call instruction to generate load/store. I think Intra-procedural register allocator is not responsible to generate load/store around the call site.</div><div class=""><br class=""></div><div class=""><span class="" style="white-space:pre"> </span> /- - -> (A) - - -> (D)</div><div class=""><span class="" style="white-space:pre"> </span>/</div><div class=""><span class="" style="white-space:pre"> </span>(K)- - ->(T)- - -> (B) - - -> (E)</div><div class=""><span class="" style="white-space:pre"> </span>\</div><div class=""><span class="" style="white-space:pre"> </span> \- - -> (C) - - -> (F)</div><div class=""><br class=""></div><div class="">So as per our discussion we would require following passes:</div><div class=""><br class=""></div><div class="">Suppose in given example call graph , register allocation for D is completed now we have that information available So 3) pass while processing A , it would collect reg usage info for all callees and OR them and then it should update A's regmask by going to parant procedure that actually calls A ?? </div></div></div></blockquote><div><br class=""></div><div>No, Pass 3) is only looking for every call MI in A and updating the associated regmask by replacing it with the information stored in the immutable pass.</div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="">How reg mask details of call D would be used by Register allocator while allocating register for A and also not generating load/store for register being used by A in body of D as we have callee saved convention. </div></div></div></blockquote><div><br class=""></div><div>I expect all of that to be handled automatically when updating the regmask.</div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">How the pass responsible for generating load/store will optimize for the child node of call graph where it does not require to load/store because caller will not use register used by callee ? I mean how our IPRA will take care of this?</div></div></div></blockquote><div><br class=""></div><div>I don't understand that.</div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">In short I am not much clear with the method for using information to get effect of IPRA without modifying Register allocator them self(i.e by updating regMask of call instructions). </div><div class=""><br class=""></div><div class="">Also 1) pass and 3) pass are seem to intersecting for their work, for example consider while scanning register usage info for T function the final register usage info should be <all regs used by T> OR < reg usage info A > OR <reg usage info B > OR < reg usage info C > because K should not use any register which is used by T, A ,D, B, C, E, F with out load/store the relevant paper also discuss this situation and suggest to fall back to load/store approach. So as we move to upper region of the call graph it is very likely that enough regiseters are not there to allocate.</div></div></div></blockquote><div><br class=""></div><div>The calling convention (for anything else than internal function) will always have some callee-saved registers.</div><div>If we have a deep call-graph of internal-only function, then we may generate a lot of spill at the top. Somehow we may have to think about driving some heuristic with PGO.</div><div>I suspect we can think about that a bit later. Let's focus on the simple for now.</div><div><br class=""></div><div>-- </div><div>Mehdi</div><div><br class=""></div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">Please bear with my silly questions.</div><div class=""><br class=""></div><div class="">Sincerely,</div><div class="">Vivek</div><div class=""><br class=""></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Wed, May 25, 2016 at 8:46 AM, vivek pandya <span dir="ltr" class=""><<a href="mailto:vivekvpandya@gmail.com" target="_blank" class="">vivekvpandya@gmail.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote"><div class=""><div class="h5">On Wed, May 25, 2016 at 8:44 AM, Hal Finkel <span dir="ltr" class=""><<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><br class=""><hr class=""><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;" class=""><b class="">From: </b>"vivek pandya" <<a href="mailto:vivekvpandya@gmail.com" target="_blank" class="">vivekvpandya@gmail.com</a>><br class=""><b class="">To: </b>"Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>><br class=""><b class="">Cc: </b>"llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>>, "Matthias Braun" <<a href="mailto:matze@braunis.de" target="_blank" class="">matze@braunis.de</a>>, "Mehdi Amini" <<a href="mailto:mehdi.amini@apple.com" target="_blank" class="">mehdi.amini@apple.com</a>>, "Quentin Colombet" <<a href="mailto:qcolombet@apple.com" target="_blank" class="">qcolombet@apple.com</a>><br class=""><b class="">Sent: </b>Tuesday, May 24, 2016 9:34:29 PM<div class=""><div class=""><br class=""><b class="">Subject: </b>Re: [GSoC 2016] Interprocedural Register Allocation - Introduction and Feedback<br class=""><br class=""><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote">On Wed, May 25, 2016 at 3:53 AM, Hal Finkel <span dir="ltr" class=""><<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><br class=""><hr class=""><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;" class=""><b class="">From: </b>"vivek pandya" <<a href="mailto:vivekvpandya@gmail.com" target="_blank" class="">vivekvpandya@gmail.com</a>><br class=""><b class="">To: </b>"Quentin Colombet" <<a href="mailto:qcolombet@apple.com" target="_blank" class="">qcolombet@apple.com</a>><br class=""><b class="">Cc: </b>"Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>>, "llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>>, "Matthias Braun" <<a href="mailto:matze@braunis.de" target="_blank" class="">matze@braunis.de</a>>, "Mehdi Amini" <<a href="mailto:mehdi.amini@apple.com" target="_blank" class="">mehdi.amini@apple.com</a>><br class=""><b class="">Sent: </b>Tuesday, May 24, 2016 1:00:58 PM<span class=""><br class=""><b class="">Subject: </b>Re: [GSoC 2016] Interprocedural Register Allocation - Introduction and Feedback<br class=""><br class=""></span><span class=""><div dir="ltr" class="">Hello,<div class=""><br class=""></div><div class="">I have written following code to check each register if it is used by machineFunction or not :</div><div class=""><br class=""></div><div class=""><div class=""><font face="monospace, monospace" class="">MachineRegisterInfo *MRI = &MF.getRegInfo();</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>TargetRegisterInfo *TRI = (TargetRegisterInfo *)MF.getSubtarget().getRegisterInfo();</font></div></div></div></span></blockquote>Some reason you can't use a const pointer here?</div></div></blockquote><div class="">MCRegisterInfo is just used to get conventional name of register for given target like AX, BX on X86. </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><span class=""><br class=""><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;" class=""><div dir="ltr" class=""><div class=""><div class=""><font face="monospace, monospace" class=""></font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>const TargetMachine &TM = MF.getTarget();</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>const MCRegisterInfo *MCRI = TM.getMCRegisterInfo();</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>DEBUG(dbgs() << "Function Name : " << MF.getName() << "\n");</font></div><div class=""><font face="monospace, monospace" class=""><br class=""></font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>for(TargetRegisterInfo::regclass_iterator i = (*TRI).regclass_begin(), e = (*TRI).regclass_end(); i != e; i++ ) {</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>for(TargetRegisterClass::iterator pregi = (*i)->begin(), prege = (*i)->end(); pregi != prege; pregi++ ) {</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>DEBUG( dbgs() << "Physical Register : " << MCRI->getName(*pregi) << " is modified "<< MRI->isPhysRegModified(*pregi) << " \n");<span style="white-space:pre-wrap" class=""> </span></font></div></div></div></blockquote></span>Try isPhysRegUsed.</div></div></blockquote><div class="">ok </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><span class=""><br class=""><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;" class=""><div dir="ltr" class=""><div class=""><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""></span></font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>}</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>}</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>DEBUG(dbgs() << "\n");</font></div></div><div class=""><br class=""></div><div class="">The pass which is executing this code is schedule POST-RA stage but this gives me true for all registers i.e in each function all registers are being used except EBP and some other similar, Is this a correct way to get register usage information ? I think I have made some mistake please help.</div></div></blockquote><br class=""></span>You might look at the implementation of these functions in lib/CodeGen/MachineRegisterInfo.cpp and figure out if they're returning true because UsedPhysRegMask.test(PhysReg) is true or because reg_nodbg_empty(*AliasReg) is true.</div></div></blockquote><div class="">Yes that helped now I am getting actual register which have been used by given function, but a little problem</div><div class="">The updated code is as shown below : </div><div class=""><font face="monospace, monospace" class="">for(TargetRegisterInfo::regclass_iterator i = (*TRI).regclass_begin(), e = (*TRI).regclass_end(); i != e; i++ ) {</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>for(TargetRegisterClass::iterator pregi = (*i)->begin(), prege = (*i)->end(); pregi != prege; pregi++ ) {</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>for (MCRegAliasIterator AliasReg(*pregi, TRI, true); AliasReg.isValid(); ++AliasReg) {</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span> if (!MRI->reg_nodbg_empty(*AliasReg)) {</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span> <span style="white-space:pre-wrap" class=""> </span>DEBUG( dbgs() << "Physical Register : " << MCRI->getName(*pregi) << " is used "<< MRI->isPhysRegUsed(*pregi) << " \n");<span style="white-space:pre-wrap" class=""> </span></font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span> <span style="white-space:pre-wrap" class=""> </span>break; // no need to process more alias</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span> }</font></div><div class=""><font face="monospace, monospace" class=""> <span style="white-space:pre-wrap" class=""> </span> }<span style="white-space:pre-wrap" class=""> </span></font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>}</font></div><div class=""><font face="monospace, monospace" class=""><span style="white-space:pre-wrap" class=""> </span>} </font></div><div class=""><font face="arial, helvetica, sans-serif" class="">But here some registers are getting processed with in different classes (unnecessary processing) Is this only way to iterate through all used register (using RegClass iterator) ? Is there any way to avoid duplicate regs?</font></div><div class=""><font face="arial, helvetica, sans-serif" class="">Of course currently I am just printing but next I am thinking to use a map to track usage info , in that only distinct register info will be stored but still due to loop structure I need to iterate through a single register 3 - 4 times making it time consuming.</font></div></div></div></div></div></div></blockquote>Yes, I believe you can just do:<br class=""><br class=""> for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {</div></div></blockquote></div></div><div class="">Oh yes thanks I just forgot that PhyReg starts at 0. </div><div class=""><div class="h5"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><span class=""><font color="#888888" class=""><br class=""><br class=""> -Hal</font></span><div class=""><div class=""><br class=""><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;" class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="arial, helvetica, sans-serif" class=""></font></div><div class=""><font face="arial, helvetica, sans-serif" class=""><br class=""></font></div><div class=""><font face="arial, helvetica, sans-serif" class="">-Vivek</font></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div style="font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><span class=""><font color="#888888" class=""><br class=""><br class=""> -Hal</font></span><div class=""><div class=""><br class=""><br class=""><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;" class=""><div dir="ltr" class=""><div class=""></div><div class=""><br class=""></div><div class="">Vivek</div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Wed, May 18, 2016 at 11:42 PM, Quentin Colombet <span dir="ltr" class=""><<a href="mailto:qcolombet@apple.com" target="_blank" class="">qcolombet@apple.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word" class=""><br class=""><div class=""><div class=""><div class=""><blockquote class=""><div class="">On May 18, 2016, at 11:00 AM, vivek pandya <<a href="mailto:vivekvpandya@gmail.com" target="_blank" class="">vivekvpandya@gmail.com</a>> wrote:</div><br class=""><div class=""><br class=""><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" clear="all" class=""><div 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" class=""><div class=""><div dir="ltr" class=""><div class=""><div dir="ltr" class=""><i class=""><font face="monospace, monospace" size="2" class=""><b class="">Vivek Pandya</b></font></i><div class=""><br class=""></div></div></div></div></div></div><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" class=""><div class="gmail_quote" 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">On Wed, May 18, 2016 at 11:25 PM, Quentin Colombet<span class=""> </span><span dir="ltr" class=""><<a href="mailto:qcolombet@apple.com" target="_blank" class="">qcolombet@apple.com</a>></span><span class=""> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word" class=""><br class=""><div class=""><div class=""><div class=""><blockquote class=""><div class="">On May 18, 2016, at 10:46 AM, vivek pandya <<a href="mailto:vivekvpandya@gmail.com" target="_blank" class="">vivekvpandya@gmail.com</a>> wrote:</div><br class=""><div class=""><br class=""><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" clear="all" class=""><div 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" class=""><div class=""><div dir="ltr" class=""><div class=""><div dir="ltr" class=""><i class=""><font face="monospace, monospace" size="2" class=""><b class="">Vivek Pandya</b></font></i><div class=""><br class=""></div></div></div></div></div></div><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" class=""><div class="gmail_quote" 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">On Wed, May 11, 2016 at 4:01 PM, Hal Finkel<span class=""> </span><span dir="ltr" class=""><<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>></span><span class=""> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div style="font-family:arial,helvetica,sans-serif;font-size:10pt" class=""><br class=""><hr class=""><blockquote style="border-left:2px solid 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" class=""><b class="">From:<span class=""> </span></b>"vivek pandya" <<a href="mailto:vivekvpandya@gmail.com" target="_blank" class="">vivekvpandya@gmail.com</a>><br class=""><b class="">To:<span class=""> </span></b>"Mehdi Amini" <<a href="mailto:mehdi.amini@apple.com" target="_blank" class="">mehdi.amini@apple.com</a>><br class=""><b class="">Cc:<span class=""> </span></b>"Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>>, "Quentin Colombet" <<a href="mailto:qcolombet@apple.com" target="_blank" class="">qcolombet@apple.com</a>>, "llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>>, "Matthias Braun" <<a href="mailto:matze@braunis.de" target="_blank" class="">matze@braunis.de</a>><br class=""><b class="">Sent:<span class=""> </span></b>Wednesday, May 11, 2016 3:15:03 AM<br class=""><b class="">Subject:<span class=""> </span></b>Re: [GSoC 2016] Interprocedural Register Allocation - Introduction and Feedback<div class=""><div class=""><br class=""><br class=""><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br clear="all" class=""><div class=""><div class=""><div dir="ltr" class=""><div class=""><div dir="ltr" class=""><i class=""><font face="monospace, monospace" size="2" class=""><b class="">Vivek Pandya</b></font></i><div class=""><br class=""></div></div></div></div></div></div><br class=""><div class="gmail_quote">On Wed, May 11, 2016 at 10:02 AM, vivek pandya<span class=""> </span><span dir="ltr" class=""><<a href="mailto:vivekvpandya@gmail.com" target="_blank" class="">vivekvpandya@gmail.com</a>></span><span class=""> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br clear="all" class=""><div class=""><div class=""><div dir="ltr" class=""><div class=""><div dir="ltr" class=""><i class=""><font face="monospace, monospace" size="2" class=""><b class="">Vivek Pandya</b></font></i><div class=""><br class=""></div></div></div></div></div></div><br class=""><div class="gmail_quote"><div class=""><div class="">On Wed, May 11, 2016 at 9:43 AM, Mehdi Amini<span class=""> </span><span dir="ltr" class=""><<a href="mailto:mehdi.amini@apple.com" target="_blank" class="">mehdi.amini@apple.com</a>></span><span class=""> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word" class=""><br class=""><div class=""><span class=""><blockquote class=""><div class="">On May 10, 2016, at 6:06 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>> wrote:</div><br class=""><div class=""><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" class=""><br class=""><br class=""><hr class=""><blockquote style="border-left:2px solid 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" class=""><b class="">From:<span class=""> </span></b>"vivek pandya" <<a href="mailto:vivekvpandya@gmail.com" target="_blank" class="">vivekvpandya@gmail.com</a>><br class=""><b class="">To:<span class=""> </span></b>"llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>>, "Tim Amini Golling" <<a href="mailto:mehdi.amini@apple.com" target="_blank" class="">mehdi.amini@apple.com</a>>, "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>><br class=""><b class="">Cc:<span class=""> </span></b>"Quentin Colombet" <<a href="mailto:qcolombet@apple.com" target="_blank" class="">qcolombet@apple.com</a>><br class=""><b class="">Sent:<span class=""> </span></b>Tuesday, May 10, 2016 2:59:16 PM<br class=""><b class="">Subject:<span class=""> </span></b>[GSoC 2016] Interprocedural Register Allocation - Introduction and Feedback<br class=""><br class=""><div dir="ltr" class=""><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">Hello LLVM Community,<br class=""></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica;min-height:14px" class=""><br class=""></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">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" class=""><br class=""></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">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" class=""><br class=""></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">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" class=""><br class=""></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">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" class="">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" class=""><br class=""></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">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" class=""><br class=""></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">1) Compile time ----- Minimizing register usage penalty at procedure calls -<span class=""> </span><a href="http://dl.acm.org/citation.cfm?id=53999" target="_blank" class="">http://dl.acm.org/citation.cfm?id=53999</a></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">====================================================================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 class=""> </span><a href="https://groups.google.com/d/topic/llvm-dev/HOYAXv3m1LY/discussion" target="_blank" class="">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" class="">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" class=""><br class=""></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">2) Link time ----- Global register allocation at link time -<span class=""> </span><a href="http://dl.acm.org/citation.cfm?id=989415" target="_blank" class="">http://dl.acm.org/citation.cfm?id=989415</a></div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">====================================================================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" class="">For these particular method help me to analyze feasibility: </div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">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" class="">2) Can llvm write informative commands to object files?</div><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">3) Can LTO is capable of leveraging those commands?<span class=""> </span><br class=""></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.<span class=""> </span></div></div></blockquote><div class=""><br class=""></div></span><div class="">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 class=""><br class=""><blockquote class=""><div class=""><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" class="">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 class=""></div></div></blockquote><div class=""><br class=""></div></span><div class="">+1 as well, our LTO will benefit naturally from the leaf-to-root information propagation. ThinLTO will be more challenging/interesting though!</div><span class=""><blockquote class=""><div class=""><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" class=""><blockquote style="border-left:2px solid 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" class=""><div dir="ltr" class=""><p style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class=""></p><div style="margin:0px;font-size:12px;line-height:normal;font-family:Helvetica" class="">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 class=""></div></div></blockquote><div class=""><span style="font-size:13px" class=""></span></div></span></div></div></blockquote></div></div><span class=""><div class=""> <span style="font-size:13px" class="">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:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><div class=""></div></div></div></blockquote><div class=""> </div></span><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><div class="">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 class=""><div class="">Matthias/Quentin may have other inputs on this aspect.</div></span></div></div></blockquote></div></div></div></blockquote><div class=""> </div><div class="">@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 class=""><div class=""><br class=""></div><div class="">void TargetPassConfig::addMachinePasses() {</div><div class="">. </div><div class="">.</div><div class="">.</div><div class=""> <span class=""> </span>// Run pre-ra passes.</div><div class=""> <span class=""> </span>addPreRegAlloc();</div><div class=""><br class=""></div><div class=""> <span class=""> </span>// Run register allocation and passes that are tightly coupled with it,</div><div class=""> <span class=""> </span>// including phi elimination and scheduling.</div><div class=""> <span class=""> </span>if (getOptimizeRegAlloc())</div><div class=""> <span class=""> </span>addOptimizedRegAlloc(createRegAllocPass(true));</div><div class=""> <span class=""> </span>else</div><div class=""> <span class=""> </span>addFastRegAlloc(createRegAllocPass(false));</div><div class=""><br class=""></div><div class=""> <span class=""> </span>// Run post-ra passes.</div><div class=""> <span class=""> </span>addPostRegAlloc();</div></div><div class="">// Adding a new pass here which keeps register mask information across function calls.</div><div class="">.</div><div class="">.</div><div class="">.</div><div class="">}</div><div class=""><br class=""></div><div class="">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></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 class=""><br class=""> <span class=""> </span>// Add a register mask operand representing the call-preserved registers.<br class=""> <span class=""> </span>const TargetRegisterInfo *TRI = Subtarget.getRegisterInfo();<br class=""> <span class=""> </span>const uint32_t *Mask =<br class=""> <span class=""> </span>TRI->getCallPreservedMask(DAG.getMachineFunction(), CallConv);<br class=""> <span class=""> </span>assert(Mask && "Missing call preserved mask for calling convention");<br class=""> <span class=""> </span>Ops.push_back(DAG.getRegisterMask(Mask));<br class=""><br class="">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 class=""><br class="">const uint32_t *<br class="">PPCRegisterInfo::getCallPreservedMask(const MachineFunction &MF,<br class=""> <span class=""> </span>CallingConv::ID CC) const {<br class=""> <span class=""> </span>const PPCSubtarget &Subtarget = MF.getSubtarget<PPCSubtarget>();<br class=""> <span class=""> </span>...<br class=""> <span class=""> </span>return TM.isPPC64() ? (Subtarget.hasAltivec() ? CSR_SVR464_Altivec_RegMask<br class=""> <span class=""> </span>: CSR_SVR464_RegMask)<br class=""> <span class=""> </span>: (Subtarget.hasAltivec() ? CSR_SVR432_Altivec_RegMask<br class=""> <span class=""> </span>: CSR_SVR432_RegMask);<br class="">}<br class=""><br class="">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 class=""></div></div></blockquote><div class="">I am thinking to add a simple Immutable pass MachineRegisterUsageInfo similar to MachineBranchProbabilityInfo that can maintain RegisterUsageInformation per function. Can it be simply done by using UsedPhysRegMask from MachineRegisterInfo ??</div></div></div></blockquote><div class=""><br class=""></div></div></div><div class="">No, like the comment said, UsedPhysRegMask gives only the registers clobbered by calls:</div><div class=""><span style="font-family:Menlo;font-size:10px" class="">// This bit vector represents all the registers clobbered by function calls.</span> </div><div class=""><br class=""></div>You want to build this information yourself on top of MachineRegisterInfo::<span style="font-family:Menlo;font-size:10px" class="">isPhysRegModified</span></div></div></blockquote><div class="">Ok but then the time complexity will be O(n) n = number of physical register on the target. Am I going correct?</div></div></div></blockquote><div class=""><br class=""></div></div></div><div class="">Yes, this is correct.</div><span class=""><br class=""><blockquote class=""><div class=""><div class="gmail_quote" 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"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><span class=""><blockquote class=""><div class=""><div class="gmail_quote" 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"><div class=""> </div><div class="">Here getCallPreservedMask will call API provided by MachineRegisterUsageInfo to avail the exact register mask but how it can know that the function is already codegen or it will query each time when getCallPreservedMask is called and of available MachineRegisterUsageInfo will return the details otherwise simply return NULL.</div><div class="">So changes will be now in TargetRegisterInfo implementation for each target right ??</div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div style="font-family:arial,helvetica,sans-serif;font-size:10pt" class=""><br class="">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 class=""><br class=""> 1. Not all of the target code calls getCallPreservedMask, but sometimes calls other similar target-specific functions (e.g. getTLSCallPreservedMask).<br class=""> 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 class=""><br class="">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.<span class=""><br class=""><br class=""><blockquote style="border-left:2px solid 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" class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""></div><div class=""><br class=""></div><div class="">I think this also applies in someway to Mehdi Amini's idea to keep a ModulePass for bookkeeping but then existing register allocators will be required to change so that the code can query the ModulePass for RegMaskBits for particular function.</div></div></div></div></blockquote></span>I think that the simplest way to do this is to create an immutable analysis pass (e.g. BasicAA) that keeps the cache of the computed register masks. This is somewhat similar in spirit to how the 'AssumptionCache' analysis works at the IR level. This analysis can then be created by lib/CodeGen/Passes.cpp early, and then queried and passed around later by the CodeGen/Target code. Because it is an immutable analysis, it won't get destroyed until the very end, which is also important because, I imagine, it will need to own the memory associated with the generated register masks.<span class=""><font color="#888888" class=""><br class=""><br class=""> -Hal</font></span><span class=""><br class=""><blockquote style="border-left:2px solid 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" class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""></div><div class=""><br class=""></div><div class="">Vivek</div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><span class=""><span class=""><font color="#888888" class=""><div class=""><br class=""></div></font></span></span></div></div></blockquote><div class="">Yes for propagating register usage approach we don't need MachineModulePass</div><span class=""><font color="#888888" class=""><div class=""> </div><div class="">Vivek</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><span class=""><font color="#888888" class=""><div class=""></div><div class="">-- </div><div class="">Mehdi</div><div class=""><br class=""></div></font></span></div></div></blockquote></font></span></div><br class=""></div></div></blockquote></div><br class=""></div></div></blockquote><br class=""><br class=""><br class=""></span><span class="">--<span class=""> </span><br class=""><div class=""><span class=""></span>Hal Finkel<br class="">Assistant Computational Scientist<br class="">Leadership Computing Facility<br class="">Argonne National Laboratory</div></span></div></div></blockquote></div></div></blockquote></span></div></div></blockquote></div></div></blockquote></span></div><br class=""></div></blockquote></div><br class=""></div>
</blockquote><br class=""><br class=""><br class="">-- <br class=""><div class=""><span class=""></span>Hal Finkel<br class="">Assistant Computational Scientist<br class="">Leadership Computing Facility<br class="">Argonne National Laboratory<span class=""></span><br class=""></div></div></div></div></div></blockquote></div><br class=""></div></div>
</blockquote><br class=""><br class=""><br class="">-- <br class=""><div class=""><span name="x" class=""></span>Hal Finkel<br class="">Assistant Computational Scientist<br class="">Leadership Computing Facility<br class="">Argonne National Laboratory<span name="x" class=""></span><br class=""></div></div></div></div></div></blockquote></div></div></div><br class=""></div></div>
</blockquote></div><br class=""></div>
</div></blockquote></div><br class=""></body></html>