Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(284)

Issue 652633002: Subzero: Improve performance of liveness analysis and live range construction. (Closed)

Created:
6 years, 2 months ago by Jim Stichnoth
Modified:
6 years, 2 months ago
CC:
native-client-reviews_googlegroups.com
Base URL:
https://chromium.googlesource.com/native_client/pnacl-subzero.git@master
Visibility:
Public.

Description

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

Patch Set 1 #

Patch Set 2 : Fix non-debug build #

Total comments: 20

Patch Set 3 : Code review changes #

Patch Set 4 : Remove TODO #

Unified diffs Side-by-side diffs Delta from patch set Stats (+322 lines, -140 lines) Patch
M src/IceCfg.h View 1 chunk +1 line, -0 lines 0 comments Download
M src/IceCfg.cpp View 1 2 3 4 chunks +29 lines, -15 lines 0 comments Download
M src/IceCfgNode.h View 2 chunks +6 lines, -0 lines 0 comments Download
M src/IceCfgNode.cpp View 1 2 13 chunks +90 lines, -40 lines 0 comments Download
M src/IceDefs.h View 1 2 3 1 chunk +7 lines, -0 lines 0 comments Download
M src/IceInst.h View 1 2 5 chunks +12 lines, -6 lines 0 comments Download
M src/IceInst.cpp View 1 2 6 chunks +25 lines, -15 lines 0 comments Download
M src/IceLiveness.h View 1 2 2 chunks +13 lines, -10 lines 0 comments Download
M src/IceLiveness.cpp View 1 2 4 chunks +5 lines, -8 lines 0 comments Download
M src/IceOperand.h View 1 2 3 4 chunks +11 lines, -3 lines 0 comments Download
M src/IceOperand.cpp View 1 2 3 chunks +9 lines, -6 lines 0 comments Download
M src/IceTargetLoweringX8632.h View 1 2 3 4 chunks +13 lines, -0 lines 0 comments Download
M src/IceTargetLoweringX8632.cpp View 1 2 3 11 chunks +41 lines, -35 lines 0 comments Download
M src/IceTimerTree.cpp View 2 chunks +5 lines, -1 line 0 comments Download
M src/IceTimerTree.def View 1 2 1 chunk +0 lines, -1 line 0 comments Download
M tests_lit/llvm2ice_tests/64bit.pnacl.ll View 3 chunks +55 lines, -0 lines 0 comments Download

Messages

Total messages: 7 (1 generated)
Jim Stichnoth
This gives a ~10% overall translation time improvement across the spec2k components, with the liveness ...
6 years, 2 months ago (2014-10-13 06:22:55 UTC) #2
jvoung (off chromium)
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 ...
6 years, 2 months ago (2014-10-13 20:50:51 UTC) #3
Jim Stichnoth
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 ...
6 years, 2 months ago (2014-10-13 23:15:23 UTC) #4
jvoung (off chromium)
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 ...
6 years, 2 months ago (2014-10-13 23:38:29 UTC) #5
Jim Stichnoth
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 ...
6 years, 2 months ago (2014-10-14 00:15:01 UTC) #6
Jim Stichnoth
6 years, 2 months ago (2014-10-14 00:15:12 UTC) #7
Message was sent while issue was closed.
Committed patchset #4 (id:290001) manually as
4775255d4244c3425da0a7afd5f2c1ccb3a7dca9 (presubmit successful).

Powered by Google App Engine
This is Rietveld 408576698