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

> 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

>From the research and code I've seen - Doesn't this break regalloc
down into a global and location allocation strategy? (maybe I'm
remembering incorrectly)

On Wed, Mar 23, 2016 at 12:04 PM, Mehdi Amini via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
>> 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
>
> _______________________________________________
> 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 9:34 AM, Mehdi Amini <mehdi.amini at apple.com>
wrote:
>
> > 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.
>
> Yes most of InterProcedural analysis in GCC uses call graphs so this can
be very useful.
> --
> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160323/8883a26c/attachment.html>

*Vivek Pandya*


On Wed, Mar 23, 2016 at 9:43 AM, C Bergström <cbergstrom at pathscale.com>
wrote:
> From the research and code I've seen - Doesn't this break regalloc
> down into a global and location allocation strategy? (maybe I'm
> remembering incorrectly)
>
> Yes I think you are correct. If I recall IP Reg allocation allocates some
registers to varibale that are used across the procedures and after that
 remaining allocation will be done at IP level.
> On Wed, Mar 23, 2016 at 12:04 PM, Mehdi Amini via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> >
> >> 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
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160323/ec43ac35/attachment-0001.html>

Hello Mehdi,

   could I ask you if you could share your patch?
We are testing whether at least some leaf call register allocation optimization
could help and you patch or some pointers on what to do will be very useful.

Thank you
   Adam


On Wed, 23 Mar 2016 05:04:41 +0100, Mehdi Amini via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>
>> 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.

Hi,

Here is the patch (I already sent it in this thread):

-------------- next part --------------
A non-text attachment was scrubbed...
Name: CGCCC.diff
Type: application/octet-stream
Size: 1603 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160410/bfc06dd3/attachment.obj>
-------------- next part --------------


Note that Vivek submitted a proposal to implement this as a GSOC project,
we'll know soon if he gets selected.

-- 
Mehdi

> On Apr 10, 2016, at 8:10 AM, Adam Husar <husar at codasip.com> wrote:
> 
> Hello Mehdi,
> 
>  could I ask you if you could share your patch?
> We are testing whether at least some leaf call register allocation
optimization could help and you patch or some pointers on what to do will be
very useful.
> 
> Thank you
>  Adam
> 
> 
> On Wed, 23 Mar 2016 05:04:41 +0100, Mehdi Amini via llvm-dev <llvm-dev
at lists.llvm.org> wrote:
> 
>> 
>>> 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.