Subzero: Local variable splitting.

Subzero: Local variable splitting.

The linear-scan register allocator takes an all-or-nothing approach -- either the variable's entire live range gets a register, or none of it does.

To help with this, we add a pass that splits successive uses of a variable within a basic block into a chain of linked variables.  This gives the register allocator the chance to allocate registers to subsets of the original live range.

The split variables are linked to each other so that if they don't get a register, they share a stack slot with the original variable, and redundant writes to that stack slot are recognized and elided.

This pass is executed after target lowering and right before register allocation.  As such, it has to deal with some idiosyncrasies of target lowering, specifically the possibility of intra-block control flow.  We experimented with doing this as a pre-lowering pass.  However, the transformations interfered with some of the target lowering's pattern matching, such as bool folding, so we concluded that post-lowering was a better place for it.

Note: Some of the lit tests are overly specific about registers, and in these cases it was the path of least resistance to just disable local variable splitting.

BUG= none
R=eholk@chromium.org, jpp@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=b9a847280e4486e566dabdd5b0d571309b4ad628

[Jim Stichnoth, 2016-07-24 02:31:27]

Description was changed from

==========
Subzero: Local variable splitting.

BUG= none
==========

to

==========
Subzero: Local variable splitting.

The linear-scan register allocator takes an all-or-nothing approach -- either
the variable's entire live range gets a register, or none of it does.

To help with this, we add a pass that splits successive uses of a variable
within a basic block into a chain of linked variables.  This gives the register
allocator the chance to allocate registers to subsets of the original live
range.

The split variables are linked to each other so that if they don't get a
register, they share a stack slot with the original variable, and redundant
writes to that stack slot are recognized and elided.

BUG= none
==========

[Jim Stichnoth, 2016-07-24 02:35:02]

Description was changed from

==========
Subzero: Local variable splitting.

The linear-scan register allocator takes an all-or-nothing approach -- either
the variable's entire live range gets a register, or none of it does.

To help with this, we add a pass that splits successive uses of a variable
within a basic block into a chain of linked variables.  This gives the register
allocator the chance to allocate registers to subsets of the original live
range.

The split variables are linked to each other so that if they don't get a
register, they share a stack slot with the original variable, and redundant
writes to that stack slot are recognized and elided.

BUG= none
==========

to

==========
Subzero: Local variable splitting.

The linear-scan register allocator takes an all-or-nothing approach -- either
the variable's entire live range gets a register, or none of it does.

To help with this, we add a pass that splits successive uses of a variable
within a basic block into a chain of linked variables.  This gives the register
allocator the chance to allocate registers to subsets of the original live
range.

The split variables are linked to each other so that if they don't get a
register, they share a stack slot with the original variable, and redundant
writes to that stack slot are recognized and elided.

Note: Some of the lit tests are overly specific about registers, and in these
cases it was the path of least resistance to just disable local variable
splitting.

BUG= none
==========

[Jim Stichnoth, 2016-07-24 03:16:58]

Description was changed from

==========
Subzero: Local variable splitting.

The linear-scan register allocator takes an all-or-nothing approach -- either
the variable's entire live range gets a register, or none of it does.

To help with this, we add a pass that splits successive uses of a variable
within a basic block into a chain of linked variables.  This gives the register
allocator the chance to allocate registers to subsets of the original live
range.

The split variables are linked to each other so that if they don't get a
register, they share a stack slot with the original variable, and redundant
writes to that stack slot are recognized and elided.

Note: Some of the lit tests are overly specific about registers, and in these
cases it was the path of least resistance to just disable local variable
splitting.

BUG= none
==========

to

==========
Subzero: Local variable splitting.

The linear-scan register allocator takes an all-or-nothing approach -- either
the variable's entire live range gets a register, or none of it does.

To help with this, we add a pass that splits successive uses of a variable
within a basic block into a chain of linked variables.  This gives the register
allocator the chance to allocate registers to subsets of the original live
range.

The split variables are linked to each other so that if they don't get a
register, they share a stack slot with the original variable, and redundant
writes to that stack slot are recognized and elided.

This pass is executed after target lowering and right before register
allocation.  As such, it has to deal with some idiosyncrasies of target
lowering, specifically the possibility of intra-block control flow.  We
experimented with doing this as a pre-lowering pass.  However, the
transformations interfered with some of the target lowering's pattern matching,
such as bool folding, so we concluded that post-lowering was a better place for
it.

Note: Some of the lit tests are overly specific about registers, and in these
cases it was the path of least resistance to just disable local variable
splitting.

BUG= none
==========

[Jim Stichnoth, 2016-07-24 05:41:20]

stichnot@chromium.org changed reviewers:
+ eholk@chromium.org, jpp@chromium.org, kschimpf@google.com, manasijm@google.com

[Jim Stichnoth, 2016-07-24 05:42:24]

This seems to improve spec2k by 1-2% overall, with ~5% gains on 2-3 of them.

[Eric Holk, 2016-07-25 19:59:22]

lgtm

My comments were mostly just questions and naming suggestions, so feel free to
consider them all optional.

https://codereview.chromium.org/2177033002/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2177033002/diff/20001/src/IceCfg.cpp#newcode840
src/IceCfg.cpp:840: bool isNormal(const Variable *Var) {
I'm not sure "normal" is the best name here, but I'm not sure what's better.
Maybe "allocatable?"

https://codereview.chromium.org/2177033002/diff/20001/src/IceCfg.cpp#newcode861
src/IceCfg.cpp:861: ///   A = B + C
Should this be `A = B1 + C1`?

https://codereview.chromium.org/2177033002/diff/20001/src/IceCfg.cpp#newcode907
src/IceCfg.cpp:907: /// instructions, without the quadratic nature that liveness
analysis usually
Does this mean that splitting live ranges totally avoids the quadratic liveness
analysis, or just that it doesn't make it any worse?

https://codereview.chromium.org/2177033002/diff/20001/src/IceCfg.cpp#newcode1008
src/IceCfg.cpp:1008: static constexpr char AnInstructionHasNoName[] = "";
:)

https://codereview.chromium.org/2177033002/diff/20001/src/IceCfg.cpp#newcode1013
src/IceCfg.cpp:1013: !getFlags().matchSplitInsts(AnInstructionHasNoName,
This is a little unclear to me, but I think I get it. Is it that matchSplitInsts
is from a more general matchSplit, which can match either by names or numbers,
but in the case of instructions they have no name so that parameter is
meaningless?

https://codereview.chromium.org/2177033002/diff/20001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/2177033002/diff/20001/src/IceInst.h#newcode159
src/IceInst.h:159: virtual const Inst *isIntraBlockBranch() const { return
nullptr; }
The "is" prefix makes me think this should be a boolean function. What about
calling it "getIntraBlockBranch" or "maybeGetIntraBlockBranch" for a rather
verbose name?

https://codereview.chromium.org/2177033002/diff/20001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/2177033002/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:794: /// This only makes sense after register allocation is
complete.
Is there an assertion you could add to make sure register allocation has
happened?

[Jim Stichnoth, 2016-07-26 05:59:09]

Along with the code review changes, I also found and fixed an error in one of
the transformations.  See lines 1083 and 1090 of IceCfg.cpp.  The comment was
correct, but it was transcribed into code incorrectly.  This change uncovered
some other problems with stack slot mapping, which I also fixed.  This seems to
have improved the spec2k geomean by about another 1%.

https://codereview.chromium.org/2177033002/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2177033002/diff/20001/src/IceCfg.cpp#newcode840
src/IceCfg.cpp:840: bool isNormal(const Variable *Var) {
On 2016/07/25 19:59:22, Eric Holk wrote:
> I'm not sure "normal" is the best name here, but I'm not sure what's better.
> Maybe "allocatable?"

Done - using the shorter "allocable".

https://codereview.chromium.org/2177033002/diff/20001/src/IceCfg.cpp#newcode861
src/IceCfg.cpp:861: ///   A = B + C
On 2016/07/25 19:59:22, Eric Holk wrote:
> Should this be `A = B1 + C1`?

No... see also the description in lines 1100-1101 below.

If you look at the various transformation options, combined with the
possibilities of the variables and their copies being in registers versus stack
locations, I think this approach is the best, in that it avoids the worst
performance problem which is storing to the stack followed by immediately
reloading it.

https://codereview.chromium.org/2177033002/diff/20001/src/IceCfg.cpp#newcode907
src/IceCfg.cpp:907: /// instructions, without the quadratic nature that liveness
analysis usually
On 2016/07/25 19:59:22, Eric Holk wrote:
> Does this mean that splitting live ranges totally avoids the quadratic
liveness
> analysis, or just that it doesn't make it any worse?

I rephrased the "quadratic" part in the comment.  What I really mean is that the
additional cost is just to traverse and process the additional instructions, and
not to merge larger bit vectors across blocks as part of the dataflow algorithm.
 The merging is what dominates liveness analysis for large functions, but the
merged bit vectors are only for multi-block variables.

https://codereview.chromium.org/2177033002/diff/20001/src/IceCfg.cpp#newcode1013
src/IceCfg.cpp:1013: !getFlags().matchSplitInsts(AnInstructionHasNoName,
On 2016/07/25 19:59:22, Eric Holk wrote:
> This is a little unclear to me, but I think I get it. Is it that
matchSplitInsts
> is from a more general matchSplit, which can match either by names or numbers,
> but in the case of instructions they have no name so that parameter is
> meaningless?

Right -- class RangeSpec allows matching by name or number or numeric range, but
instructions really don't have any meaningful name.  This is in contrast to
variables, basic block labels, and functions, all of which can have textual
names in a .ll file.

https://codereview.chromium.org/2177033002/diff/20001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/2177033002/diff/20001/src/IceInst.h#newcode159
src/IceInst.h:159: virtual const Inst *isIntraBlockBranch() const { return
nullptr; }
On 2016/07/25 19:59:22, Eric Holk wrote:
> The "is" prefix makes me think this should be a boolean function. What about
> calling it "getIntraBlockBranch" or "maybeGetIntraBlockBranch" for a rather
> verbose name?

Done.

https://codereview.chromium.org/2177033002/diff/20001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/2177033002/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:794: /// This only makes sense after register allocation is
complete.
On 2016/07/25 19:59:22, Eric Holk wrote:
> Is there an assertion you could add to make sure register allocation has
> happened?

I don't really think it could be done cleanly and reliably.  For example, there
can be multiple register allocation passes such as main register allocation
followed by post phi lowering register allocation.  So the assert would need to
know that *all* regalloc passes have completed.

[John, 2016-07-26 18:59:39]

no ARM? :(

https://codereview.chromium.org/2177033002/diff/40001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2177033002/diff/40001/src/IceCfg.cpp#newcode909
src/IceCfg.cpp:909: void Cfg::splitLocalVars() {
this is really hard to follow. I know there are a bunch of comments, but the
code is unlikely to fit in a single screen, even with a 30'' monitor set up for
portrait viewing. Perhaps split this code into several helpers?

[Jim Stichnoth, 2016-07-28 23:37:03]

PTAL.

If you care to follow along, I uploaded 3 patchsets since the last review.

Patchset 4 fixes (another) LinkedTo bug, and also fixes a big translation-time
efficiency problem.

Patchset 5 pulls the code for the pass out of IceCfg.cpp and into its own file.

Patchset 6 addresses John's comment and tries to break up the giant function
into several digestible helpers.

https://codereview.chromium.org/2177033002/diff/40001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2177033002/diff/40001/src/IceCfg.cpp#newcode909
src/IceCfg.cpp:909: void Cfg::splitLocalVars() {
On 2016/07/26 18:59:39, John wrote:
> this is really hard to follow. I know there are a bunch of comments, but the
> code is unlikely to fit in a single screen, even with a 30'' monitor set up
for
> portrait viewing. Perhaps split this code into several helpers?

Done.

[Eric Holk, 2016-07-29 18:40:58]

still lgtm

[Jim Stichnoth, 2016-07-30 20:06:56]

Sorry, one "last" patchset, with the following changes:

1. Don't bother splitting the last use of a variable in the block, since that
last split variable will never be used, and that split instruction will just be
dead-code eliminated.  This reduces the overall compilation overhead by a third.
 (As expected, the generated code is identical.)

2. Slight change in the pattern for classifying instruction types.  Explicitly
return a bool instead of having the caller check a separate state variable.

3. Added code for splitting phi dest vars, but left it disabled because it
appears to make performance slightly worse.

[John, 2016-08-01 14:17:33]

lgtm

https://codereview.chromium.org/2177033002/diff/60001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2177033002/diff/60001/src/IceCfg.cpp#newcode959
src/IceCfg.cpp:959: // A->getIndex()>B->getIndex().
add spaces around ' > ' (the gt operator)

https://codereview.chromium.org/2177033002/diff/60001/src/IceCfg.cpp#newcode1081
src/IceCfg.cpp:1081: LinkedToFixups.emplace_back(Dest);
Any reasons why you can't spliceBlockLocalLinkedToChain() here?

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
File src/IceVariableSplitting.cpp (right):

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:127: class LocalSplittingState {
This is not really a State, it contains the State for Local Variable Splitting.
A State would consist of a bunch of data, and maybe some accessors (although I
tend to think of State types as no-method types.) This class does a lot more
than keeping track of state -- it actually performs *all* of local variable
splitting logic. This class is the actual local variable splitter. Consider
renaming it (bonus points if the name does not contain a verb :))

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:154: void setInst(Inst *CurInst, InstList::iterator
Cur, InstList::iterator Next) {
isn't it possible to infer CurInst from Cur, and vice versa?

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:168: bool shouldSkipThisInstruction() const {
return ShouldSkipThisInstruction; }
perhaps this should

return ShouldSkipThisInstructions || shouldSkipAllInstructions();

After all, if you're skipping all instructions, you're also skipping this
instruction.

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:175: /// addition, they set the
ShouldSkipAllInstructions flag to indicate that no
If it indicates that no more instructions should be processed, then call this
SkipRemainingInsts?

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:180: void handleUnwantedInstruction() {
Maybe return bool, and rename this to

isUnwantedInstruction()

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:199: void handleLabel() {
Maybe return bool, and rename this to

isLabel()

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:207: if (Instr == WaitingForLabel) {
this approach will fail with "deep" short-circuiting. Perhaps it could be fixed
with a list of labels instead of a single label.

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:222: void handleIntraBlockBranch() {
Maybe return bool, and rename this to

isIntraBlockBranch()

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:244: void handleVarAssign() {
Maybe return bool, and rename this to

isTrivialVarAssign()

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:523: State.handleLabel();
if these returned bool, this could be

if (State.isLabel() ||
    State.isIntraBlockBranch() ||
    State.isUnwanted() ||
    State.isTrivialVarAssign()) {
  continue;
}

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:532: // whether its Variables are infinite-weight. 
New instructions can be
... and you can get rid of the special-case for var assigns below.

https://codereview.chromium.org/2177033002/diff/120001/src/IceVariableSplitti...
File src/IceVariableSplitting.cpp (right):

https://codereview.chromium.org/2177033002/diff/120001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:523: // performance.  Disable for now.q
now.q?

https://codereview.chromium.org/2177033002/diff/120001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:597: if (State.handleGeneralInst())
no need for this if here, right?

[Jim Stichnoth, 2016-08-01 15:13:51]

Still one comment to be addressed.

https://codereview.chromium.org/2177033002/diff/60001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2177033002/diff/60001/src/IceCfg.cpp#newcode959
src/IceCfg.cpp:959: // A->getIndex()>B->getIndex().
On 2016/08/01 14:17:31, John wrote:
> add spaces around ' > ' (the gt operator)

Done.

https://codereview.chromium.org/2177033002/diff/60001/src/IceCfg.cpp#newcode1081
src/IceCfg.cpp:1081: LinkedToFixups.emplace_back(Dest);
On 2016/08/01 14:17:31, John wrote:
> Any reasons why you can't spliceBlockLocalLinkedToChain() here?

I no longer remember the exact scenario, but this was the first thing I tried
and it didn't work. :(

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
File src/IceVariableSplitting.cpp (right):

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:127: class LocalSplittingState {
On 2016/08/01 14:17:32, John wrote:
> This is not really a State, it contains the State for Local Variable
Splitting.
> A State would consist of a bunch of data, and maybe some accessors (although I
> tend to think of State types as no-method types.) This class does a lot more
> than keeping track of state -- it actually performs *all* of local variable
> splitting logic. This class is the actual local variable splitter. Consider
> renaming it (bonus points if the name does not contain a verb :))

Changed to "class LocalVariableSplitter Splitter".

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:154: void setInst(Inst *CurInst, InstList::iterator
Cur, InstList::iterator Next) {
On 2016/08/01 14:17:32, John wrote:
> isn't it possible to infer CurInst from Cur, and vice versa?

Not if CurInst is a phi instruction.  (I think I had this in mind with respect
to my phi TODO, and actually demonstrated in the later patchset.)

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:168: bool shouldSkipThisInstruction() const {
return ShouldSkipThisInstruction; }
On 2016/08/01 14:17:32, John wrote:
> perhaps this should
> 
> return ShouldSkipThisInstructions || shouldSkipAllInstructions();
> 
> After all, if you're skipping all instructions, you're also skipping this
> instruction.

I think I sidestepped this issue with the later patchset, which gets rid of this
explicit state.

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:175: /// addition, they set the
ShouldSkipAllInstructions flag to indicate that no
On 2016/08/01 14:17:32, John wrote:
> If it indicates that no more instructions should be processed, then call this
> SkipRemainingInsts?

Done.

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:180: void handleUnwantedInstruction() {
On 2016/08/01 14:17:32, John wrote:
> Maybe return bool, and rename this to
> 
> isUnwantedInstruction()

I did change all the handle*() functions to return bool.

I'd kinda like to keep the "handle" prefix -- for consistency with the other
names, and also in case some horrible future instruction needs to be "handled"
by skipping the remaining instructions.

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:199: void handleLabel() {
On 2016/08/01 14:17:32, John wrote:
> Maybe return bool, and rename this to
> 
> isLabel()

Similar to above.  I like to keep "handle" because it changes some state,
whereas I usually expect an "is*()" function to be const.

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:222: void handleIntraBlockBranch() {
On 2016/08/01 14:17:32, John wrote:
> Maybe return bool, and rename this to
> 
> isIntraBlockBranch()

(same as above with respect to state changes)

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:244: void handleVarAssign() {
On 2016/08/01 14:17:32, John wrote:
> Maybe return bool, and rename this to
> 
> isTrivialVarAssign()

I still like "handle" because of the possible side effect of splitting.

I changed it to handleSimpleVarAssign().

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:523: State.handleLabel();
On 2016/08/01 14:17:32, John wrote:
> if these returned bool, this could be
> 
> if (State.isLabel() ||
>     State.isIntraBlockBranch() ||
>     State.isUnwanted() ||
>     State.isTrivialVarAssign()) {
>   continue;
> }

Done, in the later patchset.

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:532: // whether its Variables are infinite-weight. 
New instructions can be
On 2016/08/01 14:17:32, John wrote:
> ... and you can get rid of the special-case for var assigns below.

I think it's much cleaner now in the later patchset.

https://codereview.chromium.org/2177033002/diff/120001/src/IceVariableSplitti...
File src/IceVariableSplitting.cpp (right):

https://codereview.chromium.org/2177033002/diff/120001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:523: // performance.  Disable for now.q
On 2016/08/01 14:17:32, John wrote:
> now.q?

heh.  Done.

maybe should have been  now.:wq  or  now.:q!
:)

https://codereview.chromium.org/2177033002/diff/120001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:597: if (State.handleGeneralInst())
On 2016/08/01 14:17:32, John wrote:
> no need for this if here, right?

True, but I kinda like the consistency, and it makes it easier (i.e. fewer
changes) to add more kinds of handling in the future as needed.

[Jim Stichnoth, 2016-08-01 19:55:36]

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
File src/IceVariableSplitting.cpp (right):

https://codereview.chromium.org/2177033002/diff/100001/src/IceVariableSplitti...
src/IceVariableSplitting.cpp:207: if (Instr == WaitingForLabel) {
On 2016/08/01 14:17:32, John wrote:
> this approach will fail with "deep" short-circuiting. Perhaps it could be
fixed
> with a list of labels instead of a single label.

By "fail", I assume you mean the entire short-circuiting section will fall back
to the non-splitting code -- and not that it could produce incorrect code?

FWIW, spec2k seems to work correctly with -enable-sc (short-circuit optimization
for x8632 and x8664) so hopefully there are no correctness problems...

[Jim Stichnoth, 2016-08-01 20:18:40]

Description was changed from

==========
Subzero: Local variable splitting.

The linear-scan register allocator takes an all-or-nothing approach -- either
the variable's entire live range gets a register, or none of it does.

To help with this, we add a pass that splits successive uses of a variable
within a basic block into a chain of linked variables.  This gives the register
allocator the chance to allocate registers to subsets of the original live
range.

The split variables are linked to each other so that if they don't get a
register, they share a stack slot with the original variable, and redundant
writes to that stack slot are recognized and elided.

This pass is executed after target lowering and right before register
allocation.  As such, it has to deal with some idiosyncrasies of target
lowering, specifically the possibility of intra-block control flow.  We
experimented with doing this as a pre-lowering pass.  However, the
transformations interfered with some of the target lowering's pattern matching,
such as bool folding, so we concluded that post-lowering was a better place for
it.

Note: Some of the lit tests are overly specific about registers, and in these
cases it was the path of least resistance to just disable local variable
splitting.

BUG= none
==========

to

==========
Subzero: Local variable splitting.

The linear-scan register allocator takes an all-or-nothing approach -- either
the variable's entire live range gets a register, or none of it does.

To help with this, we add a pass that splits successive uses of a variable
within a basic block into a chain of linked variables.  This gives the register
allocator the chance to allocate registers to subsets of the original live
range.

The split variables are linked to each other so that if they don't get a
register, they share a stack slot with the original variable, and redundant
writes to that stack slot are recognized and elided.

This pass is executed after target lowering and right before register
allocation.  As such, it has to deal with some idiosyncrasies of target
lowering, specifically the possibility of intra-block control flow.  We
experimented with doing this as a pre-lowering pass.  However, the
transformations interfered with some of the target lowering's pattern matching,
such as bool folding, so we concluded that post-lowering was a better place for
it.

Note: Some of the lit tests are overly specific about registers, and in these
cases it was the path of least resistance to just disable local variable
splitting.

BUG= none
R=eholk@chromium.org, jpp@chromium.org

Committed:
https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a...
==========

[Jim Stichnoth, 2016-08-01 20:18:41]

Committed patchset #8 (id:140001) manually as
b9a847280e4486e566dabdd5b0d571309b4ad628 (presubmit successful).