[turbofan] Variable liveness analysis for deopt

[turbofan] Variable liveness analysis for deopt.

This change introduces a liveness analyzer for local variables in frame states.

The main idea is to use the AstGraphBuilder::Environment class to build the control flow graph, and record local variable loads, stores and checkpoints in the CFG basic blocks (LivenessAnalyzerBlock class).

After the graph building finishes, we run a simple data flow analysis over the CFG to figure out liveness of each local variable at each checkpoint. Finally, we run a pass over all the checkpoints and replace dead local variables in the frame states with the 'undefined' value.

Performance numbers for Embenchen are below.

----------- box2d.js
Current --turbo-deoptimization: EmbenchenBox2d(RunTime): 11265 ms.
d8-master --turbo-deoptimization: EmbenchenBox2d(RunTime): 11768 ms.
d8-master: EmbenchenBox2d(RunTime): 10996 ms.
----------- bullet.js
Current --turbo-deoptimization: EmbenchenBullet(RunTime): 17049 ms.
d8-master --turbo-deoptimization: EmbenchenBullet(RunTime): 17384 ms.
d8-master: EmbenchenBullet(RunTime): 16153 ms.
----------- copy.js
Current --turbo-deoptimization: EmbenchenCopy(RunTime): 4877 ms.
d8-master --turbo-deoptimization: EmbenchenCopy(RunTime): 4938 ms.
d8-master: EmbenchenCopy(RunTime): 4940 ms.
----------- corrections.js
Current --turbo-deoptimization: EmbenchenCorrections(RunTime): 7068 ms.
d8-master --turbo-deoptimization: EmbenchenCorrections(RunTime): 6718 ms.
d8-master: EmbenchenCorrections(RunTime): 6858 ms.
----------- fannkuch.js
Current --turbo-deoptimization: EmbenchenFannkuch(RunTime): 4167 ms.
d8-master --turbo-deoptimization: EmbenchenFannkuch(RunTime): 4608 ms.
d8-master: EmbenchenFannkuch(RunTime): 4149 ms.
----------- fasta.js
Current --turbo-deoptimization: EmbenchenFasta(RunTime): 9981 ms.
d8-master --turbo-deoptimization: EmbenchenFasta(RunTime): 9848 ms.
d8-master: EmbenchenFasta(RunTime): 9640 ms.
----------- lua_binarytrees.js
Current --turbo-deoptimization: EmbenchenLuaBinaryTrees(RunTime): 11571 ms.
d8-master --turbo-deoptimization: EmbenchenLuaBinaryTrees(RunTime): 13089 ms.
d8-master: EmbenchenLuaBinaryTrees(RunTime): 10957 ms.
----------- memops.js
Current --turbo-deoptimization: EmbenchenMemOps(RunTime): 7766 ms.
d8-master --turbo-deoptimization: EmbenchenMemOps(RunTime): 7346 ms.
d8-master: EmbenchenMemOps(RunTime): 7738 ms.
----------- primes.js
Current --turbo-deoptimization: EmbenchenPrimes(RunTime): 7459 ms.
d8-master --turbo-deoptimization: EmbenchenPrimes(RunTime): 7453 ms.
d8-master: EmbenchenPrimes(RunTime): 7451 ms.
----------- skinning.js
Current --turbo-deoptimization: EmbenchenSkinning(RunTime): 15564 ms.
d8-master --turbo-deoptimization: EmbenchenSkinning(RunTime): 15611 ms.
d8-master: EmbenchenSkinning(RunTime): 15583 ms.
----------- zlib.js
Current --turbo-deoptimization: EmbenchenZLib(RunTime): 10825 ms.
d8-master --turbo-deoptimization: EmbenchenZLib(RunTime): 11180 ms.
d8-master: EmbenchenZLib(RunTime): 10823 ms.

BUG=

Committed: https://crrev.com/ca3abde2fad3af0c84fc368e111149e966727dde
Cr-Commit-Position: refs/heads/master@{#27232}

[Jarin, 2015-02-22 10:18:54]

jarin@chromium.org changed reviewers:
+ bmeurer@chromium.org

[Jarin, 2015-02-25 09:33:04]

jarin@chromium.org changed reviewers:
+ mstarzinger@chromium.org

[Jarin, 2015-02-25 09:35:42]

On 2015/02/25 09:33:04, jarin wrote:
> mailto:jarin@chromium.org changed reviewers:
> + mailto:mstarzinger@chromium.org

Michael, could you have a look, please? I would especially welcome comments on
the AstGraphBuilder integration.

[titzer, 2015-02-27 21:03:53]

titzer@chromium.org changed reviewers:
+ titzer@chromium.org

[titzer, 2015-02-27 21:03:54]

https://codereview.chromium.org/949743002/diff/130001/src/compiler/liveness-a...
File src/compiler/liveness-analyzer.h (right):

https://codereview.chromium.org/949743002/diff/130001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.h:21: void RelaxFrameState(Node* frame_state,
ZoneVector<bool>* liveness);
Can we use a BitVector here and in the implementation. The space usage of
ZoneVector<bool> is probably not a big issue, but with BitVector it will
definitely be smaller, and we are already using BitVector in other analyses like
loop assignment analsysis.

[titzer, 2015-02-27 21:09:55]

Looks good, pretty clean. Mostly just naming nits.

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
File src/compiler/ast-graph-builder.cc (right):

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.cc:548: relaxer.Blacklist(arguments->index());
Maybe "MarkPermanentlyLive(int index)" as a better name?

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.cc:665: void
AstGraphBuilder::Environment::MakeAllLocalsLive() {
Make -> Mark?

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
File src/compiler/ast-graph-builder.h (right):

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.h:273: void RelaxFrameStatesWithLiveness();
Can we use another word than "Relax", here and elsewhere? E.g. this method might
be better called "ClearNonLiveFrameStateSlots" or something similar.

[Michael Starzinger, 2015-03-01 21:00:56]

I don't have any more constructive feedback on this CL. Please choose another
reviewer to approve this change.

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
File src/compiler/ast-graph-builder.cc (right):

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.cc:533:
graph()->SetEnd(NewNode(common()->End()));
This duplicates the end node, please don't do this.

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.cc:537: RelaxFrameStatesWithLiveness();
Rather move this call into CreateGraph() a few lines above.

[Michael Starzinger, 2015-03-02 10:56:34]

A coupla' nits.

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
File src/compiler/ast-graph-builder.cc (right):

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.cc:674: AstGraphBuilder::Environment*
AstGraphBuilder::Environment::Snapshot() {
nit: How about s/Snapshot/CopyAndShareLiveness/ here, or anything else that
starts with the "Copy" prefix?

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
File src/compiler/ast-graph-builder.h (right):

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.h:359: // shifted by 1 (receiver is parameter
index -1 but environment index 0).
nit: I think the second sentence in the comment makes more sense for the
implementation, not the interface. Can we move it to where the magic off-by one
calculation is performed?

[Jarin, 2015-03-16 21:30:12]

Benedikt, could you take another look?

I have rebased this to use the state values cache.

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
File src/compiler/ast-graph-builder.cc (right):

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.cc:533:
graph()->SetEnd(NewNode(common()->End()));
On 2015/03/01 21:00:56, Michael Starzinger wrote:
> This duplicates the end node, please don't do this.

Great catch, bad rebase. Done.

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.cc:537: RelaxFrameStatesWithLiveness();
On 2015/03/01 21:00:56, Michael Starzinger wrote:
> Rather move this call into CreateGraph() a few lines above.

Done.

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.cc:548: relaxer.Blacklist(arguments->index());
On 2015/02/27 21:09:55, titzer wrote:
> Maybe "MarkPermanentlyLive(int index)" as a better name?

Done.

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.cc:665: void
AstGraphBuilder::Environment::MakeAllLocalsLive() {
On 2015/02/27 21:09:55, titzer wrote:
> Make -> Mark?

Done.

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.cc:674: AstGraphBuilder::Environment*
AstGraphBuilder::Environment::Snapshot() {
On 2015/03/02 10:56:34, Michael Starzinger wrote:
> nit: How about s/Snapshot/CopyAndShareLiveness/ here, or anything else that
> starts with the "Copy" prefix?

Done.

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
File src/compiler/ast-graph-builder.h (right):

https://codereview.chromium.org/949743002/diff/130001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.h:359: // shifted by 1 (receiver is parameter
index -1 but environment index 0).
On 2015/03/02 10:56:34, Michael Starzinger wrote:
> nit: I think the second sentence in the comment makes more sense for the
> implementation, not the interface. Can we move it to where the magic off-by
one
> calculation is performed?

Done.

https://codereview.chromium.org/949743002/diff/130001/src/compiler/liveness-a...
File src/compiler/liveness-analyzer.h (right):

https://codereview.chromium.org/949743002/diff/130001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.h:21: void RelaxFrameState(Node* frame_state,
ZoneVector<bool>* liveness);
On 2015/02/27 21:03:54, titzer wrote:
> Can we use a BitVector here and in the implementation. The space usage of
> ZoneVector<bool> is probably not a big issue, but with BitVector it will
> definitely be smaller, and we are already using BitVector in other analyses
like
> loop assignment analsysis.

Done. (Will BitVector be really smaller? Why?)

[Benedikt Meurer, 2015-03-17 05:12:03]

https://codereview.chromium.org/949743002/diff/210001/src/compiler/ast-graph-...
File src/compiler/ast-graph-builder.h (right):

https://codereview.chromium.org/949743002/diff/210001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.h:107: LivenessAnalyzer* liveness_analyzer_;
Chromium style guide nit again: Don't turn into pointer just to be able to
forward declare.

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
File src/compiler/liveness-analyzer.cc (right):

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.cc:60: BitVector working_area(local_count_ == 0 ?
1 : static_cast<int>(local_count_),
Is it worth adding a shortcut of the rest for local_count_ == 0? In that case
you just need to setup the live_ target bit vector unless I'm missing something?

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
File src/compiler/liveness-analyzer.h (right):

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.h:54: class LivenessAnalyzer : public ZoneObject
{
Chromium style guide nit (see above): No need to inherit from ZoneObject here.

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.h:58: LivenessAnalyzerBlock* New();
Nit: Rename to NewBlock.

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.h:59: LivenessAnalyzerBlock*
New(LivenessAnalyzerBlock* predecessor);
Nit: Rename to NewBlock.

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.h:115: LivenessAnalyzerBlock(size_t id, size_t
local_count, Zone* zone)
Nit: Move implementation to .cc file.

https://codereview.chromium.org/949743002/diff/210001/src/compiler/state-valu...
File src/compiler/state-values-utils.cc (right):

https://codereview.chromium.org/949743002/diff/210001/src/compiler/state-valu...
src/compiler/state-values-utils.cc:175: DCHECK_NE(values[i]->opcode(),
IrOpcode::kStateValues);
Nit: expected, actual

[Jarin, 2015-03-17 09:22:57]

All done. Thanks!

https://codereview.chromium.org/949743002/diff/210001/src/compiler/ast-graph-...
File src/compiler/ast-graph-builder.h (right):

https://codereview.chromium.org/949743002/diff/210001/src/compiler/ast-graph-...
src/compiler/ast-graph-builder.h:107: LivenessAnalyzer* liveness_analyzer_;
On 2015/03/17 05:12:03, Benedikt Meurer wrote:
> Chromium style guide nit again: Don't turn into pointer just to be able to
> forward declare.

Done.

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
File src/compiler/liveness-analyzer.cc (right):

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.cc:60: BitVector working_area(local_count_ == 0 ?
1 : static_cast<int>(local_count_),
On 2015/03/17 05:12:03, Benedikt Meurer wrote:
> Is it worth adding a shortcut of the rest for local_count_ == 0? In that case
> you just need to setup the live_ target bit vector unless I'm missing
something?

Done.

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
File src/compiler/liveness-analyzer.h (right):

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.h:54: class LivenessAnalyzer : public ZoneObject
{
On 2015/03/17 05:12:03, Benedikt Meurer wrote:
> Chromium style guide nit (see above): No need to inherit from ZoneObject here.

Done.

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.h:58: LivenessAnalyzerBlock* New();
On 2015/03/17 05:12:03, Benedikt Meurer wrote:
> Nit: Rename to NewBlock.

Done.

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.h:59: LivenessAnalyzerBlock*
New(LivenessAnalyzerBlock* predecessor);
On 2015/03/17 05:12:03, Benedikt Meurer wrote:
> Nit: Rename to NewBlock.

Done.

https://codereview.chromium.org/949743002/diff/210001/src/compiler/liveness-a...
src/compiler/liveness-analyzer.h:115: LivenessAnalyzerBlock(size_t id, size_t
local_count, Zone* zone)
On 2015/03/17 05:12:03, Benedikt Meurer wrote:
> Nit: Move implementation to .cc file.

Done.

[Benedikt Meurer, 2015-03-17 09:29:29]

lgtm

[Jarin, 2015-03-17 09:33:56]

The CQ bit was checked by jarin@chromium.org

[commit-bot: I haz the power, 2015-03-17 09:34:09]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/949743002/230001

[commit-bot: I haz the power, 2015-03-17 09:38:42]

Committed patchset #14 (id:230001)

[commit-bot: I haz the power, 2015-03-17 09:38:50]

Patchset 14 (id:??) landed as
https://crrev.com/ca3abde2fad3af0c84fc368e111149e966727dde
Cr-Commit-Position: refs/heads/master@{#27232}