diff options
| author | Steve Block <steveblock@google.com> | 2010-05-10 14:33:55 +0100 |
|---|---|---|
| committer | Steve Block <steveblock@google.com> | 2010-05-10 15:08:22 +0100 |
| commit | 6ded16be15dd865a9b21ea304d5273c8be299c87 (patch) | |
| tree | b3661ae5d929e233f7024223f3fad0f2a284cd6e /src/data-flow.cc | |
| parent | 6599b9dd3411791c9d89ab7efbfb4131e5664c48 (diff) | |
| download | android_external_v8-6ded16be15dd865a9b21ea304d5273c8be299c87.tar.gz android_external_v8-6ded16be15dd865a9b21ea304d5273c8be299c87.tar.bz2 android_external_v8-6ded16be15dd865a9b21ea304d5273c8be299c87.zip | |
Update V8 to r4588
We're using WebKit r58033, as used by
http://src.chromium.org/svn/releases/5.0.387.0/DEPS
This requires http://v8.googlecode.com/svn/trunk@4465 but this version has a
crashing bug for ARM. Instead we use http://v8.googlecode.com/svn/trunk@4588,
which is used by http://src.chromium.org/svn/releases/6.0.399.0/DEPS
Note that a trivial bug fix was required in arm/codegen-arm.cc. This is guarded
with ANDROID. See http://code.google.com/p/v8/issues/detail?id=703
Change-Id: I459647a8286c4f8c7405f0c5581ecbf051a6f1e8
Diffstat (limited to 'src/data-flow.cc')
| -rw-r--r-- | src/data-flow.cc | 482 |
1 files changed, 338 insertions, 144 deletions
diff --git a/src/data-flow.cc b/src/data-flow.cc index 5e9d217d..4e7620ac 100644 --- a/src/data-flow.cc +++ b/src/data-flow.cc @@ -28,11 +28,28 @@ #include "v8.h" #include "data-flow.h" +#include "scopes.h" namespace v8 { namespace internal { +#ifdef DEBUG +void BitVector::Print() { + bool first = true; + PrintF("{"); + for (int i = 0; i < length(); i++) { + if (Contains(i)) { + if (!first) PrintF(","); + first = false; + PrintF("%d"); + } + } + PrintF("}"); +} +#endif + + void AstLabeler::Label(CompilationInfo* info) { info_ = info; VisitStatements(info_->function()->body()); @@ -145,8 +162,8 @@ void AstLabeler::VisitFunctionLiteral(FunctionLiteral* expr) { } -void AstLabeler::VisitFunctionBoilerplateLiteral( - FunctionBoilerplateLiteral* expr) { +void AstLabeler::VisitSharedFunctionInfoLiteral( + SharedFunctionInfoLiteral* expr) { UNREACHABLE(); } @@ -204,6 +221,9 @@ void AstLabeler::VisitAssignment(Assignment* expr) { USE(proxy); ASSERT(proxy != NULL && proxy->var()->is_this()); info()->set_has_this_properties(true); + + prop->obj()->set_num(AstNode::kNoNumber); + prop->key()->set_num(AstNode::kNoNumber); Visit(expr->value()); expr->set_num(next_number_++); } @@ -220,6 +240,9 @@ void AstLabeler::VisitProperty(Property* expr) { USE(proxy); ASSERT(proxy != NULL && proxy->var()->is_this()); info()->set_has_this_properties(true); + + expr->obj()->set_num(AstNode::kNoNumber); + expr->key()->set_num(AstNode::kNoNumber); expr->set_num(next_number_++); } @@ -271,289 +294,460 @@ void AstLabeler::VisitDeclaration(Declaration* decl) { } -ZoneList<Expression*>* VarUseMap::Lookup(Variable* var) { - HashMap::Entry* entry = HashMap::Lookup(var, var->name()->Hash(), true); - if (entry->value == NULL) { - entry->value = new ZoneList<Expression*>(1); - } - return reinterpret_cast<ZoneList<Expression*>*>(entry->value); -} +AssignedVariablesAnalyzer::AssignedVariablesAnalyzer(FunctionLiteral* fun) + : fun_(fun), + av_(fun->scope()->num_parameters() + fun->scope()->num_stack_slots()) {} -void LivenessAnalyzer::Analyze(FunctionLiteral* fun) { - // Process the function body. - VisitStatements(fun->body()); - - // All variables are implicitly defined at the function start. - // Record a definition of all variables live at function entry. - for (HashMap::Entry* p = live_vars_.Start(); - p != NULL; - p = live_vars_.Next(p)) { - Variable* var = reinterpret_cast<Variable*>(p->key); - RecordDef(var, fun); - } +void AssignedVariablesAnalyzer::Analyze() { + ASSERT(av_.length() > 0); + VisitStatements(fun_->body()); } -void LivenessAnalyzer::VisitStatements(ZoneList<Statement*>* stmts) { - // Visit statements right-to-left. - for (int i = stmts->length() - 1; i >= 0; i--) { - Visit(stmts->at(i)); +Variable* AssignedVariablesAnalyzer::FindSmiLoopVariable(ForStatement* stmt) { + // The loop must have all necessary parts. + if (stmt->init() == NULL || stmt->cond() == NULL || stmt->next() == NULL) { + return NULL; + } + // The initialization statement has to be a simple assignment. + Assignment* init = stmt->init()->StatementAsSimpleAssignment(); + if (init == NULL) return NULL; + + // We only deal with local variables. + Variable* loop_var = init->target()->AsVariableProxy()->AsVariable(); + if (loop_var == NULL || !loop_var->IsStackAllocated()) return NULL; + + // The initial value has to be a smi. + Literal* init_lit = init->value()->AsLiteral(); + if (init_lit == NULL || !init_lit->handle()->IsSmi()) return NULL; + int init_value = Smi::cast(*init_lit->handle())->value(); + + // The condition must be a compare of variable with <, <=, >, or >=. + CompareOperation* cond = stmt->cond()->AsCompareOperation(); + if (cond == NULL) return NULL; + if (cond->op() != Token::LT + && cond->op() != Token::LTE + && cond->op() != Token::GT + && cond->op() != Token::GTE) return NULL; + + // The lhs must be the same variable as in the init expression. + if (cond->left()->AsVariableProxy()->AsVariable() != loop_var) return NULL; + + // The rhs must be a smi. + Literal* term_lit = cond->right()->AsLiteral(); + if (term_lit == NULL || !term_lit->handle()->IsSmi()) return NULL; + int term_value = Smi::cast(*term_lit->handle())->value(); + + // The count operation updates the same variable as in the init expression. + CountOperation* update = stmt->next()->StatementAsCountOperation(); + if (update == NULL) return NULL; + if (update->expression()->AsVariableProxy()->AsVariable() != loop_var) { + return NULL; } -} - -void LivenessAnalyzer::RecordUse(Variable* var, Expression* expr) { - ASSERT(var->is_global() || var->is_this()); - ZoneList<Expression*>* uses = live_vars_.Lookup(var); - uses->Add(expr); + // The direction of the count operation must agree with the start and the end + // value. We currently do not allow the initial value to be the same as the + // terminal value. This _would_ be ok as long as the loop body never executes + // or executes exactly one time. + if (init_value == term_value) return NULL; + if (init_value < term_value && update->op() != Token::INC) return NULL; + if (init_value > term_value && update->op() != Token::DEC) return NULL; + + // Check that the update operation cannot overflow the smi range. This can + // occur in the two cases where the loop bound is equal to the largest or + // smallest smi. + if (update->op() == Token::INC && term_value == Smi::kMaxValue) return NULL; + if (update->op() == Token::DEC && term_value == Smi::kMinValue) return NULL; + + // Found a smi loop variable. + return loop_var; +} + +int AssignedVariablesAnalyzer::BitIndex(Variable* var) { + ASSERT(var != NULL); + ASSERT(var->IsStackAllocated()); + Slot* slot = var->slot(); + if (slot->type() == Slot::PARAMETER) { + return slot->index(); + } else { + return fun_->scope()->num_parameters() + slot->index(); + } } -void LivenessAnalyzer::RecordDef(Variable* var, Expression* expr) { - ASSERT(var->is_global() || var->is_this()); +void AssignedVariablesAnalyzer::RecordAssignedVar(Variable* var) { + ASSERT(var != NULL); + if (var->IsStackAllocated()) { + av_.Add(BitIndex(var)); + } +} - // We do not support other expressions that can define variables. - ASSERT(expr->AsFunctionLiteral() != NULL); - // Add the variable to the list of defined variables. - if (expr->defined_vars() == NULL) { - expr->set_defined_vars(new ZoneList<DefinitionInfo*>(1)); - } - DefinitionInfo* def = new DefinitionInfo(); - expr->AsFunctionLiteral()->defined_vars()->Add(def); - - // Compute the last use of the definition. The variable uses are - // inserted in reversed evaluation order. The first element - // in the list of live uses is the last use. - ZoneList<Expression*>* uses = live_vars_.Lookup(var); - while (uses->length() > 0) { - Expression* use_site = uses->RemoveLast(); - use_site->set_var_def(def); - if (uses->length() == 0) { - def->set_last_use(use_site); - } +void AssignedVariablesAnalyzer::MarkIfTrivial(Expression* expr) { + Variable* var = expr->AsVariableProxy()->AsVariable(); + if (var != NULL && + var->IsStackAllocated() && + !var->is_arguments() && + var->mode() != Variable::CONST && + (var->is_this() || !av_.Contains(BitIndex(var)))) { + expr->AsVariableProxy()->set_is_trivial(true); } } -// Visitor functions for live variable analysis. -void LivenessAnalyzer::VisitDeclaration(Declaration* decl) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::ProcessExpression(Expression* expr) { + BitVector saved_av(av_); + av_.Clear(); + Visit(expr); + av_.Union(saved_av); } - -void LivenessAnalyzer::VisitBlock(Block* stmt) { +void AssignedVariablesAnalyzer::VisitBlock(Block* stmt) { VisitStatements(stmt->statements()); } -void LivenessAnalyzer::VisitExpressionStatement( +void AssignedVariablesAnalyzer::VisitExpressionStatement( ExpressionStatement* stmt) { - Visit(stmt->expression()); + ProcessExpression(stmt->expression()); } -void LivenessAnalyzer::VisitEmptyStatement(EmptyStatement* stmt) { +void AssignedVariablesAnalyzer::VisitEmptyStatement(EmptyStatement* stmt) { // Do nothing. } -void LivenessAnalyzer::VisitIfStatement(IfStatement* stmt) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitIfStatement(IfStatement* stmt) { + ProcessExpression(stmt->condition()); + Visit(stmt->then_statement()); + Visit(stmt->else_statement()); } -void LivenessAnalyzer::VisitContinueStatement(ContinueStatement* stmt) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitContinueStatement( + ContinueStatement* stmt) { + // Nothing to do. } -void LivenessAnalyzer::VisitBreakStatement(BreakStatement* stmt) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitBreakStatement(BreakStatement* stmt) { + // Nothing to do. } -void LivenessAnalyzer::VisitReturnStatement(ReturnStatement* stmt) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitReturnStatement(ReturnStatement* stmt) { + ProcessExpression(stmt->expression()); } -void LivenessAnalyzer::VisitWithEnterStatement( +void AssignedVariablesAnalyzer::VisitWithEnterStatement( WithEnterStatement* stmt) { - UNREACHABLE(); + ProcessExpression(stmt->expression()); } -void LivenessAnalyzer::VisitWithExitStatement(WithExitStatement* stmt) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitWithExitStatement( + WithExitStatement* stmt) { + // Nothing to do. } -void LivenessAnalyzer::VisitSwitchStatement(SwitchStatement* stmt) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitSwitchStatement(SwitchStatement* stmt) { + BitVector result(av_); + av_.Clear(); + Visit(stmt->tag()); + result.Union(av_); + for (int i = 0; i < stmt->cases()->length(); i++) { + CaseClause* clause = stmt->cases()->at(i); + if (!clause->is_default()) { + av_.Clear(); + Visit(clause->label()); + result.Union(av_); + } + VisitStatements(clause->statements()); + } + av_.Union(result); } -void LivenessAnalyzer::VisitDoWhileStatement(DoWhileStatement* stmt) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitDoWhileStatement(DoWhileStatement* stmt) { + ProcessExpression(stmt->cond()); + Visit(stmt->body()); } -void LivenessAnalyzer::VisitWhileStatement(WhileStatement* stmt) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitWhileStatement(WhileStatement* stmt) { + ProcessExpression(stmt->cond()); + Visit(stmt->body()); } -void LivenessAnalyzer::VisitForStatement(ForStatement* stmt) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitForStatement(ForStatement* stmt) { + if (stmt->init() != NULL) Visit(stmt->init()); + + if (stmt->cond() != NULL) ProcessExpression(stmt->cond()); + + if (stmt->next() != NULL) Visit(stmt->next()); + + // Process loop body. After visiting the loop body av_ contains + // the assigned variables of the loop body. + BitVector saved_av(av_); + av_.Clear(); + Visit(stmt->body()); + + Variable* var = FindSmiLoopVariable(stmt); + if (var != NULL && !av_.Contains(BitIndex(var))) { + stmt->set_loop_variable(var); + } + + av_.Union(saved_av); } -void LivenessAnalyzer::VisitForInStatement(ForInStatement* stmt) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitForInStatement(ForInStatement* stmt) { + ProcessExpression(stmt->each()); + ProcessExpression(stmt->enumerable()); + Visit(stmt->body()); } -void LivenessAnalyzer::VisitTryCatchStatement(TryCatchStatement* stmt) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitTryCatchStatement( + TryCatchStatement* stmt) { + Visit(stmt->try_block()); + Visit(stmt->catch_block()); } -void LivenessAnalyzer::VisitTryFinallyStatement( +void AssignedVariablesAnalyzer::VisitTryFinallyStatement( TryFinallyStatement* stmt) { - UNREACHABLE(); + Visit(stmt->try_block()); + Visit(stmt->finally_block()); } -void LivenessAnalyzer::VisitDebuggerStatement( +void AssignedVariablesAnalyzer::VisitDebuggerStatement( DebuggerStatement* stmt) { - UNREACHABLE(); + // Nothing to do. } -void LivenessAnalyzer::VisitFunctionLiteral(FunctionLiteral* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitFunctionLiteral(FunctionLiteral* expr) { + // Nothing to do. + ASSERT(av_.IsEmpty()); } -void LivenessAnalyzer::VisitFunctionBoilerplateLiteral( - FunctionBoilerplateLiteral* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitSharedFunctionInfoLiteral( + SharedFunctionInfoLiteral* expr) { + // Nothing to do. + ASSERT(av_.IsEmpty()); } -void LivenessAnalyzer::VisitConditional(Conditional* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitConditional(Conditional* expr) { + ASSERT(av_.IsEmpty()); + + Visit(expr->condition()); + + BitVector result(av_); + av_.Clear(); + Visit(expr->then_expression()); + result.Union(av_); + + av_.Clear(); + Visit(expr->else_expression()); + av_.Union(result); } -void LivenessAnalyzer::VisitSlot(Slot* expr) { +void AssignedVariablesAnalyzer::VisitSlot(Slot* expr) { UNREACHABLE(); } -void LivenessAnalyzer::VisitVariableProxy(VariableProxy* expr) { - Variable* var = expr->var(); - ASSERT(var->is_global()); - ASSERT(!var->is_this()); - RecordUse(var, expr); +void AssignedVariablesAnalyzer::VisitVariableProxy(VariableProxy* expr) { + // Nothing to do. + ASSERT(av_.IsEmpty()); } -void LivenessAnalyzer::VisitLiteral(Literal* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitLiteral(Literal* expr) { + // Nothing to do. + ASSERT(av_.IsEmpty()); } -void LivenessAnalyzer::VisitRegExpLiteral(RegExpLiteral* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitRegExpLiteral(RegExpLiteral* expr) { + // Nothing to do. + ASSERT(av_.IsEmpty()); } -void LivenessAnalyzer::VisitObjectLiteral(ObjectLiteral* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitObjectLiteral(ObjectLiteral* expr) { + ASSERT(av_.IsEmpty()); + BitVector result(av_.length()); + for (int i = 0; i < expr->properties()->length(); i++) { + Visit(expr->properties()->at(i)->value()); + result.Union(av_); + av_.Clear(); + } + av_ = result; } -void LivenessAnalyzer::VisitArrayLiteral(ArrayLiteral* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitArrayLiteral(ArrayLiteral* expr) { + ASSERT(av_.IsEmpty()); + BitVector result(av_.length()); + for (int i = 0; i < expr->values()->length(); i++) { + Visit(expr->values()->at(i)); + result.Union(av_); + av_.Clear(); + } + av_ = result; } -void LivenessAnalyzer::VisitCatchExtensionObject( +void AssignedVariablesAnalyzer::VisitCatchExtensionObject( CatchExtensionObject* expr) { - UNREACHABLE(); + ASSERT(av_.IsEmpty()); + Visit(expr->key()); + ProcessExpression(expr->value()); } -void LivenessAnalyzer::VisitAssignment(Assignment* expr) { +void AssignedVariablesAnalyzer::VisitAssignment(Assignment* expr) { + ASSERT(av_.IsEmpty()); + + // There are three kinds of assignments: variable assignments, property + // assignments, and reference errors (invalid left-hand sides). + Variable* var = expr->target()->AsVariableProxy()->AsVariable(); Property* prop = expr->target()->AsProperty(); - ASSERT(prop != NULL); - ASSERT(prop->key()->IsPropertyName()); - VariableProxy* proxy = prop->obj()->AsVariableProxy(); - ASSERT(proxy != NULL && proxy->var()->is_this()); + ASSERT(var == NULL || prop == NULL); + + if (var != NULL) { + MarkIfTrivial(expr->value()); + Visit(expr->value()); + if (expr->is_compound()) { + // Left-hand side occurs also as an rvalue. + MarkIfTrivial(expr->target()); + ProcessExpression(expr->target()); + } + RecordAssignedVar(var); + + } else if (prop != NULL) { + MarkIfTrivial(expr->value()); + Visit(expr->value()); + if (!prop->key()->IsPropertyName()) { + MarkIfTrivial(prop->key()); + ProcessExpression(prop->key()); + } + MarkIfTrivial(prop->obj()); + ProcessExpression(prop->obj()); - // Record use of this at the assignment node. Assignments to - // this-properties are treated like unary operations. - RecordUse(proxy->var(), expr); + } else { + Visit(expr->target()); + } +} - // Visit right-hand side. - Visit(expr->value()); + +void AssignedVariablesAnalyzer::VisitThrow(Throw* expr) { + ASSERT(av_.IsEmpty()); + Visit(expr->exception()); } -void LivenessAnalyzer::VisitThrow(Throw* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitProperty(Property* expr) { + ASSERT(av_.IsEmpty()); + if (!expr->key()->IsPropertyName()) { + MarkIfTrivial(expr->key()); + Visit(expr->key()); + } + MarkIfTrivial(expr->obj()); + ProcessExpression(expr->obj()); } -void LivenessAnalyzer::VisitProperty(Property* expr) { - ASSERT(expr->key()->IsPropertyName()); - VariableProxy* proxy = expr->obj()->AsVariableProxy(); - ASSERT(proxy != NULL && proxy->var()->is_this()); - RecordUse(proxy->var(), expr); +void AssignedVariablesAnalyzer::VisitCall(Call* expr) { + ASSERT(av_.IsEmpty()); + Visit(expr->expression()); + BitVector result(av_); + for (int i = 0; i < expr->arguments()->length(); i++) { + av_.Clear(); + Visit(expr->arguments()->at(i)); + result.Union(av_); + } + av_ = result; } -void LivenessAnalyzer::VisitCall(Call* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitCallNew(CallNew* expr) { + ASSERT(av_.IsEmpty()); + Visit(expr->expression()); + BitVector result(av_); + for (int i = 0; i < expr->arguments()->length(); i++) { + av_.Clear(); + Visit(expr->arguments()->at(i)); + result.Union(av_); + } + av_ = result; } -void LivenessAnalyzer::VisitCallNew(CallNew* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitCallRuntime(CallRuntime* expr) { + ASSERT(av_.IsEmpty()); + BitVector result(av_); + for (int i = 0; i < expr->arguments()->length(); i++) { + av_.Clear(); + Visit(expr->arguments()->at(i)); + result.Union(av_); + } + av_ = result; } -void LivenessAnalyzer::VisitCallRuntime(CallRuntime* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitUnaryOperation(UnaryOperation* expr) { + ASSERT(av_.IsEmpty()); + Visit(expr->expression()); } -void LivenessAnalyzer::VisitUnaryOperation(UnaryOperation* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitCountOperation(CountOperation* expr) { + ASSERT(av_.IsEmpty()); + + Visit(expr->expression()); + + Variable* var = expr->expression()->AsVariableProxy()->AsVariable(); + if (var != NULL) RecordAssignedVar(var); } -void LivenessAnalyzer::VisitCountOperation(CountOperation* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitBinaryOperation(BinaryOperation* expr) { + ASSERT(av_.IsEmpty()); + MarkIfTrivial(expr->right()); + Visit(expr->right()); + MarkIfTrivial(expr->left()); + ProcessExpression(expr->left()); } -void LivenessAnalyzer::VisitBinaryOperation(BinaryOperation* expr) { - // Visit child nodes in reverse evaluation order. +void AssignedVariablesAnalyzer::VisitCompareOperation(CompareOperation* expr) { + ASSERT(av_.IsEmpty()); + MarkIfTrivial(expr->right()); Visit(expr->right()); - Visit(expr->left()); + MarkIfTrivial(expr->left()); + ProcessExpression(expr->left()); } -void LivenessAnalyzer::VisitCompareOperation(CompareOperation* expr) { - UNREACHABLE(); +void AssignedVariablesAnalyzer::VisitThisFunction(ThisFunction* expr) { + // Nothing to do. + ASSERT(av_.IsEmpty()); } -void LivenessAnalyzer::VisitThisFunction(ThisFunction* expr) { +void AssignedVariablesAnalyzer::VisitDeclaration(Declaration* decl) { UNREACHABLE(); } |
