Subzero: Simplify the FakeKill instruction.

Subzero: Simplify the FakeKill instruction.

Even after earlier simplifications, FakeKill was still handled somewhat inefficiently for the register allocator.  For x86-32, any function containing call instructions would result in about 11 pre-colored Variables, each with an identical and relatively complex live range consisting of points.  They would start out on the UnhandledPrecolored list, then all move to the Inactive list, where they would be repeatedly compared against each register allocation candidate via overlapsRange().

We improve this by keeping around a single copy of that live range and directly masking out the Free[] register set when that live range overlaps the current candidate's live range.  This saves ~10 overlaps() calculations per candidate while FakeKills are still pending.

Also, slightly rearrange the initialization of the Unhandled etc. sets into a separate init routine, which will make it easier to reuse the register allocator in other situations such as Om1 post-lowering.

BUG= none
R=jvoung@chromium.org

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

[Jim Stichnoth, 2014-11-14 00:38:55]

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

[Jim Stichnoth, 2014-11-14 00:51:13]

This appears to give a 2-3% performance improvement.

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

https://codereview.chromium.org/720343003/diff/20001/src/IceRegAlloc.cpp#oldc...
src/IceRegAlloc.cpp:328: overlapsDefs(Func, Cur, Item)) {
It turns out this code had a bug, because a pre-colored variable originating
from a FakeKill instruction did not have any defining instructions tabulated in
VMetadata, and therefore overlapsDefs() would always return false, sometimes
incorrectly.  As a result, AllowOverlap could be set to true even though Cur
overlapped with a FakeKill register.

[jvoung (off chromium), 2014-11-14 16:47:23]

Cool! LGTM

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

https://codereview.chromium.org/720343003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:180: llvm::SmallBitVector KillsMask =
Func->getTarget()->getRegisterSet(
Can the kills mask be lifted out of the while loop? It is also const?

[jvoung (off chromium), 2014-11-14 17:01:09]

https://codereview.chromium.org/720343003/diff/20001/src/IceOperand.h
File src/IceOperand.h (left):

https://codereview.chromium.org/720343003/diff/20001/src/IceOperand.h#oldcode313
src/IceOperand.h:313: // LiveRange &operator=(const LiveRange &) = delete;
Oh, also I didn't spot where this change was needed (new use in a vector?), so
just checking if this is actually for a later change or maybe I just missed it.

[Jim Stichnoth, 2014-11-14 18:27:03]

https://codereview.chromium.org/720343003/diff/20001/src/IceOperand.h
File src/IceOperand.h (left):

https://codereview.chromium.org/720343003/diff/20001/src/IceOperand.h#oldcode313
src/IceOperand.h:313: // LiveRange &operator=(const LiveRange &) = delete;
On 2014/11/14 17:01:09, jvoung wrote:
> Oh, also I didn't spot where this change was needed (new use in a vector?), so
> just checking if this is actually for a later change or maybe I just missed
it.

Sorry, this was just cleanup while I was in the neighborhood.  Based on Roland's
suggestion in https://codereview.chromium.org/643903006/ .

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

https://codereview.chromium.org/720343003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:180: llvm::SmallBitVector KillsMask =
Func->getTarget()->getRegisterSet(
On 2014/11/14 16:47:23, jvoung wrote:
> Can the kills mask be lifted out of the while loop? It is also const?

Good point, done.

[Jim Stichnoth, 2014-11-14 18:27:33]

Committed patchset #3 (id:40001) manually as
87ff3a186eb0e5a9ff791964e377910acceed84e (presubmit successful).