Subzero: Cleanly implement register allocation after phi lowering.

Subzero: Cleanly implement register allocation after phi lowering.

After finding a valid linearization of phi assignments, the old approach calls a complicated target-specific method that lowers and ad-hoc register allocates the phi assignments.

In the new approach, we use existing target lowering to lower assignments into mov/whatever instructions, and enhance the register allocator to be able to forcibly spill and reload a register if one is needed but none are available.

The new approach incrementally updates liveness and live ranges for newly added nodes and variable uses, to avoid having to expensively recompute it all.

Advanced phi lowering is enabled now on ARM, and constant blinding no longer needs to be disabled during phi lowering.

Some of the metadata regarding which CfgNode a local variable belongs to, needed to be made non-const, in order to add spill/fill instructions to a CfgNode during register allocation.

Most of the testing came from spec2k.  There are some minor differences in the output regarding stack frame offsets, probably related to the order that new nodes are phi-lowered.  The changes related to constant blinding were tested by running spec with "-randomize-pool-immediates=randomize -randomize-pool-threshold=8".

Unfortunately, this appears to add about 10% to the translation time for 176.gcc.  The cost is clear in the -timing output so it can be investigated later.  There is a TODO suggesting the possible cause and solution, for later investigation.

BUG= none
R=jvoung@chromium.org

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

[Jim Stichnoth, 2015-07-24 13:53:25]

stichnot@chromium.org changed reviewers:
+ jpp@chromium.org, jvoung@chromium.org, qining@google.com

[Jim Stichnoth, 2015-07-24 13:55:03]

Anthony (and others) - please check that I've removed all the hacks that were
needed for the old phi lowering.

[jvoung (off chromium), 2015-07-24 19:43:09]

https://codereview.chromium.org/1253833002/diff/20001/src/IceClFlags.cpp
File src/IceClFlags.cpp (left):

https://codereview.chromium.org/1253833002/diff/20001/src/IceClFlags.cpp#oldc...
src/IceClFlags.cpp:405: // TODO(jvoung): We need lowerPhiAssignments to handle
spilling
Thanks!

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:78: Str << "R=" << buf << "  V=";
Could you just use std::to_string(Var->getRegNumTmp()) ?

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:90: FindOverlap = (Kind != RAK_Phi);
Could you leave a comment about what FindOverlap is for (why leave out for
RAK_Phi)?

The IceOperand.h comment says "TODO(stichnot): We're not really using
FindOverlap yet, but we..." though it seems to matter?

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:106: // infinite-weight and pre-colored variables.
I'm not sure I understand the pre-colored part (there can be infinite-weight
temporaries that aren't pre-colored?)

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:311: if (Var->hasRegTmp())
This doesn't have to be concerned about Var->hasReg(), only RegTmp?

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:325: Variable *Preg = Target->getPhysicalRegister(RegNum,
Cur->getType());
Should this SpillLoc type depend on Cur->getType() or the Target's stack slot
type?

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:328: Variable *SpillLoc = Func->template
makeVariable(Cur->getType());
does this need the Func->template ... ?

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:330: Target->lowerInst(Node, SpillPoint,
InstFakeDef::create(Func, Preg));
Probably not too much, but Target->lowerInst() does end up doing
Context.init(Node); each time, though it's the same Node for all of these.

https://codereview.chromium.org/1253833002/diff/20001/src/IceTargetLoweringAR...
File src/IceTargetLoweringARM32.cpp (right):

https://codereview.chromium.org/1253833002/diff/20001/src/IceTargetLoweringAR...
src/IceTargetLoweringARM32.cpp:1478: // TODO(jvoung): check this for ARM.
can we remove the TODO now?

I think it was about "This is mostly a workaround for advanced phi lowering's
ad-hoc register allocation which assumes no register allocation is needed when
at least one of the operands is non-memory."

Also, might be able to rename SrcR to something else since it's Legal_Reg |
Legal_Flex here?

https://codereview.chromium.org/1253833002/diff/20001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1253833002/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:4898: inline bool isMemoryOperand(const
Operand *Opnd) {
I think you can remove isMemoryOperand now too, since that was for
lowerPhiAssignments

[Jim Stichnoth, 2015-07-26 04:47:50]

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:78: Str << "R=" << buf << "  V=";
On 2015/07/24 19:43:08, jvoung wrote:
> Could you just use std::to_string(Var->getRegNumTmp()) ?

That has the "%d" printf equivalent, as opposed to "%2d" above.  I found this
makes the register allocator's debugging output maximally aligned and easier to
read.

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:90: FindOverlap = (Kind != RAK_Phi);
On 2015/07/24 19:43:08, jvoung wrote:
> Could you leave a comment about what FindOverlap is for (why leave out for
> RAK_Phi)?

Done.

> 
> The IceOperand.h comment says "TODO(stichnot): We're not really using
> FindOverlap yet, but we..." though it seems to matter?

I think what I meant by this comment is that it was always the case that
FindPreference==FindOverlap and so FindOverlap wasn't actually adding any
independent state over the FindPreference setting.

But since that's no longer true, I removed the comment.

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:106: // infinite-weight and pre-colored variables.
On 2015/07/24 19:43:08, jvoung wrote:
> I'm not sure I understand the pre-colored part (there can be infinite-weight
> temporaries that aren't pre-colored?)

This is terminology that I think is used consistently in the code base, but
could probably use some cleanup and clarification.

Pre-coloring is when a variable is assigned a specific register due to
instruction or ABI requirements.  Infinite-weight forces some physical register
without specifying which one.

Pre-coloring implies infinite-weight, but unfortunately Variable::RegNum and
Variable::Weight are unrelated in the code base, so they both have to be checked
together in several places in the code base.  (And to further complicate things,
there's also Variable::Live::Weight which could also be infinite.)

It would be good to make a pass over the register allocator and lowering and
anything else relevant and try to combine these checks into a single, well-named
predicate.

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:311: if (Var->hasRegTmp())
On 2015/07/24 19:43:08, jvoung wrote:
> This doesn't have to be concerned about Var->hasReg(), only RegTmp?

That's right.  In the register allocator design, allocation decisions are
provisionally stored in the RegNumTmp field but can be later revoked. 
initForGlobal() and initForInfOnly() initialize RegNumTmp based on RegNum for
pre-colored variables, and then the end of scan() commits the decisions from
RegNumTmp->RegNum.  So in keeping with the rest of the scan() implementation,
this code deals with RegNumTmp rather than RegNum.

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:325: Variable *Preg = Target->getPhysicalRegister(RegNum,
Cur->getType());
On 2015/07/24 19:43:08, jvoung wrote:
> Should this SpillLoc type depend on Cur->getType() or the Target's stack slot
> type?

I think Cur->getType() is right.  For example, on x86-32, if it's IceType_f64,
it should use a 64-bit stack slot, and if it's a vector type, it should use an
aligned 128-bit stack slot.  If the type width is narrower than a target stack
slot, some extra stack space is probably wasted.

FWIW, across spec2k, there are a handful of instances of i1/i8/i16/double, so I
assume it's working correctly. :)

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:328: Variable *SpillLoc = Func->template
makeVariable(Cur->getType());
On 2015/07/24 19:43:08, jvoung wrote:
> does this need the Func->template ... ?

Done.  (guess I copied this from an older version of the lowering code)

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:330: Target->lowerInst(Node, SpillPoint,
InstFakeDef::create(Func, Preg));
On 2015/07/24 19:43:08, jvoung wrote:
> Probably not too much, but Target->lowerInst() does end up doing
> Context.init(Node); each time, though it's the same Node for all of these.

Yeah, my feeling was that addSpillFill() is invoked so very infrequently that it
was better to keep the design/implementation simple.

Added a TODO to the TargetLowering::lowerInst() definition.

https://codereview.chromium.org/1253833002/diff/20001/src/IceTargetLoweringAR...
File src/IceTargetLoweringARM32.cpp (right):

https://codereview.chromium.org/1253833002/diff/20001/src/IceTargetLoweringAR...
src/IceTargetLoweringARM32.cpp:1478: // TODO(jvoung): check this for ARM.
On 2015/07/24 19:43:08, jvoung wrote:
> can we remove the TODO now?
> 
> I think it was about "This is mostly a workaround for advanced phi lowering's
> ad-hoc register allocation which assumes no register allocation is needed when
> at least one of the operands is non-memory."

OK, done.  I wasn't sure whether the todo referred to that.

> 
> Also, might be able to rename SrcR to something else since it's Legal_Reg |
> Legal_Flex here?

OK, I went with the generic "NewSrc" rather than SrcR or SrcRF.

https://codereview.chromium.org/1253833002/diff/20001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1253833002/diff/20001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:4898: inline bool isMemoryOperand(const
Operand *Opnd) {
On 2015/07/24 19:43:08, jvoung wrote:
> I think you can remove isMemoryOperand now too, since that was for
> lowerPhiAssignments

Done.

[jvoung (off chromium), 2015-07-27 22:28:15]

LGTM for my comments

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:106: // infinite-weight and pre-colored variables.
I think my confusion is with the term "and" in the comments, + demorgan's,
something like

if (... !(Var->hasReg() || Var->getWeight().isInf()))
  continue;

Seems more like "only concerned with infinite-weight or pre-colored variables" ?

On 2015/07/26 04:47:50, stichnot wrote:
> On 2015/07/24 19:43:08, jvoung wrote:
> > I'm not sure I understand the pre-colored part (there can be infinite-weight
> > temporaries that aren't pre-colored?)
> 
> This is terminology that I think is used consistently in the code base, but
> could probably use some cleanup and clarification.
> 
> Pre-coloring is when a variable is assigned a specific register due to
> instruction or ABI requirements.  Infinite-weight forces some physical
register
> without specifying which one.
> 
> Pre-coloring implies infinite-weight, but unfortunately Variable::RegNum and
> Variable::Weight are unrelated in the code base, so they both have to be
checked
> together in several places in the code base.  (And to further complicate
things,
> there's also Variable::Live::Weight which could also be infinite.)
> 
> It would be good to make a pass over the register allocator and lowering and
> anything else relevant and try to combine these checks into a single,
well-named
> predicate.

Yes that might be good.

[Jim Stichnoth, 2015-07-28 18:30:43]

On 2015/07/27 22:28:15, jvoung wrote:
> LGTM for my comments

Thanks!

I decided to hold off landing this temporarily while I look a bit further into
the translation-time slowdown this is causing.

Anthony pointed out that it is actually slowing pnacl-llc.pexe by ~20%.

The slowdown is a combination of liveness analysis, live range construction, and
register allocation.

The liveness analysis part is actually not that bad.  We spend more time than
necessary copying liveness bit vectors that contain entries we ultimately don't
care about (non-pre-colored and non-infinite weight variables), but it's not all
that bad in the grand scheme and the performance numbers bear that out.

The live range construction probably spends a lot of unnecessary time updating
live ranges for variables we don't care about, most likely variables that are
live-in and live-out and not register-allocated.

The register allocator time goes up more than it ought to.  I've found in the
past that the implementation doesn't scale well when there is a large number of
pre-colored variables (such as when you try running register allocation
repeatedly until convergence to get better results).  It would be good to fix
that, but maybe I can do even better by taking advantage of the fact that all
the infinite-weight variables I care about have live ranges starting at a
specific instruction number or later, using the LiveRange::trim() functionality.

[Jim Stichnoth, 2015-07-30 07:22:18]

A fairly simple change ends up recovering about half of the translation-time
performance loss on pnacl-llc.pexe.

The rest should also be recoverable, but in a separate CL.

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1253833002/diff/20001/src/IceRegAlloc.cpp#new...
src/IceRegAlloc.cpp:106: // infinite-weight and pre-colored variables.
On 2015/07/27 22:28:15, jvoung wrote:
> I think my confusion is with the term "and" in the comments, + demorgan's,
> something like
> 
> if (... !(Var->hasReg() || Var->getWeight().isInf()))
>   continue;
> 
> Seems more like "only concerned with infinite-weight or pre-colored variables"
?

Ah, I see.  Done.

[Jim Stichnoth, 2015-07-30 19:46:11]

Committed patchset #4 (id:60001) manually as
a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2 (presubmit successful).