Subzero: Fix the simple register allocation for -Om1.

Subzero: Fix the simple register allocation for -Om1.

Background: After lowering each high-level ICE instruction, Om1 calls
postLower() to do simple register allocation.  It only assigns
registers where absolutely necessary, specifically for infinite-weight
variables, while honoring pre-coloring decisions.  The original Om1
register allocation never tried to reuse registers within a lowered
sequence, which was generally OK except for very long lowering
sequences, such as call instructions or some intrinsics.  In these
cases, when it ran out of physical registers, it would just reset the
free list and hope for the best, but with no guarantee of correctness.

The fix involves keeping track of which instruction in the lowered
sequence holds the last use of each variable, and releasing each
register back to the free list after its last use.  This makes much
better use of registers.  It's not necessarily optimal, at least with
respect to pre-colored variables, since those registers are
black-listed even if they don't interfere with an infinite-weight
variable.

BUG= none
R=jvoung@chromium.org

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

[Jim Stichnoth, 2014-08-16 06:32:00]

Adding Matt as a reviewer for old times' sake.  (Also, this is an improvement
that is needed for randomized register allocation.)

[wala, 2014-08-18 04:44:54]

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

https://codereview.chromium.org/483453002/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4156: std::map<const Variable *, const Inst *>
LastUses;
How about a DenseMap?

"DenseMap is a great way to map pointers to pointers, or map other small types
to each other."

http://llvm.org/docs/ProgrammersManual.html#llvm-adt-densemap-h

https://codereview.chromium.org/483453002/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4205: Srcs[i] = Inst->getSrc(i);
Now that Dest is included in this iteration, should there ever be a situation
where you encounter an unassigned infinite weight source operand? That would
seem to imply that the source was used before being defined.

https://codereview.chromium.org/483453002/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4221: if (Var->hasReg() && LastUses[Var] == Inst)
{
Would it make sense to assert that if Var->hasReg(), then Var->getRegNum() is
not in AvailableRegisters? This would help validate the assumption you mention
in the comment on line 4198.

[wala, 2014-08-18 04:46:31]

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

https://codereview.chromium.org/483453002/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4205: Srcs[i] = Inst->getSrc(i);
On 2014/08/18 04:44:54, wala wrote:
> Now that Dest is included in this iteration, should there ever be a situation
> where you encounter an unassigned infinite weight source operand? That would
> seem to imply that the source was used before being defined.

I meant "Dest is included in this OperandList"

[jvoung (off chromium), 2014-08-18 16:26:08]

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

https://codereview.chromium.org/483453002/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4166: continue;
The second pass doesn't skip InstFakeKill, could they potentially affect the
LastUses also?

[Jim Stichnoth, 2014-08-18 17:31:02]

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

https://codereview.chromium.org/483453002/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4156: std::map<const Variable *, const Inst *>
LastUses;
On 2014/08/18 04:44:54, wala wrote:
> How about a DenseMap?
> 
> "DenseMap is a great way to map pointers to pointers, or map other small types
> to each other."
> 
> http://llvm.org/docs/ProgrammersManual.html#llvm-adt-densemap-h

Nice, done.

https://codereview.chromium.org/483453002/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4166: continue;
On 2014/08/18 16:26:07, jvoung wrote:
> The second pass doesn't skip InstFakeKill, could they potentially affect the
> LastUses also?

It probably wouldn't affect LastUses, because InstFakeKill currently just uses
special Variable instances that are pre-colored.

All the same, I added similar logic to skip these instructions, because they do
interfere with the assertion that Matt suggests below.

https://codereview.chromium.org/483453002/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4205: Srcs[i] = Inst->getSrc(i);
On 2014/08/18 04:46:31, wala wrote:
> On 2014/08/18 04:44:54, wala wrote:
> > Now that Dest is included in this iteration, should there ever be a
situation
> > where you encounter an unassigned infinite weight source operand? That would
> > seem to imply that the source was used before being defined.
> 
> I meant "Dest is included in this OperandList"

This should generally be the case for local variables (including arguments)
defined at the bitcode level.  Infinite-weight and pre-colored are usually just
for the temporaries that are part of the lowering expansion.

https://codereview.chromium.org/483453002/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4221: if (Var->hasReg() && LastUses[Var] == Inst)
{
On 2014/08/18 04:44:54, wala wrote:
> Would it make sense to assert that if Var->hasReg(), then Var->getRegNum() is
> not in AvailableRegisters? This would help validate the assumption you mention
> in the comment on line 4198.

Done.

BTW, this required initializing RegExclude to RegSet_StackPointer instead of
RegSet_None, otherwise the stacksave/stackrestore intrinsics would cause an
assertion failure in this new assert.

[jvoung (off chromium), 2014-08-18 17:46:50]

lgtm

[Jim Stichnoth, 2014-08-18 17:54:44]

One of the tests needed to be updated after rebasing.

[Jim Stichnoth, 2014-08-18 17:55:24]

Committed patchset #4 manually as 4d79fe5 (presubmit successful).