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

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
>

*Vivek Pandya*


On Wed, Mar 23, 2016 at 10:18 PM, Quentin Colombet <qcolombet at
apple.com>
wrote:
> The pass manager already has support for calligraph connected region IIRC.
>
If I am not wrong Quentin and Mehdi Amini refers to CallGraphSCCPass.cpp
> 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.
>
> Which operands should be kept in registers between function call should be
justifying and for that we can take help from some research work ( some of
I mentioned previously I have to read it again. Please suggest some more
relevant papers  ) once that is implemented we can update the regmask for a
call instruction to indicate which registers are free to be used. Am I
going in correct direction ?

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.).
>
> Here for calling convention do you mean that has to be handle for
different kind of backends differently  or you are referring some thing I
don't know. I don't understand what do you mean by 'convey the right
information to other tool' if we have updated regmask for a call
instruction then MachineFunction should be able to reflect that fact in
MachineFunction pass which is used for intra-procedural register
allocation, all we have done is allocated some registers that should live
across the function call.

Sincerely,
Vivek

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

> On Mar 23, 2016, at 2:44 PM, vivek pandya <vivekvpandya at gmail.com>
wrote:
> 
> 
> 
> Vivek Pandya
> 
> 
> On Wed, Mar 23, 2016 at 10:18 PM, Quentin Colombet <qcolombet at
apple.com <mailto:qcolombet at apple.com>> wrote:
> The pass manager already has support for calligraph connected region IIRC.
> If I am not wrong Quentin and Mehdi Amini refers to CallGraphSCCPass.cpp 
Yes.
> 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.
> 
> Which operands should be kept in registers between function call should be
justifying and for that we can take help from some research work ( some of I
mentioned previously I have to read it again. Please suggest some more relevant
papers  ) once that is implemented we can update the regmask for a call
instruction to indicate which registers are free to be used. Am I going in
correct direction ?
I do not know if there is a paper on this as this is quite trivial, but IIRC
Open64 register allocator does that.
Anyhow, the algo is:
Given a call graph SCC
- Allocate the function with no calls or where each callee has been allocated
- Propagate the clobbered registers to the callers of that function by updating
the related regmasks on the callsites.
Repeat until no more candidate.

Allocate remaining functions “normally”.
> 
> 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.).
> 
> Here for calling convention do you mean that has to be handle for different
kind of backends differently  or you are referring some thing I don't know.
I don't understand what do you mean by 'convey the right information to
other tool' if we have updated regmask for a call instruction then
MachineFunction should be able to reflect that fact in MachineFunction pass
which is used for intra-procedural register allocation, all we have done is
allocated some registers that should live across the function call.
My mistake, I though you had in mind what I call a “true” inter procedural
registers allocator: one that changes the allocation at function boundaries as
well. I.e., it may choose that it is more efficient to put the first argument of
function foo is register FP0 even if the ABI says R0.
With this kind of scheme, you break the ABI (and you need LTO to be allowed to
do that), you need to “dynamically” adjust the calling convention to what the
register allocator chooses, and moreover you need to be able to communicate to
the other tools (dynamic linker, debugger, etc.) where are the things that are
usually defined by the ABI, like the frame pointer, the return value, etc.

Cheers,
-Quentin
> 
> Sincerely,
> Vivek
> 
> Cheers,
> Q.
> > On Mar 22, 2016, at 6:04 PM, Matthias Braun <mbraun at apple.com
<mailto: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 <mailto: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 <mailto: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 <mailto: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 <mailto:llvm-dev at
lists.llvm.org>
> >>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> >>>>
> >>>
> >>>
> >>>
> >>> --
> >>> Sanjoy Das
> >>> http://playingwithpointers.com
<http://playingwithpointers.com/>
> >>
> >>
> >>
> >> --
> >> Sanjoy Das
> >> http://playingwithpointers.com
<http://playingwithpointers.com/>
> >
> 
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160323/f9ffc131/attachment-0001.html>