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

*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>

> On May 18, 2016, at 11:00 AM, vivek pandya <vivekvpandya at
gmail.com> wrote:
> 
> 
> 
> Vivek Pandya
> 
> 
> On Wed, May 18, 2016 at 11:25 PM, Quentin Colombet <qcolombet at
apple.com <mailto:qcolombet at apple.com>> wrote:
> 
>> On May 18, 2016, at 10:46 AM, vivek pandya <vivekvpandya at
gmail.com <mailto:vivekvpandya at gmail.com>> wrote:
>> 
>> 
>> 
>> Vivek Pandya
>> 
>> 
>> On Wed, May 11, 2016 at 4:01 PM, Hal Finkel <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>> wrote:
>> 
>> From: "vivek pandya" <vivekvpandya at gmail.com
<mailto:vivekvpandya at gmail.com>>
>> To: "Mehdi Amini" <mehdi.amini at apple.com
<mailto:mehdi.amini at apple.com>>
>> Cc: "Hal Finkel" <hfinkel at anl.gov <mailto:hfinkel at
anl.gov>>, "Quentin Colombet" <qcolombet at apple.com
<mailto:qcolombet at apple.com>>, "llvm-dev" <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>, "Matthias
Braun" <matze at braunis.de <mailto: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 <mailto:vivekvpandya at gmail.com>> wrote:
>> 
>> 
>> Vivek Pandya
>> 
>> 
>> On Wed, May 11, 2016 at 9:43 AM, Mehdi Amini <mehdi.amini at
apple.com <mailto:mehdi.amini at apple.com>> wrote:
>> 
>> On May 10, 2016, at 6:06 PM, Hal Finkel <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>> wrote:
>> 
>> 
>> 
>> From: "vivek pandya" <vivekvpandya at gmail.com
<mailto:vivekvpandya at gmail.com>>
>> To: "llvm-dev" <llvm-dev at lists.llvm.org
<mailto:llvm-dev at lists.llvm.org>>, "Tim Amini Golling"
<mehdi.amini at apple.com <mailto:mehdi.amini at apple.com>>,
"Hal Finkel" <hfinkel at anl.gov <mailto:hfinkel at
anl.gov>>
>> Cc: "Quentin Colombet" <qcolombet at apple.com
<mailto: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
<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
<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
<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?
Yes, this is 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/c5112426/attachment-0001.html>

Hello,

I have written following code to check each register if it is used by
machineFunction or not :

MachineRegisterInfo *MRI = &MF.getRegInfo();
TargetRegisterInfo *TRI = (TargetRegisterInfo
*)MF.getSubtarget().getRegisterInfo();
const TargetMachine &TM = MF.getTarget();
const MCRegisterInfo *MCRI = TM.getMCRegisterInfo();
DEBUG(dbgs() << "Function Name : " << MF.getName()
<< "\n");

for(TargetRegisterInfo::regclass_iterator i = (*TRI).regclass_begin(), e
(*TRI).regclass_end(); i != e; i++ ) {
for(TargetRegisterClass::iterator pregi = (*i)->begin(), prege
(*i)->end(); pregi != prege; pregi++ ) {
DEBUG( dbgs() << "Physical Register : " <<
MCRI->getName(*pregi) << " is
modified "<< MRI->isPhysRegModified(*pregi) << "
\n");
}
}
DEBUG(dbgs() << "\n");

The pass which is executing this code is schedule POST-RA stage but this
gives me true for all registers i.e in each function all registers are
being used except EBP and some other similar, Is this a correct way to get
register usage information ? I think I have made some mistake please help.

Vivek

On Wed, May 18, 2016 at 11:42 PM, Quentin Colombet <qcolombet at
apple.com>
wrote:
>
> On May 18, 2016, at 11:00 AM, vivek pandya <vivekvpandya at
gmail.com> wrote:
>
>
>
> *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?
>
>
> Yes, this is 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/20160524/e339b3f5/attachment-0001.html>