<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"vivek pandya" <vivekvpandya@gmail.com><br><b>To: </b>"llvm-dev" <llvm-dev@lists.llvm.org>, "Tim Amini Golling" <mehdi.amini@apple.com>, "Hal Finkel" <hfinkel@anl.gov><br><b>Cc: </b>"Quentin Colombet" <qcolombet@apple.com><br><b>Sent: </b>Tuesday, May 10, 2016 2:59:16 PM<br><b>Subject: </b>[GSoC 2016] Interprocedural Register Allocation - Introduction and Feedback<br><br><div dir="ltr"><p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">Hello LLVM Community,<br></p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">Sorry for delay as I was busy in final exams.</p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p 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.</p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p 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.</p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">I have identified some old but effective research work on this area.</p>
<p 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.</p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p 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.</p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">1) Compile time ----- Minimizing register usage penalty at procedure calls - <a href="http://dl.acm.org/citation.cfm?id=53999" target="_blank">http://dl.acm.org/citation.cfm?id=53999</a></p>
<p 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 <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></p>
<p 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.</p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">2) Link time ----- Global register allocation at link time - <a href="http://dl.acm.org/citation.cfm?id=989415" target="_blank">http://dl.acm.org/citation.cfm?id=989415</a></p>
<p 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. </p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">For these particular method help me to analyze feasibility: </p>
<p 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 </p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">2) Can llvm write informative commands to object files?</p>
<p id="DWT19740" style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">3) Can LTO is capable of leveraging those commands? <br></p></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. 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><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); 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>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p id="DWT19739" 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.</p></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><br> -Hal<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); 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>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">3) Compile time ----- Minimum cost interprocedural register allocation - <a href="http://dl.acm.org/citation.cfm?id=237780" target="_blank">http://dl.acm.org/citation.cfm?id=237780</a></p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">4) Compile time ----- Register allocation across procedure and module boundaries - <a href="http://dl.acm.org/citation.cfm?id=93551" target="_blank">http://dl.acm.org/citation.cfm?id=93551</a></p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p id="DWT19738" style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">I am aspiring for true IPRA so that I would require lot of help but I think with proper guidance it is achievable. <br></p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">Any help/hints would be appreciated!</p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica; min-height: 14px;"><br></p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">Sincerely,</p>
<p style="margin: 0px; font-size: 12px; line-height: normal; font-family: Helvetica;">Vivek</p><div><br></div>
</div>
</blockquote><br><br><br>-- <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></body></html>