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

Tue May 10 12:59:16 PDT 2016

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?

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.

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160511/89e0708a/attachment.html>