Loop peeling for inner loops....

Loop peeling for inner loops.

This change adds the option to peel off the first iteration of inner loops.

Loop peeling is off by default and can enabled by a flag. It also requires building a flow graph.

As part of this I added the possibility to clone AST nodes.


Committed: http://code.google.com/p/v8/source/detail?r=4205

[William Hesse, 2010-03-22 09:48:01]

Some comments.

http://codereview.chromium.org/998001/diff/18009/25007
File src/ast.cc (right):

http://codereview.chromium.org/998001/diff/18009/25007#newcode599
src/ast.cc:599: // are already numbered.
Assert that we only copy AstNodes before node numbers are assigned.

http://codereview.chromium.org/998001/diff/18009/25007#newcode730
src/ast.cc:730: 
Couldn't conditional expressions be supported easily?  I would think they might
show up in statement bodies.

Why do properties and calls not need to be cloned when the deep copy is made? 
Or do they have no fields that need copying explicitly?

http://codereview.chromium.org/998001/diff/18009/25008
File src/parser.cc (right):

http://codereview.chromium.org/998001/diff/18009/25008#newcode3850
src/parser.cc:3850: // when peeling or unrolling such a loop.
Should we check for object literals bigger than a certain size as well, or is
that not a problem?

http://codereview.chromium.org/998001/diff/18009/25002
File src/variables.h (left):

http://codereview.chromium.org/998001/diff/18009/25002#oldcode45
src/variables.h:45: 
Why is StaticType not copied and assigned by value?  Is it likely that it will
become more complex in the future?

[Kevin Millikin (Chromium), 2010-03-22 10:24:52]

http://codereview.chromium.org/998001/diff/18009/25007
File src/ast.cc (right):

http://codereview.chromium.org/998001/diff/18009/25007#newcode598
src/ast.cc:598: // Ast node number should be unique. Assert that we don't copy
as nodes that
In the comment text: "Ast" ==> "AST", "as" ==> "AST".

http://codereview.chromium.org/998001/diff/18009/25004
File src/ast.h (right):

http://codereview.chromium.org/998001/diff/18009/25004#newcode357
src/ast.h:357: Block(Block* other, ZoneList<Statement*>* statements);
It's not obvious what this will do (why does it need both a list of statements
and another block?).  It needs a short comment here.

http://codereview.chromium.org/998001/diff/18009/25004#newcode423
src/ast.h:423: IterationStatement(IterationStatement* other, Statement* body);
Not obvious what this will do.  Needs a short comment.

http://codereview.chromium.org/998001/diff/18009/25004#newcode501
src/ast.h:501: ForStatement(ForStatement* other,
Not obvious what this will do.

http://codereview.chromium.org/998001/diff/18009/25004#newcode578
src/ast.h:578: ExpressionStatement(ExpressionStatement* other, Expression*
expression);
Not obvious.

http://codereview.chromium.org/998001/diff/18009/25004#newcode722
src/ast.h:722: IfStatement(IfStatement* other,
Same.

http://codereview.chromium.org/998001/diff/18009/25005
File src/compiler.cc (right):

http://codereview.chromium.org/998001/diff/18009/25005#newcode108
src/compiler.cc:108: builder.graph()->PrintText(builder.postorder(), function);
Please swap the order of the arguments here.

http://codereview.chromium.org/998001/diff/18009/25001
File src/data-flow.cc (right):

http://codereview.chromium.org/998001/diff/18009/25001#newcode183
src/data-flow.cc:183: ASSERT(stmt->AsForStatement() != NULL);
Argument type should just be ForStatement*.

http://codereview.chromium.org/998001/diff/18009/25001#newcode188
src/data-flow.cc:188: ForStatement* for_stmt =
copy_visitor.DeepCopyStmt(stmt)->AsForStatement();
Why copy the original and then re-copy the test, body and update?  Why not just
copy the parts you need copies of (test, body and update)?

http://codereview.chromium.org/998001/diff/18009/25001#newcode205
src/data-flow.cc:205: graph_.AppendInstruction(init);
I don't think you should be building the flow graph here---the code for flow
graph building should not be duplicated this way.

This function should just return a new statement.  In fact, it doesn't need to
be a member of FlowGraphBuilder at all, but can be a static function in this
file.

http://codereview.chromium.org/998001/diff/18009/25001#newcode274
src/data-flow.cc:274: (*stmts)[i] = ProcessStatement((*stmts)[i]);
You can write (*stmts)[i] as stmts->at(i), which seems more common in the
codebase.

http://codereview.chromium.org/998001/diff/18009/25001#newcode283
src/data-flow.cc:283: return PeelForLoop(stmt);
If you don't try to build the graph it PeelForLoop, you have:

if (FLAG_loop_peeling etc....) {
  stmt = PeelForLoop(stmt->AsForStatement());
}
Visit(stmt);
return stmt;

[fschneider, 2010-03-22 12:27:41]

Addressed all comments.

http://codereview.chromium.org/998001/diff/18009/25007
File src/ast.cc (right):

http://codereview.chromium.org/998001/diff/18009/25007#newcode598
src/ast.cc:598: // Ast node number should be unique. Assert that we don't copy
as nodes that
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> In the comment text: "Ast" ==> "AST", "as" ==> "AST".

Done.

http://codereview.chromium.org/998001/diff/18009/25007#newcode599
src/ast.cc:599: // are already numbered.
On 2010/03/22 09:48:01, William Hesse wrote:
> Assert that we only copy AstNodes before node numbers are assigned.

Done.

http://codereview.chromium.org/998001/diff/18009/25007#newcode730
src/ast.cc:730: 
On 2010/03/22 09:48:01, William Hesse wrote:
> Couldn't conditional expressions be supported easily?  I would think they
might
> show up in statement bodies.
> 
> Why do properties and calls not need to be cloned when the deep copy is made? 
> Or do they have no fields that need copying explicitly?

Yes. Those will be added later. Right now I just support the subset of nodes
where we can build a flowgraph.

http://codereview.chromium.org/998001/diff/18009/25004
File src/ast.h (right):

http://codereview.chromium.org/998001/diff/18009/25004#newcode357
src/ast.h:357: Block(Block* other, ZoneList<Statement*>* statements);
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> It's not obvious what this will do (why does it need both a list of statements
> and another block?).  It needs a short comment here.

Done.

http://codereview.chromium.org/998001/diff/18009/25004#newcode423
src/ast.h:423: IterationStatement(IterationStatement* other, Statement* body);
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> Not obvious what this will do.  Needs a short comment.

Done.

http://codereview.chromium.org/998001/diff/18009/25004#newcode501
src/ast.h:501: ForStatement(ForStatement* other,
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> Not obvious what this will do.

Done.

http://codereview.chromium.org/998001/diff/18009/25004#newcode578
src/ast.h:578: ExpressionStatement(ExpressionStatement* other, Expression*
expression);
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> Not obvious.

Done.

http://codereview.chromium.org/998001/diff/18009/25004#newcode722
src/ast.h:722: IfStatement(IfStatement* other,
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> Same.

Done.

http://codereview.chromium.org/998001/diff/18009/25005
File src/compiler.cc (right):

http://codereview.chromium.org/998001/diff/18009/25005#newcode108
src/compiler.cc:108: builder.graph()->PrintText(builder.postorder(), function);
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> Please swap the order of the arguments here.

Done.

http://codereview.chromium.org/998001/diff/18009/25001
File src/data-flow.cc (right):

http://codereview.chromium.org/998001/diff/18009/25001#newcode183
src/data-flow.cc:183: ASSERT(stmt->AsForStatement() != NULL);
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> Argument type should just be ForStatement*.

Done.

http://codereview.chromium.org/998001/diff/18009/25001#newcode188
src/data-flow.cc:188: ForStatement* for_stmt =
copy_visitor.DeepCopyStmt(stmt)->AsForStatement();
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> Why copy the original and then re-copy the test, body and update?  Why not
just
> copy the parts you need copies of (test, body and update)?

Done.

http://codereview.chromium.org/998001/diff/18009/25001#newcode205
src/data-flow.cc:205: graph_.AppendInstruction(init);
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> I don't think you should be building the flow graph here---the code for flow
> graph building should not be duplicated this way.
> 
> This function should just return a new statement.  In fact, it doesn't need to
> be a member of FlowGraphBuilder at all, but can be a static function in this
> file.

Done.

http://codereview.chromium.org/998001/diff/18009/25001#newcode274
src/data-flow.cc:274: (*stmts)[i] = ProcessStatement((*stmts)[i]);
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> You can write (*stmts)[i] as stmts->at(i), which seems more common in the
> codebase.

Done.

http://codereview.chromium.org/998001/diff/18009/25001#newcode283
src/data-flow.cc:283: return PeelForLoop(stmt);
On 2010/03/22 10:24:52, Kevin Millikin wrote:
> If you don't try to build the graph it PeelForLoop, you have:
> 
> if (FLAG_loop_peeling etc....) {
>   stmt = PeelForLoop(stmt->AsForStatement());
> }
> Visit(stmt);
> return stmt;

Done.

http://codereview.chromium.org/998001/diff/18009/25008
File src/parser.cc (right):

http://codereview.chromium.org/998001/diff/18009/25008#newcode3850
src/parser.cc:3850: // when peeling or unrolling such a loop.
On 2010/03/22 09:48:01, William Hesse wrote:
> Should we check for object literals bigger than a certain size as well, or is
> that not a problem?

Right now we don't support object literals in the flow graph. But once we do, we
certainly need more detailed rules when not to apply loop peeling.

http://codereview.chromium.org/998001/diff/18009/25002
File src/variables.h (left):

http://codereview.chromium.org/998001/diff/18009/25002#oldcode45
src/variables.h:45: 
On 2010/03/22 09:48:01, William Hesse wrote:
> Why is StaticType not copied and assigned by value?  Is it likely that it will
> become more complex in the future?

Don't know really why. I changed it to be copyable because it's really only one
enum value.

[Kevin Millikin (Chromium), 2010-03-22 13:01:04]

LGTM.