Subzero: Automatically infer regalloc preferences and overlap.

Subzero: Automatically infer regalloc preferences and overlap.

Originally, for a given Variable, register preference and overlap were manually specified.  That is, when choosing a free register for a Variable, it would be manually specified which (if any) related Variable would be a good choice for register selection, all things being equal.  Also, it allowed the rather dangerous "AllowOverlap" specification which let the Variable use its preferred Variable's register, even if their live ranges overlap.

Now, all this selection is automatic, and the machinery for manual specification is removed.

A few other changes in this CL:

- Address mode inference leverages the more precise

- Better regalloc dump messages to follow the logic

- "-verbose most" enables all verbose options except regalloc and time

- "-ias" is an alias for "-integrated-as"

- Bug fix: prevent 8-bit register ah from being used in register allocation, unless it is pre-colored

- Bug fix: the _mov helper where Dest is NULL wasn't always actually creating a new Variable

- A few tests are updated based on slightly different O2 register allocation decisions

The static stats actually improve slightly across the board (around 1%), except that frame size improves by 6-10%.  This is probably from smarter register allocation decisions, particularly involving phi lowering temporaries, where the manual hints weren't too good to start with.

BUG= none
R=jvoung@chromium.org

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

[Jim Stichnoth, 2014-09-25 06:41:09]

stichnot@chromium.org changed reviewers:
+ jvoung@chromium.org

[jvoung (off chromium), 2014-09-25 16:42:11]

https://codereview.chromium.org/597003004/diff/20001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/597003004/diff/20001/src/IceOperand.cpp#newco...
src/IceOperand.cpp:339: const Inst *VariablesMetadata::getFirstDefinition(const
Variable *Var) const {
I don't see where getFirstDefinition() is used?

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

https://codereview.chromium.org/597003004/diff/20001/src/IceOperand.h#newcode532
src/IceOperand.h:532: // the same block, e.g. T after the lowered sequence "T=B;
T+=C; A=T".
Do you mean, if Var == T, this returns the inst T=B, or do you mean if Var == A,
this returns A=T?

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (left):

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp#oldc...
src/IceRegAlloc.cpp:237: !PrecoloredUnhandled[PreferReg];
It now seems like PrecoloredUnhandled is no longer read (except in the debug
printing)?

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

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:218: if (const Inst *DefInst =
VMetadata->getSingleDefinition(Cur.Var)) {
Was this meant to be getFirstDefinition() (based on the above comment "has an
unambiguous "first" defining instruction).

On the other hand, the check below requires Cur.Var to be singledef.

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:230: if (SrcReg != Variable::NoRegister && RegMask[SrcReg])
{
Would it be better to check SrcReg != Variable::NoRegister && RegMask[SrcReg]
first, before calling overlapsDefs()? Seems like it could be cheaper.

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:232: if (AllowedToOverlap || Free[SrcReg])
Similar, would it be cheaper to check for Free[SrcReg] earlier, before calling
overlapsDefs to determine AllowedToOverlap?

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:310: if (AllowedToOverlap && Prefer &&
nit: I think technically, the "&& Prefer" check isn't needed after checking
AllowedToOverlap -- otherwise, some of the loops above seem to assume that
AllowedToOverlap => Prefer != NULL.

Also, Item.overlaps(Cur) so Cur.overlaps(Item) shouldn't be needed either?

https://codereview.chromium.org/597003004/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (left):

https://codereview.chromium.org/597003004/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4212: bool AllowOverlap, int32_t RegNum) {
yay +1!

https://codereview.chromium.org/597003004/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/597003004/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:385: Func->getVMetadata()->init();
Does the Func->liveness() already initialize VMetadata? (and would anything have
changed between then?)

https://codereview.chromium.org/597003004/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:3586: if (VMetadata->isMultiDef(Var))
Might be able to just check that the result of getSingleDefinition is non-NULL?
Similar below.

[Jim Stichnoth, 2014-09-25 18:13:55]

https://codereview.chromium.org/597003004/diff/20001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/597003004/diff/20001/src/IceOperand.cpp#newco...
src/IceOperand.cpp:339: const Inst *VariablesMetadata::getFirstDefinition(const
Variable *Var) const {
On 2014/09/25 16:42:11, jvoung wrote:
> I don't see where getFirstDefinition() is used?

Ah, nice catch.  That was supposed to be used on the current register allocation
candidate to figure out which instruction to dig into looking for Prefer
opportunities.  Instead, getSingleDefinition was used, which meant a number of
instructions weren't considered.

Changing it and spot-checking the diffs looks like a marginal improvement in
register allocation.  I'll look at the final stats later.

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

https://codereview.chromium.org/597003004/diff/20001/src/IceOperand.h#newcode532
src/IceOperand.h:532: // the same block, e.g. T after the lowered sequence "T=B;
T+=C; A=T".
On 2014/09/25 16:42:11, jvoung wrote:
> Do you mean, if Var == T, this returns the inst T=B, or do you mean if Var ==
A,
> this returns A=T?

The former.  Clarified in the comment.

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (left):

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp#oldc...
src/IceRegAlloc.cpp:237: !PrecoloredUnhandled[PreferReg];
On 2014/09/25 16:42:11, jvoung wrote:
> It now seems like PrecoloredUnhandled is no longer read (except in the debug
> printing)?

True.  It's worth keeping for the diagnostics, so I added a comment.

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

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:218: if (const Inst *DefInst =
VMetadata->getSingleDefinition(Cur.Var)) {
On 2014/09/25 16:42:11, jvoung wrote:
> Was this meant to be getFirstDefinition() (based on the above comment "has an
> unambiguous "first" defining instruction).

Yeah, fixed.
 
> On the other hand, the check below requires Cur.Var to be singledef.

The Overlap check requires single-def, but not for the Prefer hint.

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:230: if (SrcReg != Variable::NoRegister && RegMask[SrcReg])
{
On 2014/09/25 16:42:11, jvoung wrote:
> Would it be better to check SrcReg != Variable::NoRegister && RegMask[SrcReg]
> first, before calling overlapsDefs()? Seems like it could be cheaper.

Yes.  That should be fixed in the latest patchset.

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:232: if (AllowedToOverlap || Free[SrcReg])
On 2014/09/25 16:42:11, jvoung wrote:
> Similar, would it be cheaper to check for Free[SrcReg] earlier, before calling
> overlapsDefs to determine AllowedToOverlap?

Hmm, I think you're right.  The logs do show a lot of cases where Overlap is set
to true yet the variable is listed as free.  Changed.

https://codereview.chromium.org/597003004/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:310: if (AllowedToOverlap && Prefer &&
On 2014/09/25 16:42:11, jvoung wrote:
> nit: I think technically, the "&& Prefer" check isn't needed after checking
> AllowedToOverlap -- otherwise, some of the loops above seem to assume that
> AllowedToOverlap => Prefer != NULL.

Done.  I think I originally had that just to be absolutely sure the following
Prefer->getRegNumTmp() wasn't a null pointer dereference, but I've changed that
to use PreferReg so that issue is gone.

> Also, Item.overlaps(Cur) so Cur.overlaps(Item) shouldn't be needed either?

Nice, done.

https://codereview.chromium.org/597003004/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (left):

https://codereview.chromium.org/597003004/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4212: bool AllowOverlap, int32_t RegNum) {
On 2014/09/25 16:42:11, jvoung wrote:
> yay +1!

Indeed. :)

https://codereview.chromium.org/597003004/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/597003004/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:385: Func->getVMetadata()->init();
On 2014/09/25 16:42:11, jvoung wrote:
> Does the Func->liveness() already initialize VMetadata? (and would anything
have
> changed between then?)

It's true that liveness initializes VMetadata.  However, non-lightweight
liveness analysis has the side effect of deleting dead instructions, see the
call to deleteIfDead() in CfgNode::livenessPostprocess().

When dead instructions are deleted, this can tighten up some Variables, from
being used across multiple blocks to being single-block, making e.g. simple
coalescing more effective.

With that said, it probably doesn't affect register allocation, at least not for
now, because it's only the definition information being used and I don't think
that would change.  Even so, I think the cost of recomputing ought to be pretty
small and it's safest to leave it in for now.

https://codereview.chromium.org/597003004/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:3586: if (VMetadata->isMultiDef(Var))
On 2014/09/25 16:42:11, jvoung wrote:
> Might be able to just check that the result of getSingleDefinition is
non-NULL?
> Similar below.

Done.  (But left the equivalent asserts in place just in case.)

[jvoung (off chromium), 2014-09-25 18:38:11]

LGTM

[Jim Stichnoth, 2014-09-25 19:44:21]

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