[interpreter] Bytecode register optimizer.

[interpreter] Bytecode register optimizer.

Online optimization stage for reducing redundant transfers between registers.

BUG=V8:4280
LOG=N

Committed: https://crrev.com/5e8f8d4e8c36536167e36ea242b9d17e2edeaa48
Cr-Commit-Position: refs/heads/master@{#36551}

[Yang, 2016-05-20 08:00:53]

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

[Yang, 2016-05-20 08:00:55]

Found a bunch of issues in the changed .golden files. You could argue whether
they are actual issues, but you probably should check whether Layout tests
agree.

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
File
test/cctest/interpreter/bytecode_expectations/AssignmentsInBinaryExpression.golden
(right):

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/AssignmentsInBinaryExpression.golden:55:
/*   65 S> */ B(Ldar), R(1),
How come we now have an additional position? It used to be that for something
like

function f() {
  var a = 1;
  return a;
}

In FCG we have a break at the start of the return-statement, and one at the end
of the function. In bytecode, since the return value is already in the
accumulator, we don't have the break at the start of the return-statement
anymore.

I had to fix a bunch of test cases that expected the FCG behavior.

Did this change?

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/AssignmentsInBinaryExpression.golden:85:
/*   77 S> */ B(Ldar), R(0),
Ditto. This even seems unnecessary, since Ldar R0 should be a no-op?

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
File test/cctest/interpreter/bytecode_expectations/CreateArguments.golden
(right):

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/CreateArguments.golden:44:
B(KeyedLoadIC), R(0), U8(1),
The expression position disappeared. If the load throws, we will have a
diffferent stack trace. It would be nicer to preserve the expression position at
the load.

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/CreateArguments.golden:89:
B(KeyedLoadIC), R(0), U8(1),
Ditto.

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
File test/cctest/interpreter/bytecode_expectations/ForIn.golden (right):

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/ForIn.golden:87: /*   73 S> */
B(Ldar), R(2),
How come we end up with an additional statement position? This will likely
change stepping behavior.

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
File test/cctest/interpreter/bytecode_expectations/PropertyCall.golden (right):

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/PropertyCall.golden:66: /*   19 S>
*/ B(LoadIC), R(arg0), U8(0), U8(3),
If the LoadIC throws, we would end up with a different stack trace here.

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
File test/cctest/interpreter/bytecode_expectations/PropertyLoads.golden (right):

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/PropertyLoads.golden:21: /*   16
S> */ B(LoadIC), R(arg0), U8(0), U8(1),
Ditto. LoadIC throwing would result in a different stack trace.

[oth, 2016-05-20 09:01:05]

Thanks Yang, this is super helpful. Comments inline regarding matching FCG
behavior. I'll fix the missing expression positions - the damage is being done
in the peephole optimizer.

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
File
test/cctest/interpreter/bytecode_expectations/AssignmentsInBinaryExpression.golden
(right):

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/AssignmentsInBinaryExpression.golden:55:
/*   65 S> */ B(Ldar), R(1),
On 2016/05/20 08:00:55, Yang wrote:
> How come we now have an additional position? It used to be that for something
> like
> 
> function f() {
>   var a = 1;
>   return a;
> }
> 
> In FCG we have a break at the start of the return-statement, and one at the
end
> of the function. In bytecode, since the return value is already in the
> accumulator, we don't have the break at the start of the return-statement
> anymore.
> 
> I had to fix a bunch of test cases that expected the FCG behavior.
> 
> Did this change?

Yes, it matches FCG behavior. With the register optimizer and the new peephole
optimizer we are trying much harder to preserve source positions. The code on
the LHS here has been through the peephole optimizer and has dropped some source
positions. We no longer do this.

For this specific test the output is exactly the same as having no bytecode
optimizations (no peephole and no register equivalence optimization).

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/AssignmentsInBinaryExpression.golden:85:
/*   77 S> */ B(Ldar), R(0),
On 2016/05/20 08:00:55, Yang wrote:
> Ditto. This even seems unnecessary, since Ldar R0 should be a no-op?

The question is whether it's better to match FCG or to be microscopically
faster. There is a CL that peephole optimizes the Mov R0, R1; Star R0 here to
Ldar R0; Star R1.

Overall, the savings from the register optimization are pretty good:

https://docs.google.com/spreadsheets/d/1lKozV5gf9zUmsz8FrJgOzscDDoReZJxaZqfRS...

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
File test/cctest/interpreter/bytecode_expectations/CreateArguments.golden
(right):

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/CreateArguments.golden:44:
B(KeyedLoadIC), R(0), U8(1),
On 2016/05/20 08:00:55, Yang wrote:
> The expression position disappeared. If the load throws, we will have a
> diffferent stack trace. It would be nicer to preserve the expression position
at
> the load.

Ack. Need to fix this. For the debugging experience, perhaps we emit a nop here
with the statement and ensure we keep the expression on the load.

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
File test/cctest/interpreter/bytecode_expectations/ForIn.golden (right):

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/ForIn.golden:87: /*   73 S> */
B(Ldar), R(2),
On 2016/05/20 08:00:55, Yang wrote:
> How come we end up with an additional statement position? This will likely
> change stepping behavior.

The older code has peephole optimized out the statement position that is now
visible.

The completely non-optimized code looks like:

   20 E> 0x13f6a12d62b4 @    0 : 5e                StackCheck 
   42 S> 0x13f6a12d62b5 @    1 : 09 00             LdaConstant [0]
   42 E> 0x13f6a12d62b7 @    3 : 17 f9             Star r1
   68 S> 0x13f6a12d62b9 @    5 : 16 f9             Ldar r1
         0x13f6a12d62bb @    7 : 56 28             JumpIfUndefined [40]
(0x13f6a12d62e3 @ 47)
         0x13f6a12d62bd @    9 : 54 26             JumpIfNull [38]
(0x13f6a12d62e3 @ 47)
         0x13f6a12d62bf @   11 : 42                ToObject 
         0x13f6a12d62c0 @   12 : 17 f7             Star r3
         0x13f6a12d62c2 @   14 : 5a f6             ForInPrepare r4-r6
         0x13f6a12d62c4 @   16 : 02                LdaZero 
         0x13f6a12d62c5 @   17 : 17 f3             Star r7
   63 S> 0x13f6a12d62c7 @   19 : 5b f3 f4          ForInDone r7, r6
         0x13f6a12d62ca @   22 : 50 19             JumpIfToBooleanTrue [25]
(0x13f6a12d62e3 @ 47)
         0x13f6a12d62cc @   24 : 5c f7 f3 f6 01    ForInNext r3, r7, r4-r5, [1]
         0x13f6a12d62d1 @   29 : 56 0c             JumpIfUndefined [12]
(0x13f6a12d62dd @ 41)
         0x13f6a12d62d3 @   31 : 17 fa             Star r0
   54 E> 0x13f6a12d62d5 @   33 : 5e                StackCheck 
         0x13f6a12d62d6 @   34 : 16 fa             Ldar r0
         0x13f6a12d62d8 @   36 : 17 f8             Star r2
   73 S> 0x13f6a12d62da @   38 : 16 f8             Ldar r2
   85 S> 0x13f6a12d62dc @   40 : 61                Return 
         0x13f6a12d62dd @   41 : 5d f3             ForInStep r7
         0x13f6a12d62df @   43 : 17 f3             Star r7
         0x13f6a12d62e1 @   45 : 4a e6             Jump [-26] (0x13f6a12d62c7 @
19)
         0x13f6a12d62e3 @   47 : 04                LdaUndefined 
   85 S> 0x13f6a12d62e4 @   48 : 61                Return

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
File test/cctest/interpreter/bytecode_expectations/PropertyCall.golden (right):

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/PropertyCall.golden:66: /*   19 S>
*/ B(LoadIC), R(arg0), U8(0), U8(3),
On 2016/05/20 08:00:55, Yang wrote:
> If the LoadIC throws, we would end up with a different stack trace here.

Yep, must fix.

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
File test/cctest/interpreter/bytecode_expectations/PropertyLoads.golden (right):

https://codereview.chromium.org/1997653002/diff/80001/test/cctest/interpreter...
test/cctest/interpreter/bytecode_expectations/PropertyLoads.golden:21: /*   16
S> */ B(LoadIC), R(arg0), U8(0), U8(1),
On 2016/05/20 08:00:55, Yang wrote:
> Ditto. LoadIC throwing would result in a different stack trace.

Yep.

[oth, 2016-05-25 14:18:49]

oth@chromium.org changed reviewers:
+ mstarzinger@chromium.org, rmcilroy@chromium.org

[oth, 2016-05-25 14:18:51]

Ross, PTAL.

Michi/Yang, if you are interested, your comments will help.

Per the meeting today, I'm putting this out without tests to get the
conversation going. 

Suggestions for tests welcome. We'll have a source position comparer. This may
take a couple of iterations to cover the rules we have for source positions and
mutations of bytecode due to the peephole optimizer and REO.

Existing tests are super fragile with respect to minor changes in REO behaviour
though this is not a long term testing strategy.

https://codereview.chromium.org/1997653002/diff/180001/test/cctest/interprete...
File test/cctest/interpreter/bytecode_expectations/DoExpression.golden (right):

https://codereview.chromium.org/1997653002/diff/180001/test/cctest/interprete...
test/cctest/interpreter/bytecode_expectations/DoExpression.golden:20: /*   42 S>
*/ B(Nop),
TODO(oth): Look at why this Nop is not peephole optimized away.

[rmcilroy, 2016-05-26 10:24:54]

Very nice, I like it! Some nits but overall I think it's looking good.

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

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-allocator.h:18: class
TemporaryRegisterObserver;
nit - move into block above

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

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:1: // Copyright 2015 the V8
project authors. All rights reserved.
2016

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:31: RegisterInfo*
GetMaterializationCandidate();
I think these functions deserve a comment, particularly whether the current
RegisterInfo is expected to be materialized or not before they are called.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:44: int equivalence_id_;
This should probably be an unsigned long, and maybe we should do the
incrementing in a function with a CHECK if it wraps around (I agree this would
be incredibly unlikely, but it would be easier to spot in crash reports rather
than weird inconstancies in equivalency if it did ever happen).

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:70: bool
BytecodeRegisterOptimizer::RegisterInfo::IsOnlyEquivalent() const {
This name is a bit confusing to me, how about IsUnique()?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:107:
BytecodeRegisterOptimizer::RegisterInfo::GetMaterializationCandidate() {
It is difficult to figure out what this function does from the name. It's a bit
of a mouthfull, but how about something like
GetEquivalentMaterializationCandidateIfRequired()

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:110: Register best_reg;
unused

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:129: :
accumulator_(Register::bytecode_array()),
We don't use bytecode_array in bytecode, but I wonder if we might in the future.
Could we instead hide this in the slot take by the caller's PC address - this is
something we should never be able to touch in the bytecode (since it would be
untagged). We could just call it Register::virtual_accumulator() or similar and
have a comment on the method specifying that it should never be used in real
bytecode. WDYT?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:144: map_index_offset_ =
-accumulator_.index();
Does this side ever get hit? We should always have at least one parameter (the
receiver) for JS functions.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:150:
static_cast<size_t>(fixed_register_count));
Isn't fixed_register_count the same (or less than) temporary_base_? Could we
just use temporary_base_ here instead?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:182:
reg_info->set_equivalence_id(equivalence_id_++);
nit - move the setting of equivalence_id into RemoveFromEquivalenceSet

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:214: // current source position.
I'm not sure what this adds anything beyond the two paragraphs below it.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:223: // position is not lost and
being attachd to a Nop is fine as the
attached

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:228:
EmitNopTakingSourcePosition(node);
nit - move into DoLdar / DoStar / DoMov.

Optional - you could emit the original bytecode for cases where the move is
observable, and only emit the Nop with source position if you elide the move.
This might lead to less work for the peephole optimizer and might make source
positions for observable moves more constant, but I'm not sure.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:254: return;
nit - just do the FlushState here and fall-through to PrepareOperands /
WriteToNextStage ?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:314: RegisterInfo* result =
info->GetMaterializedEquivalent();
Maybe just add an option to GetMaterializedEquivalent to skip the accumulator
(potentially returning nullptr if only the accumulator is materialized), rather
than doing the double call to GetMaterializedEquivalent here.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:354:
OutputRegisterTransfer(materialized_info, output_info);
output_info should be set_materialized(true) shouldn't it? Maybe just move the
set_materialized(true) into OutputRegisterTransfer.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:403: RegisterInfo* reg_info =
GetOrCreateRegisterInfo(reg);
Reginfo should be create here shouldn't it? Just GetRegisterInfo ?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:444: if (operand_types[i + 1] ==
OperandType::kRegCount) {
This is repeated in a bunch of places (e.g., bytecode-array-writer.cc) - could
we make a common helper for it. Also - is it safe to access "operand_types[i +
1]" - what if we are at the last operand (same goes for existing implementation
in bytecode-array-writer.cc).

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:456: Register equivalent =
PrepareRegisterInputOperand(reg);
PrepareRegisterInputOperand does something different from all the other
PrepareXXX in that it gives back an equivalent register.  How about making
PrepareRegisterInputOperand do the work in this block of the if branch, and
adding a new function - GetEquivalentRegisterInputOperand(), to do the work
currently done by PrepareRegisterInputOperand ?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:515: return (index <
register_map_.size()) ? register_map_[index] : nullptr;
it looks like we always depend on this returning non-nullptr. Could you just
make the check a DCHECK instead?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
File src/interpreter/bytecode-register-optimizer.h (right):

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.h:1: // Copyright 2015 the V8
project authors. All rights reserved.
2016

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.h:51: // associated with |Nop|.
/s/|Nop|/|node| ?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.h:115: ZoneVector<RegisterInfo*>
register_map_;
This is not a map, how about register_infos_ (if so, also rename
map_index_offset_, GetMapIndex and RegisterFromMapIndex)

[oth, 2016-05-26 21:26:51]

Thanks Ross. I've attempted to incorporate, or respond, to everything in the
comments.

There's a nit in one of the tests following the changes here. I need to look
into how that's happened.

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

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-allocator.h:18: class
TemporaryRegisterObserver;
On 2016/05/26 10:24:52, rmcilroy wrote:
> nit - move into block above

Done.

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

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:1: // Copyright 2015 the V8
project authors. All rights reserved.
On 2016/05/26 10:24:53, rmcilroy wrote:
> 2016

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:31: RegisterInfo*
GetMaterializationCandidate();
On 2016/05/26 10:24:52, rmcilroy wrote:
> I think these functions deserve a comment, particularly whether the current
> RegisterInfo is expected to be materialized or not before they are called.

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:44: int equivalence_id_;
On 2016/05/26 10:24:53, rmcilroy wrote:
> This should probably be an unsigned long, and maybe we should do the
> incrementing in a function with a CHECK if it wraps around (I agree this would
> be incredibly unlikely, but it would be easier to spot in crash reports rather
> than weird inconstancies in equivalency if it did ever happen).

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:70: bool
BytecodeRegisterOptimizer::RegisterInfo::IsOnlyEquivalent() const {
On 2016/05/26 10:24:53, rmcilroy wrote:
> This name is a bit confusing to me, how about IsUnique()?

Agreed. For readability, perhaps IsOnlyMemberOfEquivalenceSet() works better
yet?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:107:
BytecodeRegisterOptimizer::RegisterInfo::GetMaterializationCandidate() {
On 2016/05/26 10:24:53, rmcilroy wrote:
> It is difficult to figure out what this function does from the name. It's a
bit
> of a mouthfull, but how about something like
> GetEquivalentMaterializationCandidateIfRequired()

GetEquivalentToMaterialize()?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:110: Register best_reg;
On 2016/05/26 10:24:53, rmcilroy wrote:
> unused

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:129: :
accumulator_(Register::bytecode_array()),
On 2016/05/26 10:24:52, rmcilroy wrote:
> We don't use bytecode_array in bytecode, but I wonder if we might in the
future.
> Could we instead hide this in the slot take by the caller's PC address - this
is
> something we should never be able to touch in the bytecode (since it would be
> untagged). We could just call it Register::virtual_accumulator() or similar
and
> have a comment on the method specifying that it should never be used in real
> bytecode. WDYT?

Done.

It was implemented in this way to keep the specific value internal to the
register optimizer.
A bunch of checks are elided because the accumulator sits in this space. If
anyone moves
the definition about it should break.

Untagged value seems reasonable. The future argument I don't like much - it's a
quick fix and I'd be wary about exposing the bytecode_array in bytecode too.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:144: map_index_offset_ =
-accumulator_.index();
On 2016/05/26 10:24:53, rmcilroy wrote:
> Does this side ever get hit? We should always have at least one parameter (the
> receiver) for JS functions.

Yes, it gets hit in tests that craft bytecode.

There is a todo here as I may not get to fix this before half-term break.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:150:
static_cast<size_t>(fixed_register_count));
On 2016/05/26 10:24:53, rmcilroy wrote:
> Isn't fixed_register_count the same (or less than) temporary_base_? Could we
> just use temporary_base_ here instead?

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:182:
reg_info->set_equivalence_id(equivalence_id_++);
On 2016/05/26 10:24:53, rmcilroy wrote:
> nit - move the setting of equivalence_id into RemoveFromEquivalenceSet

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:214: // current source position.
On 2016/05/26 10:24:53, rmcilroy wrote:
> I'm not sure what this adds anything beyond the two paragraphs below it.

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:223: // position is not lost and
being attachd to a Nop is fine as the
On 2016/05/26 10:24:53, rmcilroy wrote:
> attached

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:228:
EmitNopTakingSourcePosition(node);
On 2016/05/26 10:24:53, rmcilroy wrote:
> nit - move into DoLdar / DoStar / DoMov.
> 
> Optional - you could emit the original bytecode for cases where the move is
> observable, and only emit the Nop with source position if you elide the move.
> This might lead to less work for the peephole optimizer and might make source
> positions for observable moves more constant, but I'm not sure. 

Done. Tried the experiment with the source positions and it looks okay on my
devbox. We can re-evaluate if necessary in future.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:254: return;
On 2016/05/26 10:24:53, rmcilroy wrote:
> nit - just do the FlushState here and fall-through to PrepareOperands /
> WriteToNextStage ? 

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:314: RegisterInfo* result =
info->GetMaterializedEquivalent();
On 2016/05/26 10:24:53, rmcilroy wrote:
> Maybe just add an option to GetMaterializedEquivalent to skip the accumulator
> (potentially returning nullptr if only the accumulator is materialized),
rather
> than doing the double call to GetMaterializedEquivalent here.

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:354:
OutputRegisterTransfer(materialized_info, output_info);
On 2016/05/26 10:24:53, rmcilroy wrote:
> output_info should be set_materialized(true) shouldn't it? Maybe just move the
> set_materialized(true) into OutputRegisterTransfer.

Re-worked hopefully easier to reason about now ?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:403: RegisterInfo* reg_info =
GetOrCreateRegisterInfo(reg);
On 2016/05/26 10:24:53, rmcilroy wrote:
> Reginfo should be create here shouldn't it? Just GetRegisterInfo ?

Comment added. The create case is for the first time temporary register is used
as an operand. We sometimes end up over-allocating temporaries so prefer to do
the allocation here rather than have an extra notification from the temporary
register allocator for allocations.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:444: if (operand_types[i + 1] ==
OperandType::kRegCount) {
On 2016/05/26 10:24:53, rmcilroy wrote:
> This is repeated in a bunch of places (e.g., bytecode-array-writer.cc) - could
> we make a common helper for it. Also - is it safe to access "operand_types[i +
> 1]" - what if we are at the last operand (same goes for existing
implementation
> in bytecode-array-writer.cc).

This is a little bit raw. If it's a helper, it'll have to be inline.

But, yes, it is safe and documented as such on Bytecodes::GetOperandTypes().

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:456: Register equivalent =
PrepareRegisterInputOperand(reg);
On 2016/05/26 10:24:53, rmcilroy wrote:
> PrepareRegisterInputOperand does something different from all the other
> PrepareXXX in that it gives back an equivalent register.  How about making
> PrepareRegisterInputOperand do the work in this block of the if branch, and
> adding a new function - GetEquivalentRegisterInputOperand(), to do the work
> currently done by PrepareRegisterInputOperand ?

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:515: return (index <
register_map_.size()) ? register_map_[index] : nullptr;
On 2016/05/26 10:24:53, rmcilroy wrote:
> it looks like we always depend on this returning non-nullptr. Could you just
> make the check a DCHECK instead?

This can be called from TemporaryRegisterFreeEvent() and will have the value
nullptr if the temporary has not been presented to the optimizer in the bytecode
stream. There are situations in the bytecode generator where temporaries are
over-allocated.

In other call sites, if nullptr is returned the crash will be very explicit
about the failure. I'd lean to just having a common function for this. WDYT?

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
File src/interpreter/bytecode-register-optimizer.h (right):

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.h:1: // Copyright 2015 the V8
project authors. All rights reserved.
On 2016/05/26 10:24:53, rmcilroy wrote:
> 2016

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.h:51: // associated with |Nop|.
On 2016/05/26 10:24:54, rmcilroy wrote:
> /s/|Nop|/|node| ?

Done.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.h:115: ZoneVector<RegisterInfo*>
register_map_;
On 2016/05/26 10:24:53, rmcilroy wrote:
> This is not a map, how about register_infos_ (if so, also rename
> map_index_offset_, GetMapIndex and RegisterFromMapIndex)

Done.

https://codereview.chromium.org/1997653002/diff/240001/test/cctest/interprete...
File test/cctest/interpreter/bytecode_expectations/IfConditions.golden (right):

https://codereview.chromium.org/1997653002/diff/240001/test/cctest/interprete...
test/cctest/interpreter/bytecode_expectations/IfConditions.golden:279: /*   74
S> */ B(Ldar), R(1),
TODO(oth): review. This would be wrong if the debugger live edited one of these
variables. Changed following patch set 11.

[rmcilroy, 2016-05-27 09:18:58]

It would be nice to have some simple unittest of the register optimizer before
landing (cctests for source position can wait for a followup CL). Otherwise LGTM
once you figure out your TODO comment in the golden file.

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

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:70: bool
BytecodeRegisterOptimizer::RegisterInfo::IsOnlyEquivalent() const {
On 2016/05/26 21:26:51, oth wrote:
> On 2016/05/26 10:24:53, rmcilroy wrote:
> > This name is a bit confusing to me, how about IsUnique()?
> 
> Agreed. For readability, perhaps IsOnlyMemberOfEquivalenceSet() works better
> yet?

SGTM, thanks.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:107:
BytecodeRegisterOptimizer::RegisterInfo::GetMaterializationCandidate() {
On 2016/05/26 21:26:50, oth wrote:
> On 2016/05/26 10:24:53, rmcilroy wrote:
> > It is difficult to figure out what this function does from the name. It's a
> bit
> > of a mouthfull, but how about something like
> > GetEquivalentMaterializationCandidateIfRequired()
> 
> GetEquivalentToMaterialize()?

SGTM, thanks.

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:144: map_index_offset_ =
-accumulator_.index();
On 2016/05/26 21:26:50, oth wrote:
> On 2016/05/26 10:24:53, rmcilroy wrote:
> > Does this side ever get hit? We should always have at least one parameter
(the
> > receiver) for JS functions.
> 
> Yes, it gets hit in tests that craft bytecode.
> 
> There is a todo here as I may not get to fix this before half-term break.

SG, thanks

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:354:
OutputRegisterTransfer(materialized_info, output_info);
On 2016/05/26 21:26:51, oth wrote:
> On 2016/05/26 10:24:53, rmcilroy wrote:
> > output_info should be set_materialized(true) shouldn't it? Maybe just move
the
> > set_materialized(true) into OutputRegisterTransfer.
> 
> Re-worked hopefully easier to reason about now ?
> 

Looks good, thanks

https://codereview.chromium.org/1997653002/diff/200001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:515: return (index <
register_map_.size()) ? register_map_[index] : nullptr;
On 2016/05/26 21:26:50, oth wrote:
> On 2016/05/26 10:24:53, rmcilroy wrote:
> > it looks like we always depend on this returning non-nullptr. Could you just
> > make the check a DCHECK instead?
> 
> This can be called from TemporaryRegisterFreeEvent() and will have the value
> nullptr if the temporary has not been presented to the optimizer in the
bytecode
> stream. There are situations in the bytecode generator where temporaries are
> over-allocated.
> 
> In other call sites, if nullptr is returned the crash will be very explicit
> about the failure. I'd lean to just having a common function for this. WDYT?

OK sounds good, thanks.

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

https://codereview.chromium.org/1997653002/diff/240001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.cc:574: void
BytecodeRegisterOptimizer::GrowRegisterMap(Register reg) {
GrowRegisterInfoTable

https://codereview.chromium.org/1997653002/diff/240001/src/interpreter/byteco...
File src/interpreter/bytecode-register-optimizer.h (right):

https://codereview.chromium.org/1997653002/diff/240001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.h:115: Register
RegisterFromRegisterInfoTableIndex(size_t index) const {
nit - RegisterFromTableIndex ?

https://codereview.chromium.org/1997653002/diff/240001/src/interpreter/byteco...
src/interpreter/bytecode-register-optimizer.h:136: int equivalence_id_;
uint32_t (given kInvalidEquivalenceId is uint32_t).

[oth, 2016-05-27 15:23:41]

Michi/Yang, we're going to try landing this to start collecting impact data.

If you have time to look at the CL, comments still appreciated and will be acted
upon.

There are some basic tests here with more to follow.

Thanks
Orion

[oth, 2016-05-27 15:24:26]

The CQ bit was checked by oth@chromium.org

[oth, 2016-05-27 15:24:27]

The patchset sent to the CQ was uploaded after l-g-t-m from
rmcilroy@chromium.org
Link to the patchset: https://codereview.chromium.org/1997653002/#ps400001
(title: "Decouple a test from implementation.")

[commit-bot: I haz the power, 2016-05-27 15:24:31]

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

[commit-bot: I haz the power, 2016-05-27 15:57:47]

Committed patchset #21 (id:400001)

[commit-bot: I haz the power, 2016-05-27 15:59:26]

Description was changed from

==========
[interpreter] Bytecode register optimizer.

Online optimization stage for reducing redundant transfers between registers.

BUG=V8:4280
LOG=N
==========

to

==========
[interpreter] Bytecode register optimizer.

Online optimization stage for reducing redundant transfers between registers.

BUG=V8:4280
LOG=N

Committed: https://crrev.com/5e8f8d4e8c36536167e36ea242b9d17e2edeaa48
Cr-Commit-Position: refs/heads/master@{#36551}
==========

[commit-bot: I haz the power, 2016-05-27 15:59:28]

Patchset 21 (id:??) landed as
https://crrev.com/5e8f8d4e8c36536167e36ea242b9d17e2edeaa48
Cr-Commit-Position: refs/heads/master@{#36551}