Weight variables by their number of uses for register allocation.

Weight variables for register allocation by their number of uses.

Count the number of instructions that use a variable following the heuristic
that more uses implies higher register priority. This is currently very simple
but is precursor work for weighting variables by loop nest depth.

BUG=
R=jvoung@chromium.org

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

[ascull, 2015-08-26 19:24:36]

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

[ascull, 2015-08-26 19:24:36]

https://codereview.chromium.org/1312433004/diff/1/tests_lit/llvm2ice_tests/na...
File tests_lit/llvm2ice_tests/nacl-atomic-cmpxchg-optimization.ll (left):

https://codereview.chromium.org/1312433004/diff/1/tests_lit/llvm2ice_tests/na...
tests_lit/llvm2ice_tests/nacl-atomic-cmpxchg-optimization.ll:131: ; O2: mov
{{.*}}
Discussed with Jan. This used to match a register spill which is no longer
present.

[jvoung (off chromium), 2015-08-26 21:45:47]

https://codereview.chromium.org/1312433004/diff/1/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/1312433004/diff/1/src/IceInst.cpp#newcode183
src/IceInst.cpp:183: Dest->addUse(1);
Hmm, not sure we should count definitions as a Use (would that inflate the
weight in a way that is undesirable, e.g., with a sequence of two-address
instructions?)

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode335
src/IceOperand.h:335: bool isInf() const { return Weight == Inf; }
It looks like the isInf() method isn't used anymore. Remove?

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode336
src/IceOperand.h:336: bool isZero() const { return Weight == Zero; }
similar for isZero

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode346
src/IceOperand.h:346: enum RegRequirement {
Should this enum be scoped in RegWeight? (near the Inf and Zero values)?

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode356
src/IceOperand.h:356: /// weight, in case e.g. we want a live range to have
higher weight
LiveRange doesn't include the weight field anymore?

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode480
src/IceOperand.h:480: assert(WeightDelta != RegWeight::Inf);
WeightDelta is only used in assert builds now and looks like it's always 1.
Should that just be removed?

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode509
src/IceOperand.h:509: /// RegNumTmp, Weight, Live, LoVar, HiVar, VarsReal.
Weight -> UseWeight ?

[ascull, 2015-08-26 22:06:39]

https://codereview.chromium.org/1312433004/diff/1/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/1312433004/diff/1/src/IceInst.cpp#newcode183
src/IceInst.cpp:183: Dest->addUse(1);
On 2015/08/26 21:45:46, jvoung wrote:
> Hmm, not sure we should count definitions as a Use (would that inflate the
> weight in a way that is undesirable, e.g., with a sequence of two-address
> instructions?)

If there are two uses of a variable in a function doesn't that mean the variable
should have higher register priority? Or is it no possible to have two memory
arguments?

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode335
src/IceOperand.h:335: bool isInf() const { return Weight == Inf; }
On 2015/08/26 21:45:46, jvoung wrote:
> It looks like the isInf() method isn't used anymore. Remove?

Done.

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode336
src/IceOperand.h:336: bool isZero() const { return Weight == Zero; }
On 2015/08/26 21:45:46, jvoung wrote:
> similar for isZero

Done.

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode346
src/IceOperand.h:346: enum RegRequirement {
On 2015/08/26 21:45:47, jvoung wrote:
> Should this enum be scoped in RegWeight? (near the Inf and Zero values)?

It is separate from RegWeight which is an 'infinity' capped integer. It is
however only used privately by Variable which is where I moved it. I was going
to use it in LiveRange too but I got rid of the weight there as it was
redundant.

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode356
src/IceOperand.h:356: /// weight, in case e.g. we want a live range to have
higher weight
On 2015/08/26 21:45:46, jvoung wrote:
> LiveRange doesn't include the weight field anymore?

Yes, the weight is managed by the Variable which, given SSA, is equivalent to a
live range. Removed this comment.

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode480
src/IceOperand.h:480: assert(WeightDelta != RegWeight::Inf);
On 2015/08/26 21:45:46, jvoung wrote:
> WeightDelta is only used in assert builds now and looks like it's always 1.
> Should that just be removed?

Done.

https://codereview.chromium.org/1312433004/diff/1/src/IceOperand.h#newcode509
src/IceOperand.h:509: /// RegNumTmp, Weight, Live, LoVar, HiVar, VarsReal.
On 2015/08/26 21:45:46, jvoung wrote:
> Weight -> UseWeight ?

UseWeight -> Weight. Missed this refactor.

[jvoung (off chromium), 2015-08-26 22:35:16]

https://codereview.chromium.org/1312433004/diff/1/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/1312433004/diff/1/src/IceInst.cpp#newcode183
src/IceInst.cpp:183: Dest->addUse(1);
On 2015/08/26 22:06:38, ascull wrote:
> On 2015/08/26 21:45:46, jvoung wrote:
> > Hmm, not sure we should count definitions as a Use (would that inflate the
> > weight in a way that is undesirable, e.g., with a sequence of two-address
> > instructions?)
> 
> If there are two uses of a variable in a function doesn't that mean the
variable
> should have higher register priority? Or is it no possible to have two memory
> arguments?

Sorry, by two-address I meant, for example, add instructions that can only do:

a += b

vs an add instruction that can do:

a = b + c

I didn't mean address as something related to a memory operand.

Yes, to "If there are two uses of a variable in a function doesn't that mean the
variable
should have higher register priority?"

What I meant was here you're counting a use whenever a variable defined (Dest),
not just when it's used as a (Src).  In any case, this might be okay.  Every
instance of a "Dest" is a potential "Spill", and a every instance of a "Src" may
be a potential "Fill", and you can check the stats before and after this change
with "--szstats".

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

https://codereview.chromium.org/1312433004/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:460: void addUse(uint32_t Weight) { Weight += Weight; }
I'm a bit worried about the variable shadowing here (Weight += Weight)?

[ascull, 2015-08-26 22:53:49]

https://codereview.chromium.org/1312433004/diff/1/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/1312433004/diff/1/src/IceInst.cpp#newcode183
src/IceInst.cpp:183: Dest->addUse(1);
On 2015/08/26 22:35:16, jvoung wrote:
> On 2015/08/26 22:06:38, ascull wrote:
> > On 2015/08/26 21:45:46, jvoung wrote:
> > > Hmm, not sure we should count definitions as a Use (would that inflate the
> > > weight in a way that is undesirable, e.g., with a sequence of two-address
> > > instructions?)
> > 
> > If there are two uses of a variable in a function doesn't that mean the
> variable
> > should have higher register priority? Or is it no possible to have two
memory
> > arguments?
> 
> Sorry, by two-address I meant, for example, add instructions that can only do:
> 
> a += b
> 
> vs an add instruction that can do:
> 
> a = b + c
> 
> I didn't mean address as something related to a memory operand.
> 
> Yes, to "If there are two uses of a variable in a function doesn't that mean
the
> variable
> should have higher register priority?"
> 
> What I meant was here you're counting a use whenever a variable defined
(Dest),
> not just when it's used as a (Src).  In any case, this might be okay.  Every
> instance of a "Dest" is a potential "Spill", and a every instance of a "Src"
may
> be a potential "Fill", and you can check the stats before and after this
change
> with "--szstats".

This is what I meant it to do. But thinking again SSA means this has little/no
impact. There might be some custom code from a TargetLowering that would
benefit.

I've removed this for now.

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

https://codereview.chromium.org/1312433004/diff/20001/src/IceOperand.h#newcod...
src/IceOperand.h:460: void addUse(uint32_t Weight) { Weight += Weight; }
On 2015/08/26 22:35:16, jvoung wrote:
> I'm a bit worried about the variable shadowing here (Weight += Weight)?

Done.

[Jim Stichnoth, 2015-08-27 05:03:06]

https://codereview.chromium.org/1312433004/diff/60001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/1312433004/diff/60001/src/IceInst.cpp#newcode185
src/IceInst.cpp:185: Live[VarNum] = false;
I kind of expected Dest to be marked as having a use here.

Maybe that doesn't really matter because non-SSA variables with more than one
definition are only infinite-weight variables from lowering?

Maybe that unfairly diminishes weights of function arguments, which lack
explicit definitions?

If you mean to not track the use of Dest here, it's probably good to leave a
comment.

EDIT: I see this issue was already discussed.  I actually vote for counting the
dest var as a use.  Ignoring the fact that two-address instructions generally
involve infinite-weight variables, if we have an instruction like this:
  add [esp], 1
then there are actually two memory operations and it seems that the register
allocator should weight it accordingly.

https://codereview.chromium.org/1312433004/diff/60001/src/IceInst.cpp#newcode208
src/IceInst.cpp:208: Var->addUse(1);
So there's kind of a maybe sort of big problem here.

Liveness analysis is a dataflow algorithm that iterates until convergence.  If
the Cfg nodes are topologically sorted and there are no loops (i.e., backward
branches), everything is find and liveness converges after one iteration per
node.  But if there is a loop, convergence is generally proportional to the loop
nest depth.  I think this means that the uses will end up being counted N times
when they are inside a loop nest of depth N.

Maybe that's OK since we anyway want to apply higher weight inside loops, but
it's not necessarily strictly the use count.

So far, the best solution I can think of (other than just living with the
approximate count) is a separate pass instead of combining it with liveness
analysis.  Otherwise you need some way of representing per-block use counts, and
you have to make use of sparsity, and that's tough.

https://codereview.chromium.org/1312433004/diff/60001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/1312433004/diff/60001/src/IceOperand.h#newcod...
src/IceOperand.h:412: ShouldHaveRegister,
I prefer to prefix enum values with some prefix, like RR_ .

Also, "Should" suggests something too strong here -- maybe MayHaveRegister or
NoRequirement ?

[jvoung (off chromium), 2015-08-27 18:34:27]

https://codereview.chromium.org/1312433004/diff/60001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/1312433004/diff/60001/src/IceInst.cpp#newcode185
src/IceInst.cpp:185: Live[VarNum] = false;
On 2015/08/27 05:03:06, stichnot wrote:
> I kind of expected Dest to be marked as having a use here.
> 
> Maybe that doesn't really matter because non-SSA variables with more than one
> definition are only infinite-weight variables from lowering?
> 
> Maybe that unfairly diminishes weights of function arguments, which lack
> explicit definitions?
> 
> If you mean to not track the use of Dest here, it's probably good to leave a
> comment.
> 
> EDIT: I see this issue was already discussed.  I actually vote for counting
the
> dest var as a use.  Ignoring the fact that two-address instructions generally
> involve infinite-weight variables, if we have an instruction like this:
>   add [esp], 1
> then there are actually two memory operations and it seems that the register
> allocator should weight it accordingly.


I'm not against counting Dests too, but wanted to understand what would be
affected.

https://codereview.chromium.org/1312433004/diff/60001/src/IceInst.cpp#newcode208
src/IceInst.cpp:208: Var->addUse(1);
On 2015/08/27 05:03:06, stichnot wrote:
> So there's kind of a maybe sort of big problem here.
> 
> Liveness analysis is a dataflow algorithm that iterates until convergence.  If
> the Cfg nodes are topologically sorted and there are no loops (i.e., backward
> branches), everything is find and liveness converges after one iteration per
> node.  But if there is a loop, convergence is generally proportional to the
loop
> nest depth.  I think this means that the uses will end up being counted N
times
> when they are inside a loop nest of depth N.
> 
> Maybe that's OK since we anyway want to apply higher weight inside loops, but
> it's not necessarily strictly the use count.
> 
> So far, the best solution I can think of (other than just living with the
> approximate count) is a separate pass instead of combining it with liveness
> analysis.  Otherwise you need some way of representing per-block use counts,
and
> you have to make use of sparsity, and that's tough.

Good point =)  So the TODO was almost done ;-)

Seems better to be more explicit about the loop nest and have a separate pass
then? I was about to suggest making it part of the VMetadata init() pass, but
that's run multiple times while this is only needed for regalloc.

Also, be careful about where the Var->resetUses() is done. That currently
happens as part of resetLiveRange(), but that's after Inst::liveness()?

[Jim Stichnoth, 2015-08-27 20:04:21]

https://codereview.chromium.org/1312433004/diff/60001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/1312433004/diff/60001/src/IceInst.cpp#newcode208
src/IceInst.cpp:208: Var->addUse(1);
On 2015/08/27 18:34:27, jvoung wrote:
> On 2015/08/27 05:03:06, stichnot wrote:
> > So there's kind of a maybe sort of big problem here.
> > 
> > Liveness analysis is a dataflow algorithm that iterates until convergence. 
If
> > the Cfg nodes are topologically sorted and there are no loops (i.e.,
backward
> > branches), everything is find and liveness converges after one iteration per
> > node.  But if there is a loop, convergence is generally proportional to the
> loop
> > nest depth.  I think this means that the uses will end up being counted N
> times
> > when they are inside a loop nest of depth N.
> > 
> > Maybe that's OK since we anyway want to apply higher weight inside loops,
but
> > it's not necessarily strictly the use count.
> > 
> > So far, the best solution I can think of (other than just living with the
> > approximate count) is a separate pass instead of combining it with liveness
> > analysis.  Otherwise you need some way of representing per-block use counts,
> and
> > you have to make use of sparsity, and that's tough.
> 
> Good point =)  So the TODO was almost done ;-)
> 
> Seems better to be more explicit about the loop nest and have a separate pass
> then? I was about to suggest making it part of the VMetadata init() pass, but
> that's run multiple times while this is only needed for regalloc.
> 
> Also, be careful about where the Var->resetUses() is done. That currently
> happens as part of resetLiveRange(), but that's after Inst::liveness()?

Actually, incrementing the use count right at the start of
VariableTracking::markUse() seems like a really good idea.

[ascull, 2015-08-28 19:26:36]

Now the counting happen along with the VariableMetadata.

Below show the previous number of Spill+Fill and the new number for the spec2k.
There are a few thousand less in each case. How it affect performance I don't
know as my measurements haven't been very consistent.

 old   ->  new
---------------
58689  -> 44313
14333  -> 11257
16110  -> 12892
26769  -> 21959
9610   -> 7420
29585  -> 24253
125167 -> 94076
14255  -> 11143
33932  -> 26350
22449  -> 17334
50773  -> 34880
41897  -> 29868
37187  -> 29872
10145  -> 8200
45011  -> 33784
54580  -> 44431

https://codereview.chromium.org/1312433004/diff/60001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/1312433004/diff/60001/src/IceInst.cpp#newcode185
src/IceInst.cpp:185: Live[VarNum] = false;
On 2015/08/27 18:34:27, jvoung wrote:
> On 2015/08/27 05:03:06, stichnot wrote:
> > I kind of expected Dest to be marked as having a use here.
> > 
> > Maybe that doesn't really matter because non-SSA variables with more than
one
> > definition are only infinite-weight variables from lowering?
> > 
> > Maybe that unfairly diminishes weights of function arguments, which lack
> > explicit definitions?
> > 
> > If you mean to not track the use of Dest here, it's probably good to leave a
> > comment.
> > 
> > EDIT: I see this issue was already discussed.  I actually vote for counting
> the
> > dest var as a use.  Ignoring the fact that two-address instructions
generally
> > involve infinite-weight variables, if we have an instruction like this:
> >   add [esp], 1
> > then there are actually two memory operations and it seems that the register
> > allocator should weight it accordingly.
> 
> 
> I'm not against counting Dests too, but wanted to understand what would be
> affected.

Dest counting will return.

https://codereview.chromium.org/1312433004/diff/60001/src/IceInst.cpp#newcode208
src/IceInst.cpp:208: Var->addUse(1);
On 2015/08/27 20:04:21, stichnot wrote:
> On 2015/08/27 18:34:27, jvoung wrote:
> > On 2015/08/27 05:03:06, stichnot wrote:
> > > So there's kind of a maybe sort of big problem here.
> > > 
> > > Liveness analysis is a dataflow algorithm that iterates until convergence.

> If
> > > the Cfg nodes are topologically sorted and there are no loops (i.e.,
> backward
> > > branches), everything is find and liveness converges after one iteration
per
> > > node.  But if there is a loop, convergence is generally proportional to
the
> > loop
> > > nest depth.  I think this means that the uses will end up being counted N
> > times
> > > when they are inside a loop nest of depth N.
> > > 
> > > Maybe that's OK since we anyway want to apply higher weight inside loops,
> but
> > > it's not necessarily strictly the use count.
> > > 
> > > So far, the best solution I can think of (other than just living with the
> > > approximate count) is a separate pass instead of combining it with
liveness
> > > analysis.  Otherwise you need some way of representing per-block use
counts,
> > and
> > > you have to make use of sparsity, and that's tough.
> > 
> > Good point =)  So the TODO was almost done ;-)
> > 
> > Seems better to be more explicit about the loop nest and have a separate
pass
> > then? I was about to suggest making it part of the VMetadata init() pass,
but
> > that's run multiple times while this is only needed for regalloc.
> > 
> > Also, be careful about where the Var->resetUses() is done. That currently
> > happens as part of resetLiveRange(), but that's after Inst::liveness()?
> 
> Actually, incrementing the use count right at the start of
> VariableTracking::markUse() seems like a really good idea.

Moved into VMetadata.

https://codereview.chromium.org/1312433004/diff/60001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/1312433004/diff/60001/src/IceOperand.h#newcod...
src/IceOperand.h:412: ShouldHaveRegister,
On 2015/08/27 05:03:06, stichnot wrote:
> I prefer to prefix enum values with some prefix, like RR_ .
> 
> Also, "Should" suggests something too strong here -- maybe MayHaveRegister or
> NoRequirement ?

Done.

[jvoung (off chromium), 2015-08-28 20:31:45]

otherwise LGTM -- the new spill+fill counts are pretty encouraging!

https://codereview.chromium.org/1312433004/diff/100001/src/IceInst.cpp
File src/IceInst.cpp (left):

https://codereview.chromium.org/1312433004/diff/100001/src/IceInst.cpp#oldcod...
src/IceInst.cpp:206: const Variable *Var = Src->getVar(J);
any reason for this change?

https://codereview.chromium.org/1312433004/diff/100001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/1312433004/diff/100001/src/IceOperand.h#newco...
src/IceOperand.h:497: /// RegNumTmp, Weight, Live, LoVar, HiVar, VarsReal.
can remove Weight field comment too

https://codereview.chromium.org/1312433004/diff/100001/src/IceOperand.h#newco...
src/IceOperand.h:654: /// loop nest depth facter for each use.
facter -> factor

https://codereview.chromium.org/1312433004/diff/100001/tests_lit/assembler/x8...
File tests_lit/assembler/x86/jump_encodings.ll (right):

https://codereview.chromium.org/1312433004/diff/100001/tests_lit/assembler/x8...
tests_lit/assembler/x86/jump_encodings.ll:174: ; CHECK-NEXT: {{.*}} mov
{{.*}},0x1
Hmm yes, this test is pretty brittle and annoying to update. However, removing
the instruction addresses and jmp targets mean it's not testing anything new
(the "make sure that the instruction size accounting for the forward branches
are correct").

On possible middle-ground is to only check the jmp to %next2 and the address of
%next2.

That is, keep the address of mov {{.*}},0x1 (the first instruction for %next2),
and keep the target of the last jmp (which goes to %next2). For me, the address
is 0x16.

[ascull, 2015-08-28 21:22:37]

https://codereview.chromium.org/1312433004/diff/100001/src/IceInst.cpp
File src/IceInst.cpp (left):

https://codereview.chromium.org/1312433004/diff/100001/src/IceInst.cpp#oldcod...
src/IceInst.cpp:206: const Variable *Var = Src->getVar(J);
On 2015/08/28 20:31:45, jvoung wrote:
> any reason for this change?

There was, but no longer. Done.

https://codereview.chromium.org/1312433004/diff/100001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/1312433004/diff/100001/src/IceOperand.h#newco...
src/IceOperand.h:497: /// RegNumTmp, Weight, Live, LoVar, HiVar, VarsReal.
On 2015/08/28 20:31:45, jvoung wrote:
> can remove Weight field comment too

Done.

https://codereview.chromium.org/1312433004/diff/100001/src/IceOperand.h#newco...
src/IceOperand.h:654: /// loop nest depth facter for each use.
On 2015/08/28 20:31:45, jvoung wrote:
> facter -> factor

Done.

https://codereview.chromium.org/1312433004/diff/100001/tests_lit/assembler/x8...
File tests_lit/assembler/x86/jump_encodings.ll (right):

https://codereview.chromium.org/1312433004/diff/100001/tests_lit/assembler/x8...
tests_lit/assembler/x86/jump_encodings.ll:174: ; CHECK-NEXT: {{.*}} mov
{{.*}},0x1
On 2015/08/28 20:31:45, jvoung wrote:
> Hmm yes, this test is pretty brittle and annoying to update. However, removing
> the instruction addresses and jmp targets mean it's not testing anything new
> (the "make sure that the instruction size accounting for the forward branches
> are correct").
> 
> On possible middle-ground is to only check the jmp to %next2 and the address
of
> %next2.
> 
> That is, keep the address of mov {{.*}},0x1 (the first instruction for
%next2),
> and keep the target of the last jmp (which goes to %next2). For me, the
address
> is 0x16.

Done.

[ascull, 2015-08-28 21:24:19]

Committed patchset #7 (id:120001) manually as
11c9a325399b282cb4ea7d1d24d42fceeec2a09a (presubmit successful).