Add iterative primitive type analysis....

Add iterative primitive type analysis.

This change adds a data-flow pass to statically determine
if a variable contains a primitive type.

It requires building the flow graph and computing reaching
definitions as pre-requisites. The analysis annotates all
VariableProxy nodes with the result.


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

[fschneider, 2010-03-22 21:34:26]

First version.

[Kevin Millikin (Chromium), 2010-03-23 07:52:42]

Initial comments.  Overall looks about right.

http://codereview.chromium.org/1132005/diff/1/8
File src/ast.cc (right):

http://codereview.chromium.org/1132005/diff/1/8#newcode523
src/ast.cc:523: bool VariableProxy::IsPrimitive() { return is_primitive_; }
Move this function after the "not primitive" section and add a comment to the
effect that variable references are primitive unless the primitivity (?)
analysis determines they aren't.

Also, you may want to consider parameters rewritten as explicit arguments
accesses.  They are aliased by the arguments object, so the safe thing is to
conclude not primitive.

http://codereview.chromium.org/1132005/diff/1/4
File src/data-flow.cc (right):

http://codereview.chromium.org/1132005/diff/1/4#newcode2009
src/data-flow.cc:2009: while (changed) {
This is a case where it might be clearer to have a do...while loop?

http://codereview.chromium.org/1132005/diff/1/4#newcode2016
src/data-flow.cc:2016: for (int i = 0; i < postorder_->length(); i++) {
I wonder if we converge in one fewer iteration if we iterate this list in
reverse?

http://codereview.chromium.org/1132005/diff/1/4#newcode2018
src/data-flow.cc:2018: if (node->IsBlockNode()) {
Since we control the Node class and don't have external clients, we could just
add a virtual AnalyzeTypes function that performs the body of this if for
BlockNodes and nothing for the other node types.

Advantage is that we don't have to expose as much of the structure of the block
nodes (eg, instructions() array).  Disadvantage is that it's not inlined at the
call site.

http://codereview.chromium.org/1132005/diff/1/7
File src/data-flow.h (right):

http://codereview.chromium.org/1132005/diff/1/7#newcode217
src/data-flow.h:217: virtual BlockNode* AsBlockNode() { return NULL; }
There are two kinds of type testing/casting used in V8: separate virtual IsXXX
predicate and static XXX:cast (a la objects.h) and unified virtual AsXXX (a la
ast.h).

I prefer the former and was using it here.  You could convince me to use the
latter instead, but I don't think there's any reason to mix them.

http://codereview.chromium.org/1132005/diff/1/7#newcode645
src/data-flow.h:645: bool IsPrimitiveDef(int i);
Small comment needed for this function, especially since the name "i" is so
generic.

[fschneider, 2010-03-23 11:39:14]

http://codereview.chromium.org/1132005/diff/1/8
File src/ast.cc (right):

http://codereview.chromium.org/1132005/diff/1/8#newcode523
src/ast.cc:523: bool VariableProxy::IsPrimitive() { return is_primitive_; }
On 2010/03/23 07:52:42, Kevin Millikin wrote:
> Move this function after the "not primitive" section and add a comment to the
> effect that variable references are primitive unless the primitivity (?)
> analysis determines they aren't.
> 
> Also, you may want to consider parameters rewritten as explicit arguments
> accesses.  They are aliased by the arguments object, so the safe thing is to
> conclude not primitive.

Maybe it's simpler for now to handle arguments accesses in the reaching
definitions. i.e. variables rewritten as arguments access have
(reaching_definitions() == NULL).

http://codereview.chromium.org/1132005/diff/1/4
File src/data-flow.cc (right):

http://codereview.chromium.org/1132005/diff/1/4#newcode2009
src/data-flow.cc:2009: while (changed) {
On 2010/03/23 07:52:42, Kevin Millikin wrote:
> This is a case where it might be clearer to have a do...while loop?

Done.

http://codereview.chromium.org/1132005/diff/1/4#newcode2016
src/data-flow.cc:2016: for (int i = 0; i < postorder_->length(); i++) {
On 2010/03/23 07:52:42, Kevin Millikin wrote:
> I wonder if we converge in one fewer iteration if we iterate this list in
> reverse?

True. That would be reverse-post-order. I changed it, but for the programs I
looked at it made no difference.

http://codereview.chromium.org/1132005/diff/1/4#newcode2018
src/data-flow.cc:2018: if (node->IsBlockNode()) {
On 2010/03/23 07:52:42, Kevin Millikin wrote:
> Since we control the Node class and don't have external clients, we could just
> add a virtual AnalyzeTypes function that performs the body of this if for
> BlockNodes and nothing for the other node types.
> 
> Advantage is that we don't have to expose as much of the structure of the
block
> nodes (eg, instructions() array).  Disadvantage is that it's not inlined at
the
> call site.

I considered that too - since there is only work to be done for BlockNode I
thought it's ok to just handle that case locally here.

http://codereview.chromium.org/1132005/diff/1/7
File src/data-flow.h (right):

http://codereview.chromium.org/1132005/diff/1/7#newcode217
src/data-flow.h:217: virtual BlockNode* AsBlockNode() { return NULL; }
On 2010/03/23 07:52:42, Kevin Millikin wrote:
> There are two kinds of type testing/casting used in V8: separate virtual IsXXX
> predicate and static XXX:cast (a la objects.h) and unified virtual AsXXX (a la
> ast.h).
> 
> I prefer the former and was using it here.  You could convince me to use the
> latter instead, but I don't think there's any reason to mix them.

Done. I overlooked that there are existing casting function already. Otherwise I
would spend the effort adding extra ones :)

http://codereview.chromium.org/1132005/diff/1/7#newcode645
src/data-flow.h:645: bool IsPrimitiveDef(int i);
On 2010/03/23 07:52:42, Kevin Millikin wrote:
> Small comment needed for this function, especially since the name "i" is so
> generic.

Done.

[Kevin Millikin (Chromium), 2010-03-23 12:41:14]

LGTM.

http://codereview.chromium.org/1132005/diff/19001/2008
File src/data-flow.h (right):

http://codereview.chromium.org/1132005/diff/19001/2008#newcode208
src/data-flow.h:208: class BlockNode;
No longer needed.

http://codereview.chromium.org/1132005/diff/19001/2003
File src/prettyprinter.cc (right):

http://codereview.chromium.org/1132005/diff/19001/2003#newcode17
src/prettyprinter.cc:17: // "AS IS" AND ANY EXPRESS OR IMPLID WARRANTIES,
INCLUDING, BUT NOT
Inadvertent change?

[fschneider, 2010-03-23 12:59:42]

http://codereview.chromium.org/1132005/diff/19001/2008
File src/data-flow.h (right):

http://codereview.chromium.org/1132005/diff/19001/2008#newcode208
src/data-flow.h:208: class BlockNode;
On 2010/03/23 12:41:14, Kevin Millikin wrote:
> No longer needed.

Done.

http://codereview.chromium.org/1132005/diff/19001/2003
File src/prettyprinter.cc (right):

http://codereview.chromium.org/1132005/diff/19001/2003#newcode17
src/prettyprinter.cc:17: // "AS IS" AND ANY EXPRESS OR IMPLID WARRANTIES,
INCLUDING, BUT NOT
On 2010/03/23 12:41:14, Kevin Millikin wrote:
> Inadvertent change?

Oops. Done.