Subzero: Consider all instruction variables for register preference.

Subzero: Consider all instruction variables for register preference.

The original code only looked at top-level source operands in the defining instruction, with a TODO to instead consider all inner variables in the instruction.

The primary reason is so that we end up with more instructions like
  mov eax, eax
which are later elided as redundant assignments.

A secondary reason is to foster more instructions like:
  mov ecx, [ecx]
rather than
  mov eax, [ecx]
where ecx's live range ends.  This hopefully keeps eax (in the latter case) free for longer and maybe allow some other variable to get a register.  By considering all instruction variables, we enable this.

BUG= none
R=jpp@chromium.org

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

[Jim Stichnoth, 2015-10-12 00:27:09]

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

[John, 2015-10-12 15:35:17]

lgtm

lgtm otherwise

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceInstARM32.h
File src/IceInstARM32.h (right):

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceInstARM32.h#n...
src/IceInstARM32.h:1155: bool isVarAssign() const override { return
llvm::isa<Variable>(getSrc(0)); }
this method is inline, but the other is not. does it matter?

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceInstX86Base.h
File src/IceInstX86Base.h (right):

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceInstX86Base.h...
src/IceInstX86Base.h:980: bool isVarAssign() const override {
the previous (inline) method is defined in a single line, this one isn't. does
it matter?

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceRegAlloc.cpp#...
src/IceRegAlloc.cpp:504: if (SrcVar->hasRegTmp() && (Iter.RegMask &
*RegAliases[SrcReg]).any()) {
this is super hard to read!!!

const bool SrcVarRegAliasAvailable = (set & set).any();

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceRegAlloc.cpp#...
src/IceRegAlloc.cpp:544: // TODO(stichnot): Do this with bitvector ops, not a
loop, for efficiency.
this is a simple TODOne:

for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; RegAlias =
Aliases.find_next(RegAlias)) {
...
}

change it now?

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceRegAlloc.cpp#...
src/IceRegAlloc.cpp:859: // correctness issue.
This is definitively a correctness issue... :(

https://chromiumcodereview.appspot.com/1392383003/diff/1/tests_lit/llvm2ice_t...
File tests_lit/llvm2ice_tests/64bit.pnacl.ll (right):

https://chromiumcodereview.appspot.com/1392383003/diff/1/tests_lit/llvm2ice_t...
tests_lit/llvm2ice_tests/64bit.pnacl.ll:517: ; ARM32: orr     [[T3:r[0-9]+]],
[[T0]], r1, lsl [[T1]]
why/how did this change?

[Jim Stichnoth, 2015-10-12 17:27:31]

PTAL.

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceInstARM32.h
File src/IceInstARM32.h (right):

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceInstARM32.h#n...
src/IceInstARM32.h:1155: bool isVarAssign() const override { return
llvm::isa<Variable>(getSrc(0)); }
On 2015/10/12 15:35:16, John wrote:
> this method is inline, but the other is not. does it matter?

The implementation of InstAssign::isVarAssign() had to be moved into the .cpp
file, instead of being inline, because the Variable class definition wasn't yet
available.

That turns out not to be the case in these IceInst*.h files, so I'll keep it
inline until it breaks...

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceInstX86Base.h
File src/IceInstX86Base.h (right):

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceInstX86Base.h...
src/IceInstX86Base.h:980: bool isVarAssign() const override {
On 2015/10/12 15:35:16, John wrote:
> the previous (inline) method is defined in a single line, this one isn't. does
> it matter?

(same answer as before)

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceRegAlloc.cpp#...
src/IceRegAlloc.cpp:504: if (SrcVar->hasRegTmp() && (Iter.RegMask &
*RegAliases[SrcReg]).any()) {
On 2015/10/12 15:35:17, John wrote:
> this is super hard to read!!!
> 
> const bool SrcVarRegAliasAvailable = (set & set).any();
> 

Done.  Note that I want to put the cheap hasRegTmp() test before the more
expensive bitvector operation.

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceRegAlloc.cpp#...
src/IceRegAlloc.cpp:544: // TODO(stichnot): Do this with bitvector ops, not a
loop, for efficiency.
On 2015/10/12 15:35:17, John wrote:
> this is a simple TODOne:
> 
> for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; RegAlias =
> Aliases.find_next(RegAlias)) {
> ...
> }
> 
> change it now?

What I mean is, I think it can be changed to something like:

Iter.Free ~= ~Aliases;
if (Iter.AllowOverlap && Item != Iter.Prefer && Aliases[Iter.PreferReg] &&
overlapsDefs(...)) ...

I'm planning to do it as part of the x86-32 proper register aliasing
CL, so I can test that before-and-after output on spec2k is identical.

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceRegAlloc.cpp#...
src/IceRegAlloc.cpp:859: // correctness issue.
On 2015/10/12 15:35:17, John wrote:
> This is definitively a correctness issue... :(

Yeah, I want to address it in the context of the x86-32 proper register aliasing
CL, where I have a chance of actually testing it.

https://chromiumcodereview.appspot.com/1392383003/diff/1/tests_lit/llvm2ice_t...
File tests_lit/llvm2ice_tests/64bit.pnacl.ll (right):

https://chromiumcodereview.appspot.com/1392383003/diff/1/tests_lit/llvm2ice_t...
tests_lit/llvm2ice_tests/64bit.pnacl.ll:517: ; ARM32: orr     [[T3:r[0-9]+]],
[[T0]], r1, lsl [[T1]]
On 2015/10/12 15:35:17, John wrote:
> why/how did this change?

Turns out it shouldn't have changed, and the "break;" statement inside the
FOREACH_VAR_IN_INST() wasn't doing what I expected.

After fixing it to use a BREAK macro, this test output is back to the original
version.

[John, 2015-10-12 20:39:58]

lgtm

Still LGTM.

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://chromiumcodereview.appspot.com/1392383003/diff/1/src/IceRegAlloc.cpp#...
src/IceRegAlloc.cpp:504: if (SrcVar->hasRegTmp() && (Iter.RegMask &
*RegAliases[SrcReg]).any()) {
On 2015/10/12 17:27:31, stichnot wrote:
> On 2015/10/12 15:35:17, John wrote:
> > this is super hard to read!!!
> > 
> > const bool SrcVarRegAliasAvailable = (set & set).any();
> > 
> 
> Done.  Note that I want to put the cheap hasRegTmp() test before the more
> expensive bitvector operation.

Then you can define a static method (in an unnamed name space)

namespace {
bool SrcVarRegAliasAvaiabke(Iter, RegAliases[SrcReg]) {
}
}

[Jim Stichnoth, 2015-10-12 22:24:52]

Committed patchset #2 (id:20001) manually as
28b71be495bb1eada446ba36b5236914d79cea0e (presubmit successful).