Add last use data flow information to the fast code generator....

Add last use data flow information to the fast code generator.

This change add simple local live variable information to 
the fast code generator.  It supports only AST nodes that 
are accepted by the syntax checker.

Each variable use points to a variable definition structure
which contains the last use of the definition.

To determine whether a variable is live after a certain point
we can check whether its last use occurs later in the evaluation
order defined by the AST labeling number.

The new information is currently only printed out together with
the IR and not yet used for code generation.


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

[fschneider, 2010-02-10 14:46:38]

This first change is just the new data flow pass. Allocating 
registers will be a separate change.

[Kevin Millikin (Chromium), 2010-02-11 13:40:39]

Comments below.

http://codereview.chromium.org/603004/diff/1/4
File src/ast.h (right):

http://codereview.chromium.org/603004/diff/1/4#newcode105
src/ast.h:105: class VarDef;
I prefer slightly longer names.

http://codereview.chromium.org/603004/diff/1/4#newcode216
src/ast.h:216: VarDef* var_def() { return def_; }
As discussed, it will soon be possible to have multiple variable uses in the
same AST expression node.

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

http://codereview.chromium.org/603004/diff/1/3#newcode277
src/data-flow.cc:277: entry->value = new ZoneList<Expression*>(1);
ZoneLists have bad resizing behavior.  If you create it with backing store of
size 1, it will resize to 2 on the second insertion; resize to 4 on the third
insertion; and resize to 7 on the fifth insertion.

On the one hand we don't want to be frequently resizing but on the other we
don't want to waste space per variable def if they don't have a lot of uses.

We should investigate a way to thread the uses into a linked list during the
analysis using their definition pointer.

http://codereview.chromium.org/603004/diff/1/3#newcode307
src/data-flow.cc:307: if (!var->is_global()) {
ASSERT(var->is_global() || var->is_this());

http://codereview.chromium.org/603004/diff/1/3#newcode316
src/data-flow.cc:316: if (!var->is_global()) {
ASSERT(var->is_global() || var->is_this());

http://codereview.chromium.org/603004/diff/1/3#newcode505
src/data-flow.cc:505: // Visit left-hand side.
right-hand :)

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

http://codereview.chromium.org/603004/diff/1/6#newcode65
src/data-flow.h:65: class VarUseMap : public HashMap {
As discussed, a HashMap will not scale as soon as we need to support set union
and difference.

I think it's OK to commit it with the HashMap, but it should be replaced before
or immediately after we start handling control flow.

http://codereview.chromium.org/603004/diff/1/6#newcode73
src/data-flow.h:73: static uint32_t ComputeHash(Variable* var);
It looks like this is an unused declaration?

http://codereview.chromium.org/603004/diff/1/6#newcode90
src/data-flow.h:90: class LiveVariableAnalysis : public AstVisitor {
This class computes the analysis or performs the analysis.  Perhaps a better
name is LivenessAnalyzer.

http://codereview.chromium.org/603004/diff/1/6#newcode94
src/data-flow.h:94: void DoAnalysis(FunctionLiteral* fun);
"Analyze" means the same as "DoAnalysis" and reads a bit better.

http://codereview.chromium.org/603004/diff/1/6#newcode97
src/data-flow.h:97: void VisitStmtsBackwards(ZoneList<Statement*>* stmts);
Just call this VisitStatements.  Backwards could mean "right-to-left" or it
could mean "in the opposite direction this pass usually uses".

http://codereview.chromium.org/603004/diff/1/6#newcode100
src/data-flow.h:100: void RecurdUseDefChain(ZoneList<Expression*>* uses,
Expression* def);
Spelling?  Unused declaration?

http://codereview.chromium.org/603004/diff/1/5
File src/fast-codegen.cc (right):

http://codereview.chromium.org/603004/diff/1/5#newcode431
src/fast-codegen.cc:431: LiveVariableAnalysis lva;
LivenessAnalyzer analyzer;
analyzer.Analyze(info->function());

http://codereview.chromium.org/603004/diff/1/5#newcode590
src/fast-codegen.cc:590: PrintF("%d: t%d = Global(%s)  // last_use = %d\n",
expr->num(),
OK for now, but probably more useful to have "// def = #", and at the definition
site "// a: last use = #".

[fschneider, 2010-02-11 14:39:21]

http://codereview.chromium.org/603004/diff/1/4
File src/ast.h (right):

http://codereview.chromium.org/603004/diff/1/4#newcode105
src/ast.h:105: class VarDef;
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> I prefer slightly longer names.

Agree. I couldn't come up with sth more meaningful. Maybe VarDefInfo or
DefinitionInfo?

http://codereview.chromium.org/603004/diff/1/4#newcode216
src/ast.h:216: VarDef* var_def() { return def_; }
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> As discussed, it will soon be possible to have multiple variable uses in the
> same AST expression node.

Yes, we need some way of abstracting this so that we can support ast nodes with
0, 1, 2, possibly >=3 uses.

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

http://codereview.chromium.org/603004/diff/1/3#newcode277
src/data-flow.cc:277: entry->value = new ZoneList<Expression*>(1);
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> ZoneLists have bad resizing behavior.  If you create it with backing store of
> size 1, it will resize to 2 on the second insertion; resize to 4 on the third
> insertion; and resize to 7 on the fifth insertion.
> 
> On the one hand we don't want to be frequently resizing but on the other we
> don't want to waste space per variable def if they don't have a lot of uses.
> 
> We should investigate a way to thread the uses into a linked list during the
> analysis using their definition pointer.

Agree.

http://codereview.chromium.org/603004/diff/1/3#newcode307
src/data-flow.cc:307: if (!var->is_global()) {
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> ASSERT(var->is_global() || var->is_this());

Done.

http://codereview.chromium.org/603004/diff/1/3#newcode316
src/data-flow.cc:316: if (!var->is_global()) {
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> ASSERT(var->is_global() || var->is_this());

Done.

http://codereview.chromium.org/603004/diff/1/3#newcode505
src/data-flow.cc:505: // Visit left-hand side.
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> right-hand :)

Done. One of those days where I mix up left and right :)

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

http://codereview.chromium.org/603004/diff/1/6#newcode65
src/data-flow.h:65: class VarUseMap : public HashMap {
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> As discussed, a HashMap will not scale as soon as we need to support set union
> and difference.
> 
> I think it's OK to commit it with the HashMap, but it should be replaced
before
> or immediately after we start handling control flow.

Yes.

http://codereview.chromium.org/603004/diff/1/6#newcode73
src/data-flow.h:73: static uint32_t ComputeHash(Variable* var);
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> It looks like this is an unused declaration?

Done. Removed.

http://codereview.chromium.org/603004/diff/1/6#newcode90
src/data-flow.h:90: class LiveVariableAnalysis : public AstVisitor {
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> This class computes the analysis or performs the analysis.  Perhaps a better
> name is LivenessAnalyzer.

Done.

http://codereview.chromium.org/603004/diff/1/6#newcode94
src/data-flow.h:94: void DoAnalysis(FunctionLiteral* fun);
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> "Analyze" means the same as "DoAnalysis" and reads a bit better.

Done.

http://codereview.chromium.org/603004/diff/1/6#newcode97
src/data-flow.h:97: void VisitStmtsBackwards(ZoneList<Statement*>* stmts);
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> Just call this VisitStatements.  Backwards could mean "right-to-left" or it
> could mean "in the opposite direction this pass usually uses".

Done.

http://codereview.chromium.org/603004/diff/1/6#newcode100
src/data-flow.h:100: void RecurdUseDefChain(ZoneList<Expression*>* uses,
Expression* def);
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> Spelling?  Unused declaration?

Done. Removed.

http://codereview.chromium.org/603004/diff/1/5
File src/fast-codegen.cc (right):

http://codereview.chromium.org/603004/diff/1/5#newcode431
src/fast-codegen.cc:431: LiveVariableAnalysis lva;
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> LivenessAnalyzer analyzer;
> analyzer.Analyze(info->function());

Done.

http://codereview.chromium.org/603004/diff/1/5#newcode590
src/fast-codegen.cc:590: PrintF("%d: t%d = Global(%s)  // last_use = %d\n",
expr->num(),
On 2010/02/11 13:40:39, Kevin Millikin wrote:
> OK for now, but probably more useful to have "// def = #", and at the
definition
> site "// a: last use = #".

I think I keep the output for now as is (we have only 1 definition at the start
of the function now.) 

We also may add more info about allocated registers later. On the other hand it
should be still well readable.