[Interpreter] Local flow control in the bytecode graph builder.

[Interpreter] Local flow control in the bytecode graph builder.

This change adds support for local control flow when building graphs
from bytecode. The change ensures loop emitted from the bytecode
generator are in natural order so the only back branches are for loops.

BUG=v8:4280
LOG=N

Committed: https://crrev.com/d3168202f52d78cbcfe755d17884bbafa6cc09b5
Cr-Commit-Position: refs/heads/master@{#32911}

[oth, 2015-12-07 16:42:32]

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

[oth, 2015-12-07 16:42:33]

rmcilroy@chromium.org: PTAL, thanks!

mstarzinger@chromium.org: PTAL at the changes in the compiler directory, thanks!

[rmcilroy, 2015-12-08 13:25:08]

I'll not pretend to understand all of this, but looks pretty awesome! Some
comments, but nothing major.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
File src/compiler/bytecode-basic-block-analysis.cc (right):

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:62: if (offset_block_pair->first >
offset) {
nit - comment would be good here

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:67: if (offset_block_pair->first <
offset) {
nit - offset_block_pair->first != offset (for clarity) ?

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:78: ZoneVector<int>
split_offsets(zone());
nit - jump_targets would be clearer here IMO

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:89: bytecode_array_->length()) {
Can you not call !iterator.done() instead of "iterator.current_offset() +
iterator.current_size() < bytecode_array_->length()" ?

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:101: for (auto split_offset =
split_offsets.begin();
Comment that you are splitting basic blocks based on incoming jumps here.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:118:
interpreter::Bytecodes::Size(iterator.current_bytecode()) !=
iterator.current_bytecode_size()  ?

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:226: if (i == 0) {
Could you add a comment on what this if/else block is doing

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:236: while (changed) {
A couple of comments here would be good.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
File src/compiler/bytecode-basic-block-analysis.h (right):

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.h:81: const size_t incoming_count()
const { return incoming_.size(); }
nit - newline above

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.h:85: void
add_incoming(BytecodeBasicBlock* incoming) {
nit - newlines between all these functions down to end_with_block

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
File src/compiler/bytecode-graph-builder.cc (right):

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1243: BuildConditionalJump(comparison);
Please factor out the common code here into a BuildJumpIfValueEquals(Node*
comperand) helper function, and call it from
VisitJumpIfTrue/Constant/False/Null/Undefined, etc.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1275: BuildConditionalJump(comparison);
ditto, with a BuildJumpIfToBooleanValueEquals(...)

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1382: void
BytecodeGraphBuilder::PrepareForNewBasicBlockVisit() {
nit - I would drop the "new" here, but don't really mind if you want to keep it.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1410: if (default_done) {
Could you get rid of the default_done boolean by adding a
DCHECK_NULL(environment()) at the top of this function, and then doing: 
  if (environment()) {
    environment()->Merge(preceding_environment);
  } else {
    set_environment(preceding_environment);
  }

If this doesn't work, could you rename "default_done" to something else (the
"default" is a bit confusing to me since it makes me think this incoming path
has some kind of special control flow or something).

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1419: if (back_edges) {
nit - back_edges != 0

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1426: void
BytecodeGraphBuilder::CompleteNewBasicBlockVisit() {
ditto

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1431: if
(!interpreter::Bytecodes::IsLocalControlFlow(last_bytecode)) {
Could you do the IsLocalControlFlow check in the bytecode analyzer and add a
flag for it on the basic_block?

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1435: DCHECK_NOT_NULL(environment());
Should environment not always be non-null at this point? Could we move this
DCHECK out of the conditinoals to the start of the function?

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1439:
BuildBackEdgeIfRequired(basic_block()->if_true());
Would be good to have a comment here one why what appears to be a fallthrough
basic block might actually be a back edge from the point of view of the TF graph
due to loop headers

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1455: void
BytecodeGraphBuilder::BuildBackEdgeIfRequired(BytecodeBasicBlock* target) {
nit - move above BuildReturn (group BuildReturn / Jump / etc.)

https://codereview.chromium.org/1502243002/diff/20001/src/interpreter/bytecod...
File src/interpreter/bytecode-array-iterator.h (right):

https://codereview.chromium.org/1502243002/diff/20001/src/interpreter/bytecod...
src/interpreter/bytecode-array-iterator.h:25: int current_size() const { return
Bytecodes::Size(current_bytecode()); }
nit - current_bytecode_size

https://codereview.chromium.org/1502243002/diff/20001/src/interpreter/bytecod...
File src/interpreter/bytecodes.h (right):

https://codereview.chromium.org/1502243002/diff/20001/src/interpreter/bytecod...
src/interpreter/bytecodes.h:340: // an immediate byte operand
(OperandType::kImm8).
fix comment

[oth, 2015-12-09 11:26:45]

Thanks for the excellent comments. Incorporated all which simplified block
creation and linking.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
File src/compiler/bytecode-basic-block-analysis.cc (right):

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:62: if (offset_block_pair->first >
offset) {
On 2015/12/08 13:25:07, rmcilroy wrote:
> nit - comment would be good here

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:67: if (offset_block_pair->first <
offset) {
On 2015/12/08 13:25:07, rmcilroy wrote:
> nit - offset_block_pair->first != offset (for clarity) ?

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:78: ZoneVector<int>
split_offsets(zone());
On 2015/12/08 13:25:07, rmcilroy wrote:
> nit - jump_targets would be clearer here IMO

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:89: bytecode_array_->length()) {
On 2015/12/08 13:25:07, rmcilroy wrote:
> Can you not call !iterator.done() instead of "iterator.current_offset() +
> iterator.current_size() < bytecode_array_->length()" ?

Yes, flattened into a single loop.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:101: for (auto split_offset =
split_offsets.begin();
On 2015/12/08 13:25:07, rmcilroy wrote:
> Comment that you are splitting basic blocks based on incoming jumps here.

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:118:
interpreter::Bytecodes::Size(iterator.current_bytecode()) !=
On 2015/12/08 13:25:07, rmcilroy wrote:
> iterator.current_bytecode_size()  ?

Removed current_bytecode from BytecodeArrayIterator.

With the revision to CreateBasicBlocks, this method just passes over the basic
blocks and not the bytecode.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:226: if (i == 0) {
On 2015/12/08 13:25:07, rmcilroy wrote:
> Could you add a comment on what this if/else block is doing

Done and added a reference to the algorithm.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.cc:236: while (changed) {
On 2015/12/08 13:25:07, rmcilroy wrote:
> A couple of comments here would be good.

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
File src/compiler/bytecode-basic-block-analysis.h (right):

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.h:81: const size_t incoming_count()
const { return incoming_.size(); }
On 2015/12/08 13:25:07, rmcilroy wrote:
> nit - newline above

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-b...
src/compiler/bytecode-basic-block-analysis.h:85: void
add_incoming(BytecodeBasicBlock* incoming) {
On 2015/12/08 13:25:07, rmcilroy wrote:
> nit - newlines between all these functions down to end_with_block

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
File src/compiler/bytecode-graph-builder.cc (right):

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1243: BuildConditionalJump(comparison);
On 2015/12/08 13:25:07, rmcilroy wrote:
> Please factor out the common code here into a BuildJumpIfValueEquals(Node*
> comperand) helper function, and call it from
> VisitJumpIfTrue/Constant/False/Null/Undefined, etc.

I'd like to keep the control flow aspects and condition building separate so
these methods now look like:

Node* condition = BuildConditionForJump...
BuildConditionalJump(condition)

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1275: BuildConditionalJump(comparison);
On 2015/12/08 13:25:07, rmcilroy wrote:
> ditto, with a BuildJumpIfToBooleanValueEquals(...)

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1382: void
BytecodeGraphBuilder::PrepareForNewBasicBlockVisit() {
On 2015/12/08 13:25:07, rmcilroy wrote:
> nit - I would drop the "new" here, but don't really mind if you want to keep
it.

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1410: if (default_done) {
On 2015/12/08 13:25:07, rmcilroy wrote:
> Could you get rid of the default_done boolean by adding a
> DCHECK_NULL(environment()) at the top of this function, and then doing: 
>   if (environment()) {
>     environment()->Merge(preceding_environment);
>   } else {
>     set_environment(preceding_environment);
>   }
> 
> If this doesn't work, could you rename "default_done" to something else (the
> "default" is a bit confusing to me since it makes me think this incoming path
> has some kind of special control flow or something).

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1419: if (back_edges) {
On 2015/12/08 13:25:07, rmcilroy wrote:
> nit - back_edges != 0

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1426: void
BytecodeGraphBuilder::CompleteNewBasicBlockVisit() {
On 2015/12/08 13:25:07, rmcilroy wrote:
> ditto

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1431: if
(!interpreter::Bytecodes::IsLocalControlFlow(last_bytecode)) {
On 2015/12/08 13:25:08, rmcilroy wrote:
> Could you do the IsLocalControlFlow check in the bytecode analyzer and add a
> flag for it on the basic_block?

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1435: DCHECK_NOT_NULL(environment());
On 2015/12/08 13:25:08, rmcilroy wrote:
> Should environment not always be non-null at this point? Could we move this
> DCHECK out of the conditinoals to the start of the function?

Change to make the invariant true.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1439:
BuildBackEdgeIfRequired(basic_block()->if_true());
On 2015/12/08 13:25:07, rmcilroy wrote:
> Would be good to have a comment here one why what appears to be a fallthrough
> basic block might actually be a back edge from the point of view of the TF
graph
> due to loop headers 

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/compiler/bytecode-g...
src/compiler/bytecode-graph-builder.cc:1455: void
BytecodeGraphBuilder::BuildBackEdgeIfRequired(BytecodeBasicBlock* target) {
On 2015/12/08 13:25:07, rmcilroy wrote:
> nit - move above BuildReturn (group BuildReturn / Jump / etc.)

Done.

https://codereview.chromium.org/1502243002/diff/20001/src/interpreter/bytecod...
File src/interpreter/bytecode-array-iterator.h (right):

https://codereview.chromium.org/1502243002/diff/20001/src/interpreter/bytecod...
src/interpreter/bytecode-array-iterator.h:25: int current_size() const { return
Bytecodes::Size(current_bytecode()); }
On 2015/12/08 13:25:08, rmcilroy wrote:
> nit - current_bytecode_size

Removed.

https://codereview.chromium.org/1502243002/diff/20001/src/interpreter/bytecod...
File src/interpreter/bytecodes.h (right):

https://codereview.chromium.org/1502243002/diff/20001/src/interpreter/bytecod...
src/interpreter/bytecodes.h:340: // an immediate byte operand
(OperandType::kImm8).
On 2015/12/08 13:25:08, rmcilroy wrote:
> fix comment

Done.

[oth, 2015-12-12 13:36:43]

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

[commit-bot: I haz the power, 2015-12-12 13:36:56]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1502243002/120001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1502243002/120001

[commit-bot: I haz the power, 2015-12-12 13:38:25]

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

[commit-bot: I haz the power, 2015-12-12 13:38:26]

Dry run: Try jobs failed on following builders:
  v8_linux64_rel on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_rel/builds/13136)
  v8_linux_dbg on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_dbg/builds/12027)
  v8_linux_gcc_compile_rel on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_gcc_compile_rel/bu...)
  v8_linux_mipsel_compile_rel on tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_mipsel_compile_rel...)

[oth, 2015-12-14 07:38:18]

Description was changed from

==========
[Interpreter] Local flow control in the bytecode graph builder.

This change adds support for local control flow when building graphs
from bytecode. Pre-processing steps in BytecodeBasicBlockAnalysis.{h,cc}
assist in identifying basic blocks, their dominators, and the order
to visit blocks when generating code.

BUG=v8:4280
LOG=N
==========

to

==========
[Interpreter] Local flow control in the bytecode graph builder.

This change adds support for local control flow when building graphs
from bytecode. The change ensures loop emitted from the bytecode
generator are in natural order so the only back branches are for loops.

BUG=v8:4280
LOG=N
==========

[oth, 2015-12-14 07:47:14]

Michi, Ross, PTAL. This latest change aims to constrain and simplify the problem
as discussed last week. Thanks!

[rmcilroy, 2015-12-15 17:35:44]

Looking good. I like the changes in the bytecode-generator, makes things simpler
IMO.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
File src/compiler/bytecode-branch-analysis.cc (right):

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.cc:27: // a back-edge predecessor.
nit - these comments would be better on the public getters

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.cc:97: }
nit - pull the repeated code out into a shared helper function.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
File src/compiler/bytecode-branch-analysis.h (right):

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:18: class BytecodeBranchAnalysis
BASE_EMBEDDED {
A comment on what the class does would be good

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:26: void Analyze();
Comment?

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:31: // Offsets of bytecodes having a
foreward branch to the bytecode at |offset|.
/s/foreward/forward

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
File src/compiler/bytecode-graph-builder.cc (right):

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1386: void
BytecodeGraphBuilder::ApplyBranchAnalysis(
Not keen on the name. How about MergeEnvironmentWithForwardBranches and a
separate SaveLoopHeaderEnvironment or similar.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1399: set_environment(nullptr);
why set nullptr here and set to merged immediately below?

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1420: if (back_branches->back() ==
source_offset) {
Use IsLastBackwardBranchTo here (or remove that function if you aren't going to
use it).

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1428:
loop_header_environments_[target_offset]->Merge(environment);
nit - could we pull the back-branch stuff out into a
"MergeEnvironmentForBackwardBranches"

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
File src/compiler/bytecode-graph-builder.h (right):

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.h:160: Node*
BuildToBooleanJumpCondition(Node* comperand);
Drop the "Jump" from these functions - they don't perform the jump and it makes
it difficult to grok the difference between BuildConditinalJump with
BuildJumpCondition.

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

https://codereview.chromium.org/1502243002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-array-iterator.h:39: // is jump or conditional jump,
kMinInt otherwise.
It never actually returns kMinInt since there is an UNREACHABLE there. I'd just
remove this part of the comment and mention this should only be called fi the
current bytecode is a jump.

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

https://codereview.chromium.org/1502243002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-generator.cc:747: if (stmt->cond()->ToBooleanIsTrue())
{
nit - avoid nesting this if, just make it an "else if" in the outer if.

https://codereview.chromium.org/1502243002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-generator.cc:755: loop_builder.JumpToHeaderIfTrue();
Any reason this can't be written as:

 Visit(stmt->body());
 loop_builder.Condition();
 if (stmt->cond()->ToBooleanIsTrue()) {
   loop_builder.JumpToHeader();
 } else {
   VisitForAccumulatorValue(stmt->cond());
   loop_builder.JumpToHeaderIfTrue();
}

?

https://codereview.chromium.org/1502243002/diff/140001/src/interpreter/contro...
File src/interpreter/control-flow-builders.cc (right):

https://codereview.chromium.org/1502243002/diff/140001/src/interpreter/contro...
src/interpreter/control-flow-builders.cc:88: // Loop must have closed form, ie
all loop elements are within the
nit - /ie/i.e./

[oth, 2015-12-15 22:42:17]

Thanks for the excellent feedback, incorporated nearly everything.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
File src/compiler/bytecode-branch-analysis.cc (right):

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.cc:27: // a back-edge predecessor.
On 2015/12/15 17:35:43, rmcilroy wrote:
> nit - these comments would be better on the public getters

Done.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.cc:97: }
On 2015/12/15 17:35:43, rmcilroy wrote:
> nit - pull the repeated code out into a shared helper function. 

Nit - ignoring this one, the delta is back_edge_offsets() vs
fore_edge_offsets().

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
File src/compiler/bytecode-branch-analysis.h (right):

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:18: class BytecodeBranchAnalysis
BASE_EMBEDDED {
On 2015/12/15 17:35:43, rmcilroy wrote:
> A comment on what the class does would be good

Done.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:26: void Analyze();
On 2015/12/15 17:35:43, rmcilroy wrote:
> Comment?

Done.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:31: // Offsets of bytecodes having a
foreward branch to the bytecode at |offset|.
On 2015/12/15 17:35:43, rmcilroy wrote:
> /s/foreward/forward

Done.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
File src/compiler/bytecode-graph-builder.cc (right):

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1386: void
BytecodeGraphBuilder::ApplyBranchAnalysis(
On 2015/12/15 17:35:43, rmcilroy wrote:
> Not keen on the name. How about MergeEnvironmentWithForwardBranches and a
> separate SaveLoopHeaderEnvironment or similar.

Done.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1399: set_environment(nullptr);
On 2015/12/15 17:35:43, rmcilroy wrote:
> why set nullptr here and set to merged immediately below?

Churn, removed.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1420: if (back_branches->back() ==
source_offset) {
On 2015/12/15 17:35:43, rmcilroy wrote:
> Use IsLastBackwardBranchTo here (or remove that function if you aren't going
to
> use it).

Removed it, want the branches immediately if true.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1428:
loop_header_environments_[target_offset]->Merge(environment);
On 2015/12/15 17:35:43, rmcilroy wrote:
> nit - could we pull the back-branch stuff out into a
> "MergeEnvironmentForBackwardBranches" 

Done.

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
File src/compiler/bytecode-graph-builder.h (right):

https://codereview.chromium.org/1502243002/diff/140001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.h:160: Node*
BuildToBooleanJumpCondition(Node* comperand);
On 2015/12/15 17:35:43, rmcilroy wrote:
> Drop the "Jump" from these functions - they don't perform the jump and it
makes
> it difficult to grok the difference between BuildConditinalJump with
> BuildJumpCondition.

Done.

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

https://codereview.chromium.org/1502243002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-array-iterator.h:39: // is jump or conditional jump,
kMinInt otherwise.
On 2015/12/15 17:35:44, rmcilroy wrote:
> It never actually returns kMinInt since there is an UNREACHABLE there. I'd
just
> remove this part of the comment and mention this should only be called fi the
> current bytecode is a jump.

Done. Yes, doh!

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

https://codereview.chromium.org/1502243002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-generator.cc:747: if (stmt->cond()->ToBooleanIsTrue())
{
On 2015/12/15 17:35:44, rmcilroy wrote:
> nit - avoid nesting this if, just make it an "else if" in the outer if.

Done.

https://codereview.chromium.org/1502243002/diff/140001/src/interpreter/byteco...
src/interpreter/bytecode-generator.cc:755: loop_builder.JumpToHeaderIfTrue();
On 2015/12/15 17:35:44, rmcilroy wrote:
> Any reason this can't be written as:
> 
>  Visit(stmt->body());
>  loop_builder.Condition();
>  if (stmt->cond()->ToBooleanIsTrue()) {
>    loop_builder.JumpToHeader();
>  } else {
>    VisitForAccumulatorValue(stmt->cond());
>    loop_builder.JumpToHeaderIfTrue();
> }
> 
> ?

The Condition() is the target for continue statements. This would mean two jumps
for continue statements in do...while(true) whilst interpreting.

https://codereview.chromium.org/1502243002/diff/140001/src/interpreter/contro...
File src/interpreter/control-flow-builders.cc (right):

https://codereview.chromium.org/1502243002/diff/140001/src/interpreter/contro...
src/interpreter/control-flow-builders.cc:88: // Loop must have closed form, ie
all loop elements are within the
On 2015/12/15 17:35:44, rmcilroy wrote:
> nit - /ie/i.e./

Done.

[Michael Starzinger, 2015-12-16 12:40:12]

Looking good, I like this new approach. Only nits.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
File src/compiler/bytecode-branch-analysis.h (right):

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:9: #include "src/compiler.h"
nit: Can we get by without including the compiler.h grab-bag header here? AFAICT
the handles.h header and a forward declare of "BytecodeArray" should suffice,
but with V8 you never know. :)

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:21: // control flow logic for turbofan
graphs built from bytecode.
nit: s/turbofan graphs/high-level IR graphs/

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:30: reachable_(bytecode_array->length(),
zone),
nit: Can we move this constructor into the .cc file, otherwise a whole slew of
headers needs to be included for the BytecodeArray::length function.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
File src/compiler/bytecode-graph-builder.cc (right):

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:162: for (int i = 0; i <
static_cast<int>(values_.size()); i++) {
nit: s/int/size_t/ here and drop the static_cast instead. I should do the same
in AstGraphBuilder at some point.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:178: UpdateEffectDependency(effect);
nit: Can we reorder this function so that it follows the same structure/order as
Environment::Merge? Just for readability and that the symmetry is obvious.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1395: Environment* environment =
merge_environments_[back_branches->at(0)];
nit: s/environment/merged/ for readability.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1396: for (size_t i = 1; i <
back_branches->size(); i++) {
nit: Would it be possible to have a similar check here as with the forward
branches? Something along the lines of ...

DCHECK_GT(branch_sites->at(i), target_offset);

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1558: // TODO(mstarzinger): Revisit this
once we have proper effect states.
nit: This TODO is outdated, I should remove it from the AstGraphBuilder as well.
Let's drop it from here.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1620: 
nit: Stray empty newline.

https://codereview.chromium.org/1502243002/diff/180001/src/interpreter/byteco...
File src/interpreter/bytecodes.cc (right):

https://codereview.chromium.org/1502243002/diff/180001/src/interpreter/byteco...
src/interpreter/bytecodes.cc:211: return bytecode == Bytecode::kReturn ||
IsJump(bytecode);
nit: The name is not fully fitting, because the list also contains "non-local"
control flow. How would you feel about calling it "IsControlFlow" instead? Also,
I am not sure, should kThrow be in this list as well? If not, then a comment
explaining why not could be useful.

https://codereview.chromium.org/1502243002/diff/180001/src/interpreter/contro...
File src/interpreter/control-flow-builders.h (right):

https://codereview.chromium.org/1502243002/diff/180001/src/interpreter/contro...
src/interpreter/control-flow-builders.h:51: 
nit: Stray empty newline.

[oth, 2015-12-16 14:17:06]

Excellent comments. Revised and updated the CL. Thanks!

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
File src/compiler/bytecode-branch-analysis.h (right):

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:9: #include "src/compiler.h"
On 2015/12/16 12:40:11, Michael Starzinger wrote:
> nit: Can we get by without including the compiler.h grab-bag header here?
AFAICT
> the handles.h header and a forward declare of "BytecodeArray" should suffice,
> but with V8 you never know. :)

Done.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:21: // control flow logic for turbofan
graphs built from bytecode.
On 2015/12/16 12:40:11, Michael Starzinger wrote:
> nit: s/turbofan graphs/high-level IR graphs/

Done.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-branch-analysis.h:30: reachable_(bytecode_array->length(),
zone),
On 2015/12/16 12:40:11, Michael Starzinger wrote:
> nit: Can we move this constructor into the .cc file, otherwise a whole slew of
> headers needs to be included for the BytecodeArray::length function.

Done.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
File src/compiler/bytecode-graph-builder.cc (right):

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:162: for (int i = 0; i <
static_cast<int>(values_.size()); i++) {
On 2015/12/16 12:40:12, Michael Starzinger wrote:
> nit: s/int/size_t/ here and drop the static_cast instead. I should do the same
> in AstGraphBuilder at some point.

Done.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:178: UpdateEffectDependency(effect);
On 2015/12/16 12:40:12, Michael Starzinger wrote:
> nit: Can we reorder this function so that it follows the same structure/order
as
> Environment::Merge? Just for readability and that the symmetry is obvious.

Done.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1395: Environment* environment =
merge_environments_[back_branches->at(0)];
On 2015/12/16 12:40:12, Michael Starzinger wrote:
> nit: s/environment/merged/ for readability.

Done.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1396: for (size_t i = 1; i <
back_branches->size(); i++) {
On 2015/12/16 12:40:12, Michael Starzinger wrote:
> nit: Would it be possible to have a similar check here as with the forward
> branches? Something along the lines of ...
> 
> DCHECK_GT(branch_sites->at(i), target_offset);

Done.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1558: // TODO(mstarzinger): Revisit this
once we have proper effect states.
On 2015/12/16 12:40:12, Michael Starzinger wrote:
> nit: This TODO is outdated, I should remove it from the AstGraphBuilder as
well.
> Let's drop it from here.

Done.

https://codereview.chromium.org/1502243002/diff/180001/src/compiler/bytecode-...
src/compiler/bytecode-graph-builder.cc:1620: 
On 2015/12/16 12:40:12, Michael Starzinger wrote:
> nit: Stray empty newline.

Done.

https://codereview.chromium.org/1502243002/diff/180001/src/interpreter/byteco...
File src/interpreter/bytecodes.cc (right):

https://codereview.chromium.org/1502243002/diff/180001/src/interpreter/byteco...
src/interpreter/bytecodes.cc:211: return bytecode == Bytecode::kReturn ||
IsJump(bytecode);
On 2015/12/16 12:40:12, Michael Starzinger wrote:
> nit: The name is not fully fitting, because the list also contains "non-local"
> control flow. How would you feel about calling it "IsControlFlow" instead?
Also,
> I am not sure, should kThrow be in this list as well? If not, then a comment
> explaining why not could be useful.

Renamed to IsJumpOrReturn(). Pedants might say return is local control flow
(and/but so is call). Throw isn't.

https://codereview.chromium.org/1502243002/diff/180001/src/interpreter/contro...
File src/interpreter/control-flow-builders.h (right):

https://codereview.chromium.org/1502243002/diff/180001/src/interpreter/contro...
src/interpreter/control-flow-builders.h:51: 
On 2015/12/16 12:40:12, Michael Starzinger wrote:
> nit: Stray empty newline.

Done.

[rmcilroy, 2015-12-16 15:08:51]

lgtm

[Michael Starzinger, 2015-12-16 15:12:04]

LGTM.

[oth, 2015-12-16 16:03:46]

The CQ bit was checked by oth@chromium.org

[commit-bot: I haz the power, 2015-12-16 16:03:55]

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

[oth, 2015-12-16 16:04:34]

Thanks for the help with this. Attempting to land now.

[commit-bot: I haz the power, 2015-12-16 16:29:13]

Description was changed from

==========
[Interpreter] Local flow control in the bytecode graph builder.

This change adds support for local control flow when building graphs
from bytecode. The change ensures loop emitted from the bytecode
generator are in natural order so the only back branches are for loops.

BUG=v8:4280
LOG=N
==========

to

==========
[Interpreter] Local flow control in the bytecode graph builder.

This change adds support for local control flow when building graphs
from bytecode. The change ensures loop emitted from the bytecode
generator are in natural order so the only back branches are for loops.

BUG=v8:4280
LOG=N
==========

[commit-bot: I haz the power, 2015-12-16 16:29:14]

Committed patchset #11 (id:200001)

[commit-bot: I haz the power, 2015-12-16 16:29:53]

Description was changed from

==========
[Interpreter] Local flow control in the bytecode graph builder.

This change adds support for local control flow when building graphs
from bytecode. The change ensures loop emitted from the bytecode
generator are in natural order so the only back branches are for loops.

BUG=v8:4280
LOG=N
==========

to

==========
[Interpreter] Local flow control in the bytecode graph builder.

This change adds support for local control flow when building graphs
from bytecode. The change ensures loop emitted from the bytecode
generator are in natural order so the only back branches are for loops.

BUG=v8:4280
LOG=N

Committed: https://crrev.com/d3168202f52d78cbcfe755d17884bbafa6cc09b5
Cr-Commit-Position: refs/heads/master@{#32911}
==========

[commit-bot: I haz the power, 2015-12-16 16:29:54]

Patchset 11 (id:??) landed as
https://crrev.com/d3168202f52d78cbcfe755d17884bbafa6cc09b5
Cr-Commit-Position: refs/heads/master@{#32911}