[llvm-dev] [GSoC 2016] [Weekly Status] Interprocedural Register Allocation

[vivek pandya via llvm-dev]

Dear Community,

This week I got my patch reviewed by mentors and based on that I have done
changes. Also we have identified a problem with callee-saved registers
being marked as clobbered registers so we fixed that bug. I have described
other minor changes in following section.

It was expected to get the patch committed by end of this week but due to
unexpected mistake I was not able to complete writing test cases. Sorry for
that.
I had build llvm with ipra enable by default and that build files were on
my path ! Due to that next time I tried to build llvm it was terribly slow
 (almost 1 hour for 10% build ). I spend to much time on fixing this by
playing around with environment variables, cmake options etc.
But I think this is a serious concern, we need to think verify this time
complexity other wise building a large software with IPRA enable would be
very time consuming.

The toughest part for this week was to get lit and FileCheck work as you
expect them to work, specially when analysis pass prints info on stdio and
there is also a output file generated by llc or opt command.

So here is brief summary :

Implementation:
============

RegUsageInfoCollector is now Calling Convention aware so that RegMask does
not mark callee saved register as clobbered register. Due to this register
allocator can use callee saved register for caller.
PhysicalRegisterUsageInfo.cpp renamed to RegisterUsageInfo.cpp.
StringMap used in RegisterUsageInfo.cpp is replaced by DenseMap of
GlobalVariable * to RegMask.
DummyCGSCCPass moved from TargetPassConfig.cpp to CallGraphSCCPass.h.
Minor correction in comments, changes to adhere coding standards of LLVM.

Testing:
=====

The above mentioned changes has been tested with SNU-Realtime benchmarks.

Studied lit and FileCheck tool and written simple test to verify
functionality of coding.


Study and other:

============

Studied some examples of lit compatible llvm IR with comments to RUN test
cases, FileCheck tool syntax and how to use it with in lit infrastructure.

I also understand X86 calling convention in more details.

I also studied basic concepts in llvm IR language while reading .ll files
written for lit.

I learned about rvalue references and move semantics introduced in C++11.


Plan for next week:

1) Get the patch committed along with proper tets cases.

2) Analyse time complexity of the approach.

3) Make target specific pass to CodeGen as it seems it is not required to
be target specific.

4) If possible build a large application with ipra enable and analyze the
impact.


Sincerely,

Vivek


On Sat, May 28, 2016 at 7:31 PM, vivek pandya <vivekvpandya at gmail.com>
wrote:

> Dear community,
>
> This is to brief you the progress of Interprocedural Register Allocation,
> for those who are interested to see the progress in terms of code please
> consider http://reviews.llvm.org/D20769
> This patch contains simple infrastructure to propagate register usage
> information of callee to caller in call graph. The code generation order is
> changed to follow bottom up order on call graph , Thanks to Mehdi Amini for
> the patch for the same !  I will write a blog on this very soon.
>
> So during this week as per the schedule proposed it should be study
> related infrastructure in LLVM and finalizing an approach for IPRA, but
> instead I am able to implement a working (may not be fully correct)
> prototype because I have used community bonding period to discuss and learn
> related stuffs from the mentors and also due to patch for CodeGen
> reordering was provided by dear mentor Mehdi Amini.
>
> So I conclude the work done during this week as follows:
> Implementation :
> ============
> Following passes have been implemented during this week: An immutable pass
> to store competed RegMask, a  machine function pass that iterates through
> each registers and check if it is used or not and based on that details
> create a RegMask and a target specific machine function pass that uses the
> RegMask created by second pass and propagates information by updating call
> instructions RegMask. To update the RegMask of MI , setRegMask() function
> has been added to MachineOperand, a command line option -enable-ipra and
> debug type -debug-only=“ipra" has been added to control the optimization
> through llc.
>
> Testing:
> =====
> The above mentioned implementation has been tested over SNU-Real-Time
> benchmark suit (http://www.cprover.org/goto-cc/examples/snu.html) and
> some simple programs that uses library function ( for a library function
> register allocation is not done by LLVM so this optimization will simply
> skip them)
>
> Study and Other:
> =============
> I have learned following things in LLVM, how it stores reg clobbering
> information? how it is used by Reg allocators through LivePhysRegs,
> LiveRegMatrix and other related passes? How to schedule a pass using
> TargetPassConfig and TargetMachine? What are called callee saved registers?
> What is an Immutable Pass? Apart from that I have also learned how to use
> phabricator to send review request. I have also read some related
> literatures.
>
> During this week though task was to schedule the passes in proper order so
> that dependencies of related passes are satisfied.
>
> Plan for next week:
> 1) Perform more testing and debug any known issue
> 2) Fine ture the implementation so as to eliminate any unnecessary work
> 3) During the testing from the stats I have observed that IPRA does not
> always improve the work of IntraProcedural register allocators and it is
> also observer that the amount of benefit (in terms of spilled live ranges )
> is not deterministic. So I would like to find reasons for this behavior.
> 4) Start implementing target specific pass for other targets if review
> passes properly with no major bugs.
>
> Please provide any feedback/suggestion including for format of this email.
>
> I would also like to thanks my mentors Mehdi Amini , Hal Finkel, Quentin
> Colombet, Matthias Braun and other community members for providing quick
> help every time when I asked ( I have got replies even after 8 PM ( PDT) !
> ) .
>
> Sincerely,
> Vivek
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160605/a01010bc/attachment.html>