Subzero: Improve performance of liveness analysis and live range construction.

Subzero: Improve performance of liveness analysis and live range construction.

The key performance problem was that the per-block LiveBegin and LiveEnd vectors were dense with respect to the multi-block "global" variables, even though very few of the global variables are ever live within the block.  This led to large vectors needlessly initialized and iterated over.

The new approach is to accumulate two small vectors of <variable,instruction_number> tuples (LiveBegin and LiveEnd) as each block is processed, then sort the vectors and iterate over them in parallel to construct the live ranges.

Some of the anomalies in the original liveness analysis code have been straightened out:

1. Variables have an IgnoreLiveness attribute to suppress analysis.  This is currently used only on the esp register.

2. Instructions have a DestNonKillable attribute which causes the Dest variable not to be marked as starting a new live range at that instruction.  This is used when a variable is non-SSA and has more than one assignment within a block, but we want to treat it as a single live range.  This lets the variable have zero or one live range begins or ends within a block.  DestNonKillable is derived automatically for two-address instructions, and annotated manually in a few other cases.

This is tested by comparing the O2 asm output in each Spec2K component.  In theory, the output should be the same except for some differences in pseudo-instructions output as comments.  However, some actual differences showed up, related to the i64 shl instruction followed by trunc to i32.  This turned out to be a liveness bug that was accidentally fixed.

BUG= none
R=jvoung@chromium.org

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

[Jim Stichnoth, 2014-10-13 06:21:52]

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

[Jim Stichnoth, 2014-10-13 06:22:55]

This gives a ~10% overall translation time improvement across the spec2k
components, with the liveness analysis time roughly cut in half.

[jvoung (off chromium), 2014-10-13 20:50:51]

Nice speedup

https://codereview.chromium.org/652633002/diff/160001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/652633002/diff/160001/src/IceCfg.cpp#newcode269
src/IceCfg.cpp:269: // this wouldn't work with non-SSA temporaries during
with the new flag for non-SSA temporaries, could the containsValue() be stricter
(if I'm reading the TODO comment correctly)?

https://codereview.chromium.org/652633002/diff/160001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/652633002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:442: InstNumberT LB = i == i1 ? IBB->second : FirstInstNum;
So it's possible that i == i1 && i == i2, in which case, LB is based on IBB and
LE is based on IEB?

It wasn't completely obvious to me that was happening when I first looked over
this, but I'm not sure what could make it clearer. I was concerned about what
would happen when that isn't the case, and it seems like that should only happen
when the "LB" should be really be FirstInstNum or the "LE" should be LastInstNum
+ 1.

https://codereview.chromium.org/652633002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:450: assert(i < Liveness->getNumGlobalVars());
I found it nice before where there was a variable "IsGlobal" to indicate what i
< NumGlobals meant. It's a bit less convenient now that it's only used for the
assert -- maybe leave a comment?

https://codereview.chromium.org/652633002/diff/160001/src/IceDefs.h
File src/IceDefs.h (right):

https://codereview.chromium.org/652633002/diff/160001/src/IceDefs.h#newcode73
src/IceDefs.h:73: typedef std::pair<SizeT, InstNumberT> BeginEndMapEntry;
Could you leave a comment about the structure of the BeginEndMaps? (what is the
SizeT in the pairs?).

Also, it might be good to call the type LiveBeginEnd..., though that's a bit
longer and the variable names usually have "Live" in it...

https://codereview.chromium.org/652633002/diff/160001/src/IceLiveness.h
File src/IceLiveness.h (right):

https://codereview.chromium.org/652633002/diff/160001/src/IceLiveness.h#newco...
src/IceLiveness.h:62: SizeT getLiveIndex(const Variable *Var) const;
Can this variant of getLiveIndex() be removed now?

https://codereview.chromium.org/652633002/diff/160001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (left):

https://codereview.chromium.org/652633002/diff/160001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4303: TimerMarker T(TimerStack::TT_postLower,
Func);
Is this removal intentional? Otherwise, you could remove TT_postLower from the
enum.

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

https://codereview.chromium.org/652633002/diff/160001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:1263: // eliminated in the presence of its later
definition.
Now that the fakeuse is removed, can the comment be tweaked slightly?

https://codereview.chromium.org/652633002/diff/160001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4294: // Find non-SSA instructions where
Dest==Src0, and set the
Add a note to clarify that this is for two-address instruction patterns?

https://codereview.chromium.org/652633002/diff/160001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/64bit.pnacl.ll (right):

https://codereview.chromium.org/652633002/diff/160001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/64bit.pnacl.ll:391: ; OPTM1: sar {{.*}}, 31
could the CHECK also check sar ..., 31 to be consistent with the OPTM1: ?

[Jim Stichnoth, 2014-10-13 23:15:23]

https://codereview.chromium.org/652633002/diff/160001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/652633002/diff/160001/src/IceCfg.cpp#newcode269
src/IceCfg.cpp:269: // this wouldn't work with non-SSA temporaries during
On 2014/10/13 20:50:50, jvoung wrote:
> with the new flag for non-SSA temporaries, could the containsValue() be
stricter
> (if I'm reading the TODO comment correctly)?

Cool, done.  There's a minor problem when a phi temporary is assigned in the
first instruction of the block, but is also live at the end of the previous
block, so we just avoid testing the first instruction of the block.

https://codereview.chromium.org/652633002/diff/160001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/652633002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:442: InstNumberT LB = i == i1 ? IBB->second : FirstInstNum;
On 2014/10/13 20:50:50, jvoung wrote:
> So it's possible that i == i1 && i == i2, in which case, LB is based on IBB
and
> LE is based on IEB?
> 
> It wasn't completely obvious to me that was happening when I first looked over
> this, but I'm not sure what could make it clearer. I was concerned about what
> would happen when that isn't the case, and it seems like that should only
happen
> when the "LB" should be really be FirstInstNum or the "LE" should be
LastInstNum
> + 1.

You're right on all points.  I added a comment here to try to clarify.

https://codereview.chromium.org/652633002/diff/160001/src/IceCfgNode.cpp#newc...
src/IceCfgNode.cpp:450: assert(i < Liveness->getNumGlobalVars());
On 2014/10/13 20:50:50, jvoung wrote:
> I found it nice before where there was a variable "IsGlobal" to indicate what
i
> < NumGlobals meant. It's a bit less convenient now that it's only used for the
> assert -- maybe leave a comment?

Agreed -- added a comment.

https://codereview.chromium.org/652633002/diff/160001/src/IceDefs.h
File src/IceDefs.h (right):

https://codereview.chromium.org/652633002/diff/160001/src/IceDefs.h#newcode73
src/IceDefs.h:73: typedef std::pair<SizeT, InstNumberT> BeginEndMapEntry;
On 2014/10/13 20:50:50, jvoung wrote:
> Could you leave a comment about the structure of the BeginEndMaps? (what is
the
> SizeT in the pairs?).
> 
> Also, it might be good to call the type LiveBeginEnd..., though that's a bit
> longer and the variable names usually have "Live" in it...

Both suggestions done.

https://codereview.chromium.org/652633002/diff/160001/src/IceLiveness.h
File src/IceLiveness.h (right):

https://codereview.chromium.org/652633002/diff/160001/src/IceLiveness.h#newco...
src/IceLiveness.h:62: SizeT getLiveIndex(const Variable *Var) const;
On 2014/10/13 20:50:50, jvoung wrote:
> Can this variant of getLiveIndex() be removed now?

Done.

https://codereview.chromium.org/652633002/diff/160001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (left):

https://codereview.chromium.org/652633002/diff/160001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4303: TimerMarker T(TimerStack::TT_postLower,
Func);
On 2014/10/13 20:50:50, jvoung wrote:
> Is this removal intentional? Otherwise, you could remove TT_postLower from the
> enum.

Removed the enum value.

I removed the TimerMarker because timing every instruction adds a lot of timing
overhead.  I'm hesitant to even keep per-block timers, but I did leave one, and
it appears to cost about 3% of total execution time.

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

https://codereview.chromium.org/652633002/diff/160001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:1263: // eliminated in the presence of its later
definition.
On 2014/10/13 20:50:50, jvoung wrote:
> Now that the fakeuse is removed, can the comment be tweaked slightly?

Done.

https://codereview.chromium.org/652633002/diff/160001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4294: // Find non-SSA instructions where
Dest==Src0, and set the
On 2014/10/13 20:50:50, jvoung wrote:
> Add a note to clarify that this is for two-address instruction patterns?

Done.

https://codereview.chromium.org/652633002/diff/160001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/64bit.pnacl.ll (right):

https://codereview.chromium.org/652633002/diff/160001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/64bit.pnacl.ll:391: ; OPTM1: sar {{.*}}, 31
On 2014/10/13 20:50:50, jvoung wrote:
> could the CHECK also check sar ..., 31 to be consistent with the OPTM1: ?

No - with O2 (liveness analysis + DCE), the result of the latter sar instruction
is unused and therefore the sar is eliminated.  It would be nice if I could
specify that no sar instruction may appear before the end of the function
(without the hassle of a separate RUN line and prefix).

This is similar to the shl test where the O2 version should not use shld.

[jvoung (off chromium), 2014-10-13 23:38:29]

LGTM

https://codereview.chromium.org/652633002/diff/160001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/652633002/diff/160001/src/IceCfg.cpp#newcode269
src/IceCfg.cpp:269: // this wouldn't work with non-SSA temporaries during
On 2014/10/13 23:15:22, stichnot wrote:
> On 2014/10/13 20:50:50, jvoung wrote:
> > with the new flag for non-SSA temporaries, could the containsValue() be
> stricter
> > (if I'm reading the TODO comment correctly)?
> 
> Cool, done.  There's a minor problem when a phi temporary is assigned in the
> first instruction of the block, but is also live at the end of the previous
> block, so we just avoid testing the first instruction of the block.

Thanks! Can the TODO be removed then?

[Jim Stichnoth, 2014-10-14 00:15:01]

https://codereview.chromium.org/652633002/diff/160001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/652633002/diff/160001/src/IceCfg.cpp#newcode269
src/IceCfg.cpp:269: // this wouldn't work with non-SSA temporaries during
On 2014/10/13 23:38:29, jvoung wrote:
> On 2014/10/13 23:15:22, stichnot wrote:
> > On 2014/10/13 20:50:50, jvoung wrote:
> > > with the new flag for non-SSA temporaries, could the containsValue() be
> > stricter
> > > (if I'm reading the TODO comment correctly)?
> > 
> > Cool, done.  There's a minor problem when a phi temporary is assigned in the
> > first instruction of the block, but is also live at the end of the previous
> > block, so we just avoid testing the first instruction of the block.
> 
> Thanks! Can the TODO be removed then?

Oops, done.

[Jim Stichnoth, 2014-10-14 00:15:12]

Committed patchset #4 (id:290001) manually as
4775255d4244c3425da0a7afd5f2c1ccb3a7dca9 (presubmit successful).