[Interpreter] Replace BytecodeRegisterAllocator with a simple bump pointer.

[Interpreter] Replace BytecodeRegisterAllocator with a simple bump pointer.

There are only a few occasions where we allocate a register in an outer
expression allocation scope, which makes the costly free-list approach
of the BytecodeRegisterAllocator unecessary. This CL replaces all
occurrences with moves to the accumulator and stores to a register
allocated in the correct scope. By doing this, we can simplify the
BytecodeRegisterAllocator to be a simple bump-pointer allocator
with registers released in the same order as allocated.

The following changes are also made:
 - Make BytecodeRegisterOptimizer able to use registers which have been
   unallocated, but not yet reused
 - Remove RegisterExpressionResultScope and rename
   AccumulatorExpressionResultScope to ValueExpressionResultScope
 - Introduce RegisterList to represent consecutive register
   allocations, and use this for operands to call bytecodes.

By avoiding the free-list handling, this gives another couple of
percent on CodeLoad.

BUG=v8:4280
Committed: https://crrev.com/27fe988b85e9b0b77eb5c376d4bdd1350dfc3e17
Cr-Commit-Position: refs/heads/master@{#39905}

[rmcilroy, 2016-09-26 10:12:01]

The CQ bit was checked by rmcilroy@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-09-26 10:12:10]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-09-26 10:13:58]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-09-26 10:13:59]

Dry run: Try jobs failed on following builders:
  v8_linux64_avx2_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_avx2_rel_ng/buil...)
  v8_linux64_gyp_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_gyp_rel_ng/build...)
  v8_linux_arm_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_arm_rel_ng/builds/...)
  v8_linux_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_rel_ng/builds/13396)
  v8_presubmit on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_presubmit/builds/24959)

[rmcilroy, 2016-09-26 10:20:13]

Description was changed from

==========
[Interpreter] Replace BytecodeRegisterAllocator with a simple bump pointer.

There are only a few occasions where we allocate a register in an outer
expression allocation scope, which makes the costly free-list approach
of the BytecodeRegisterAllocator unecessary. This CL replaces all
occurrences with moves to the accumulator and stores to a register
allocated in the correct scope. By doing this, we can simplify the
BytecodeRegisterAllocator to be a simple bump-pointer allocator
with registers released in the same order as allocated.

The following changes are also made:
 - Make BytecodeRegisterOptimizer able to use registers which have been
   unallocated, but not yet reused
 - Remove RegisterExpressionResultScope and rename
   AccumulatorExpressionResultScope to ValueExpressionResultScope
 - Introduce RegisterList to represent consecutive register
   allocations, and use this for operands to call bytecodes.

By avoiding the free-list handling, this gives another couple of
percent on CodeLoad.

BUG=v8:4280

[Interpreter] Optimize BytecodeArrayBuilder and BytecodeArrayWriter.


[Test] Fix AsmJsUnOpsCheckOrigin off-stack access.
==========

to

==========
[Interpreter] Replace BytecodeRegisterAllocator with a simple bump pointer.

There are only a few occasions where we allocate a register in an outer
expression allocation scope, which makes the costly free-list approach
of the BytecodeRegisterAllocator unecessary. This CL replaces all
occurrences with moves to the accumulator and stores to a register
allocated in the correct scope. By doing this, we can simplify the
BytecodeRegisterAllocator to be a simple bump-pointer allocator
with registers released in the same order as allocated.

The following changes are also made:
 - Make BytecodeRegisterOptimizer able to use registers which have been
   unallocated, but not yet reused
 - Remove RegisterExpressionResultScope and rename
   AccumulatorExpressionResultScope to ValueExpressionResultScope
 - Introduce RegisterList to represent consecutive register
   allocations, and use this for operands to call bytecodes.

By avoiding the free-list handling, this gives another couple of
percent on CodeLoad.

BUG=v8:4280
==========

[rmcilroy, 2016-09-26 10:40:27]

Patchset #1 (id:1) has been deleted

[rmcilroy, 2016-09-26 10:40:33]

The CQ bit was checked by rmcilroy@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-09-26 10:40:44]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-09-26 10:43:34]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-09-26 10:43:34]

Dry run: Try jobs failed on following builders:
  v8_linux64_gyp_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_gyp_rel_ng/build...)
  v8_linux_arm64_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_arm64_rel_ng/build...)
  v8_linux_arm_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_arm_rel_ng/builds/...)
  v8_linux_dbg_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_dbg_ng/builds/13436)
  v8_linux_gcc_compile_rel on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_gcc_compile_rel/bu...)
  v8_linux_nodcheck_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_nodcheck_rel_ng/bu...)

[rmcilroy, 2016-09-26 10:59:54]

Patchset #1 (id:20001) has been deleted

[rmcilroy, 2016-09-26 11:00:03]

The CQ bit was checked by rmcilroy@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-09-26 11:00:14]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-09-26 11:03:32]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-09-26 11:03:33]

Dry run: Try jobs failed on following builders:
  v8_win_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_win_rel_ng/builds/15013)

[rmcilroy, 2016-09-26 20:32:56]

The CQ bit was checked by rmcilroy@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-09-26 20:33:03]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-09-26 20:38:55]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-09-26 20:38:56]

Dry run: Try jobs failed on following builders:
  v8_linux64_gyp_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_gyp_rel_ng/build...)

[rmcilroy, 2016-09-26 20:44:40]

The CQ bit was checked by rmcilroy@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-09-26 20:44:42]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-09-26 20:50:13]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-09-26 20:50:14]

Dry run: Try jobs failed on following builders:
  v8_win_compile_dbg on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_win_compile_dbg/builds/2...)
  v8_win_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_win_rel_ng/builds/15073)

[rmcilroy, 2016-09-26 21:23:52]

Patchset #3 (id:80001) has been deleted

[rmcilroy, 2016-09-26 21:23:58]

The CQ bit was checked by rmcilroy@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-09-26 21:24:02]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-09-26 21:31:32]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-09-26 21:31:33]

Dry run: Try jobs failed on following builders:
  v8_linux64_gyp_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_gyp_rel_ng/build...)

[rmcilroy, 2016-09-26 22:17:26]

Patchset #3 (id:100001) has been deleted

[rmcilroy, 2016-09-26 22:17:33]

The CQ bit was checked by rmcilroy@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-09-26 22:17:41]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-09-26 22:44:01]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-09-26 22:44:02]

Dry run: This issue passed the CQ dry run.

[rmcilroy, 2016-09-27 07:54:23]

The CQ bit was checked by rmcilroy@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-09-27 07:54:32]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[rmcilroy, 2016-09-27 07:55:54]

rmcilroy@chromium.org changed reviewers:
+ leszeks@chromium.org, mythria@chromium.org

[rmcilroy, 2016-09-27 07:55:55]

Appologies about another large CL, but the refactorings seemed worth it after
the change in the register allocator. PTAL.

[rmcilroy, 2016-09-27 07:56:03]

Appologies about another large CL, but the refactorings seemed worth it after
the change in the register allocator. PTAL.

[commit-bot: I haz the power, 2016-09-27 08:25:07]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-09-27 08:25:09]

Dry run: This issue passed the CQ dry run.

[mythria, 2016-09-28 11:45:30]

Nice, we actually reduce the frame sizes in a couple of tests. I am not sure I
understand the bytecode-register-optimizer fully. I added two comments in there.
apart from that lgtm.

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
File src/interpreter/bytecode-array-builder.h (right):

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-array-builder.h:185: // |callable|. The arguments
should be in |args|, with the receiver should in
remove should (with the receiver should in -> with the receiver in).

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
File src/interpreter/bytecode-register-optimizer.cc (right):

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:163: if (visitor->materialized())
{
I am not sure I understand it fully, but what would happen if this was a
unallocated register that was materialized. We can reuse it and there will be a
register create event which will just move it out of this equivalence set. There
may be allocated registers which should have got materialized in this call, but
this check might prevent it. Should we have visitor->materialized() &&
visitor->allocated() here?

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:656: }
If I understand correctly, the idea here is that, we retain an unallocated
register in the equivalent set and hope to use its value. Is that the reason we
don't remove it from the existing equivalence set. I also don't understand why
we don't need to materialize some other register in that set. I mean why don't
we need CreateMaterializedEquivalent(info) here?

[Leszek Swirski, 2016-09-28 15:27:25]

lgtm aside from some nits

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
File src/interpreter/bytecode-generator.cc (right):

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-generator.cc:2226: // avoid DCHECK fails assert
accumulator has been set.
is this comment still valid?

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
File src/interpreter/bytecode-register-allocator.h (right):

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-register-allocator.h:16: class
BytecodeRegisterAllocator;
Is this forward declaration useful?

[rmcilroy, 2016-09-30 08:37:54]

Thanks for the reviews, all addressed.

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
File src/interpreter/bytecode-array-builder.h (right):

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-array-builder.h:185: // |callable|. The arguments
should be in |args|, with the receiver should in
On 2016/09/28 11:45:29, mythria wrote:
> remove should (with the receiver should in -> with the receiver in).

Done.

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
File src/interpreter/bytecode-generator.cc (right):

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-generator.cc:2226: // avoid DCHECK fails assert
accumulator has been set.
On 2016/09/28 15:27:25, Leszek Swirski wrote:
> is this comment still valid?

Not any more, good catch.

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
File src/interpreter/bytecode-register-allocator.h (right):

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-register-allocator.h:16: class
BytecodeRegisterAllocator;
On 2016/09/28 15:27:25, Leszek Swirski wrote:
> Is this forward declaration useful?

Nope, removed.

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
File src/interpreter/bytecode-register-optimizer.cc (right):

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:163: if (visitor->materialized())
{
On 2016/09/28 11:45:29, mythria wrote:
> I am not sure I understand it fully, but what would happen if this was a
> unallocated register that was materialized. We can reuse it and there will be
a
> register create event which will just move it out of this equivalence set.
There
> may be allocated registers which should have got materialized in this call,
but
> this check might prevent it. Should we have visitor->materialized() &&
> visitor->allocated() here? 

As discussed offline, yes we can reuse it even if unallocated, since nothing has
overridden it yet.

https://codereview.chromium.org/2369873002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:656: }
On 2016/09/28 11:45:29, mythria wrote:
> If I understand correctly, the idea here is that, we retain an unallocated
> register in the equivalent set and hope to use its value. Is that the reason
we
> don't remove it from the existing equivalence set. I also don't understand why
> we don't need to materialize some other register in that set. I mean why don't
> we need CreateMaterializedEquivalent(info) here?

As discussed offline, we don't need to materialize another register because that
will be done whenever the register get's used again after being reallocated, and
the value is fine in this register until then.

[rmcilroy, 2016-09-30 08:38:03]

The CQ bit was checked by rmcilroy@chromium.org

[rmcilroy, 2016-09-30 08:38:03]

The patchset sent to the CQ was uploaded after l-g-t-m from
mythria@chromium.org, leszeks@chromium.org
Link to the patchset: https://codereview.chromium.org/2369873002/#ps180001
(title: "Rebase")

[commit-bot: I haz the power, 2016-09-30 08:38:15]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-09-30 09:03:02]

Description was changed from

==========
[Interpreter] Replace BytecodeRegisterAllocator with a simple bump pointer.

There are only a few occasions where we allocate a register in an outer
expression allocation scope, which makes the costly free-list approach
of the BytecodeRegisterAllocator unecessary. This CL replaces all
occurrences with moves to the accumulator and stores to a register
allocated in the correct scope. By doing this, we can simplify the
BytecodeRegisterAllocator to be a simple bump-pointer allocator
with registers released in the same order as allocated.

The following changes are also made:
 - Make BytecodeRegisterOptimizer able to use registers which have been
   unallocated, but not yet reused
 - Remove RegisterExpressionResultScope and rename
   AccumulatorExpressionResultScope to ValueExpressionResultScope
 - Introduce RegisterList to represent consecutive register
   allocations, and use this for operands to call bytecodes.

By avoiding the free-list handling, this gives another couple of
percent on CodeLoad.

BUG=v8:4280
==========

to

==========
[Interpreter] Replace BytecodeRegisterAllocator with a simple bump pointer.

There are only a few occasions where we allocate a register in an outer
expression allocation scope, which makes the costly free-list approach
of the BytecodeRegisterAllocator unecessary. This CL replaces all
occurrences with moves to the accumulator and stores to a register
allocated in the correct scope. By doing this, we can simplify the
BytecodeRegisterAllocator to be a simple bump-pointer allocator
with registers released in the same order as allocated.

The following changes are also made:
 - Make BytecodeRegisterOptimizer able to use registers which have been
   unallocated, but not yet reused
 - Remove RegisterExpressionResultScope and rename
   AccumulatorExpressionResultScope to ValueExpressionResultScope
 - Introduce RegisterList to represent consecutive register
   allocations, and use this for operands to call bytecodes.

By avoiding the free-list handling, this gives another couple of
percent on CodeLoad.

BUG=v8:4280
==========

[commit-bot: I haz the power, 2016-09-30 09:03:04]

Committed patchset #6 (id:180001)

[commit-bot: I haz the power, 2016-09-30 09:03:34]

Description was changed from

==========
[Interpreter] Replace BytecodeRegisterAllocator with a simple bump pointer.

There are only a few occasions where we allocate a register in an outer
expression allocation scope, which makes the costly free-list approach
of the BytecodeRegisterAllocator unecessary. This CL replaces all
occurrences with moves to the accumulator and stores to a register
allocated in the correct scope. By doing this, we can simplify the
BytecodeRegisterAllocator to be a simple bump-pointer allocator
with registers released in the same order as allocated.

The following changes are also made:
 - Make BytecodeRegisterOptimizer able to use registers which have been
   unallocated, but not yet reused
 - Remove RegisterExpressionResultScope and rename
   AccumulatorExpressionResultScope to ValueExpressionResultScope
 - Introduce RegisterList to represent consecutive register
   allocations, and use this for operands to call bytecodes.

By avoiding the free-list handling, this gives another couple of
percent on CodeLoad.

BUG=v8:4280
==========

to

==========
[Interpreter] Replace BytecodeRegisterAllocator with a simple bump pointer.

There are only a few occasions where we allocate a register in an outer
expression allocation scope, which makes the costly free-list approach
of the BytecodeRegisterAllocator unecessary. This CL replaces all
occurrences with moves to the accumulator and stores to a register
allocated in the correct scope. By doing this, we can simplify the
BytecodeRegisterAllocator to be a simple bump-pointer allocator
with registers released in the same order as allocated.

The following changes are also made:
 - Make BytecodeRegisterOptimizer able to use registers which have been
   unallocated, but not yet reused
 - Remove RegisterExpressionResultScope and rename
   AccumulatorExpressionResultScope to ValueExpressionResultScope
 - Introduce RegisterList to represent consecutive register
   allocations, and use this for operands to call bytecodes.

By avoiding the free-list handling, this gives another couple of
percent on CodeLoad.

BUG=v8:4280

Committed: https://crrev.com/27fe988b85e9b0b77eb5c376d4bdd1350dfc3e17
Cr-Commit-Position: refs/heads/master@{#39905}
==========

[commit-bot: I haz the power, 2016-09-30 09:03:35]

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