Subzero: Allow delaying Phi lowering until after register allocation.

Subzero: Implementation of "advanced Phi lowering".

Delays Phi lowering until after register allocation.  This lets the Phi assignment order take register allocation into account and avoid creating false dependencies.

All edges that lead to Phi instructions are split, and the new node gets mov instructions in the correct topological order, using available physical registers as needed.

This lowering style is controllable under -O2 using -phi-edge-split (enabled by default).

The result is faster translation time (due to fewer temporaries leading to faster liveness analysis and register allocation) as well as better code quality (due to better register allocation and fewer phi-based assignments).

BUG= none
R=jvoung@chromium.org

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

[Jim Stichnoth, 2014-10-26 06:15:33]

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

[jvoung (off chromium), 2014-10-27 22:12:21]

whew

https://codereview.chromium.org/680733002/diff/60001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/680733002/diff/60001/src/IceCfg.cpp#newcode194
src/IceCfg.cpp:194: Nodes[Cur++] = Node;
Would it be good to renumber the nodes too (the "Node->getIndex() / Number"
field)?

Maybe not... downside is that dump() could end up confusing if the node label
synthesized from the number changes as the passes run.

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:219: // out-edge list, this node's in-edge list, and the Phi
instruction's
So if this happens, the phi lowering might be wrong? (assignments only apply to
one of the edges and not the other?)

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:284: // Phi scheduling until after register allocation can
helps unless
"can helps" -> "can help"

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:295: // earlier, in case that register becomes free
afterwards; and prefer
", and" instead of "; and" ?

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:342: if (Desc[I].Processed)
It wasn't clear to me why Processed would be true at this point, considering the
for-loop right before sets Desc[I].Processed = false, for each I? Same below.

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:421: // Set Tmp's optional Name parameter to something like
Did you want to do the name-setting here, or mark as TODO?

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:444: if (Variable *Var = llvm::dyn_cast<Variable>(Src)) {
nit: could auto this too

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:769: I->repointEdge(this, OutEdges[0]);
Could break out of the loop here too, once the edge is found? (could also
iterate over instructions in reverse)

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

https://codereview.chromium.org/680733002/diff/60001/src/IceInst.cpp#newcode138
src/IceInst.cpp:138: // Returns true if the instruction is tentatively retained,
or false
nit: Might be clearer if the return value is described in terms of live vs dead,
since this is a liveness() function (vs deleted which is what a separate pass
would do with this info)

https://codereview.chromium.org/680733002/diff/60001/src/IceInst.cpp#newcode275
src/IceInst.cpp:275: return false;
Should this always succeed or no (only be one terminator in block)?

https://codereview.chromium.org/680733002/diff/60001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/680733002/diff/60001/src/IceInst.h#newcode117
src/IceInst.h:117: bool liveness(InstNumberT InstNumber, LivenessBV &Live,
Liveness *Liveness,
document the meaning of the "bool" return value of liveness()?

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:56: Begin = getNode()->getInsts().begin();
It seems a bit unexpected that this isn't like init() in that it doesn't
skipDeleted(Cur).

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

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:726: if (ComputedLiveRanges &&
!Var->needsStackSlot())
Just for reference, I remember you mentioned there was bug related to the
original getLiveRange().isEmpty() check, but I don't know if there was a simple
reproducer =)

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:1710: // RI is either a physical register or an
immediate.
Seems like the comment on "RI is either..." is no longer true if Dest->hasReg()?

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4177: // actual work of remove the live-in
registers from the set.
"of remove the" -> "of removing the"

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4254: Tmp1->setNeedsStackSlot();
Woh interesting -- Tmp1 is a "makeReg()" so has infinite weight, but it also
NeedsStackSlot. Could makeVariable() be used instead or no?

[Jim Stichnoth, 2014-10-28 01:20:14]

https://codereview.chromium.org/680733002/diff/60001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/680733002/diff/60001/src/IceCfg.cpp#newcode194
src/IceCfg.cpp:194: Nodes[Cur++] = Node;
On 2014/10/27 22:12:20, jvoung wrote:
> Would it be good to renumber the nodes too (the "Node->getIndex() / Number"
> field)?
> 
> Maybe not... downside is that dump() could end up confusing if the node label
> synthesized from the number changes as the passes run.

There is also the issue that Liveness and VariablesMetadata are accessed by node
Number, and so the renumbering would have to be applied to those structures, or
they would have to be invalidated.

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:219: // out-edge list, this node's in-edge list, and the Phi
instruction's
On 2014/10/27 22:12:20, jvoung wrote:
> So if this happens, the phi lowering might be wrong? (assignments only apply
to
> one of the edges and not the other?)

After thinking about this, my belief is that if there are multiple edges from
the same predecessor to the same successor, the Phi source operands must be
identical.  It's possible the LLVM IR validates this, but I doubt the PNaCl
bitcode reader validates it, and Subzero definitely doesn't at this point.

I think the risk is more about accepting invalid bitcode, rather than generating
incorrect code for valid bitcode.

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:284: // Phi scheduling until after register allocation can
helps unless
On 2014/10/27 22:12:21, jvoung wrote:
> "can helps" -> "can help"

Done.

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:295: // earlier, in case that register becomes free
afterwards; and prefer
On 2014/10/27 22:12:21, jvoung wrote:
> ", and" instead of "; and" ?

Done.

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:342: if (Desc[I].Processed)
On 2014/10/27 22:12:21, jvoung wrote:
> It wasn't clear to me why Processed would be true at this point, considering
the
> for-loop right before sets Desc[I].Processed = false, for each I? Same below.

You're right - I think I over-conservatively added those checks at some point. 
Removed the 3 instances before the "for (...Remaining...)" loop.

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:421: // Set Tmp's optional Name parameter to something like
On 2014/10/27 22:12:21, jvoung wrote:
> Did you want to do the name-setting here, or mark as TODO?

I meant it sort of as a weak TODO.  But thinking about it, I just went ahead
made the change.  The string concatenation operation will be rare, and anyway
the "minimal build" will just macro-ignore the string.

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:444: if (Variable *Var = llvm::dyn_cast<Variable>(Src)) {
On 2014/10/27 22:12:21, jvoung wrote:
> nit: could auto this too

Done.

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:769: I->repointEdge(this, OutEdges[0]);
On 2014/10/27 22:12:20, jvoung wrote:
> Could break out of the loop here too, once the edge is found? (could also
> iterate over instructions in reverse)

E.g., there could be a lowered Switch instruction in the predecessor with
multiple edges to this contracted node, and they all need to be repointed.

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

https://codereview.chromium.org/680733002/diff/60001/src/IceInst.cpp#newcode138
src/IceInst.cpp:138: // Returns true if the instruction is tentatively retained,
or false
On 2014/10/27 22:12:21, jvoung wrote:
> nit: Might be clearer if the return value is described in terms of live vs
dead,
> since this is a liveness() function (vs deleted which is what a separate pass
> would do with this info)

Tried to clarify the description (in the .h file).

https://codereview.chromium.org/680733002/diff/60001/src/IceInst.cpp#newcode275
src/IceInst.cpp:275: return false;
On 2014/10/27 22:12:21, jvoung wrote:
> Should this always succeed or no (only be one terminator in block)?

It should fail (return false) only if something gets out of sync between the
CfgNode edges and the branch instruction.  Note that the caller,
splitIncomingEdge(), asserts that some repointing was successful.

https://codereview.chromium.org/680733002/diff/60001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/680733002/diff/60001/src/IceInst.h#newcode117
src/IceInst.h:117: bool liveness(InstNumberT InstNumber, LivenessBV &Live,
Liveness *Liveness,
On 2014/10/27 22:12:21, jvoung wrote:
> document the meaning of the "bool" return value of liveness()?

I had documented it in the .cpp file, so I moved that comment over here.

(It looks like I am very inconsistent about .h versus .cpp documentation, so
that should be fixed at some point.)

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:56: Begin = getNode()->getInsts().begin();
On 2014/10/27 22:12:21, jvoung wrote:
> It seems a bit unexpected that this isn't like init() in that it doesn't
> skipDeleted(Cur).

Refactored init() to call rewind() - and added the skipDeleted() call to
rewind().

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

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:726: if (ComputedLiveRanges &&
!Var->needsStackSlot())
On 2014/10/27 22:12:21, jvoung wrote:
> Just for reference, I remember you mentioned there was bug related to the
> original getLiveRange().isEmpty() check, but I don't know if there was a
simple
> reproducer =)

I think the problem was that the temporary generated for breaking dependence
cycles didn't have a live range associated with it, and at the same time
ComputedLiveRanges was true, so the temporary wasn't getting a stack slot
assigned but was ultimately using a stack offset of 0.  So maybe a reproducer
would be to not set NeedsStackSlot for the temporary...

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:1710: // RI is either a physical register or an
immediate.
On 2014/10/27 22:12:21, jvoung wrote:
> Seems like the comment on "RI is either..." is no longer true if
Dest->hasReg()?

Oops, comment changed.

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4177: // actual work of remove the live-in
registers from the set.
On 2014/10/27 22:12:21, jvoung wrote:
> "of remove the" -> "of removing the"

Done.

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4254: Tmp1->setNeedsStackSlot();
On 2014/10/27 22:12:21, jvoung wrote:
> Woh interesting -- Tmp1 is a "makeReg()" so has infinite weight, but it also
> NeedsStackSlot. Could makeVariable() be used instead or no?

Good point, done.

[Derek Schuff, 2014-10-28 22:35:02]

Context-free ignorant drive-by: premature optimization is the root of all evil.
Wouldn't it make more sense to have mostly-working ARM/x86-64 lowering before
doing this kind of thing so you'd know whether it was really enough of a win ot
justify the extra complexity?

[jvoung (off chromium), 2014-10-29 13:46:51]

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:769: I->repointEdge(this, OutEdges[0]);
On 2014/10/28 01:20:14, stichnot wrote:
> On 2014/10/27 22:12:20, jvoung wrote:
> > Could break out of the loop here too, once the edge is found? (could also
> > iterate over instructions in reverse)
> 
> E.g., there could be a lowered Switch instruction in the predecessor with
> multiple edges to this contracted node, and they all need to be repointed.

Ah okay... I was looking at the way splitIncomingEdge() had called
repointEdge().

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

https://codereview.chromium.org/680733002/diff/60001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:726: if (ComputedLiveRanges &&
!Var->needsStackSlot())
On 2014/10/28 01:20:14, stichnot wrote:
> On 2014/10/27 22:12:21, jvoung wrote:
> > Just for reference, I remember you mentioned there was bug related to the
> > original getLiveRange().isEmpty() check, but I don't know if there was a
> simple
> > reproducer =)
> 
> I think the problem was that the temporary generated for breaking dependence
> cycles didn't have a live range associated with it, and at the same time
> ComputedLiveRanges was true, so the temporary wasn't getting a stack slot
> assigned but was ultimately using a stack offset of 0.  So maybe a reproducer
> would be to not set NeedsStackSlot for the temporary...

Okay, nevermind =)

https://codereview.chromium.org/680733002/diff/80001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/680733002/diff/80001/src/IceCfg.cpp#newcode177
src/IceCfg.cpp:177: if (PredPosition == NoPlace) {
Maybe it would help to describe briefly what Unplaced and Extra are meant to
mean, near the declaration.

It seems like Unplaced nodes will be pretty unusual. It seems like it will be
split nodes, whose predecessor are also split nodes? I'm guessing this because
non-split nodes would have been visited first and be placed, given that split
nodes are inserted at the end in earlier phases. It seems like that can only
happen if the non-split-node predecessor of a split node was empty and
contracted, creating this split node -> split node edge.

The main thing it seems is that Unplaced are just "not ideally placed" because
of luck/iteration order.

https://codereview.chromium.org/680733002/diff/80001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/680733002/diff/80001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:379: // implementation is O(N^2) where N is the number of Phi
Any idea the "usual" # of Phis? (Would the N^2 be a problem? Anyway, this can be
tuned later too, but does look like dealing with cycles will be more work the
O(N) way).

https://codereview.chromium.org/680733002/diff/80001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:432: if (Dest != Src)
Could it be broadened beyond syntactically the same (to include all of
IsSelfAssignment)?

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

https://codereview.chromium.org/680733002/diff/80001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4161: assert(Node->getOutEdges().size() == 1);
Would it help to also also assert that the Node is empty (no existing terminator
branch, since it's added by this)?

https://codereview.chromium.org/680733002/diff/80001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4172: // available (not live) at the beginning of
the block, minus all
At the beginning of the successor block?

I guess because this node is empty, the two are the same, but if the Phis are
considered to be added to the end of this current block, then you're looking for
the LiveIn of the successor?

https://codereview.chromium.org/680733002/diff/80001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4222: if (llvm::isa<ConstantUndef>(Src)) {
Probably rare, but might be good to add a test for this case --  It seems like
isMemoryOperand() is a bit conservative for ConstantUndef of integers (that's
not really mem=mem is it?). It wasn't obvious to me why Undef is made
deterministically 0 here, but not in the branches.

[Jim Stichnoth, 2014-10-29 14:30:54]

On 2014/10/28 22:35:02, Derek Schuff wrote:
> Context-free ignorant drive-by: premature optimization is the root of all
evil.
> Wouldn't it make more sense to have mostly-working ARM/x86-64 lowering before
> doing this kind of thing so you'd know whether it was really enough of a win
ot
> justify the extra complexity?

Fair question.  TL;DR: yes. :)  The data is unfortunately a bit noisy, but:
  - Testing on my z620 workstation
  - Only x86-32 unsandboxed so far, of course
  - Looking at each of the 16 spec2k components
  - Best of 10 translation times
  - Best of 10 run times (using training sets)

Phi edge splitting improves translation time by an average of 5%.  The pass
isn't that expensive, and the win comes from reducing the IR size, especially
when it comes to the super-linear passes like liveness analysis and register
allocation.  A few comments on this:
  - The phi lowering pass itself could use some tuning, as the --timing info
shows it's taking more time than similarly simple passes.
  - I don't expect much difference with sandboxing or targeting different
architectures.
  - 5-10% (and more, after the native bitcode reader and the integrated
assembler are there) is an important step toward Subzero's translation time
goal.

Phi edge splitting improves run time by an average of 10%.
  - Without this, our average spec2k run time is about 5% better than llc -O0,
with 4 out of 16 components doing worse than llc -O0.
  - With phi edge splitting, we are 15% better, with 2 of 16 components doing
worse (13% on equake and 18% on twolf, so there's probably something low-hanging
there).
  - It's still pretty far from llc -O2, but with respect to the llc -O0
performance target, it adds the performance buffer I was hoping for that lets me
try passes that improve translation time at the cost of code quality.
  - I expect fairly similar wins on other architectures because real
applications have similar register pressure at this scale of number of
registers.

This is a rare optimization that improves translation time *and* run time, and I
doubt we'll see more of those.  The only other major translation time improver
on my radar is pre-lowering local register allocation, which will actually make
overall register allocation worse but will similarly reduce the IR size and
improve translation time.

[Jim Stichnoth, 2014-10-30 00:25:27]

(unfortunately it looks like "make format-diff" got a bit more aggressive than
it should have.)

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/680733002/diff/60001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:342: if (Desc[I].Processed)
On 2014/10/28 01:20:14, stichnot wrote:
> On 2014/10/27 22:12:21, jvoung wrote:
> > It wasn't clear to me why Processed would be true at this point, considering
> the
> > for-loop right before sets Desc[I].Processed = false, for each I? Same
below.
> 
> You're right - I think I over-conservatively added those checks at some point.

> Removed the 3 instances before the "for (...Remaining...)" loop.

BTW, these checks are now back after moving the redundant assignment pruning
before the O(N^2) loop.

https://codereview.chromium.org/680733002/diff/80001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/680733002/diff/80001/src/IceCfg.cpp#newcode177
src/IceCfg.cpp:177: if (PredPosition == NoPlace) {
On 2014/10/29 13:46:50, jvoung wrote:
> Maybe it would help to describe briefly what Unplaced and Extra are meant to
> mean, near the declaration.
> 
> It seems like Unplaced nodes will be pretty unusual. It seems like it will be
> split nodes, whose predecessor are also split nodes? I'm guessing this because
> non-split nodes would have been visited first and be placed, given that split
> nodes are inserted at the end in earlier phases. It seems like that can only
> happen if the non-split-node predecessor of a split node was empty and
> contracted, creating this split node -> split node edge.
> 
> The main thing it seems is that Unplaced are just "not ideally placed" because
> of luck/iteration order.

Hmm, you're right.  In all of spec2k, Unplaced is always empty, so I got rid of
it and make sure placement is still valid if the original Unplaced condition
pops up.

https://codereview.chromium.org/680733002/diff/80001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/680733002/diff/80001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:379: // implementation is O(N^2) where N is the number of Phi
On 2014/10/29 13:46:50, jvoung wrote:
> Any idea the "usual" # of Phis? (Would the N^2 be a problem? Anyway, this can
be
> tuned later too, but does look like dealing with cycles will be more work the
> O(N) way).

OK, I ran some numbers across spec2k (is that representative? I don't know). 
Here is the distribution of number of Phi instructions in a basic block, across
all basic blocks in spec2k.  99% of blocks have 4 or fewer Phi instructions. 
(If we consider blocks with only 2 or more Phis, the 99% point is 9 Phis.)

Phis  Total   Fract.  Cumulative
0     154892  77.62%  77.62%
1     27688   13.88%  91.50%
2     9400    4.71%   96.21%
3     4750    2.38%   98.59%
4     1345    0.67%   99.27%
5     597     0.30%   99.57%
6     340     0.17%   99.74%
7     131     0.07%   99.80%
8     153     0.08%   99.88%
9     86      0.04%   99.92%
10    35      0.02%   99.94%
11    36      0.02%   99.96%
12    21      0.01%   99.97%
13    2       0.00%   99.97%
14    21      0.01%   99.98%
15    20      0.01%   99.99%
16    3       0.00%   99.99%
17    3       0.00%   99.99%
18    2       0.00%   99.99%
19    3       0.00%   99.99%
20    2       0.00%   100.00%
21    0       0.00%   100.00%
22    0       0.00%   100.00%
23    0       0.00%   100.00%
24    0       0.00%   100.00%
25    0       0.00%   100.00%
26    1       0.00%   100.00%
27    1       0.00%   100.00%
28    4       0.00%   100.00%
29    0       0.00%   100.00%
30    2       0.00%   100.00%
31    1       0.00%   100.00%

Actually, this N^2 loop is done for every edge, not every node, so those
statistics look like the following.  99% are 6 or fewer Phis, or 14 or fewer
when considering only 2 or more Phis.


Phis  Total   Fract.  Cumulative
0     200284  60.65%  60.65%
1     81668   24.73%  85.38%
2     25454   7.71%   93.09%
3     12362   3.74%   96.83%
4     4196    1.27%   98.10%
5     1848    0.56%   98.66%
6     1494    0.45%   99.11%
7     474     0.14%   99.26%
8     801     0.24%   99.50%
9     684     0.21%   99.71%
10    113     0.03%   99.74%
11    164     0.05%   99.79%
12    87      0.03%   99.82%
13    4       0.00%   99.82%
14    293     0.09%   99.91%
15    208     0.06%   99.97%
16    15      0.00%   99.97%
17    19      0.01%   99.98%
18    5       0.00%   99.98%
19    6       0.00%   99.98%
20    5       0.00%   99.99%
21    0       0.00%   99.99%
22    0       0.00%   99.99%
23    0       0.00%   99.99%
24    0       0.00%   99.99%
25    0       0.00%   99.99%
26    2       0.00%   99.99%
27    2       0.00%   99.99%
28    10      0.00%   99.99%
29    0       0.00%   99.99%
30    32      0.01%   100.00%
31    2       0.00%   100.00%

One more thing.  Summing up Total*Phis as an approximation of an O(N) algorithm
cost, compared to summing up Total*Phis*Phis as an O(N^2) cost, gives the O(N^2)
cost as 3.4x the O(N) cost, to give an idea of the opportunity.  (My conclusion:
something to consider later, but I'm not holding my breath.)

https://codereview.chromium.org/680733002/diff/80001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:432: if (Dest != Src)
On 2014/10/29 13:46:50, jvoung wrote:
> Could it be broadened beyond syntactically the same (to include all of
> IsSelfAssignment)?

This was actually deliberate because if the test is broadened, you would lose
assignments like "A:eax=B:eax", and if another liveness pass gets run later, you
could have the assignment of B incorrectly eliminated, and the liveness of A
could incorrectly propagate all the way back to the entry node.  But this is
never a problem with "A=A" style assignments.

That said, these redundant assignments do contribute to the O(N^2) time, so I
moved them to be handled during initialization.

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

https://codereview.chromium.org/680733002/diff/80001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4161: assert(Node->getOutEdges().size() == 1);
On 2014/10/29 13:46:50, jvoung wrote:
> Would it help to also also assert that the Node is empty (no existing
terminator
> branch, since it's added by this)?

Done.

https://codereview.chromium.org/680733002/diff/80001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4172: // available (not live) at the beginning of
the block, minus all
On 2014/10/29 13:46:50, jvoung wrote:
> At the beginning of the successor block?
> 
> I guess because this node is empty, the two are the same, but if the Phis are
> considered to be added to the end of this current block, then you're looking
for
> the LiveIn of the successor?

That's right, the beginning of the successor block.

One way to think about this is the following.  CfgNode::liveness() did a
backward pass over the successor's regular instructions, and then did a special
pass over its phi instructions where it marked the phi dest variables as not
live but ignored the phi src variables (see IsPhi in Inst::liveness()).  We're
trying to reconstruct the liveness state at the point between the regular
instructions and the phi instructions by starting with the final result
(successor's LiveIn) and undoing the killing of dest variables, meaning livening
them, meaning removing their registers from the available set.

While writing this, it occurred to me that this work is being identically
repeated on the successor node for every split edge, and could be done slightly
more efficiently at the time of splitting.  Added a TODO.

https://codereview.chromium.org/680733002/diff/80001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4222: if (llvm::isa<ConstantUndef>(Src)) {
On 2014/10/29 13:46:50, jvoung wrote:
> Probably rare, but might be good to add a test for this case --  It seems like
> isMemoryOperand() is a bit conservative for ConstantUndef of integers (that's
> not really mem=mem is it?). It wasn't obvious to me why Undef is made
> deterministically 0 here, but not in the branches.

Because of the "(!isMemoryOperand(Dest) || !isMemoryOperand(Src))" test above,
Src must be memory and therefore not an integer constant (including undef).

Basically, this is copying some of the logic of legalize() which includes
lowering under to zeroes.  In the other situations, lowerAssign() will be called
which in turn calls legalize() which lowers them to zeroes.

[jvoung (off chromium), 2014-10-30 15:55:25]

otherwise LGTM

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

https://codereview.chromium.org/680733002/diff/80001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4222: if (llvm::isa<ConstantUndef>(Src)) {
On 2014/10/30 00:25:25, stichnot wrote:
> On 2014/10/29 13:46:50, jvoung wrote:
> > Probably rare, but might be good to add a test for this case --  It seems
like
> > isMemoryOperand() is a bit conservative for ConstantUndef of integers
(that's
> > not really mem=mem is it?). It wasn't obvious to me why Undef is made
> > deterministically 0 here, but not in the branches.
> 
> Because of the "(!isMemoryOperand(Dest) || !isMemoryOperand(Src))" test above,
> Src must be memory and therefore not an integer constant (including undef).
> 
> Basically, this is copying some of the logic of legalize() which includes
> lowering under to zeroes.  In the other situations, lowerAssign() will be
called
> which in turn calls legalize() which lowers them to zeroes.


How about legalize() in the later else-case? lowerAssign() is used for the first
if(), but not that later else (when mem=mem and no registers are free)?

[Jim Stichnoth, 2014-10-30 19:10:34]

PTAL, thanks!

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

https://codereview.chromium.org/680733002/diff/80001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4222: if (llvm::isa<ConstantUndef>(Src)) {
On 2014/10/30 15:55:25, jvoung wrote:
> On 2014/10/30 00:25:25, stichnot wrote:
> > On 2014/10/29 13:46:50, jvoung wrote:
> > > Probably rare, but might be good to add a test for this case --  It seems
> like
> > > isMemoryOperand() is a bit conservative for ConstantUndef of integers
> (that's
> > > not really mem=mem is it?). It wasn't obvious to me why Undef is made
> > > deterministically 0 here, but not in the branches.
> > 
> > Because of the "(!isMemoryOperand(Dest) || !isMemoryOperand(Src))" test
above,
> > Src must be memory and therefore not an integer constant (including undef).
> > 
> > Basically, this is copying some of the logic of legalize() which includes
> > lowering under to zeroes.  In the other situations, lowerAssign() will be
> called
> > which in turn calls legalize() which lowers them to zeroes.
> 
> 
> How about legalize() in the later else-case? lowerAssign() is used for the
first
> if(), but not that later else (when mem=mem and no registers are free)?

I refactored the mem=mem case to be more uniform between the cases where there
is a register available and when one has to be spilled.

[jvoung (off chromium), 2014-10-30 19:47:42]

https://codereview.chromium.org/680733002/diff/120001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/680733002/diff/120001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4228: bool NeedSpill = !AvailRegsForType.any();
nit: Could be NeedSpill == (RegNum == -1); (already searched the bitvector)

https://codereview.chromium.org/680733002/diff/120001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4243: // Materialize an actual constant instead
of undef.
Hmm you mentioned this could generate an infinite weight temporary (to make a
vector of zeros, it does _pxor(Reg, Reg), where Reg is NoRegister). What happens
then?

Should legalize() be given RegNum as the register to use?

[Jim Stichnoth, 2014-10-30 21:43:01]

https://codereview.chromium.org/680733002/diff/120001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/680733002/diff/120001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4228: bool NeedSpill = !AvailRegsForType.any();
On 2014/10/30 19:47:42, jvoung wrote:
> nit: Could be NeedSpill == (RegNum == -1); (already searched the bitvector)

Done.

https://codereview.chromium.org/680733002/diff/120001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4243: // Materialize an actual constant instead
of undef.
On 2014/10/30 19:47:42, jvoung wrote:
> Hmm you mentioned this could generate an infinite weight temporary (to make a
> vector of zeros, it does _pxor(Reg, Reg), where Reg is NoRegister). What
happens
> then?
> 
> Should legalize() be given RegNum as the register to use?

Done.

[jvoung (off chromium), 2014-10-30 22:01:06]

LGTM

[Jim Stichnoth, 2014-10-30 22:01:45]

Committed patchset #8 (id:140001) manually as
336f6c4a90e7f5ee156bc9a339d80c7def5ddeff (presubmit successful).