Subzero: Refactor tracking of Defs and block-local Variables.

Subzero: Refactor tracking of Defs and block-local Variables.

This affects tracking of two kinds of Variable metadata: whether a
Variable is block-local (i.e., all uses are in a single block) and if
so, which CfgNode that is; and whether a Variable has a single defining
instruction, and if so, which Inst that is.

Originally, this metadata was constructed incrementally, which was
quite fragile and most likely inaccurate under many circumstances.

In the new approach, this metadata is reconstructed in a separate pass
as needed.

As a side benefit, the metadata fields are removed from each Variable
and pulled into a separate structure, shrinking the size of Variable.

There should be no functional changes, except that simple stack slot
coalescing is turned off under Om1, since it takes a separate pass to
calculate block-local variables, and passes are minimized under Om1.
As a result, a couple of the lit tests needed to be changed.

There are a few non-mechanical changes, generally to tighten up
Variable tracking for liveness analysis.

This is being done mainly to get precise Variable definition
information so that register allocation can infer the best register
preferences as well as when overlapping live ranges are allowable.

BUG=none
R=jvoung@chromium.org

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

[Jim Stichnoth, 2014-09-22 05:31:37]

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

[Jim Stichnoth, 2014-09-22 12:54:24]

> There should be no functional changes

Comparing the asm output determined that was a lie.

Notably, the new code is much better at finding block-local variables and
applying simple stack slot coalescing.  This seems to be because the old code
would mark source operands of Phi instructions as multi-block and they would
stay that way, even after Phi lowering made them actually single-block.  This
doesn't actually show up on the simple lit tests, but it's quite apparent on the
spec2k tests.

Also, it turned out that arg variables were being marked as multi-def simply
because a defining instruction wasn't found.  This would restrict address mode
optimization, notably on simple_loop.ll.  This is fixed in the latest patchset.

I'm still investigating minor diffs in instruction counts on spec, where the new
code sometimes generates more instructions.

[jvoung (off chromium), 2014-09-22 17:07:29]

https://codereview.chromium.org/589003002/diff/40001/src/IceConverter.cpp
File src/IceConverter.cpp (left):

https://codereview.chromium.org/589003002/diff/40001/src/IceConverter.cpp#old...
src/IceConverter.cpp:135: assert(CurrentNode);
It seems like CurrentNode is not read anymore, so can it be removed?

https://codereview.chromium.org/589003002/diff/40001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/589003002/diff/40001/src/IceOperand.cpp#newco...
src/IceOperand.cpp:167: if (Var->getIsArg()) {
Why not use the Func->getArgs() list, which will have fewer variables to iterate
over? It looks like lowerArguments() should keep the list in tact (new variables
which are setIsArg() should take the place in the list, and the old variables
are setIsArg(false)).

https://codereview.chromium.org/589003002/diff/40001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/589003002/diff/40001/src/IceOperand.h#newcode504
src/IceOperand.h:504: void markUse(const Inst *Instr, const CfgNode *Node, bool
IsFromDef) {
Should markUse not be inlined, since it seems like it could be rather big?

https://codereview.chromium.org/589003002/diff/40001/src/IceOperand.h#newcode510
src/IceOperand.h:510: // assert(Node);
assert(Node); is commented out -- just remove?

There's also a check that "if (Node == NULL || ...)" below that would seem to
contradict the assert. When can Node be NULL?

[Jim Stichnoth, 2014-09-22 21:00:46]

https://codereview.chromium.org/589003002/diff/40001/src/IceConverter.cpp
File src/IceConverter.cpp (left):

https://codereview.chromium.org/589003002/diff/40001/src/IceConverter.cpp#old...
src/IceConverter.cpp:135: assert(CurrentNode);
On 2014/09/22 17:07:29, jvoung wrote:
> It seems like CurrentNode is not read anymore, so can it be removed?

Nice!  Done.

https://codereview.chromium.org/589003002/diff/40001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/589003002/diff/40001/src/IceOperand.cpp#newco...
src/IceOperand.cpp:167: if (Var->getIsArg()) {
On 2014/09/22 17:07:29, jvoung wrote:
> Why not use the Func->getArgs() list, which will have fewer variables to
iterate
> over? It looks like lowerArguments() should keep the list in tact (new
variables
> which are setIsArg() should take the place in the list, and the old variables
> are setIsArg(false)).

The only problem with using Func->getArgs() is the getPhysicalRegister() hack
where esp is marked as an arg so that it is considered live upon function entry.

A better approach (see latest patchset) is to maintain two separate lists: the
original arg list (variables that by definition are live coming in), and a list
of implicit args, which could include esp, a reserved register for a TLS
pointer, etc.

https://codereview.chromium.org/589003002/diff/40001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/589003002/diff/40001/src/IceOperand.h#newcode504
src/IceOperand.h:504: void markUse(const Inst *Instr, const CfgNode *Node, bool
IsFromDef) {
On 2014/09/22 17:07:29, jvoung wrote:
> Should markUse not be inlined, since it seems like it could be rather big?

Done, and the same for markDef() for symmetry.

https://codereview.chromium.org/589003002/diff/40001/src/IceOperand.h#newcode510
src/IceOperand.h:510: // assert(Node);
On 2014/09/22 17:07:29, jvoung wrote:
> assert(Node); is commented out -- just remove?
> 
> There's also a check that "if (Node == NULL || ...)" below that would seem to
> contradict the assert. When can Node be NULL?

VariablesMetadata::init() passes in Node=NULL for items on the Cfg arglist,
which then triggers these arguments to be marked as multi-block use.  Without
that, we run into liveness problems/asserts with arguments, especially with the
esp case in the presence of stacksave/stackrestore intrinsics.

That said, I changed this to add an explicit argument indicating an implicit
function arg like esp, which always gets marked as multiblock.  This way, we can
assert(Node) safely.

[jvoung (off chromium), 2014-09-22 21:29:55]

LGTM

[jvoung (off chromium), 2014-09-22 21:48:03]

https://codereview.chromium.org/589003002/diff/60001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/589003002/diff/60001/src/IceOperand.cpp#newco...
src/IceOperand.cpp:230: for (VarList::const_iterator I = ArgList.begin(), E =
ArgList.end(); I != E;
Hmm, actually, split64() also creates new variables and does setIsArg(), but it
doesn't add it to the list?

[Jim Stichnoth, 2014-09-22 22:25:07]

https://codereview.chromium.org/589003002/diff/60001/src/IceOperand.cpp
File src/IceOperand.cpp (right):

https://codereview.chromium.org/589003002/diff/60001/src/IceOperand.cpp#newco...
src/IceOperand.cpp:230: for (VarList::const_iterator I = ArgList.begin(), E =
ArgList.end(); I != E;
On 2014/09/22 21:48:03, jvoung wrote:
> Hmm, actually, split64() also creates new variables and does setIsArg(), but
it
> doesn't add it to the list?

Interesting.  I guess I was over-zealous in marking these uses.  I removed the
marking of explicit args, and there was no difference in the asm generated
across all of spec2k, nor in the fully verbose output across all the lit tests.

[Jim Stichnoth, 2014-09-22 23:03:09]

Committed patchset #5 (id:80001) manually as 144cdce (presubmit successful).