Improve GVN handling of ElementTransitions.

Improve GVN handling of ElementTransitions.

BUG=
TEST=

Committed: https://code.google.com/p/v8/source/detail?r=10651

[danno, 2012-01-24 22:10:48]

PTAL

[fschneider, 2012-01-25 00:04:57]

http://codereview.chromium.org/9141016/diff/8001/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/9141016/diff/8001/src/hydrogen.cc#newcode1494
src/hydrogen.cc:1494: // instruction.
In general a path from the header to the current instruction may involve all
blocks from the loop that are not dominated by the current instruction.
  preceeding_loop_depends accumulates the dependencies of the blocks with an id
less than the current block, and therefore can be missing the ones of blocks
with higher ids that are not dominated by the current instruction.

http://codereview.chromium.org/9141016/diff/8001/src/hydrogen.cc#newcode1495
src/hydrogen.cc:1495: can_hoist =
Please add a unit test that covers the two cases that can occur here: hoisting
and not hoisting the instruction.

[danno, 2012-01-31 15:38:25]

Please take another look.

https://chromiumcodereview.appspot.com/9141016/diff/8001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/9141016/diff/8001/src/hydrogen.cc#newc...
src/hydrogen.cc:1494: // instruction.
I'm not sure that's true. We're careful to order the blocks in reverse post
order, which means that ignoring loops, if there is a path a -> b -> c, then
a.id() < b.id() < c.id(). It's overly conservative, but correct. I talked to
Kevin, and he also agreed that this reasoning is sound, and also pointed out
that liveness analysis relies on this same principle.
On 2012/01/25 00:04:57, fschneider wrote:
> In general a path from the header to the current instruction may involve all
> blocks from the loop that are not dominated by the current instruction.
>   preceeding_loop_depends accumulates the dependencies of the blocks with an
id
> less than the current block, and therefore can be missing the ones of blocks
> with higher ids that are not dominated by the current instruction.

https://chromiumcodereview.appspot.com/9141016/diff/8001/src/hydrogen.cc#newc...
src/hydrogen.cc:1495: can_hoist =
On 2012/01/25 00:04:57, fschneider wrote:
> Please add a unit test that covers the two cases that can occur here: hoisting
> and not hoisting the instruction.

Done.

[fschneider, 2012-02-01 10:54:14]

https://chromiumcodereview.appspot.com/9141016/diff/16001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/9141016/diff/16001/src/hydrogen.cc#new...
src/hydrogen.cc:1478: // the current block contain all of the loop's
dependencies.
I don't think this works in general: e.g. in a simple while-loop:

P->H
H->A
H->X
A->B
A->C
B->D
C->D
D-->H

If I understand the code correctly, the outstanding count would be > 0 for all
blocks A, B, C, D.

https://chromiumcodereview.appspot.com/9141016/diff/16001/test/mjsunit/elemen...
File test/mjsunit/elements-transition-hoisting.js (right):

https://chromiumcodereview.appspot.com/9141016/diff/16001/test/mjsunit/elemen...
test/mjsunit/elements-transition-hoisting.js:50: // point, but when the code
gets optimized, the double transition should
s/double//

https://chromiumcodereview.appspot.com/9141016/diff/16001/test/mjsunit/elemen...
test/mjsunit/elements-transition-hoisting.js:56: } while (false);
do { } while(false) may be optimized away by the compiler. Not sure if we
currently do it, but in the future it will definitely be.

https://chromiumcodereview.appspot.com/9141016/diff/16001/test/mjsunit/elemen...
test/mjsunit/elements-transition-hoisting.js:57: // Check outside of loop to
prevent call in loop
This comment does not make sense: there is already a call to assertTrue,
%HasFastElements, etc. inside the loop.

https://chromiumcodereview.appspot.com/9141016/diff/16001/test/mjsunit/elemen...
test/mjsunit/elements-transition-hoisting.js:76: // point, but when the code
gets optimized, the double transition should
s/double//

https://chromiumcodereview.appspot.com/9141016/diff/16001/test/mjsunit/elemen...
test/mjsunit/elements-transition-hoisting.js:109: a.foo = object; // This map
check should be hoistable
There are calls inside the loop, so this map check won't be hoisted.

[danno, 2012-02-01 16:53:15]

please take another look.

http://codereview.chromium.org/9141016/diff/16001/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/9141016/diff/16001/src/hydrogen.cc#newcode1478
src/hydrogen.cc:1478: // the current block contain all of the loop's
dependencies.
On 2012/02/01 10:54:14, fschneider wrote:
> I don't think this works in general: e.g. in a simple while-loop:
> 
> P->H
> H->A
> H->X
> A->B
> A->C
> B->D
> C->D
> D-->H
> 
> If I understand the code correctly, the outstanding count would be > 0 for all
> blocks A, B, C, D.

Done.

http://codereview.chromium.org/9141016/diff/16001/test/mjsunit/elements-trans...
File test/mjsunit/elements-transition-hoisting.js (right):

http://codereview.chromium.org/9141016/diff/16001/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:50: // point, but when the code
gets optimized, the double transition should
On 2012/02/01 10:54:14, fschneider wrote:
> s/double//

Done.

http://codereview.chromium.org/9141016/diff/16001/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:56: } while (false);
On 2012/02/01 10:54:14, fschneider wrote:
> do { } while(false) may be optimized away by the compiler. Not sure if we
> currently do it, but in the future it will definitely be.

Done.

http://codereview.chromium.org/9141016/diff/16001/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:57: // Check outside of loop to
prevent call in loop
On 2012/02/01 10:54:14, fschneider wrote:
> This comment does not make sense: there is already a call to assertTrue,
> %HasFastElements, etc. inside the loop.

Done.

http://codereview.chromium.org/9141016/diff/16001/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:76: // point, but when the code
gets optimized, the double transition should
On 2012/02/01 10:54:14, fschneider wrote:
> s/double//

Done.

http://codereview.chromium.org/9141016/diff/16001/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:109: a.foo = object; // This map
check should be hoistable
On 2012/02/01 10:54:14, fschneider wrote:
> There are calls inside the loop, so this map check won't be hoisted.

Done.

[fschneider, 2012-02-02 14:59:50]

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen-instructions.h...
src/hydrogen-instructions.h:4170: SetGVNFlag(kDependsOnMaps);
There is currently no instruction that has kChangesMaps set (except calls that
have all side effects).

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen-instructions.h...
src/hydrogen-instructions.h:4188: virtual bool HasOneTimeSideEffects() const {
It may be not worth making a predicate that applies to exactly one instruction a
separate virtual function (unless we plan to get more instructions like this).

 I'd just use IsTransitionElementsKind() for now.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode330
src/hydrogen.cc:330: int outstanding_sucsessors = 1;  // one edge from the
pre-header
s/sucsessors/successors/g

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode333
src/hydrogen.cc:333: for (int j = block_id(); j <= last->block_id(); ++j) {
Maybe this be simplified: The header is always marked, so there is no need to
include it in the iteration:

Would it work to initialize outstanding_successors to 0 and  start at block_id()
+ 1 instead?

Then you could also save detecting back edges below.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode338
src/hydrogen.cc:338: for (int i = 0; i < predecessor_count; ++i) {
Maybe it would make sense to introduce a HPredecessorIterator, similar to
HSuccessorIterator for more concise code.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode358
src/hydrogen.cc:358: MarkAsLoopSuccessorDominator();
I guess this should be:

candidate_dominator->MarkAsLoopSuccessorDominator();

otherwise no other block will be marked.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode362
src/hydrogen.cc:362: for (int current = 0; current < successor_count; ++current)
{
You can use HSuccessorIterator here.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode1478
src/hydrogen.cc:1478: for (int i = 0; i < loop_side_effects_.length(); ++i) {
Comment on why resetting the loop side effect sets.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode1552
src/hydrogen.cc:1552: !instr->HasObservableSideEffects() &&
maybe just say: 

if (!can_hoist && instr->IsTransitionElementsKind())

I think this should be generalized as necessary in the future.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode1572
src/hydrogen.cc:1572: can_hoist = !not_in_nested_loop &&
The double negation !not... should be avoided for readability.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode1597
src/hydrogen.cc:1597: // SideEffects flags to not prevent hosting
OneTimeSideEffecct
I find the double negation in the comment confusing. How about the following:

If an instruction is not hoisted, we have to account for its side effects when
hoisting later HTransitionElementsKind instructions.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.h
File src/hydrogen.h (right):

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.h#newcode156
src/hydrogen.h:156: void MarkAsLoopSuccessorDominator() {
Please add output to --trace-hydrogen so that you can identify the marked blocks
in the visualizer.

[danno, 2012-02-06 16:54:57]

Feedback addressed, please take another look.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen-instructions.h...
src/hydrogen-instructions.h:4170: SetGVNFlag(kDependsOnMaps);
But if we ever add one, then it will be incorrect to hoist the transitions about
it, so I'd prefer to keep this in.
On 2012/02/02 14:59:50, fschneider wrote:
> There is currently no instruction that has kChangesMaps set (except calls that
> have all side effects).

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen-instructions.h...
src/hydrogen-instructions.h:4188: virtual bool HasOneTimeSideEffects() const {
On 2012/02/02 14:59:50, fschneider wrote:
> It may be not worth making a predicate that applies to exactly one instruction
a
> separate virtual function (unless we plan to get more instructions like this).
> 
>  I'd just use IsTransitionElementsKind() for now.

Done.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode330
src/hydrogen.cc:330: int outstanding_sucsessors = 1;  // one edge from the
pre-header
On 2012/02/02 14:59:50, fschneider wrote:
> s/sucsessors/successors/g

Done.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode333
src/hydrogen.cc:333: for (int j = block_id(); j <= last->block_id(); ++j) {
You have to iterate over every block's successors, even the header, so the
header must be included in the iteration over the loop.
On 2012/02/02 14:59:50, fschneider wrote:
> Maybe this be simplified: The header is always marked, so there is no need to
> include it in the iteration:
> 
> Would it work to initialize outstanding_successors to 0 and  start at
block_id()
> + 1 instead?
> 
> Then you could also save detecting back edges below.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode338
src/hydrogen.cc:338: for (int i = 0; i < predecessor_count; ++i) {
On 2012/02/02 14:59:50, fschneider wrote:
> Maybe it would make sense to introduce a HPredecessorIterator, similar to
> HSuccessorIterator for more concise code.

Done.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode358
src/hydrogen.cc:358: MarkAsLoopSuccessorDominator();
On 2012/02/02 14:59:50, fschneider wrote:
> I guess this should be:
> 
> candidate_dominator->MarkAsLoopSuccessorDominator();
> 
> otherwise no other block will be marked.

Done.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode362
src/hydrogen.cc:362: for (int current = 0; current < successor_count; ++current)
{
On 2012/02/02 14:59:50, fschneider wrote:
> You can use HSuccessorIterator here.

Done.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode1478
src/hydrogen.cc:1478: for (int i = 0; i < loop_side_effects_.length(); ++i) {
On 2012/02/02 14:59:50, fschneider wrote:
> Comment on why resetting the loop side effect sets.

Done.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode1552
src/hydrogen.cc:1552: !instr->HasObservableSideEffects() &&
On 2012/02/02 14:59:50, fschneider wrote:
> maybe just say: 
> 
> if (!can_hoist && instr->IsTransitionElementsKind())
> 
> I think this should be generalized as necessary in the future.

Done.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode1572
src/hydrogen.cc:1572: can_hoist = !not_in_nested_loop &&
On 2012/02/02 14:59:50, fschneider wrote:
> The double negation !not... should be avoided for readability.

Done.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.cc#newcode1597
src/hydrogen.cc:1597: // SideEffects flags to not prevent hosting
OneTimeSideEffecct
On 2012/02/02 14:59:50, fschneider wrote:
> I find the double negation in the comment confusing. How about the following:
> 
> If an instruction is not hoisted, we have to account for its side effects when
> hoisting later HTransitionElementsKind instructions.

Done.

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.h
File src/hydrogen.h (right):

http://codereview.chromium.org/9141016/diff/20017/src/hydrogen.h#newcode156
src/hydrogen.h:156: void MarkAsLoopSuccessorDominator() {
On 2012/02/02 14:59:50, fschneider wrote:
> Please add output to --trace-hydrogen so that you can identify the marked
blocks
> in the visualizer.

Done.

[fschneider, 2012-02-07 10:05:05]

Please make sure that all tests work in the intended way by verifying the HIR
output. 

I really think we should have some automated way of testing individual
optimizations. Otherwise, the effort of manually verifying that a test does the
right thing is just enormous.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
File test/mjsunit/elements-transition-hoisting.js (right):

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:45: // Make sure that multiple
stores to an object array get hoisted in a way that
What is meant by hoisting multiple stores? Stores themselves never get hoisted.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:52: } while (global_false);
Maybe you should go around the loop >1 times in all tests where you want to test
that hoisting does not cause deopts.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:101: // Make sure that non-element
related map checks still get hoisted if all
The description of this test does not match the comment below where you write
that the map check should not be hoisted.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:111: a.foo = object; // This map
check should NOT be hoistable because includes
When running this test I see this map check hoisted which contradicts your
expectation here.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:128: a.foo = 0;
Since a.foo is not used in the loop, I don't see why it's necessary to add it
here.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:131: if (global_false != true) {
if (!global_false)

Otherwise the compare is generic (and a call inside the loop).

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:146: a.foo = 0;
Since a.foo is not used in the loop, I don't see why it's necessary to add it
here.

[danno, 2012-02-08 17:18:42]

Addressed feedback.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
File test/mjsunit/elements-transition-hoisting.js (right):

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:45: // Make sure that multiple
stores to an object array get hoisted in a way that
On 2012/02/07 10:05:05, fschneider wrote:
> What is meant by hoisting multiple stores? Stores themselves never get
hoisted.

Done.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:52: } while (global_false);
On 2012/02/07 10:05:05, fschneider wrote:
> Maybe you should go around the loop >1 times in all tests where you want to
test
> that hoisting does not cause deopts.

Done.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:101: // Make sure that non-element
related map checks still get hoisted if all
On 2012/02/07 10:05:05, fschneider wrote:
> The description of this test does not match the comment below where you write
> that the map check should not be hoisted.

Done.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:111: a.foo = object; // This map
check should NOT be hoistable because includes
On 2012/02/07 10:05:05, fschneider wrote:
> When running this test I see this map check hoisted which contradicts your
> expectation here.
> 

Done.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:128: a.foo = 0;
On 2012/02/07 10:05:05, fschneider wrote:
> Since a.foo is not used in the loop, I don't see why it's necessary to add it
> here.

Done.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:131: if (global_false != true) {
On 2012/02/07 10:05:05, fschneider wrote:
> if (!global_false)
> 
> Otherwise the compare is generic (and a call inside the loop).

Done.

http://codereview.chromium.org/9141016/diff/29002/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:146: a.foo = 0;
On 2012/02/07 10:05:05, fschneider wrote:
> Since a.foo is not used in the loop, I don't see why it's necessary to add it
> here.

Done.

[fschneider, 2012-02-09 08:43:32]

LGTM.

http://codereview.chromium.org/9141016/diff/35001/src/flag-definitions.h
File src/flag-definitions.h (right):

http://codereview.chromium.org/9141016/diff/35001/src/flag-definitions.h#newc...
src/flag-definitions.h:121: DEFINE_bool(smi_only_arrays, true, "tracks arrays
with only smi values")
Not sure if this is intended.

http://codereview.chromium.org/9141016/diff/35001/test/mjsunit/elements-trans...
File test/mjsunit/elements-transition-hoisting.js (right):

http://codereview.chromium.org/9141016/diff/35001/test/mjsunit/elements-trans...
test/mjsunit/elements-transition-hoisting.js:84: // depend on an elements
transition before them  and it's not possible to hoist
Long line.