[llvm-dev] [GSoC 2016] Interprocedural Register Allocation - Introduction and Feedback

Tue May 10 21:29:31 PDT 2016

*Vivek Pandya*

On Wed, May 11, 2016 at 6:36 AM, Hal Finkel <hfinkel at anl.gov> wrote:

>
>
> ------------------------------
>
> *From: *"vivek pandya" <vivekvpandya at gmail.com>
> *To: *"llvm-dev" <llvm-dev at lists.llvm.org>, "Tim Amini Golling" <
> mehdi.amini at apple.com>, "Hal Finkel" <hfinkel at anl.gov>
> *Cc: *"Quentin Colombet" <qcolombet at apple.com>
> *Sent: *Tuesday, May 10, 2016 2:59:16 PM
> *Subject: *[GSoC 2016] Interprocedural Register Allocation - Introduction
> and Feedback
>
> Hello LLVM Community,
>
>
> Sorry for delay as I was busy in final exams.
>
>
> 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.
>
>
> IPRA can reduce code size and runtime of programs by allocating register
> across the module and procedure boundaries.
>
>
> I have identified some old but effective research work on this area.
>
> I want community's feedback for feasibility of these approach and I am
> targeting to implement two of them during this project.
>
>
> 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.
>
>
> 1) Compile time ----- Minimizing register usage penalty at procedure calls
> - http://dl.acm.org/citation.cfm?id=53999
>
> ====================================================================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
> https://groups.google.com/d/topic/llvm-dev/HOYAXv3m1LY/discussion
>
> 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.
>
>
> 2) Link time ----- Global register allocation at link time -
> http://dl.acm.org/citation.cfm?id=989415
>
> ====================================================================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.
>
> For these particular method help me to analyze feasibility:
>
> 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
>
> 2) Can llvm write informative commands to object files?
>
> 3) Can LTO is capable of leveraging those commands?
>
> 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.
>
>
> 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.
>
> Sorry my mistake here by first part I mean 1) requirement in the link time
approach.

> 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).
>
Yes for propogating register usage approach we don't need MachineModulePass.

Sincerely,
Vivek

>
>  -Hal
>
>
> 3) Compile time ----- Minimum cost interprocedural register allocation -
> http://dl.acm.org/citation.cfm?id=237780
>
> 4) Compile time ----- Register allocation across procedure and module
> boundaries - http://dl.acm.org/citation.cfm?id=93551
>
>
> I am aspiring for true IPRA so that I would require lot of help but I
> think with proper guidance it is achievable.
>
> Any help/hints would be appreciated!
>
>
> Sincerely,
>
> Vivek
>
>
>
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160511/119c2ff2/attachment-0001.html>