Collect AstNode type information

Collect AstNode type information

Committed: https://code.google.com/p/v8/source/detail?r=10631

[Jakob Kummerow, 2012-01-17 13:10:45]

Kevin: PTAL. Is this what you had in mind?

The new methods aren't used anywhere yet; but they will be as soon as Ulan and
myself will rebase our pending CLs on top of this one.

[Sven Panne, 2012-01-17 13:46:58]

https://chromiumcodereview.appspot.com/9221011/diff/1/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/1/src/ast.h#newcode153
src/ast.h:153: typedef int Flag;
Drive-by comment: One could use EnumSet<FlagIndex> instead of plain old int here
and kill all the masks. "FlagIndex" might need some better name then, too...

[Kevin Millikin (Chromium), 2012-01-17 15:30:20]

I agree with Sven---I'd do something to avoid the duplication required by the
masks.  You could either use the EnumSet utility class or use a macro to
generate them.

Could we take a look at the overhead of running this for everything we compile?

[Jakob Kummerow, 2012-01-30 11:02:50]

New approach, please take another look.

Please disregard the delta from the first patch set, as this is pretty much a
complete rewrite (and rebased onto current bleeding_edge).

The patch is pretty big, but most of it is just refactoring: 
• AstNodes' ctors in ast.h have been moved to the "protected" section of the
respective class, to make sure they're only used by the factory.
• The methods in AstNodeFactory are, as factory methods tend to be, very similar
to the ctors they're calling; plus some housekeeping, and with implicit
isolate/zone parameters.
• parser.cc, scopes.cc, and rewriter.cc use the new factory methods instead of
calling AstNode ctors directly.

Rationale for this approach:
A visitor is probably the cleanest way to compute information about a tree/AST,
but walking the tree at an arbitrary time is relatively expensive, so we do the
work at tree construction time.

Object ownership is a bit tricky, because:
• AstProperties is a zone object and lives as long as the AST nodes do
• AstConstructionVisitor is BASE_EMBEDDED, so its lifetime must be tied to some
other C++ object that owns it
• AstNodeFactory can live anywhere in the C++ world; I could have it live in a
CompilationInfo if someone thinks that would be better.

I'm open to suggestions on how to make this even cleaner, but I also think we
can live with it as it is.

Computation of the kDontSoftInline flag is not yet included, but can easily be
added to the AstConstructionVisitor.

[Vyacheslav Egorov (Chromium), 2012-01-30 11:48:46]

How about some C++ template magic?

class Parser {
  inline void OnNewNode(AstNode* t) {
    /* do nothing */
  }

  inline void OnNewNode(WithStatement* t) {
    /* do something special with WithStatement */
  }

  template<typename T, typename A1>
  T* mk(A1 a1) {
    T* t = new T(a1, a2, a3);
    OnNewNode(t);
    return t;
  }

  template<typename T, typename A1, typename A2>
  T* mk(A1 a1, A2 a2, A3 a3) {
    T* t = new T(a1, a2, a3);
    OnNewNode(t);
    return t;
  }

  template<typename T, typename A1, typename A2, typename A3>
  T* mk(A1 a1, A2 a2, A3 a3) {
    T* t = new T(a1, a2, a3);
    OnNewNode(t);
    return t;
  }

  /* add as much overloads of mk as you need */

  WithStatement* ParseWithStatement() {
    return mk<WithStatement>(x, y, z);
  }
};

[fschneider, 2012-01-30 12:10:35]

drive-by comments:

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/ast.h#newcode2349
src/ast.h:2349: class AstNodeFactory {
maybe make it BASE_EMBEDDED.

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/parser.h
File src/parser.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/parser.h#newcode797
src/parser.h:797: AstNodeFactory* ast_node_factory_;
Embedded instance 

AstNodeFactory ast_node_factory_;

instead of malloced with new/delete would be better.

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/rewriter.cc
File src/rewriter.cc (right):

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/rewriter.cc#newc...
src/rewriter.cc:46: factory_ = new AstNodeFactory(isolate());
Why not just embed it in the instance? Then there is no need to call new/delete
(which is expensive if it is malloced)

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/rewriter.cc#newc...
src/rewriter.cc:57: return factory_;
return &factory_;

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/rewriter.cc#newc...
src/rewriter.cc:76: AstNodeFactory* factory_;
AstNodeFactory factory_;

[fschneider, 2012-01-30 13:54:26]

more dbc:

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/ast.h#newcode1254
src/ast.h:1254: AstProperties* ast_properties_;
It seems quite expensive to add a pointer to each VariableProxy to record later
changes in the AstProperties. VariableProxy is one of the most frequent of all
AST nodes.

Maybe pass the AstProperties instead on to the phase that may change the
VariableProxy?

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/objects.h
File src/objects.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/objects.h#newcod...
src/objects.h:5412: kAstNodeCountOffset + kPointerSize;
You could reduce the x64 version by pairing two properties from above like done
for the ones below here.

[Jakob Kummerow, 2012-02-01 14:46:09]

Thanks for all the feedback; I've uploaded a new revision.

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/ast.h#newcode1254
src/ast.h:1254: AstProperties* ast_properties_;
On 2012/01/30 13:54:26, fschneider wrote:
> It seems quite expensive to add a pointer to each VariableProxy to record
later
> changes in the AstProperties. VariableProxy is one of the most frequent of all
> AST nodes.
> 
> Maybe pass the AstProperties instead on to the phase that may change the
> VariableProxy?

The problem is that at the time the VariableProxy is bound to a variable (via
BindTo()), the kDontInline bit potentially needs to be flipped. I don't see a
way to do that without either storing this pointer (which costs memory, yes) or
walking the tree top-down to find all VariableProxies (which costs time). If you
have any other solution in mind, I'm all ears :-)

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/ast.h#newcode2349
src/ast.h:2349: class AstNodeFactory {
On 2012/01/30 12:10:35, fschneider wrote:
> maybe make it BASE_EMBEDDED.

Done.

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/objects.h
File src/objects.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/objects.h#newcod...
src/objects.h:5412: kAstNodeCountOffset + kPointerSize;
On 2012/01/30 13:54:26, fschneider wrote:
> You could reduce the x64 version by pairing two properties from above like
done
> for the ones below here.

Done.

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/parser.h
File src/parser.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/parser.h#newcode797
src/parser.h:797: AstNodeFactory* ast_node_factory_;
On 2012/01/30 12:10:35, fschneider wrote:
> Embedded instance 
> 
> AstNodeFactory ast_node_factory_;
> 
> instead of malloced with new/delete would be better.

Done.

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/rewriter.cc
File src/rewriter.cc (right):

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/rewriter.cc#newc...
src/rewriter.cc:46: factory_ = new AstNodeFactory(isolate());
On 2012/01/30 12:10:35, fschneider wrote:
> Why not just embed it in the instance? Then there is no need to call
new/delete
> (which is expensive if it is malloced)

Done.

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/rewriter.cc#newc...
src/rewriter.cc:57: return factory_;
On 2012/01/30 12:10:35, fschneider wrote:
> return &factory_;

Done.

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/rewriter.cc#newc...
src/rewriter.cc:76: AstNodeFactory* factory_;
On 2012/01/30 12:10:35, fschneider wrote:
> AstNodeFactory factory_;

Done.

[fschneider, 2012-02-02 15:54:07]

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/ast.h#newcode1254
src/ast.h:1254: AstProperties* ast_properties_;
It seems that we only visit the VariableProxy to filter out LOOKUP slot
variables.

I think we can skip those when setting the kDontInline flag: If there is no eval
or with-statement (which we can't optimize either), then there shouldn't be any
variables of type LOOKUP.

(Even if there was, we would bailout safely from the Hydrogen graph builder, and
abort optimization for the current function.)

[Jakob Kummerow, 2012-02-03 10:06:22]

Florian: I'm inclined to agree with that analysis :-)

New patch set uploaded.

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/4001/src/ast.h#newcode1254
src/ast.h:1254: AstProperties* ast_properties_;
On 2012/02/02 15:54:07, fschneider wrote:
> It seems that we only visit the VariableProxy to filter out LOOKUP slot
> variables.
> 
> I think we can skip those when setting the kDontInline flag: If there is no
eval
> or with-statement (which we can't optimize either), then there shouldn't be
any
> variables of type LOOKUP.
> 
> (Even if there was, we would bailout safely from the Hydrogen graph builder,
and
> abort optimization for the current function.)

Done.

[fschneider, 2012-02-06 14:14:29]

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.cc
File src/ast.cc (right):

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.cc#newcode1020
src/ast.cc:1020: // proxy()->var()->IsStackAllocated() && fun() == NULL;
Forgotten commented code?

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode1492
src/ast.h:1492: ? static_cast<int>(GetNextId(isolate))
GetNextId returns unsigned, yet all ast ids are stored as int. Does it just work
changing GetNextId to return an int instead?

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2329
src/ast.h:2329: virtual void Visit##type(type* node);
It seems that none of the functions actually recursively visit their children.
In this case you can avoid inheriting from AstVisitor and make all the functions
non-virtual.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2340
src/ast.h:2340: // hold the results; is passed to VariableProxies upon their
construction
Comment outdated? VariableProxies don't update their info later anymore, do
they?

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2356
src/ast.h:2356: zone_(zone),
Maybe simplify initialization to:

zone_(zone != NULL ? zone : isolate->zone()),

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2370
src/ast.h:2370: visitor_->Visit##NodeType(node); \
Suggestion for further optimization:

If the visitor was embedded in the AstNodeFactory (or even AstNodeFactory
includes all from AstConstructionVisitor), you could get rid of the additional
indirection and avoid checking visitor_ == NULL for each New* call.

You could create a templated version of AstNodeFactory<bool is_visiting> where
the template parameters controls if you do the visitor-action or not. I think it
would be a minimal change to the code overall.

The FunctionState then would have an instance of AstNodeFactory embedded instead
of having an AstConstructionVisitor and save/restore while parsing it in the
FunctionState constructor/destructor.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/compiler.h
File src/compiler.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/compiler.h#newc...
src/compiler.h:1: // Copyright 2012 the V8 project authors. All rights reserved.
No changes in this file.

[Kevin Millikin (Chromium), 2012-02-06 15:14:22]

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2322
src/ast.h:2322: AstProperties* DetachAstProperties();
I don't understand why the AstProperties ownership is so complicated.  Wouldn't
it work to:

1. Make AstProperties BASE_EMBEDDED
2. Remove DISALLOW_COPY_AND_ASSIGN(AstProperties);
3. Give each FunctionLiteral an embedded AstProperties.
4. Give the visitor a single embedded AstProperties.
5. Simply copy from (factory's) visitor to function literal when constructing a
function literal?

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2356
src/ast.h:2356: zone_(zone),
Since every call (that I could find) does not pass zone or visitor, I'd just
leave them off the parameter list and assume their default values (I don't
understand what is the semantics of passing a zone other than isolate->zone()
anyway).

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2370
src/ast.h:2370: visitor_->Visit##NodeType(node); \
Possibly:

visitor_->Visit##NodeType((node));

to allow a comma expression as 'node'.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2399
src/ast.h:2399: ITERATION_STATEMENT(SwitchStatement)
Switch is not iteration, so this is probably a bad name for the macro.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2460
src/ast.h:2460: static EmptyStatement* empty = ::new EmptyStatement();
It seems wrong to have this singleton empty statement.  The AST is no longer a
tree, the nodes no longer have a unique identity, and I'm not sure it's really
any optimization.

I'd take this opportunity to get rid of it.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2617
src/ast.h:2617: bool visit_with_visitor = true) {
No need for default value.  Boolean default values are extra scary.

I also don't like two boolean parameters in a row.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/compiler.h
File src/compiler.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/compiler.h#newc...
src/compiler.h:1: // Copyright 2012 the V8 project authors. All rights reserved.
On 2012/02/06 14:14:29, fschneider wrote:
> No changes in this file.

I think you mean "no other changes in this file".

[Jakob Kummerow, 2012-02-07 12:38:36]

"a minimal change"? Yeah, right ;-)

But I agree that the CL looks better now. All comments addressed, please take
another look.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.cc
File src/ast.cc (right):

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.cc#newcode1020
src/ast.cc:1020: // proxy()->var()->IsStackAllocated() && fun() == NULL;
On 2012/02/06 14:14:29, fschneider wrote:
> Forgotten commented code?

No, two-line comment :-)
It was intended as a reminder for a possible future optimization: we could do an
early exit (before re-parsing) from HGraphBuilder::TryInline() if the persisted
AstProperties information told us that some declaration is not inlineable
anyway.
But that's probably not going to happen now anyway, so I've just removed the
comment.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode1492
src/ast.h:1492: ? static_cast<int>(GetNextId(isolate))
On 2012/02/06 14:14:29, fschneider wrote:
> GetNextId returns unsigned, yet all ast ids are stored as int. Does it just
work
> changing GetNextId to return an int instead?

Done.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2322
src/ast.h:2322: AstProperties* DetachAstProperties();
On 2012/02/06 15:14:23, Kevin Millikin wrote:
> I don't understand why the AstProperties ownership is so complicated. 
Wouldn't
> it work to:
> 
> 1. Make AstProperties BASE_EMBEDDED
> 2. Remove DISALLOW_COPY_AND_ASSIGN(AstProperties);
> 3. Give each FunctionLiteral an embedded AstProperties.
> 4. Give the visitor a single embedded AstProperties.
> 5. Simply copy from (factory's) visitor to function literal when constructing
a
> function literal?

Done.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2329
src/ast.h:2329: virtual void Visit##type(type* node);
On 2012/02/06 14:14:29, fschneider wrote:
> It seems that none of the functions actually recursively visit their children.
> In this case you can avoid inheriting from AstVisitor and make all the
functions
> non-virtual.

Done.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2340
src/ast.h:2340: // hold the results; is passed to VariableProxies upon their
construction
On 2012/02/06 14:14:29, fschneider wrote:
> Comment outdated? VariableProxies don't update their info later anymore, do
> they?

Done.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2356
src/ast.h:2356: zone_(zone),
On 2012/02/06 14:14:29, fschneider wrote:
> Maybe simplify initialization to:
> 
> zone_(zone != NULL ? zone : isolate->zone()),

Obsolete -- see Kevin's comment.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2356
src/ast.h:2356: zone_(zone),
On 2012/02/06 15:14:23, Kevin Millikin wrote:
> Since every call (that I could find) does not pass zone or visitor, I'd just
> leave them off the parameter list and assume their default values (I don't
> understand what is the semantics of passing a zone other than isolate->zone()
> anyway).

Done.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2370
src/ast.h:2370: visitor_->Visit##NodeType(node); \
On 2012/02/06 14:14:29, fschneider wrote:
> Suggestion for further optimization:
> 
> If the visitor was embedded in the AstNodeFactory (or even AstNodeFactory
> includes all from AstConstructionVisitor), you could get rid of the additional
> indirection and avoid checking visitor_ == NULL for each New* call.
> 
> You could create a templated version of AstNodeFactory<bool is_visiting> where
> the template parameters controls if you do the visitor-action or not. I think
it
> would be a minimal change to the code overall.
> 
> The FunctionState then would have an instance of AstNodeFactory embedded
instead
> of having an AstConstructionVisitor and save/restore while parsing it in the
> FunctionState constructor/destructor.

Done.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2370
src/ast.h:2370: visitor_->Visit##NodeType(node); \
On 2012/02/06 15:14:23, Kevin Millikin wrote:
> Possibly:
> 
> visitor_->Visit##NodeType((node));
> 
> to allow a comma expression as 'node'.

Done.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2399
src/ast.h:2399: ITERATION_STATEMENT(SwitchStatement)
On 2012/02/06 15:14:23, Kevin Millikin wrote:
> Switch is not iteration, so this is probably a bad name for the macro.

Done.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2460
src/ast.h:2460: static EmptyStatement* empty = ::new EmptyStatement();
On 2012/02/06 15:14:23, Kevin Millikin wrote:
> It seems wrong to have this singleton empty statement.  The AST is no longer a
> tree, the nodes no longer have a unique identity, and I'm not sure it's really
> any optimization.
> 
> I'd take this opportunity to get rid of it.

Done.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/ast.h#newcode2617
src/ast.h:2617: bool visit_with_visitor = true) {
On 2012/02/06 15:14:23, Kevin Millikin wrote:
> No need for default value.  Boolean default values are extra scary.

Done.

> I also don't like two boolean parameters in a row.

Done.

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/compiler.h
File src/compiler.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/13003/src/compiler.h#newc...
src/compiler.h:1: // Copyright 2012 the V8 project authors. All rights reserved.
On 2012/02/06 14:14:29, fschneider wrote:
> No changes in this file.

Done.

[fschneider, 2012-02-07 14:31:49]

LGTM.

[Kevin Millikin (Chromium), 2012-02-08 09:13:18]

LGTM.

https://chromiumcodereview.appspot.com/9221011/diff/19001/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/19001/src/ast.h#newcode148
src/ast.h:148: kDontCrankshaft,
To be pedantic (everybody loves that), "Crankshaft" is the name of the entire
backend, not just the optimizing compiler.  And it's not a verb anyway.  I
suggest "kDontOptimize".

https://chromiumcodereview.appspot.com/9221011/diff/19001/src/ast.h#newcode161
src/ast.h:161: explicit AstProperties(const AstProperties& other)
Default copy constructor and assignment operator should do the right thing.

[Jakob Kummerow, 2012-02-08 09:51:02]

Thanks for the reviews. 
Nits are fixed, landing.

https://chromiumcodereview.appspot.com/9221011/diff/19001/src/ast.h
File src/ast.h (right):

https://chromiumcodereview.appspot.com/9221011/diff/19001/src/ast.h#newcode148
src/ast.h:148: kDontCrankshaft,
On 2012/02/08 09:13:18, Kevin Millikin wrote:
> To be pedantic (everybody loves that), "Crankshaft" is the name of the entire
> backend, not just the optimizing compiler.  And it's not a verb anyway.  I
> suggest "kDontOptimize".

Done.

https://chromiumcodereview.appspot.com/9221011/diff/19001/src/ast.h#newcode161
src/ast.h:161: explicit AstProperties(const AstProperties& other)
On 2012/02/08 09:13:18, Kevin Millikin wrote:
> Default copy constructor and assignment operator should do the right thing.

Done.