Subzero: Initial O2 lowering

Subzero: Initial O2 lowering

Includes the following:
1. Liveness analysis.
2. Linear-scan register allocation.
3. Address mode optimization.
4. Compare-branch fusing.

All of these depend on liveness analysis.  There are three versions of liveness analysis (in order of increasing cost):
1. Lightweight.  This computes last-uses for variables local to a single basic block.
2. Full.  This computes last-uses for all variables based on global dataflow analysis.
3. Full live ranges.  This computes all last-uses, plus calculates the live range intervals in terms of instruction numbers.  (The live ranges are needed for register allocation.)

For testing the full live range computation, Cfg::validateLiveness() checks every Variable of every Inst and verifies that the current Inst is contained within the Variable's live range.

The cross tests are run with O2 in addition to Om1.

Some of the lit tests (for what good they do) are updated with O2 code sequences.

BUG= none
R=jvoung@chromium.org

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

[JF, 2014-05-25 22:50:49]

First pass.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode150
src/IceCfg.cpp:150: (*I)->liveness(Mode, getLiveness());
Can't getLiveness() return a nullptr here?

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode161
src/IceCfg.cpp:161: }
Can you set the entire bit vector to true? If all nodes have unique indices, and
they're all in the [0, Nodes.size()[ range.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode192
src/IceCfg.cpp:192: Timer T_liveRange;
Why just time this part?

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode216
src/IceCfg.cpp:216: Live->addLiveRange(Hi, -1, 0, 0);
What's this lo/hi thing?

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode235
src/IceCfg.cpp:235: assert(validateLiveness());
Could you validate passes after the pass instead? Have validation be an option
(and each pass is declared to have a list of validations that would run after
they run), instead of doing it when asserts are on.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode264
src/IceCfg.cpp:264: assert(Valid);
i'm confused by this. Do you want to print the invalid instructions instead?

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode275
src/IceCfg.cpp:275: assert(Valid);
Ditto.

https://codereview.chromium.org/300563003/diff/1/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceCfgNode.cpp#newcode139
src/IceCfgNode.cpp:139: }
Can you explain this?

https://codereview.chromium.org/300563003/diff/1/src/IceCfgNode.cpp#newcode266
src/IceCfgNode.cpp:266: // failed.
Shouldn't the block be before the assertion?

https://codereview.chromium.org/300563003/diff/1/src/IceGlobalContext.cpp
File src/IceGlobalContext.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceGlobalContext.cpp#new...
src/IceGlobalContext.cpp:133: // because sscanf behavior is undefined on integer
overflow.
Add an assert that has this comment.

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode101
src/IceInst.cpp:101: SizeT Mask = LiveRangesEnded;
You should use the same typedef for LiveRangesEnded.

https://codereview.chromium.org/300563003/diff/1/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/300563003/diff/1/src/IceInst.h#newcode116
src/IceInst.h:116: if (VarIndex < 8 * sizeof(LiveRangesEnded))
s/8/CHAR_BIT/

https://codereview.chromium.org/300563003/diff/1/src/IceInst.h#newcode117
src/IceInst.h:117: LiveRangesEnded |= (1u << VarIndex);
Use a typedef for LiveRangesEnded, and cast 1u to that type.

[jvoung (off chromium), 2014-05-28 17:48:14]

scanned through a bit too

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode231
src/IceCfg.cpp:231: dump();
If ctx->isVerbose, then dump() to avoid iterating through?

Is CFG->dump() the "highest level" dump?  Maybe just check isVerbose() early in
there and exit early if false, instead of checking isVerbose() in a bunch of
places? Maybe it doesn't work because there's different granularities of
verbosity.

At some point, might also want to #if !NDEBUG the dump() methods if we don't
need it in release mode.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode267
src/IceCfg.cpp:267: SizeT VarIndex = 0;
VarIndex unused (just incremented)?

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode94
src/IceInst.cpp:94: // If Src is an Variable, it returns true if this
instruction ends
"is a Variable"?

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode100
src/IceInst.cpp:100: SizeT VarIndex = 0;
VarIndex unused here (just incremented)? Looks like this is handled by shifting
the Mask and testing & 1, instead of using VarIndex.

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode124
src/IceInst.cpp:124: SizeT VarIndex = 0;
VarIndex also unused here (just incremented)?

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode158
src/IceInst.cpp:158: setLastUse(VarIndex);
I see... so VarIndex is an optimized, different numbering than Var->getIndex(),
limited to < 32.

I guess I'm wondering if it's worth this optimization when there are 3(?) types
of indexing, and you need to remember which index to use when.

Var->getIndex()
VarIndex
Liveness->getLiveIndex(Var)

It seems to depend on the LivenessMode:
* Live[Index] for Liveness_LREndLightweight, w/ Index being from Var->getIndex.
* Live[VarNum] where VarNum comes from Liveness->getLiveIndex(), otherwise.

Maybe a better split between the code for the different LivenessModes?

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode474
src/IceInst.cpp:474: SizeT VarIndex = 0;
VarIndex unused?

https://codereview.chromium.org/300563003/diff/1/src/IceLiveness.cpp
File src/IceLiveness.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceLiveness.cpp#newcode1
src/IceLiveness.cpp:1: //===- subzero/src/Liveness.cpp - Liveness analysis
implementation -----===//
IceLiveness.cpp

https://codereview.chromium.org/300563003/diff/1/src/IceLiveness.h
File src/IceLiveness.h (right):

https://codereview.chromium.org/300563003/diff/1/src/IceLiveness.h#newcode1
src/IceLiveness.h:1: //===- subzero/src/Liveness.h - Liveness analysis
------------*- C++ -*-===//
IceLiveness.h for consistency?

https://codereview.chromium.org/300563003/diff/1/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceRegAlloc.cpp#newcode36
src/IceRegAlloc.cpp:36: if (!RegMaskFull.any())
Should the RegMaskFull ever be completely 0?  I'm wondering if this should be an
assert or not, but I haven't looked at all the places scan() is called.

https://codereview.chromium.org/300563003/diff/1/src/IceRegAlloc.cpp#newcode100
src/IceRegAlloc.cpp:100: Cur.Var->setRegNumTmp(RegNum);
Already set above in line 65 (didn't actually read the full loop, so not sure if
an invariant is that it's only in the Unhandled set once).

https://codereview.chromium.org/300563003/diff/1/src/IceTargetLoweringX8632.cpp
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceTargetLoweringX8632.c...
src/IceTargetLoweringX8632.cpp:238: Func->dump();
dump() vs isVerbose() consistency?

https://codereview.chromium.org/300563003/diff/1/src/IceTargetLoweringX8632.c...
src/IceTargetLoweringX8632.cpp:242: T_doAddressOpt.printElapsedUs(Context,
"doAddressOpt()");
Does doAddressOpt() depend on the instruction numbers?

If not, can you just renumberInstructions() one time after this, instead of
doing it twice?

The comment below is about liveness, but what you re-run is
renumberInstructions, which doesn't touch liveness?

https://codereview.chromium.org/300563003/diff/1/src/IceTargetLoweringX8632.c...
src/IceTargetLoweringX8632.cpp:1785: void computeAddressOpt(Cfg * /*Func*/,
Variable *&Base, Variable *&Index,
Is this expected to change to use the Func parameter? Is this for something to
test the which basic block the defining instructions belong to?

https://codereview.chromium.org/300563003/diff/1/src/IceTargetLoweringX8632.c...
src/IceTargetLoweringX8632.cpp:1812: //   set Index=Var
Maybe the assignment transitivity checks could be lifted into a helper function?

https://codereview.chromium.org/300563003/diff/1/tests_lit/llvm2ice_tests/con...
File tests_lit/llvm2ice_tests/convert.ll (right):

https://codereview.chromium.org/300563003/diff/1/tests_lit/llvm2ice_tests/con...
tests_lit/llvm2ice_tests/convert.ll:3: ; RUN: %llvm2ice -O2 --verbose none %s |
FileCheck --check-prefix=OPTM1 %s
What uses the CHECK prefix then (there are CHECK checks)?

https://codereview.chromium.org/300563003/diff/1/tests_lit/llvm2ice_tests/fpc...
File tests_lit/llvm2ice_tests/fpconst.pnacl.ll (right):

https://codereview.chromium.org/300563003/diff/1/tests_lit/llvm2ice_tests/fpc...
tests_lit/llvm2ice_tests/fpconst.pnacl.ll:10: ; RUN: %llvm2ice -O2 --verbose
none %s | FileCheck %s
Nit: flip the O2 and Om1 for consistency w/ the rest of the tests?

[Jim Stichnoth, 2014-05-29 01:39:46]

This addresses JF's and Jan's initial comments.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode150
src/IceCfg.cpp:150: (*I)->liveness(Mode, getLiveness());
On 2014/05/25 22:50:50, JF wrote:
> Can't getLiveness() return a nullptr here?

Yes, but as it turns out, the "lightweight" mode doesn't actually use the
Liveness object, so everything should be OK, right?

Clearly, after having another look at this, it's just icky, so I've broken it
into livenessLightweight() and liveness().  The normal (non-lightweight) version
now has two modes instead of three: the Basic mode that computes live-in,
live-out, and end of live ranges; and the Intervals mode that additional
calculates the live intervals for each variable.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode161
src/IceCfg.cpp:161: }
On 2014/05/25 22:50:50, JF wrote:
> Can you set the entire bit vector to true? If all nodes have unique indices,
and
> they're all in the [0, Nodes.size()[ range.

Done (via the constructor).  That loop-based initialization was left over from
when the Node indexes weren't necessarily packed.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode192
src/IceCfg.cpp:192: Timer T_liveRange;
On 2014/05/25 22:50:50, JF wrote:
> Why just time this part?

Added a comment to explain.  Basically, I want a breakdown of the live interval
construction in addition to the total time for liveness analysis.  The caller of
Cfg::liveness() is already timing the whole thing.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode216
src/IceCfg.cpp:216: Live->addLiveRange(Hi, -1, 0, 0);
On 2014/05/25 22:50:50, JF wrote:
> What's this lo/hi thing?

Added a comment explaining.  BTW, there's a TODO in IceOperand.h about redoing
the Lo/Hi thing since it's really target-specific.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode231
src/IceCfg.cpp:231: dump();
On 2014/05/28 17:48:15, jvoung wrote:
> If ctx->isVerbose, then dump() to avoid iterating through?
> 
> Is CFG->dump() the "highest level" dump?  Maybe just check isVerbose() early
in
> there and exit early if false, instead of checking isVerbose() in a bunch of
> places? Maybe it doesn't work because there's different granularities of
> verbosity.
> 
> At some point, might also want to #if !NDEBUG the dump() methods if we don't
> need it in release mode.

Good idea.  dump() now takes an optional intro message argument and all the
isVerbose() checking is simpler.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode235
src/IceCfg.cpp:235: assert(validateLiveness());
On 2014/05/25 22:50:50, JF wrote:
> Could you validate passes after the pass instead? Have validation be an option
> (and each pass is declared to have a list of validations that would run after
> they run), instead of doing it when asserts are on.

Removed the liveness validation from liveness(), and added it after the
liveness() call, and outside the timing measurement.  Added a TODO to put it
under a flag.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode264
src/IceCfg.cpp:264: assert(Valid);
On 2014/05/25 22:50:50, JF wrote:
> i'm confused by this. Do you want to print the invalid instructions instead?

Done.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode267
src/IceCfg.cpp:267: SizeT VarIndex = 0;
On 2014/05/28 17:48:15, jvoung wrote:
> VarIndex unused (just incremented)?

This iterator pattern is copied in several places.  I removed the use of
VarIndex everywhere except the two instances where it is actually needed.

https://codereview.chromium.org/300563003/diff/1/src/IceCfg.cpp#newcode275
src/IceCfg.cpp:275: assert(Valid);
On 2014/05/25 22:50:50, JF wrote:
> Ditto.

Done.

https://codereview.chromium.org/300563003/diff/1/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceCfgNode.cpp#newcode139
src/IceCfgNode.cpp:139: }
On 2014/05/25 22:50:50, JF wrote:
> Can you explain this?

Done.  Also modified the logic to look only for *conditional* branches followed
by cmp instructions.

https://codereview.chromium.org/300563003/diff/1/src/IceCfgNode.cpp#newcode266
src/IceCfgNode.cpp:266: // failed.
On 2014/05/25 22:50:50, JF wrote:
> Shouldn't the block be before the assertion?

Good point.  Fixed this, including replacing the assert() with an
llvm_unreachable() at the end of the block.

https://codereview.chromium.org/300563003/diff/1/src/IceGlobalContext.cpp
File src/IceGlobalContext.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceGlobalContext.cpp#new...
src/IceGlobalContext.cpp:133: // because sscanf behavior is undefined on integer
overflow.
On 2014/05/25 22:50:50, JF wrote:
> Add an assert that has this comment.

An assert isn't appropriate here.  The idea is to try to demangle a C++ symbol
involving a namespace, and if that fails, fall back to adding a prefix to a
presumed C symbol.  (There is one test in mangle.ll that tests for such integer
overflow.)

I updated the comment, and also tried to improve the overflow check by testing
whether the following string starts with a digit.

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode94
src/IceInst.cpp:94: // If Src is an Variable, it returns true if this
instruction ends
On 2014/05/28 17:48:15, jvoung wrote:
> "is a Variable"?

Fixed this and several other instances. :)  (This was because Ice::Variable used
to be IceVariable.)

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode100
src/IceInst.cpp:100: SizeT VarIndex = 0;
On 2014/05/28 17:48:15, jvoung wrote:
> VarIndex unused here (just incremented)? Looks like this is handled by
shifting
> the Mask and testing & 1, instead of using VarIndex.

Done.

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode101
src/IceInst.cpp:101: SizeT Mask = LiveRangesEnded;
On 2014/05/25 22:50:50, JF wrote:
> You should use the same typedef for LiveRangesEnded.

Done.

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode124
src/IceInst.cpp:124: SizeT VarIndex = 0;
On 2014/05/28 17:48:15, jvoung wrote:
> VarIndex also unused here (just incremented)?

Done.

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode158
src/IceInst.cpp:158: setLastUse(VarIndex);
On 2014/05/28 17:48:15, jvoung wrote:
> I see... so VarIndex is an optimized, different numbering than
Var->getIndex(),
> limited to < 32.
> 
> I guess I'm wondering if it's worth this optimization when there are 3(?)
types
> of indexing, and you need to remember which index to use when.
> 
> Var->getIndex()
> VarIndex
> Liveness->getLiveIndex(Var)
> 
> It seems to depend on the LivenessMode:
> * Live[Index] for Liveness_LREndLightweight, w/ Index being from
Var->getIndex.
> * Live[VarNum] where VarNum comes from Liveness->getLiveIndex(), otherwise.
> 
> Maybe a better split between the code for the different LivenessModes?

OK, it looks like I never properly documented VarIndex and
Inst::LiveRangesEnded.  The purpose of LiveRangesEnded is to mark which
Variables' live ranges end in this instruction.  An instruction can have an
arbitrary number of source operands (e.g. a call instruction), and each source
operand can contain 0, 1, or more Variables (x86 mem operands can have 2
registers).  I tried out several ways to deal with this, balancing time, space,
and simplicity, and this was the best mechanism I came up with (or perhaps the
least icky mechanism).

Note that VarIndex/LiveRangesEnded is a property of the instruction, whereas
Var->getIndex() and Liveness->getLiveIndex(Var) are properties of the Variable.

https://codereview.chromium.org/300563003/diff/1/src/IceInst.cpp#newcode474
src/IceInst.cpp:474: SizeT VarIndex = 0;
On 2014/05/28 17:48:15, jvoung wrote:
> VarIndex unused?

Done.

https://codereview.chromium.org/300563003/diff/1/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/300563003/diff/1/src/IceInst.h#newcode116
src/IceInst.h:116: if (VarIndex < 8 * sizeof(LiveRangesEnded))
On 2014/05/25 22:50:50, JF wrote:
> s/8/CHAR_BIT/

Done.

https://codereview.chromium.org/300563003/diff/1/src/IceInst.h#newcode117
src/IceInst.h:117: LiveRangesEnded |= (1u << VarIndex);
On 2014/05/25 22:50:50, JF wrote:
> Use a typedef for LiveRangesEnded, and cast 1u to that type.

Done.

https://codereview.chromium.org/300563003/diff/1/src/IceLiveness.cpp
File src/IceLiveness.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceLiveness.cpp#newcode1
src/IceLiveness.cpp:1: //===- subzero/src/Liveness.cpp - Liveness analysis
implementation -----===//
On 2014/05/28 17:48:15, jvoung wrote:
> IceLiveness.cpp

Done.

https://codereview.chromium.org/300563003/diff/1/src/IceLiveness.h
File src/IceLiveness.h (right):

https://codereview.chromium.org/300563003/diff/1/src/IceLiveness.h#newcode1
src/IceLiveness.h:1: //===- subzero/src/Liveness.h - Liveness analysis
------------*- C++ -*-===//
On 2014/05/28 17:48:15, jvoung wrote:
> IceLiveness.h for consistency?

Done.  (Global-replace failure earlier. :) )

https://codereview.chromium.org/300563003/diff/1/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceRegAlloc.cpp#newcode36
src/IceRegAlloc.cpp:36: if (!RegMaskFull.any())
On 2014/05/28 17:48:15, jvoung wrote:
> Should the RegMaskFull ever be completely 0?  I'm wondering if this should be
an
> assert or not, but I haven't looked at all the places scan() is called.

It's only called once from TargetLowering::regAlloc().

This is really an early-exit optimization, and you're right, it would be foolish
not to give the register allocator any registers to allocate, so I changed it to
assert.

https://codereview.chromium.org/300563003/diff/1/src/IceRegAlloc.cpp#newcode100
src/IceRegAlloc.cpp:100: Cur.Var->setRegNumTmp(RegNum);
On 2014/05/28 17:48:15, jvoung wrote:
> Already set above in line 65 (didn't actually read the full loop, so not sure
if
> an invariant is that it's only in the Unhandled set once).

You're right.  I changed it to an assert just to be safe.

https://codereview.chromium.org/300563003/diff/1/src/IceTargetLoweringX8632.cpp
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/300563003/diff/1/src/IceTargetLoweringX8632.c...
src/IceTargetLoweringX8632.cpp:238: Func->dump();
On 2014/05/28 17:48:15, jvoung wrote:
> dump() vs isVerbose() consistency?

The Cfg-level dumping should be cleaned up now.

https://codereview.chromium.org/300563003/diff/1/src/IceTargetLoweringX8632.c...
src/IceTargetLoweringX8632.cpp:242: T_doAddressOpt.printElapsedUs(Context,
"doAddressOpt()");
On 2014/05/28 17:48:15, jvoung wrote:
> Does doAddressOpt() depend on the instruction numbers?
> 
> If not, can you just renumberInstructions() one time after this, instead of
> doing it twice?
> 
> The comment below is about liveness, but what you re-run is
> renumberInstructions, which doesn't touch liveness?

You're right.  Hopefully this is cleaned up now and also a bit easier to read.

https://codereview.chromium.org/300563003/diff/1/src/IceTargetLoweringX8632.c...
src/IceTargetLoweringX8632.cpp:1785: void computeAddressOpt(Cfg * /*Func*/,
Variable *&Base, Variable *&Index,
On 2014/05/28 17:48:15, jvoung wrote:
> Is this expected to change to use the Func parameter? Is this for something to
> test the which basic block the defining instructions belong to?

Removed.  I think this was originally meant for the possibility of constructing
new Constant operands, but now that Constants are pooled a the GlobalContext
level rather than Cfg, we would actually need a GlobalContext pointer here.  We
can add things back if needed later.

https://codereview.chromium.org/300563003/diff/1/src/IceTargetLoweringX8632.c...
src/IceTargetLoweringX8632.cpp:1812: //   set Index=Var
On 2014/05/28 17:48:15, jvoung wrote:
> Maybe the assignment transitivity checks could be lifted into a helper
function?

Added a TODO (since it's actually only implemented for one case so far).

https://codereview.chromium.org/300563003/diff/1/tests_lit/llvm2ice_tests/con...
File tests_lit/llvm2ice_tests/convert.ll (right):

https://codereview.chromium.org/300563003/diff/1/tests_lit/llvm2ice_tests/con...
tests_lit/llvm2ice_tests/convert.ll:3: ; RUN: %llvm2ice -O2 --verbose none %s |
FileCheck --check-prefix=OPTM1 %s
On 2014/05/28 17:48:15, jvoung wrote:
> What uses the CHECK prefix then (there are CHECK checks)?

It turned out that when Karl made changes to this test to make the typing of
globals correct for the PNaCl ABI, it slightly changed the O2 asm generated,
which broke all the overly-specific CHECK lines, and it turned out the general
OPTM1 lines are appropriate for O2 as well.

I removed the original CHECK lines and renamed OPTM1 to CHECK.

https://codereview.chromium.org/300563003/diff/1/tests_lit/llvm2ice_tests/fpc...
File tests_lit/llvm2ice_tests/fpconst.pnacl.ll (right):

https://codereview.chromium.org/300563003/diff/1/tests_lit/llvm2ice_tests/fpc...
tests_lit/llvm2ice_tests/fpconst.pnacl.ll:10: ; RUN: %llvm2ice -O2 --verbose
none %s | FileCheck %s
On 2014/05/28 17:48:15, jvoung wrote:
> Nit: flip the O2 and Om1 for consistency w/ the rest of the tests?

Done.

[jvoung (off chromium), 2014-05-30 15:41:30]

looks pretty good -- mostly nits

https://codereview.chromium.org/300563003/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/300563003/diff/20001/src/IceCfg.cpp#newcode224
src/IceCfg.cpp:224: setCurrentNode(NULL);
Does setCurrentNode(NULL) need to happen for every variable, or is it loop
invariant?

https://codereview.chromium.org/300563003/diff/20001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/300563003/diff/20001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:259: if (FirstPhiNumber <= 0)
nit: could be a strict == test, since you're just checking against the sentinel
value?

Similar for the FirstInstNum below, or is there a reason for <= check?

https://codereview.chromium.org/300563003/diff/20001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/300563003/diff/20001/src/IceInst.h#newcode126
src/IceInst.h:126: // Number is the instruction number for describing live
ranges.
Could be worth documenting somewhere numbers that have special meanings (w/
comment or constants)?
E.g., 0 is a sentinel, and non-deleted instructions are positive?

https://codereview.chromium.org/300563003/diff/20001/src/IceLiveness.h
File src/IceLiveness.h (right):

https://codereview.chromium.org/300563003/diff/20001/src/IceLiveness.h#newcode44
src/IceLiveness.h:44: std::vector<int> LiveBegin, LiveEnd;
int32_t to match InstNumber's usual type?

https://codereview.chromium.org/300563003/diff/20001/src/IceLiveness.h#newcode61
src/IceLiveness.h:61: SizeT getLocalSize(const CfgNode *Node) const {
nit: Name seems a bit misleading since this has NumGlobals + ...NumLocals.

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

https://codereview.chromium.org/300563003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:194: if (Item.overlaps(Cur)) {
Just double checking: Is this possible? The loop before went over Inactive, and
if Item.overlaps(Cur), it is moved out of Inactive into the Active list?   That
would have also bumped up the RegUses, so that Free would have been set to false
already?

https://codereview.chromium.org/300563003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:355: assert(RegUses[MinWeightIndex] >= 0);
Should the assert go before the ++ ? Otherwise, it's pretty much guaranteed to
be >= 0, since it never goes negative?

[Jim Stichnoth, 2014-05-30 23:06:18]

https://codereview.chromium.org/300563003/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/300563003/diff/20001/src/IceCfg.cpp#newcode224
src/IceCfg.cpp:224: setCurrentNode(NULL);
On 2014/05/30 15:41:31, jvoung wrote:
> Does setCurrentNode(NULL) need to happen for every variable, or is it loop
> invariant?

Loop invariant, but actually it doesn't need to be here at all because
Cfg::dump() will take care of it.

https://codereview.chromium.org/300563003/diff/20001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/300563003/diff/20001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:259: if (FirstPhiNumber <= 0)
On 2014/05/30 15:41:31, jvoung wrote:
> nit: could be a strict == test, since you're just checking against the
sentinel
> value?
> 
> Similar for the FirstInstNum below, or is there a reason for <= check?

As it turns out, the <= test also makes us ignore deleted instructions (which
are then also ignored in Inst::liveness()) for the purpose of computing
FirstPhiNumber.

But, this is unclear and fragile, so I changed the code to be more explicit
about deleted instructions.

https://codereview.chromium.org/300563003/diff/20001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/300563003/diff/20001/src/IceInst.h#newcode126
src/IceInst.h:126: // Number is the instruction number for describing live
ranges.
On 2014/05/30 15:41:31, jvoung wrote:
> Could be worth documenting somewhere numbers that have special meanings (w/
> comment or constants)?
> E.g., 0 is a sentinel, and non-deleted instructions are positive?

Done -- Inst::NumberDeleted=-1 and Inst::NumberSentinel=0.

https://codereview.chromium.org/300563003/diff/20001/src/IceLiveness.h
File src/IceLiveness.h (right):

https://codereview.chromium.org/300563003/diff/20001/src/IceLiveness.h#newcode44
src/IceLiveness.h:44: std::vector<int> LiveBegin, LiveEnd;
On 2014/05/30 15:41:31, jvoung wrote:
> int32_t to match InstNumber's usual type?

Done.  While I'm at it, I changed int32_t to Ice::InstNumberT.

https://codereview.chromium.org/300563003/diff/20001/src/IceLiveness.h#newcode61
src/IceLiveness.h:61: SizeT getLocalSize(const CfgNode *Node) const {
On 2014/05/30 15:41:31, jvoung wrote:
> nit: Name seems a bit misleading since this has NumGlobals + ...NumLocals.

Changed to getNumVarsInNode().  Also getGlobalSize() -> getNumGlobalVars() for a
bit more consistency.

Better name suggestions are welcome. :)

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

https://codereview.chromium.org/300563003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:194: if (Item.overlaps(Cur)) {
On 2014/05/30 15:41:31, jvoung wrote:
> Just double checking: Is this possible? The loop before went over Inactive,
and
> if Item.overlaps(Cur), it is moved out of Inactive into the Active list?  
That
> would have also bumped up the RegUses, so that Free would have been set to
false
> already?

This is a good point.  I took another look at the original paper, and I see that
I have a slight transcription error in this code.  In some cases the paper says
"if i overlaps cur.beg" and in others it says "if i overlaps cur".  My
implementation always uses the latter test.  I'm not sure of the practical
differences, but most likely my implementation is behaving more conservatively.

I went ahead and made the changes in two places to match the paper.  The lit
tests and cross tests continue to work with no changes.  I also captured this
output before and after the change:

for i in tests_lit/llvm2ice_tests/*.ll ; do ./llvm2ice -O2 -verbose all $i ;
done | grep -v ' usec '

There are some diffs in the results, but it appears that the register
assignments end up the same.  So I will keep the changes to make it true to the
paper.

https://codereview.chromium.org/300563003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:355: assert(RegUses[MinWeightIndex] >= 0);
On 2014/05/30 15:41:31, jvoung wrote:
> Should the assert go before the ++ ? Otherwise, it's pretty much guaranteed to
> be >= 0, since it never goes negative?

Done.

[jvoung (off chromium), 2014-06-02 17:07:40]

Otherwise LGTM

https://codereview.chromium.org/300563003/diff/20001/src/IceLiveness.h
File src/IceLiveness.h (right):

https://codereview.chromium.org/300563003/diff/20001/src/IceLiveness.h#newcode44
src/IceLiveness.h:44: std::vector<int> LiveBegin, LiveEnd;
On 2014/05/30 23:06:18, stichnot wrote:
> On 2014/05/30 15:41:31, jvoung wrote:
> > int32_t to match InstNumber's usual type?
> 
> Done.  While I'm at it, I changed int32_t to Ice::InstNumberT.

This instance is still "int"?

https://codereview.chromium.org/300563003/diff/20001/src/IceLiveness.h#newcode61
src/IceLiveness.h:61: SizeT getLocalSize(const CfgNode *Node) const {
On 2014/05/30 23:06:18, stichnot wrote:
> On 2014/05/30 15:41:31, jvoung wrote:
> > nit: Name seems a bit misleading since this has NumGlobals + ...NumLocals.
> 
> Changed to getNumVarsInNode().  Also getGlobalSize() -> getNumGlobalVars() for
a
> bit more consistency.
> 
> Better name suggestions are welcome. :)

sgtm

https://codereview.chromium.org/300563003/diff/30001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/300563003/diff/30001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:212: if (Item.Var->hasReg() && Item.overlaps(Cur)) {
because unhandled is sorted and !Cur.endsBefore(Item), is Item guaranteed to
overlap(Cur) already?

https://codereview.chromium.org/300563003/diff/30001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:275: LiveRangeWrapper Item = *I;
Do you have to check for overlap first? For Active you can assume it overlaps,
but for Inactive it's not so certain?

[Jim Stichnoth, 2014-06-04 14:18:03]

https://codereview.chromium.org/300563003/diff/20001/src/IceLiveness.h
File src/IceLiveness.h (right):

https://codereview.chromium.org/300563003/diff/20001/src/IceLiveness.h#newcode44
src/IceLiveness.h:44: std::vector<int> LiveBegin, LiveEnd;
On 2014/06/02 17:07:40, jvoung wrote:
> On 2014/05/30 23:06:18, stichnot wrote:
> > On 2014/05/30 15:41:31, jvoung wrote:
> > > int32_t to match InstNumber's usual type?
> > 
> > Done.  While I'm at it, I changed int32_t to Ice::InstNumberT.
> 
> This instance is still "int"?

<embarrassed>
Done.  Also changed several int32_t to size_t, mostly in IceTargetLoweringX8632.

https://codereview.chromium.org/300563003/diff/30001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/300563003/diff/30001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:212: if (Item.Var->hasReg() && Item.overlaps(Cur)) {
On 2014/06/02 17:07:43, jvoung wrote:
> because unhandled is sorted and !Cur.endsBefore(Item), is Item guaranteed to
> overlap(Cur) already?

Not necessarily.  Example:

  int Cur = ...;
  if (cond) {
    int Item = ...;
    // use Item
    // no uses of Cur in this block
  } else {
    // use Cur
  }
  // no more uses of Cur

Assuming the instruction numbering matches C statement ordering, the live range
of Cur has a gap corresponding to the true branch of the if statement, and the
live range of Item is contained within the true branch.  Therefore they don't
overlap and so it doesn't matter to Cur whether Item is precolored, yet Item
comes after Cur in the sorted Unhandled list.

https://codereview.chromium.org/300563003/diff/30001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:275: LiveRangeWrapper Item = *I;
On 2014/06/02 17:07:43, jvoung wrote:
> Do you have to check for overlap first? For Active you can assume it overlaps,
> but for Inactive it's not so certain?

I think you're right and the lack of overlap check was a transcription or
copy/paste error.

[jvoung (off chromium), 2014-06-04 18:17:57]

https://codereview.chromium.org/300563003/diff/30001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/300563003/diff/30001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:212: if (Item.Var->hasReg() && Item.overlaps(Cur)) {
On 2014/06/04 14:18:03, stichnot wrote:
> On 2014/06/02 17:07:43, jvoung wrote:
> > because unhandled is sorted and !Cur.endsBefore(Item), is Item guaranteed to
> > overlap(Cur) already?
> 
> Not necessarily.  Example:
> 
>   int Cur = ...;
>   if (cond) {
>     int Item = ...;
>     // use Item
>     // no uses of Cur in this block
>   } else {
>     // use Cur
>   }
>   // no more uses of Cur
> 
> Assuming the instruction numbering matches C statement ordering, the live
range
> of Cur has a gap corresponding to the true branch of the if statement, and the
> live range of Item is contained within the true branch.  Therefore they don't
> overlap and so it doesn't matter to Cur whether Item is precolored, yet Item
> comes after Cur in the sorted Unhandled list.

Ah okay, makes sense.

[Jim Stichnoth, 2014-06-04 18:57:12]

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