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

[vivek pandya via llvm-dev]

*Vivek Pandya*


On Thu, Mar 24, 2016 at 3:29 AM, Quentin Colombet <qcolombet at apple.com>
wrote:

>
> 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>
> 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.
>
> I feel that as I don't have exposure to LTO in LLVM ( for GCC I have the
basic idea ) I should not go with true register allocator  at this stage
instead minimizing spill code by propagating calles' register usage to
caller would be enough.

Cheers,
> -Quentin
>
>
> 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/20160325/fe9384db/attachment.html>