Subzero. Changes the Register Allocator so that it is aware of register

Subzero. Changes the Register Allocator so that it is aware of register
aliases.

BUG=
R=jvoung@chromium.org, stichnot@chromium.org

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

[John, 2015-09-02 22:36:12]

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

[Jim Stichnoth, 2015-09-03 17:48:49]

Probably add Jan as a reviewer.

Update the Subject and Description so the commit message is 1 line of <80 chars.

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:228: TargetLowering *Target = Func->getTarget();
I think maybe it's about time to make TargetLowering *Target a field of
LinearScan.

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:232: RegAliases[Reg] = &Target->getAliasesForRegister(Reg);
Would it be easier/cleaner to just call something like
Target->getRegisterAliases() and get read-only access to the array of
SmallBitVectors?  Since you're anyway copying into your own array.

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:351: for (int32_t RegNum = Aliases.find_first(); RegNum >=
0;
This repeated loop pattern uses 4 different variable name variants: Reg,
RegAlias, RegNum, and ItemReg.  Would it be inappropriate to make them the same
everywhere?

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:479: // TODO(jpp): This loop should not update the weight of
"parent" (i.e.,
I don't understand this TODO.  The purpose of this part is to mark the
pre-colored register off-limits by marking that register's weight as infinite. 
A register's weight can never be more than infinite.

I wonder if this comment was meant for handleNoFreeRegisters()?

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:550: Iter.Weights[Item->getRegNumTmp()].addWeight(W);
Should probably drop a TODO here about the fact that we need to consider whether
each alias gets the same weight increment.  (At least I don't think we've come
to a decision on that.)

https://codereview.chromium.org/1319203005/diff/100001/src/IceTargetLoweringX...
File src/IceTargetLoweringX8632Traits.h (right):

https://codereview.chromium.org/1319203005/diff/100001/src/IceTargetLoweringX...
src/IceTargetLoweringX8632Traits.h:28: #include <vector>
Is this needed?  I would have expected <array> if anything.

[John, 2015-09-03 22:38:24]

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

[John, 2015-09-03 22:38:25]

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:228: TargetLowering *Target = Func->getTarget();
On 2015/09/03 17:48:49, stichnot wrote:
> I think maybe it's about time to make TargetLowering *Target a field of
> LinearScan.

Done.

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:232: RegAliases[Reg] = &Target->getAliasesForRegister(Reg);
On 2015/09/03 17:48:49, stichnot wrote:
> Would it be easier/cleaner to just call something like
> Target->getRegisterAliases() and get read-only access to the array of
> SmallBitVectors?  Since you're anyway copying into your own array.

As we spoke offline, the underlying types holding the register aliases are not
the same.

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:351: for (int32_t RegNum = Aliases.find_first(); RegNum >=
0;
On 2015/09/03 17:48:49, stichnot wrote:
> This repeated loop pattern uses 4 different variable name variants: Reg,
> RegAlias, RegNum, and ItemReg.  Would it be inappropriate to make them the
same
> everywhere?

Done.

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:479: // TODO(jpp): This loop should not update the weight of
"parent" (i.e.,
On 2015/09/03 17:48:49, stichnot wrote:
> I don't understand this TODO.  The purpose of this part is to mark the
> pre-colored register off-limits by marking that register's weight as infinite.

> A register's weight can never be more than infinite.
> 
> I wonder if this comment was meant for handleNoFreeRegisters()?

Misplaced TODO.

https://codereview.chromium.org/1319203005/diff/100001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:550: Iter.Weights[Item->getRegNumTmp()].addWeight(W);
On 2015/09/03 17:48:49, stichnot wrote:
> Should probably drop a TODO here about the fact that we need to consider
whether
> each alias gets the same weight increment.  (At least I don't think we've come
> to a decision on that.)

Done.

https://codereview.chromium.org/1319203005/diff/100001/src/IceTargetLoweringX...
File src/IceTargetLoweringX8632Traits.h (right):

https://codereview.chromium.org/1319203005/diff/100001/src/IceTargetLoweringX...
src/IceTargetLoweringX8632Traits.h:28: #include <vector>
On 2015/09/03 17:48:49, stichnot wrote:
> Is this needed?  I would have expected <array> if anything.

Done.

[Jim Stichnoth, 2015-09-04 00:10:20]

lgtm

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:351: for (int32_t RegAlias = Aliases.find_first(); RegAlias
>= 0;
So I greatly prefer using int32_t rather than int.  Unfortunately,
SmallBitVector.h chooses to use int for the return value of find_first() and
find_next().  I wonder if it's reasonable to typedef something to int and use it
for these SmallBitVector accesses, so that the type actually matches yet we
minimize our explicit use of int.

[jvoung (off chromium), 2015-09-04 16:14:46]

Otherwise LGTM too

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:306: Iter.RegMask[Var->getRegNumTmp()] = false;
Do you need to go over the aliases here too?

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:447: int32_t RegNum = Item->getRegNumTmp();
Do you need to go over the aliases here too?

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.h
File src/IceRegAlloc.h (right):

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.h#newc...
src/IceRegAlloc.h:111: llvm::SmallVector<const llvm::SmallBitVector *,
REGS_SIZE> RegAliases;
Just a note that on ARM (and probably MIPS?) the target will have more registers
than will fit in the SmallBitVector's uintptr_t X field (up to 64
single-precision FP slots + 16 GPR slots).

[Jim Stichnoth, 2015-09-04 16:38:51]

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:306: Iter.RegMask[Var->getRegNumTmp()] = false;
On 2015/09/04 16:14:46, jvoung wrote:
> Do you need to go over the aliases here too?

Good catch, I think the aliases do need to be removed here.

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:447: int32_t RegNum = Item->getRegNumTmp();
On 2015/09/04 16:14:46, jvoung wrote:
> Do you need to go over the aliases here too?

Yeah, I think so...

[Jim Stichnoth, 2015-09-04 16:50:17]

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:646: Func->getTarget()->makeRandomRegisterPermutation(
Can you change this and basically all Func->getTarget() instances to just
Target?

[Jim Stichnoth, 2015-09-04 16:53:10]

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:228: Target = Func->getTarget();
Actually, Target is probably better initialized in the ctor, similar to Ctx.

[John, 2015-09-04 17:32:25]

please take another look.

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:228: Target = Func->getTarget();
On 2015/09/04 16:53:10, stichnot wrote:
> Actually, Target is probably better initialized in the ctor, similar to Ctx.

Done.

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:306: Iter.RegMask[Var->getRegNumTmp()] = false;
On 2015/09/04 16:38:51, stichnot wrote:
> On 2015/09/04 16:14:46, jvoung wrote:
> > Do you need to go over the aliases here too?
> 
> Good catch, I think the aliases do need to be removed here.

Done.

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:351: for (int32_t RegAlias = Aliases.find_first(); RegAlias
>= 0;
On 2015/09/04 00:10:20, stichnot wrote:
> So I greatly prefer using int32_t rather than int.  Unfortunately,
> SmallBitVector.h chooses to use int for the return value of find_first() and
> find_next().  I wonder if it's reasonable to typedef something to int and use
it
> for these SmallBitVector accesses, so that the type actually matches yet we
> minimize our explicit use of int.

This is an excellent case where using auto is superior to **anything** (ok,
maybe using decltype() magic would also work, but... yikes.)

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:447: int32_t RegNum = Item->getRegNumTmp();
On 2015/09/04 16:38:51, stichnot wrote:
> On 2015/09/04 16:14:46, jvoung wrote:
> > Do you need to go over the aliases here too?
> 
> Yeah, I think so...

Done.

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.cpp#ne...
src/IceRegAlloc.cpp:646: Func->getTarget()->makeRandomRegisterPermutation(
On 2015/09/04 16:50:17, stichnot wrote:
> Can you change this and basically all Func->getTarget() instances to just
> Target?

Done.

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.h
File src/IceRegAlloc.h (right):

https://codereview.chromium.org/1319203005/diff/120001/src/IceRegAlloc.h#newc...
src/IceRegAlloc.h:111: llvm::SmallVector<const llvm::SmallBitVector *,
REGS_SIZE> RegAliases;
On 2015/09/04 16:14:46, jvoung wrote:
> Just a note that on ARM (and probably MIPS?) the target will have more
registers
> than will fit in the SmallBitVector's uintptr_t X field (up to 64
> single-precision FP slots + 16 GPR slots).

I added a TODO here. Maybe it is worth investigating what the performance
penalty is.

[Jim Stichnoth, 2015-09-04 18:19:24]

Still LGTM.

IIRC, when we discussed this yesterday, I thought there were one or two cases
where you didn't need to iterate over all aliases of a particular register.  Is
that still the case, and if so, can you mark them with a comment?

https://codereview.chromium.org/1319203005/diff/140001/src/IceRegAlloc.h
File src/IceRegAlloc.h (right):

https://codereview.chromium.org/1319203005/diff/140001/src/IceRegAlloc.h#newc...
src/IceRegAlloc.h:113: // Evaluate what the performance impact on tose
architectures is.
those

[John, 2015-09-04 18:23:21]

I thought we agreed we always needed to iterate over the registers?... well, I
can always send another CL later.

https://codereview.chromium.org/1319203005/diff/140001/src/IceRegAlloc.h
File src/IceRegAlloc.h (right):

https://codereview.chromium.org/1319203005/diff/140001/src/IceRegAlloc.h#newc...
src/IceRegAlloc.h:113: // Evaluate what the performance impact on tose
architectures is.
On 2015/09/04 18:19:24, stichnot wrote:
> those

Done.

[John, 2015-09-04 18:23:45]

Committed patchset #9 (id:160001) manually as
bb0a5fe31a71fdc5b3292d62169f428d531437a4 (presubmit successful).