[llvm-dev] [GSoC 2016] Interprocedural Register Allocation - Introduction and Feedback

Wed May 18 11:00:38 PDT 2016

*Vivek Pandya*

On Wed, May 18, 2016 at 11:25 PM, Quentin Colombet <qcolombet at apple.com>
wrote:

>
> On May 18, 2016, at 10:46 AM, vivek pandya <vivekvpandya at gmail.com> wrote:
>
>
>
> *Vivek Pandya*
>
>
> On Wed, May 11, 2016 at 4:01 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>
>>
>> ------------------------------
>>
>> *From: *"vivek pandya" <vivekvpandya at gmail.com>
>> *To: *"Mehdi Amini" <mehdi.amini at apple.com>
>> *Cc: *"Hal Finkel" <hfinkel at anl.gov>, "Quentin Colombet" <
>> qcolombet at apple.com>, "llvm-dev" <llvm-dev at lists.llvm.org>, "Matthias
>> Braun" <matze at braunis.de>
>> *Sent: *Wednesday, May 11, 2016 3:15:03 AM
>> *Subject: *Re: [GSoC 2016] Interprocedural Register Allocation -
>> Introduction and Feedback
>>
>>
>>
>>
>> *Vivek Pandya*
>>
>>
>> On Wed, May 11, 2016 at 10:02 AM, vivek pandya <vivekvpandya at gmail.com>
>> wrote:
>>
>>>
>>>
>>> *Vivek Pandya*
>>>
>>>
>>> On Wed, May 11, 2016 at 9:43 AM, Mehdi Amini <mehdi.amini at apple.com>
>>> wrote:
>>>
>>>>
>>>> On May 10, 2016, at 6:06 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>>>>
>>>>
>>>>
>>>> ------------------------------
>>>>
>>>> *From: *"vivek pandya" <vivekvpandya at gmail.com>
>>>> *To: *"llvm-dev" <llvm-dev at lists.llvm.org>, "Tim Amini Golling" <
>>>> mehdi.amini at apple.com>, "Hal Finkel" <hfinkel at anl.gov>
>>>> *Cc: *"Quentin Colombet" <qcolombet at apple.com>
>>>> *Sent: *Tuesday, May 10, 2016 2:59:16 PM
>>>> *Subject: *[GSoC 2016] Interprocedural Register Allocation -
>>>> Introduction and Feedback
>>>>
>>>> Hello LLVM Community,
>>>>
>>>> Sorry for delay as I was busy in final exams.
>>>>
>>>> I am Vivek from India. Thanks for choosing my proposal for
>>>> Interprocedural Register Allocation (IPRA) in LLVM. Mehdi Amini and Hal
>>>> Finkel will be mentoring me for this project.
>>>>
>>>> IPRA can reduce code size and runtime of programs by allocating
>>>> register across the module and procedure boundaries.
>>>>
>>>> I have identified some old but effective research work on this area.
>>>> I want community's feedback for feasibility of these approach and I am
>>>> targeting to implement two of them during this project.
>>>>
>>>> Here is list of the papers, I have read first two papers and I would
>>>> like to discuss those approach first, I will read other two paper then
>>>> initiate discussion for them as well. All I want is to find out a concrete
>>>> implementation plan before 23 May, 2016 and for that I need community's
>>>> help.
>>>>
>>>> 1) Compile time ----- Minimizing register usage penalty at procedure
>>>> calls - http://dl.acm.org/citation.cfm?id=53999
>>>> ====================================================================In
>>>> this approach intra-procedural register allocation is used as base but
>>>> machine code generation order is bottom up traversal of call graph and
>>>> inter-procedural effect is achieved by propagating register usage
>>>> information of callee function to caller (i.e child to parent in CallGraph)
>>>> so that caller can use different registers than callee and can save load
>>>> store cost at procedure call, this is not trivial as it seems due to
>>>> recursive calls, library function usage etc. Also for upper region of the
>>>> graph in this technique available number of registers might become zero in
>>>> that case it should fall back to normal load store at procedure call. Apart
>>>> from these difficulties other difficulties have been identified please
>>>> follow this mail-chain
>>>> https://groups.google.com/d/topic/llvm-dev/HOYAXv3m1LY/discussion
>>>> My mentor has already provided me a patch that alters code generation
>>>> order as per bottom up call graph traversal, I am working from that point
>>>> now. Any other help/suggestion is always welcomed.
>>>>
>>>> 2) Link time ----- Global register allocation at link time -
>>>> http://dl.acm.org/citation.cfm?id=989415
>>>> ====================================================================In
>>>> this particular approach (sort of true IPRA) registers will be reallocated
>>>> (this optimization will be optional if turned off still code will be
>>>> compiled as per intra-procedural allocation) at link time. Here modules are
>>>> first complied as per normal compilation but the object code is annotated
>>>> with details so that linker can build call graph and also calculate usage
>>>> information at link time. Compiler also write hints in object code that if
>>>> particular variable is allocated in some other register ( due to new
>>>> allocation) then how the code should be changed? Thus linker can use these
>>>> information to decide which variables (global) need to be in same register
>>>> through out the program execution and also according to register usage
>>>> information in call graph which procedure will not be active simultaneously
>>>> so that locals for that procedures can be in same registers with out load
>>>> store at procedure calls.
>>>> For these particular method help me to analyze feasibility:
>>>> 1) Can llvm collects following information at module level in
>>>> MachineIR? list of procedures in module, list of locals in procedures, list
>>>> of procedures that a particular procedure can call, and a list of the
>>>> variables this procedure references. Each entry in the last two lists
>>>> includes an estimate of the number of times the procedure is called or the
>>>> variable is referenced in each execution of this procedure
>>>> 2) Can llvm write informative commands to object files?
>>>> 3) Can LTO is capable of leveraging those commands?
>>>>
>>>> In terms of scoping the project for the summer, I definitely recommend
>>>> that you focus on (1) first. If you finish that, we can certainly move on
>>>> to other things.
>>>>
>>>>
>>>> I'll add +1 here, but I already wrote the same thing on IRC when
>>>> discussing with Vivek. True IPRA without a proper MachineModule
>>>> infrastructure won't be doable in my opinion (even with such
>>>> infrastructure, it may not be trivial in LLVM in general).
>>>>
>>>> Regarding link time, note that any such a design would likely look much
>>>> different than in David Wall's paper however, because our LTO re-codegens
>>>> everything anyway. The paper says, "Finally, it keeps us honest as
>>>> designers of the system; once we postpone anything until link time, the
>>>> temptation is great to postpone everything, ..." - Well, we've long-since
>>>> succumb to that temptation when we LTO. C'est la vie.
>>>>
>>>>
>>>> +1 as well, our LTO will benefit naturally from the leaf-to-root
>>>> information propagation. ThinLTO will be more challenging/interesting
>>>> though!
>>>>
>>>> For the first part a mechanism similar to MachineModulePass would be
>>>> desirable but that may not be possible during this project, but if we can
>>>> make some sort of smaller version of that to suit our purpose.
>>>>
>>>> I don't think we need to make any kind of MachineModulePass to make
>>>> this work. Once we alter the visitation order based on the CGSCC iteration
>>>> scheme, we can keep state in-between functions in the pre-existing hacky
>>>> way (using static members of the relevant function passes).
>>>>
>>>>  Sorry my mistake here by first part I mean 1) requirement in the link
>>> time approach.
>>>
>>>>
>>>
>>>> I also don't see where/why we need a MachineModule(Pass) for the CGSCC
>>>> scheme, that said I'd rather avoid using a function pass with static
>>>> members, if we can have a ModuleAnalysis that is bookkeeping the results
>>>> for functions in the module and queries by the register allocator somehow.
>>>> Matthias/Quentin may have other inputs on this aspect.
>>>>
>>>
>> @Hal do you mean to add a simple MachineFunction pass that will just
>> operate on register allocated function and prepare a BitVector to indicate
>> which register is being used by MachineFunction, and then use this pass as
>> analysis pass (i.e just simply return static BitVector for clobbered
>> register when register allocation for next function begins. This part is
>> not much clear to me) this thing can be done by scheduling a pass post
>> register allocation in lib/CodeGen/Passes.cpp
>>
>> void TargetPassConfig::addMachinePasses() {
>> .
>> .
>> .
>>   // Run pre-ra passes.
>>   addPreRegAlloc();
>>
>>   // Run register allocation and passes that are tightly coupled with it,
>>   // including phi elimination and scheduling.
>>   if (getOptimizeRegAlloc())
>>     addOptimizedRegAlloc(createRegAllocPass(true));
>>   else
>>     addFastRegAlloc(createRegAllocPass(false));
>>
>>   // Run post-ra passes.
>>   addPostRegAlloc();
>> // Adding a new pass here which keeps register mask information across
>> function calls.
>> .
>> .
>> .
>> }
>>
>> But this also requires current register allocators to use this
>> information in someway because RegMaskBits in LiveIntervalAnalysis.cpp is
>> not static across calls. I mean I am not clear for how to propagate static
>> info to Intra-procedural Register allocators (if possible without
>> disturbing their code )
>>
>> First, my hope is that we won't need to change the register allocators,
>> as such, in order to make use of this information. Instead, we'll simply be
>> able to alter the register masks generated for the call instructions. These
>> masks will indicate fewer clobbers than might otherwise be present based on
>> the ABI because of information gathered during the codegen of the callee.
>> These masks are generally constructed by target based on the calling
>> convention. The PowerPC backend, for example, looks like this:
>>
>>   // Add a register mask operand representing the call-preserved
>> registers.
>>   const TargetRegisterInfo *TRI = Subtarget.getRegisterInfo();
>>   const uint32_t *Mask =
>>       TRI->getCallPreservedMask(DAG.getMachineFunction(), CallConv);
>>   assert(Mask && "Missing call preserved mask for calling convention");
>>   Ops.push_back(DAG.getRegisterMask(Mask));
>>
>> but it can be more complicated. If you look for uses of 'getRegisterMask'
>> in Target/*/*ISelLowering.cpp, you'll see what I mean. Regardless, the code
>> ends up calling some method is the targets TargetRegisterInfo subclass.
>> These methods generally look something like this:
>>
>> const uint32_t *
>> PPCRegisterInfo::getCallPreservedMask(const MachineFunction &MF,
>>                                       CallingConv::ID CC) const {
>>   const PPCSubtarget &Subtarget = MF.getSubtarget<PPCSubtarget>();
>>   ...
>>   return TM.isPPC64() ? (Subtarget.hasAltivec() ?
>> CSR_SVR464_Altivec_RegMask
>>                                                 : CSR_SVR464_RegMask)
>>                       : (Subtarget.hasAltivec() ?
>> CSR_SVR432_Altivec_RegMask
>>                                                 : CSR_SVR432_RegMask);
>> }
>>
>> In any case, the fundamental idea here is that, when someone calls
>> getCallPreservedMask in order to set the regmask on a call, we might not
>> have to use the CC at all. Instead, if we've already codegened the
>> function, we might use a cache of 'exact' register masks computed during
>> codegen of the potential callees instead.
>>
> I am thinking to add a simple Immutable pass MachineRegisterUsageInfo
> similar to MachineBranchProbabilityInfo that can maintain
> RegisterUsageInformation per function. Can it be simply done by using
> UsedPhysRegMask from MachineRegisterInfo ??
>
>
> No, like the comment said, UsedPhysRegMask gives only the registers
> clobbered by calls:
> // This bit vector represents all the registers clobbered by function
> calls.
>
> You want to build this information yourself on top of MachineRegisterInfo::
> isPhysRegModified
>
Ok but then the time complexity will be O(n) n = number of physical
register on the target. Am I going correct?

>
> Here getCallPreservedMask will call API provided by
> MachineRegisterUsageInfo to avail the exact register mask but how it can
> know that the function is already codegen or it will query each time when
> getCallPreservedMask is called and of available MachineRegisterUsageInfo
> will return the details otherwise simply return NULL.
> So changes will be now in TargetRegisterInfo implementation for each
> target right ??
>
>
>> In order to do this, I think we'll need to provide a function callable
>> from the target's getCallPreservedMask implementation, which can return
>> such an 'exact' regmask when available. I think we need to do it this way
>> for two reasons:
>>
>>  1. Not all of the target code calls getCallPreservedMask, but sometimes
>> calls other similar target-specific functions (e.g.
>> getTLSCallPreservedMask).
>>  2. The targets need to opt-in to this behavior because only the target
>> can know that all register uses are really tagged correctly post "pre-emit".
>>
>> Because the target is free to introduce uses of registers at essentially
>> any time, we need to do the scanning for used registers after the
>> "pre-emit" passes run. This can be done by scheduling some simple
>> register-use scanning pass after the call to addPreEmitPass in
>> lib/CodeGen/Passes.cpp.
>>
>>
>> I think this also applies in someway to Mehdi Amini's idea to keep a
>> ModulePass for bookkeeping but then existing register allocators will be
>> required to change so that the code can query the ModulePass for
>> RegMaskBits for particular function.
>>
>> I think that the simplest way to do this is to create an immutable
>> analysis pass (e.g. BasicAA) that keeps the cache of the computed register
>> masks. This is somewhat similar in spirit to how the 'AssumptionCache'
>> analysis works at the IR level. This analysis can then be created by
>> lib/CodeGen/Passes.cpp early, and then queried and passed around later by
>> the CodeGen/Target code. Because it is an immutable analysis, it won't get
>> destroyed until the very end, which is also important because, I imagine,
>> it will need to own the memory associated with the generated register masks.
>>
>>  -Hal
>>
>>
>> Vivek
>>
>>
>>>> Yes for propagating register usage approach we don't need
>>> MachineModulePass
>>>
>>> Vivek
>>>
>>>> --
>>>> Mehdi
>>>>
>>>>
>>>
>>
>>
>>
>> --
>> Hal Finkel
>> Assistant Computational Scientist
>> Leadership Computing Facility
>> Argonne National Laboratory
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160518/bbb02cdf/attachment.html>