First implementation of allocation elimination in Hydrogen.

First implementation of allocation elimination in Hydrogen.

This change implements a simple data-flow analysis pass over captured
objects to the existing escape analysis. It tracks the state of values
in the Hydrogen graph through CapturedObject marker instructions that
are used to construct an appropriate translation for the deoptimizer to
be able to materialize these objects again.

This can be considered a combination of scalar replacement of loads and
stores on captured objects and sinking of unused allocations.

R=titzer@chromium.org
TEST=mjsunit/compiler/escape-analysis

Committed: http://code.google.com/p/v8/source/detail?r=16098

[Michael Starzinger, 2013-07-31 13:13:40]

First prototype is ready. There are a couple of open issue, hence the escape
analysis is still disabled in this patch. But I wanted to get a first round of
high level comments first. Known issues are:

* Ports to x64 and ARM still missing.
* HCheckMaps can only be eliminated for constant maps.
* HSimualtes with deltas are not tracked during analysis.
* Unsafe handle dereference (parallel compiler) during analysis.
* Missing fix-point iteration to improve analysis result.

[titzer, 2013-08-01 17:11:50]

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
File src/hydrogen-escape-analysis.cc (right):

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.cc:74: for (int i = 0; i <
graph()->blocks()->length(); i++) {
You can start i at allocate_block->id(), since the allocation cannot dominate
blocks that come before.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.cc:99: for (int index = 0; index <
number_of_values_; index++) {
You're creating a lot of phis here. You only need to create a phi if this block
is a loop header, or if the predecessors do not have the same HValue for a
tracked field.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.cc:117: int index = load->access().offset() /
kPointerSize;
Are you only tracking in-object properties? Otherwise, you need to check the
in-objectness of the access as well.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.cc:189: SetStateAt(block, state);
You should forward-propagate the block state to all successors of this block;
then you can delete (or even reuse) the block state.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.cc:206: for (int index = 0; index <
number_of_values_; index++) {
This is somewhat brittle because the phi input indexes must match up with the
predecessor indexes, and since your edges are coming off a stack, I'm really
surprised you were so lucky. This needs to be more robust somehow.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
File src/hydrogen-escape-analysis.h (right):

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.h:61: HCapturedObject* NewState(HInstruction*
previous) {
Not sure why these New* methods are in the header. They seem pretty complicated,
too.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.h:146: BitVector loops_affected_by_stores_;
As I understand it, you were going to track which loops had stores in a later
CL. If so, you can just leave this guy out for now.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-instructions....
src/hydrogen-instructions.h:3451: ZoneList<HValue*> values_;
How is this values_ array indexed? Does it store only in-object properties and
is indexed by field index?

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen.cc#newcode2952
src/hydrogen.cc:2952: 
whitespace change

https://codereview.chromium.org/21055011/diff/3001/src/ia32/lithium-codegen-i...
File src/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/21055011/diff/3001/src/ia32/lithium-codegen-i...
src/ia32/lithium-codegen-ia32.cc:785: if
(environment->ObjectIsDuplicateAt(object_index)) {
ObjectDuplicate means...object reference?

https://codereview.chromium.org/21055011/diff/3001/src/lithium.h
File src/lithium.h (right):

https://codereview.chromium.org/21055011/diff/3001/src/lithium.h#newcode624
src/lithium.h:624: static LOperand* materialization_marker() { return NULL; }
NULL seems like it could get mixed up sometime. Maybe -1?

[Michael Starzinger, 2013-08-05 15:13:00]

Addressed comments. Starting with architecture ports. PTAL.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
File src/hydrogen-escape-analysis.cc (right):

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.cc:74: for (int i = 0; i <
graph()->blocks()->length(); i++) {
On 2013/08/01 17:11:50, titzer wrote:
> You can start i at allocate_block->id(), since the allocation cannot dominate
> blocks that come before.

Done. So obvious, I feel embarrassed now.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.cc:99: for (int index = 0; index <
number_of_values_; index++) {
On 2013/08/01 17:11:50, titzer wrote:
> You're creating a lot of phis here. You only need to create a phi if this
block
> is a loop header, or if the predecessors do not have the same HValue for a
> tracked field.

Done. Switched to lazy creation of phis only once one of the incoming values is
actually different from the others.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.cc:117: int index = load->access().offset() /
kPointerSize;
On 2013/08/01 17:11:50, titzer wrote:
> Are you only tracking in-object properties? Otherwise, you need to check the
> in-objectness of the access as well.

Done. Good point, currently we don't HAllocate objects that have out-of-object
fields and hence this doesn't happen. But I added asserts to guard that.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.cc:189: SetStateAt(block, state);
On 2013/08/01 17:11:50, titzer wrote:
> You should forward-propagate the block state to all successors of this block;
> then you can delete (or even reuse) the block state.

Done. Switched to forward propagation of the block state.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.cc:206: for (int index = 0; index <
number_of_values_; index++) {
On 2013/08/01 17:11:50, titzer wrote:
> This is somewhat brittle because the phi input indexes must match up with the
> predecessor indexes, and since your edges are coming off a stack, I'm really
> surprised you were so lucky. This needs to be more robust somehow.

Done. Switched to use HBasicBlock::PredecessorIndexOf to always set operands at
the correct index. Also the post-processing step is obsolete after switching to
forward propagation.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
File src/hydrogen-escape-analysis.h (right):

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.h:61: HCapturedObject* NewState(HInstruction*
previous) {
On 2013/08/01 17:11:50, titzer wrote:
> Not sure why these New* methods are in the header. They seem pretty
complicated,
> too.

Done. Moved their implementation into the .cc file.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-escape-analys...
src/hydrogen-escape-analysis.h:146: BitVector loops_affected_by_stores_;
On 2013/08/01 17:11:50, titzer wrote:
> As I understand it, you were going to track which loops had stores in a later
> CL. If so, you can just leave this guy out for now.

Done. Ooops, that is a leftover from a previous implementation and I forgot to
remove it. Removed.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen-instructions....
src/hydrogen-instructions.h:3451: ZoneList<HValue*> values_;
On 2013/08/01 17:11:50, titzer wrote:
> How is this values_ array indexed? Does it store only in-object properties and
> is indexed by field index?

Correct. I added a comment to both HArgumentsObject and HCapturedObject below
that covers this.

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/21055011/diff/3001/src/hydrogen.cc#newcode2952
src/hydrogen.cc:2952: 
On 2013/08/01 17:11:50, titzer wrote:
> whitespace change

Done. Removed. Even though I think there should be whitespace here.

https://codereview.chromium.org/21055011/diff/3001/src/ia32/lithium-codegen-i...
File src/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/21055011/diff/3001/src/ia32/lithium-codegen-i...
src/ia32/lithium-codegen-ia32.cc:785: if
(environment->ObjectIsDuplicateAt(object_index)) {
On 2013/08/01 17:11:50, titzer wrote:
> ObjectDuplicate means...object reference?

Correct. It means that a previously translated object is referenced again by
another slot (either on the stack or inside another dematerialized object). I
can rename all uses of "duplicated object" to "referenced object" if you think
that clarifies the situation. Let me know.

https://codereview.chromium.org/21055011/diff/3001/src/lithium.h
File src/lithium.h (right):

https://codereview.chromium.org/21055011/diff/3001/src/lithium.h#newcode624
src/lithium.h:624: static LOperand* materialization_marker() { return NULL; }
On 2013/08/01 17:11:50, titzer wrote:
> NULL seems like it could get mixed up sometime. Maybe -1?

That would require many changes in the register allocator, because NULL is the
only LOperand being skipped there. We can do that, but I would very much like to
do that in another CL, not as part of this one.

[titzer, 2013-08-06 12:15:46]

LGTM with some comments

https://codereview.chromium.org/21055011/diff/28001/src/heap.cc
File src/heap.cc (right):

https://codereview.chromium.org/21055011/diff/28001/src/heap.cc#newcode4516
src/heap.cc:4516: Map* map, PretenureFlag pretenure) {
Seems to be a lot of overlap with the above function. Can we factor that out
somehow, maybe even have one function that can do both?

https://codereview.chromium.org/21055011/diff/28001/src/hydrogen-escape-analy...
File src/hydrogen-escape-analysis.cc (right):

https://codereview.chromium.org/21055011/diff/28001/src/hydrogen-escape-analy...
src/hydrogen-escape-analysis.cc:224: // is not a HConstant. Find a repro test
case and fix this.
Could it be the case that a later load or store still references this checkmaps
instruction? In that case, wouldn't those uses then refer directly to value? Or
do you consider such a check to be an escaping use?

https://codereview.chromium.org/21055011/diff/28001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/21055011/diff/28001/src/hydrogen.cc#newcode2964
src/hydrogen.cc:2964: if (FLAG_use_escape_analysis) Run<HEscapeAnalysisPhase>();
I think you might want to run after the first DCE phase, so that objects don't
escape through dead code somehow.

[Michael Starzinger, 2013-08-07 10:51:16]

Addressed comments. Rebasing. Landing.

https://codereview.chromium.org/21055011/diff/28001/src/heap.cc
File src/heap.cc (right):

https://codereview.chromium.org/21055011/diff/28001/src/heap.cc#newcode4516
src/heap.cc:4516: Map* map, PretenureFlag pretenure) {
On 2013/08/06 12:15:47, titzer wrote:
> Seems to be a lot of overlap with the above function. Can we factor that out
> somehow, maybe even have one function that can do both? 

Done. Merged together and added a flag.

https://codereview.chromium.org/21055011/diff/28001/src/hydrogen-escape-analy...
File src/hydrogen-escape-analysis.cc (right):

https://codereview.chromium.org/21055011/diff/28001/src/hydrogen-escape-analy...
src/hydrogen-escape-analysis.cc:224: // is not a HConstant. Find a repro test
case and fix this.
On 2013/08/06 12:15:47, titzer wrote:
> Could it be the case that a later load or store still references this
checkmaps
> instruction? In that case, wouldn't those uses then refer directly to value?
Or
> do you consider such a check to be an escaping use?

Yes, this could unfortunately happen. We cannot enable this until I solved the
CheckMaps problem. I'll work on that next, the TODO is already in place (might
just be phrased incompletely).

https://codereview.chromium.org/21055011/diff/28001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/21055011/diff/28001/src/hydrogen.cc#newcode2964
src/hydrogen.cc:2964: if (FLAG_use_escape_analysis) Run<HEscapeAnalysisPhase>();
On 2013/08/06 12:15:47, titzer wrote:
> I think you might want to run after the first DCE phase, so that objects don't
> escape through dead code somehow.

Done. Moved to after DCE.

[Michael Starzinger, 2013-08-07 11:24:29]

Committed patchset #6 manually as r16098 (presubmit successful).