llvm dev - Mar 2016 - Open Project : Inter-procedural Register Allocation [GSoC 2016]

Apologies: didn't notice how old this thread is before replying.

On Tue, Mar 22, 2016 at 5:24 PM, Sanjoy Das
<sanjoy at playingwithpointers.com> wrote:
> Hi Vivek,
>
> [+CC Matthias, Quentin]
>
> Inter-procedural register allocation can be a big win, but my estimate
> is that it will be challenging to complete within one summer unless
> you're already familiar with LLVM's register allocator.
>
> I've CC'ed some people who can give you some more detailed
information.
>
> -- Sanjoy
>
>
> On Tue, Feb 9, 2016 at 9:17 PM, vivek pandya via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>> Hello Community,
>>
>> I would like to know status of the project and also importance of it.
If the
>> project is still open I would like to work on GSoC 2016 proposal for
>> Inter-procedural Register Allocation, in that case please also suggest
>> possible mentor or let me know if anyone is willing to be mentor for
this.
>>
>> Sincerely,
>> Vivek Pandya
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>
>
> --
> Sanjoy Das
> http://playingwithpointers.com


-- 
Sanjoy Das
http://playingwithpointers.com

No need to apologize this thread surely deserved some answers :)

From my perspective this project sounds doable. I would expect the register
allocation parts to be not too hard: I imagine this being just distilling a new
clobber regmask after allocating a function. I would expect the challenging (or
annoying) part to get a machine module pass (or a similar mechanism to influence
the order in which functions are processed) and a callgraph in the backend. So
this might end up being more pass manager / infrastructure work than register
allocation.

I'd be happy to answer detail questions or give guidance on the register
allocation aspects.

- Matthias
> On Mar 22, 2016, at 5:27 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> Apologies: didn't notice how old this thread is before replying.
> 
> On Tue, Mar 22, 2016 at 5:24 PM, Sanjoy Das
> <sanjoy at playingwithpointers.com> wrote:
>> Hi Vivek,
>> 
>> [+CC Matthias, Quentin]
>> 
>> Inter-procedural register allocation can be a big win, but my estimate
>> is that it will be challenging to complete within one summer unless
>> you're already familiar with LLVM's register allocator.
>> 
>> I've CC'ed some people who can give you some more detailed
information.
>> 
>> -- Sanjoy
>> 
>> 
>> On Tue, Feb 9, 2016 at 9:17 PM, vivek pandya via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>>> Hello Community,
>>> 
>>> I would like to know status of the project and also importance of
it. If the
>>> project is still open I would like to work on GSoC 2016 proposal
for
>>> Inter-procedural Register Allocation, in that case please also
suggest
>>> possible mentor or let me know if anyone is willing to be mentor
for this.
>>> 
>>> Sincerely,
>>> Vivek Pandya
>>> 
>>> 
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>> 
>> 
>> 
>> 
>> --
>> Sanjoy Das
>> http://playingwithpointers.com
> 
> 
> 
> -- 
> Sanjoy Das
> http://playingwithpointers.com

> On Mar 22, 2016, at 6:04 PM, Matthias Braun via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> No need to apologize this thread surely deserved some answers :)
> 
> From my perspective this project sounds doable. I would expect the register
allocation parts to be not too hard: I imagine this being just distilling a new
clobber regmask after allocating a function. I would expect the challenging (or
annoying) part to get a machine module pass (or a similar mechanism to influence
the order in which functions are processed) and a callgraph in the backend.
I have a very tiny patch that wrap the backend in a CGSCC pass manager, which
will achieve what is needed here I believe: i.e. running CodeGen for every
callee before any caller.
I can rebase it if anyone is interested.

-- 
Mehdi


> So this might end up being more pass manager / infrastructure work than
register allocation.
> 
> I'd be happy to answer detail questions or give guidance on the
register allocation aspects.
> 
> - Matthias
> 
>> On Mar 22, 2016, at 5:27 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
>> 
>> Apologies: didn't notice how old this thread is before replying.
>> 
>> On Tue, Mar 22, 2016 at 5:24 PM, Sanjoy Das
>> <sanjoy at playingwithpointers.com> wrote:
>>> Hi Vivek,
>>> 
>>> [+CC Matthias, Quentin]
>>> 
>>> Inter-procedural register allocation can be a big win, but my
estimate
>>> is that it will be challenging to complete within one summer unless
>>> you're already familiar with LLVM's register allocator.
>>> 
>>> I've CC'ed some people who can give you some more detailed
information.
>>> 
>>> -- Sanjoy
>>> 
>>> 
>>> On Tue, Feb 9, 2016 at 9:17 PM, vivek pandya via llvm-dev
>>> <llvm-dev at lists.llvm.org> wrote:
>>>> Hello Community,
>>>> 
>>>> I would like to know status of the project and also importance
of it. If the
>>>> project is still open I would like to work on GSoC 2016
proposal for
>>>> Inter-procedural Register Allocation, in that case please also
suggest
>>>> possible mentor or let me know if anyone is willing to be
mentor for this.
>>>> 
>>>> Sincerely,
>>>> Vivek Pandya
>>>> 
>>>> 
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>> 
>>> 
>>> 
>>> 
>>> --
>>> Sanjoy Das
>>> http://playingwithpointers.com
>> 
>> 
>> 
>> -- 
>> Sanjoy Das
>> http://playingwithpointers.com
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

*Vivek Pandya*


On Wed, Mar 23, 2016 at 5:57 AM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Apologies: didn't notice how old this thread is before replying.
>
> Thank you for reply !
At the time of this thread I have also gathered some papers related to
this.
Minimum Cost Interprocedural Register Allocation - Steven M. Kurlander,
Charles N. Fischer
Global Register Allocation at Link Time - David W. Wall
Interprocedural Register Allocation for Lazy Function Languages - Urban
Boquist
A Simple Interprocedural Register Allocation Algorithm and Its
Effectiveness for LISP - PETER A. STEENKISTE and JOHN L. HENNESSY

But due to less interest from the community I thought that this is not
useful for LLVM. Apparently GCC has some work on this .
> On Tue, Mar 22, 2016 at 5:24 PM, Sanjoy Das
> <sanjoy at playingwithpointers.com> wrote:
> > Hi Vivek,
> >
> > [+CC Matthias, Quentin]
> >
> > Inter-procedural register allocation can be a big win, but my estimate
> > is that it will be challenging to complete within one summer unless
> > you're already familiar with LLVM's register allocator.
> >
> > I've CC'ed some people who can give you some more detailed
information.
> >
> > -- Sanjoy
> >
> >
> > On Tue, Feb 9, 2016 at 9:17 PM, vivek pandya via llvm-dev
> > <llvm-dev at lists.llvm.org> wrote:
> >> Hello Community,
> >>
> >> I would like to know status of the project and also importance of
it.
> If the
> >> project is still open I would like to work on GSoC 2016 proposal
for
> >> Inter-procedural Register Allocation, in that case please also
suggest
> >> possible mentor or let me know if anyone is willing to be mentor
for
> this.
> >>
> >> Sincerely,
> >> Vivek Pandya
> >>
> >>
> >> _______________________________________________
> >> LLVM Developers mailing list
> >> llvm-dev at lists.llvm.org
> >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >>
> >
> >
> >
> > --
> > Sanjoy Das
> > http://playingwithpointers.com
>
>
>
> --
> Sanjoy Das
> http://playingwithpointers.com
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160323/aff22cb3/attachment.html>

*Vivek Pandya*


On Wed, Mar 23, 2016 at 6:34 AM, Matthias Braun <mbraun at apple.com>
wrote:
> No need to apologize this thread surely deserved some answers :)
>
> From my perspective this project sounds doable. I would expect the
> register allocation parts to be not too hard: I imagine this being just
> distilling a new clobber regmask after allocating a function. I would
> expect the challenging (or annoying) part to get a machine module pass (or
> a similar mechanism to influence the order in which functions are
> processed) and a callgraph in the backend. So this might end up being more
> pass manager / infrastructure work than register allocation.
>
> I'd be happy to answer detail questions or give guidance on the
register
> allocation aspects.
>
> Actually  I have a draft proposal for Add machine Module pass ( which is
not a very concrete approach )
https://docs.google.com/document/d/17ROHuyj0Tyg2SXEMoutpAedEXXuGxj8-zgTuHBRp4HY/edit?usp=sharing
I was thinking to implement a simple Interprocedural Register Allocator as
an example that uses this work.But that may be too much of work to complete
in the summer.

- Matthias
>
> > On Mar 22, 2016, at 5:27 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
> wrote:
> >
> > Apologies: didn't notice how old this thread is before replying.
> >
> > On Tue, Mar 22, 2016 at 5:24 PM, Sanjoy Das
> > <sanjoy at playingwithpointers.com> wrote:
> >> Hi Vivek,
> >>
> >> [+CC Matthias, Quentin]
> >>
> >> Inter-procedural register allocation can be a big win, but my
estimate
> >> is that it will be challenging to complete within one summer
unless
> >> you're already familiar with LLVM's register allocator.
> >>
> >> I've CC'ed some people who can give you some more detailed
information.
> >>
> >> -- Sanjoy
> >>
> >>
> >> On Tue, Feb 9, 2016 at 9:17 PM, vivek pandya via llvm-dev
> >> <llvm-dev at lists.llvm.org> wrote:
> >>> Hello Community,
> >>>
> >>> I would like to know status of the project and also importance
of it.
> If the
> >>> project is still open I would like to work on GSoC 2016
proposal for
> >>> Inter-procedural Register Allocation, in that case please also
suggest
> >>> possible mentor or let me know if anyone is willing to be
mentor for
> this.
> >>>
> >>> Sincerely,
> >>> Vivek Pandya
> >>>
> >>>
> >>> _______________________________________________
> >>> LLVM Developers mailing list
> >>> llvm-dev at lists.llvm.org
> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >>>
> >>
> >>
> >>
> >> --
> >> Sanjoy Das
> >> http://playingwithpointers.com
> >
> >
> >
> > --
> > Sanjoy Das
> > http://playingwithpointers.com
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160323/27062bb9/attachment.html>

The pass manager already has support for calligraph connected region IIRC.
As for the regmask part, we probably could hack something up in a week or so,
but I believe this is not what Vivek had in mind.

I think the main challenge of a real inter-procedural register allocator is to
change all of the calling convention dynamically and more importantly convey the
right information to other tools (via CFA, CFI, etc.).

Cheers,
Q.
> On Mar 22, 2016, at 6:04 PM, Matthias Braun <mbraun at apple.com>
wrote:
> 
> No need to apologize this thread surely deserved some answers :)
> 
> From my perspective this project sounds doable. I would expect the register
allocation parts to be not too hard: I imagine this being just distilling a new
clobber regmask after allocating a function. I would expect the challenging (or
annoying) part to get a machine module pass (or a similar mechanism to influence
the order in which functions are processed) and a callgraph in the backend. So
this might end up being more pass manager / infrastructure work than register
allocation.
> 
> I'd be happy to answer detail questions or give guidance on the
register allocation aspects.
> 
> - Matthias
> 
>> On Mar 22, 2016, at 5:27 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
>> 
>> Apologies: didn't notice how old this thread is before replying.
>> 
>> On Tue, Mar 22, 2016 at 5:24 PM, Sanjoy Das
>> <sanjoy at playingwithpointers.com> wrote:
>>> Hi Vivek,
>>> 
>>> [+CC Matthias, Quentin]
>>> 
>>> Inter-procedural register allocation can be a big win, but my
estimate
>>> is that it will be challenging to complete within one summer unless
>>> you're already familiar with LLVM's register allocator.
>>> 
>>> I've CC'ed some people who can give you some more detailed
information.
>>> 
>>> -- Sanjoy
>>> 
>>> 
>>> On Tue, Feb 9, 2016 at 9:17 PM, vivek pandya via llvm-dev
>>> <llvm-dev at lists.llvm.org> wrote:
>>>> Hello Community,
>>>> 
>>>> I would like to know status of the project and also importance
of it. If the
>>>> project is still open I would like to work on GSoC 2016
proposal for
>>>> Inter-procedural Register Allocation, in that case please also
suggest
>>>> possible mentor or let me know if anyone is willing to be
mentor for this.
>>>> 
>>>> Sincerely,
>>>> Vivek Pandya
>>>> 
>>>> 
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>> 
>>> 
>>> 
>>> 
>>> --
>>> Sanjoy Das
>>> http://playingwithpointers.com
>> 
>> 
>> 
>> -- 
>> Sanjoy Das
>> http://playingwithpointers.com
>