[turbofan] remove non-linearity in PopulateReferenceMaps

Some of the regression in the bug below was already addressed as
part of a compile time improvement push. We got from 3 minutes down
to ~30 seconds prior to the change here.

This change further reduces the compile time down to 2 seconds, which
is actually slightly better than the pre-splintering total execution time
of about 3 seconds.

The cause of the regression was the repeated traversal of the children
of a live range, seeking for the one covering a safe point. The fix is to
leverage the intrinsic ordering in the chain of live range children, as well
as that of the safe points.

BUG=chromium:567745
LOG=N

Committed: https://crrev.com/9e8b7564f79ed95b05041bea5f320fb1ca7f2373
Cr-Commit-Position: refs/heads/master@{#32958}

[Mircea Trofin, 2015-12-17 01:46:06]

Description was changed from

==========
fix perf

BUG=
==========

to

==========
Some of the regression in the bug below was already addressed as 
part of a compile time improvement push. We got from 3 minutes down
to ~30 seconds prior to the change here.

This change further reduces the compile time down to 2 seconds, which 
is actually slightly better than the pre-splintering total execution time
of about 3 seconds.

The cause of the regression was the repeated traversal of the children
of a live range, seeking for the one covering a safe point. The fix is to
leverage the intrinsic ordering in the chain of live range children, as well
as that of the safe points.

BUG= chromium:567745
==========

[Mircea Trofin, 2015-12-17 01:46:06]

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

[Jarin, 2015-12-17 08:51:37]

lgtm

https://codereview.chromium.org/1529293002/diff/50001/src/compiler/register-a...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1529293002/diff/50001/src/compiler/register-a...
src/compiler/register-allocator.cc:3130: DCHECK_NOT_NULL(cur);
I am wondering whether we could nopt do some sanity check for safepoint
ordering. Could not we DCHECK safe_point_pos >= cur->Start() here? (Actually we
might have to handle the first range separately, i.e. something like
DCHECK(safe_point_pos >= cur->Start() || range == cur).) What do you think?

[Mircea Trofin, 2015-12-17 16:32:45]

On 2015/12/17 08:51:37, Jarin wrote:
> lgtm
> 
>
https://codereview.chromium.org/1529293002/diff/50001/src/compiler/register-a...
> File src/compiler/register-allocator.cc (right):
> 
>
https://codereview.chromium.org/1529293002/diff/50001/src/compiler/register-a...
> src/compiler/register-allocator.cc:3130: DCHECK_NOT_NULL(cur);
> I am wondering whether we could nopt do some sanity check for safepoint
> ordering. Could not we DCHECK safe_point_pos >= cur->Start() here? (Actually
we
> might have to handle the first range separately, i.e. something like
> DCHECK(safe_point_pos >= cur->Start() || range == cur).) What do you think?

Do we want LOG=Y for this CL?

[Mircea Trofin, 2015-12-17 16:37:15]

Patchset #5 (id:70001) has been deleted

[Jarin, 2015-12-17 16:38:19]

On 2015/12/17 16:32:45, Mircea Trofin wrote:
> On 2015/12/17 08:51:37, Jarin wrote:
> > lgtm
> > 
> >
>
https://codereview.chromium.org/1529293002/diff/50001/src/compiler/register-a...
> > File src/compiler/register-allocator.cc (right):
> > 
> >
>
https://codereview.chromium.org/1529293002/diff/50001/src/compiler/register-a...
> > src/compiler/register-allocator.cc:3130: DCHECK_NOT_NULL(cur);
> > I am wondering whether we could nopt do some sanity check for safepoint
> > ordering. Could not we DCHECK safe_point_pos >= cur->Start() here? (Actually
> we
> > might have to handle the first range separately, i.e. something like
> > DCHECK(safe_point_pos >= cur->Start() || range == cur).) What do you think?
> 
> Do we want LOG=Y for this CL?

Not sure, I never do LOG=Y.

[Mircea Trofin, 2015-12-17 16:39:48]

Patchset #5 (id:90001) has been deleted

[Mircea Trofin, 2015-12-17 16:43:20]

The CQ bit was checked by mtrofin@chromium.org

[Mircea Trofin, 2015-12-17 16:43:20]

The patchset sent to the CQ was uploaded after l-g-t-m from jarin@chromium.org
Link to the patchset: https://codereview.chromium.org/1529293002/#ps130001
(title: "feedback")

[commit-bot: I haz the power, 2015-12-17 16:43:25]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1529293002/130001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1529293002/130001

[Mircea Trofin, 2015-12-17 16:43:26]

The CQ bit was unchecked by mtrofin@chromium.org

[Mircea Trofin, 2015-12-17 16:50:57]

https://codereview.chromium.org/1529293002/diff/50001/src/compiler/register-a...
File src/compiler/register-allocator.cc (right):

https://codereview.chromium.org/1529293002/diff/50001/src/compiler/register-a...
src/compiler/register-allocator.cc:3130: DCHECK_NOT_NULL(cur);
On 2015/12/17 08:51:37, Jarin wrote:
> I am wondering whether we could nopt do some sanity check for safepoint
> ordering. Could not we DCHECK safe_point_pos >= cur->Start() here? (Actually
we
> might have to handle the first range separately, i.e. something like
> DCHECK(safe_point_pos >= cur->Start() || range == cur).) What do you think?

Done.

[Mircea Trofin, 2015-12-17 18:45:51]

Description was changed from

==========
Some of the regression in the bug below was already addressed as 
part of a compile time improvement push. We got from 3 minutes down
to ~30 seconds prior to the change here.

This change further reduces the compile time down to 2 seconds, which 
is actually slightly better than the pre-splintering total execution time
of about 3 seconds.

The cause of the regression was the repeated traversal of the children
of a live range, seeking for the one covering a safe point. The fix is to
leverage the intrinsic ordering in the chain of live range children, as well
as that of the safe points.

BUG= chromium:567745
==========

to

==========
Some of the regression in the bug below was already addressed as 
part of a compile time improvement push. We got from 3 minutes down
to ~30 seconds prior to the change here.

This change further reduces the compile time down to 2 seconds, which 
is actually slightly better than the pre-splintering total execution time
of about 3 seconds.

The cause of the regression was the repeated traversal of the children
of a live range, seeking for the one covering a safe point. The fix is to
leverage the intrinsic ordering in the chain of live range children, as well
as that of the safe points.

BUG= chromium:567745
LOG=N
==========

[Mircea Trofin, 2015-12-17 18:45:55]

The CQ bit was checked by mtrofin@chromium.org

[commit-bot: I haz the power, 2015-12-17 18:45:57]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1529293002/130001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1529293002/130001

[commit-bot: I haz the power, 2015-12-17 18:47:01]

Description was changed from

==========
Some of the regression in the bug below was already addressed as 
part of a compile time improvement push. We got from 3 minutes down
to ~30 seconds prior to the change here.

This change further reduces the compile time down to 2 seconds, which 
is actually slightly better than the pre-splintering total execution time
of about 3 seconds.

The cause of the regression was the repeated traversal of the children
of a live range, seeking for the one covering a safe point. The fix is to
leverage the intrinsic ordering in the chain of live range children, as well
as that of the safe points.

BUG= chromium:567745
LOG=N
==========

to

==========
Some of the regression in the bug below was already addressed as 
part of a compile time improvement push. We got from 3 minutes down
to ~30 seconds prior to the change here.

This change further reduces the compile time down to 2 seconds, which 
is actually slightly better than the pre-splintering total execution time
of about 3 seconds.

The cause of the regression was the repeated traversal of the children
of a live range, seeking for the one covering a safe point. The fix is to
leverage the intrinsic ordering in the chain of live range children, as well
as that of the safe points.

BUG= chromium:567745
LOG=N
==========

[commit-bot: I haz the power, 2015-12-17 18:47:02]

Committed patchset #6 (id:130001)

[commit-bot: I haz the power, 2015-12-17 18:47:43]

Description was changed from

==========
Some of the regression in the bug below was already addressed as 
part of a compile time improvement push. We got from 3 minutes down
to ~30 seconds prior to the change here.

This change further reduces the compile time down to 2 seconds, which 
is actually slightly better than the pre-splintering total execution time
of about 3 seconds.

The cause of the regression was the repeated traversal of the children
of a live range, seeking for the one covering a safe point. The fix is to
leverage the intrinsic ordering in the chain of live range children, as well
as that of the safe points.

BUG= chromium:567745
LOG=N
==========

to

==========
Some of the regression in the bug below was already addressed as
part of a compile time improvement push. We got from 3 minutes down
to ~30 seconds prior to the change here.

This change further reduces the compile time down to 2 seconds, which
is actually slightly better than the pre-splintering total execution time
of about 3 seconds.

The cause of the regression was the repeated traversal of the children
of a live range, seeking for the one covering a safe point. The fix is to
leverage the intrinsic ordering in the chain of live range children, as well
as that of the safe points.

BUG= chromium:567745
LOG=N

Committed: https://crrev.com/9e8b7564f79ed95b05041bea5f320fb1ca7f2373
Cr-Commit-Position: refs/heads/master@{#32958}
==========

[commit-bot: I haz the power, 2015-12-17 18:47:45]

Patchset 6 (id:??) landed as
https://crrev.com/9e8b7564f79ed95b05041bea5f320fb1ca7f2373
Cr-Commit-Position: refs/heads/master@{#32958}