diff options
author | Steve Block <steveblock@google.com> | 2009-10-30 11:49:00 +0000 |
---|---|---|
committer | Steve Block <steveblock@google.com> | 2009-11-03 17:23:38 +0000 |
commit | a7e24c173cf37484693b9abb38e494fa7bd7baeb (patch) | |
tree | 4aeefe31292fbed0d94f1b93fe86c51849b001c2 /src/rewriter.cc | |
parent | af654c46444383e0baed1cb27a4c1d1bdcac8dd9 (diff) | |
download | android_external_v8-a7e24c173cf37484693b9abb38e494fa7bd7baeb.tar.gz android_external_v8-a7e24c173cf37484693b9abb38e494fa7bd7baeb.tar.bz2 android_external_v8-a7e24c173cf37484693b9abb38e494fa7bd7baeb.zip |
Move V8 to external/v8
Change-Id: If68025d67453785a651c5dfb34fad298c16676a4
Diffstat (limited to 'src/rewriter.cc')
-rw-r--r-- | src/rewriter.cc | 831 |
1 files changed, 831 insertions, 0 deletions
diff --git a/src/rewriter.cc b/src/rewriter.cc new file mode 100644 index 00000000..11fc071f --- /dev/null +++ b/src/rewriter.cc @@ -0,0 +1,831 @@ +// Copyright 2006-2008 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include "v8.h" + +#include "ast.h" +#include "func-name-inferrer.h" +#include "scopes.h" +#include "rewriter.h" + +namespace v8 { +namespace internal { + + +class AstOptimizer: public AstVisitor { + public: + explicit AstOptimizer() : has_function_literal_(false) {} + explicit AstOptimizer(Handle<String> enclosing_name) + : has_function_literal_(false) { + func_name_inferrer_.PushEnclosingName(enclosing_name); + } + + void Optimize(ZoneList<Statement*>* statements); + + private: + // Used for loop condition analysis. Cleared before visiting a loop + // condition, set when a function literal is visited. + bool has_function_literal_; + // Helper object for function name inferring. + FuncNameInferrer func_name_inferrer_; + + // Helpers + void OptimizeArguments(ZoneList<Expression*>* arguments); + + // Node visitors. +#define DEF_VISIT(type) \ + virtual void Visit##type(type* node); + AST_NODE_LIST(DEF_VISIT) +#undef DEF_VISIT + + DISALLOW_COPY_AND_ASSIGN(AstOptimizer); +}; + + +void AstOptimizer::Optimize(ZoneList<Statement*>* statements) { + int len = statements->length(); + for (int i = 0; i < len; i++) { + Visit(statements->at(i)); + } +} + + +void AstOptimizer::OptimizeArguments(ZoneList<Expression*>* arguments) { + for (int i = 0; i < arguments->length(); i++) { + Visit(arguments->at(i)); + } +} + + +void AstOptimizer::VisitBlock(Block* node) { + Optimize(node->statements()); +} + + +void AstOptimizer::VisitExpressionStatement(ExpressionStatement* node) { + Visit(node->expression()); +} + + +void AstOptimizer::VisitIfStatement(IfStatement* node) { + Visit(node->condition()); + Visit(node->then_statement()); + if (node->HasElseStatement()) { + Visit(node->else_statement()); + } +} + + +void AstOptimizer::VisitLoopStatement(LoopStatement* node) { + if (node->init() != NULL) { + Visit(node->init()); + } + if (node->cond() != NULL) { + has_function_literal_ = false; + Visit(node->cond()); + node->may_have_function_literal_ = has_function_literal_; + } + if (node->body() != NULL) { + Visit(node->body()); + } + if (node->next() != NULL) { + Visit(node->next()); + } +} + + +void AstOptimizer::VisitForInStatement(ForInStatement* node) { + Visit(node->each()); + Visit(node->enumerable()); + Visit(node->body()); +} + + +void AstOptimizer::VisitTryCatch(TryCatch* node) { + Visit(node->try_block()); + Visit(node->catch_var()); + Visit(node->catch_block()); +} + + +void AstOptimizer::VisitTryFinally(TryFinally* node) { + Visit(node->try_block()); + Visit(node->finally_block()); +} + + +void AstOptimizer::VisitSwitchStatement(SwitchStatement* node) { + Visit(node->tag()); + for (int i = 0; i < node->cases()->length(); i++) { + CaseClause* clause = node->cases()->at(i); + if (!clause->is_default()) { + Visit(clause->label()); + } + Optimize(clause->statements()); + } +} + + +void AstOptimizer::VisitContinueStatement(ContinueStatement* node) { + USE(node); +} + + +void AstOptimizer::VisitBreakStatement(BreakStatement* node) { + USE(node); +} + + +void AstOptimizer::VisitDeclaration(Declaration* node) { + // Will not be reached by the current optimizations. + USE(node); +} + + +void AstOptimizer::VisitEmptyStatement(EmptyStatement* node) { + USE(node); +} + + +void AstOptimizer::VisitReturnStatement(ReturnStatement* node) { + Visit(node->expression()); +} + + +void AstOptimizer::VisitWithEnterStatement(WithEnterStatement* node) { + Visit(node->expression()); +} + + +void AstOptimizer::VisitWithExitStatement(WithExitStatement* node) { + USE(node); +} + + +void AstOptimizer::VisitDebuggerStatement(DebuggerStatement* node) { + USE(node); +} + + +void AstOptimizer::VisitFunctionLiteral(FunctionLiteral* node) { + has_function_literal_ = true; + + if (node->name()->length() == 0) { + // Anonymous function. + func_name_inferrer_.AddFunction(node); + } +} + + +void AstOptimizer::VisitFunctionBoilerplateLiteral( + FunctionBoilerplateLiteral* node) { + USE(node); +} + + +void AstOptimizer::VisitConditional(Conditional* node) { + Visit(node->condition()); + Visit(node->then_expression()); + Visit(node->else_expression()); +} + + +void AstOptimizer::VisitSlot(Slot* node) { + USE(node); +} + + +void AstOptimizer::VisitVariableProxy(VariableProxy* node) { + Variable* var = node->AsVariable(); + if (var != NULL) { + if (var->type()->IsKnown()) { + node->type()->CopyFrom(var->type()); + } else if (node->type()->IsLikelySmi()) { + var->type()->SetAsLikelySmi(); + } + + if (!var->is_this() && + !Heap::result_symbol()->Equals(*var->name())) { + func_name_inferrer_.PushName(var->name()); + } + } +} + + +void AstOptimizer::VisitLiteral(Literal* node) { + Handle<Object> literal = node->handle(); + if (literal->IsSmi()) { + node->type()->SetAsLikelySmi(); + } else if (literal->IsString()) { + Handle<String> lit_str(Handle<String>::cast(literal)); + if (!Heap::prototype_symbol()->Equals(*lit_str)) { + func_name_inferrer_.PushName(lit_str); + } + } +} + + +void AstOptimizer::VisitRegExpLiteral(RegExpLiteral* node) { + USE(node); +} + + +void AstOptimizer::VisitArrayLiteral(ArrayLiteral* node) { + for (int i = 0; i < node->values()->length(); i++) { + Visit(node->values()->at(i)); + } +} + +void AstOptimizer::VisitObjectLiteral(ObjectLiteral* node) { + for (int i = 0; i < node->properties()->length(); i++) { + ScopedFuncNameInferrer scoped_fni(&func_name_inferrer_); + scoped_fni.Enter(); + Visit(node->properties()->at(i)->key()); + Visit(node->properties()->at(i)->value()); + } +} + + +void AstOptimizer::VisitCatchExtensionObject(CatchExtensionObject* node) { + Visit(node->key()); + Visit(node->value()); +} + + +void AstOptimizer::VisitAssignment(Assignment* node) { + ScopedFuncNameInferrer scoped_fni(&func_name_inferrer_); + switch (node->op()) { + case Token::INIT_VAR: + case Token::INIT_CONST: + case Token::ASSIGN: + // No type can be infered from the general assignment. + + // Don't infer if it is "a = function(){...}();"-like expression. + if (node->value()->AsCall() == NULL) { + scoped_fni.Enter(); + } + break; + case Token::ASSIGN_BIT_OR: + case Token::ASSIGN_BIT_XOR: + case Token::ASSIGN_BIT_AND: + case Token::ASSIGN_SHL: + case Token::ASSIGN_SAR: + case Token::ASSIGN_SHR: + node->type()->SetAsLikelySmiIfUnknown(); + node->target()->type()->SetAsLikelySmiIfUnknown(); + node->value()->type()->SetAsLikelySmiIfUnknown(); + break; + case Token::ASSIGN_ADD: + case Token::ASSIGN_SUB: + case Token::ASSIGN_MUL: + case Token::ASSIGN_DIV: + case Token::ASSIGN_MOD: + if (node->type()->IsLikelySmi()) { + node->target()->type()->SetAsLikelySmiIfUnknown(); + node->value()->type()->SetAsLikelySmiIfUnknown(); + } + break; + default: + UNREACHABLE(); + break; + } + + Visit(node->target()); + Visit(node->value()); + + switch (node->op()) { + case Token::INIT_VAR: + case Token::INIT_CONST: + case Token::ASSIGN: + // Pure assignment copies the type from the value. + node->type()->CopyFrom(node->value()->type()); + break; + case Token::ASSIGN_BIT_OR: + case Token::ASSIGN_BIT_XOR: + case Token::ASSIGN_BIT_AND: + case Token::ASSIGN_SHL: + case Token::ASSIGN_SAR: + case Token::ASSIGN_SHR: + // Should have been setup above already. + break; + case Token::ASSIGN_ADD: + case Token::ASSIGN_SUB: + case Token::ASSIGN_MUL: + case Token::ASSIGN_DIV: + case Token::ASSIGN_MOD: + if (node->type()->IsUnknown()) { + if (node->target()->type()->IsLikelySmi() || + node->value()->type()->IsLikelySmi()) { + node->type()->SetAsLikelySmi(); + } + } + break; + default: + UNREACHABLE(); + break; + } + + // Since this is an assignment. We have to propagate this node's type to the + // variable. + VariableProxy* proxy = node->target()->AsVariableProxy(); + if (proxy != NULL) { + Variable* var = proxy->AsVariable(); + if (var != NULL) { + SmiAnalysis* var_type = var->type(); + if (var_type->IsUnknown()) { + var_type->CopyFrom(node->type()); + } else if (var_type->IsLikelySmi()) { + // We do not reset likely types to Unknown. + } + } + } +} + + +void AstOptimizer::VisitThrow(Throw* node) { + Visit(node->exception()); +} + + +void AstOptimizer::VisitProperty(Property* node) { + Visit(node->obj()); + Visit(node->key()); +} + + +void AstOptimizer::VisitCall(Call* node) { + Visit(node->expression()); + OptimizeArguments(node->arguments()); +} + + +void AstOptimizer::VisitCallNew(CallNew* node) { + Visit(node->expression()); + OptimizeArguments(node->arguments()); +} + + +void AstOptimizer::VisitCallRuntime(CallRuntime* node) { + ScopedFuncNameInferrer scoped_fni(&func_name_inferrer_); + if (Factory::InitializeVarGlobal_symbol()->Equals(*node->name()) && + node->arguments()->length() >= 2 && + node->arguments()->at(1)->AsFunctionLiteral() != NULL) { + scoped_fni.Enter(); + } + OptimizeArguments(node->arguments()); +} + + +void AstOptimizer::VisitUnaryOperation(UnaryOperation* node) { + Visit(node->expression()); +} + + +void AstOptimizer::VisitCountOperation(CountOperation* node) { + // Count operations assume that they work on Smis. + node->type()->SetAsLikelySmiIfUnknown(); + node->expression()->type()->SetAsLikelySmiIfUnknown(); + Visit(node->expression()); +} + + +void AstOptimizer::VisitBinaryOperation(BinaryOperation* node) { + // Depending on the operation we can propagate this node's type down the + // AST nodes. + switch (node->op()) { + case Token::COMMA: + case Token::OR: + case Token::AND: + break; + case Token::BIT_OR: + case Token::BIT_XOR: + case Token::BIT_AND: + case Token::SHL: + case Token::SAR: + case Token::SHR: + node->type()->SetAsLikelySmiIfUnknown(); + node->left()->type()->SetAsLikelySmiIfUnknown(); + node->right()->type()->SetAsLikelySmiIfUnknown(); + break; + case Token::ADD: + case Token::SUB: + case Token::MUL: + case Token::DIV: + case Token::MOD: + if (node->type()->IsLikelySmi()) { + node->left()->type()->SetAsLikelySmiIfUnknown(); + node->right()->type()->SetAsLikelySmiIfUnknown(); + } + break; + default: + UNREACHABLE(); + break; + } + + Visit(node->left()); + Visit(node->right()); + + // After visiting the operand nodes we have to check if this node's type + // can be updated. If it does, then we can push that information down + // towards the leafs again if the new information is an upgrade over the + // previous type of the operand nodes. + if (node->type()->IsUnknown()) { + if (node->left()->type()->IsLikelySmi() || + node->right()->type()->IsLikelySmi()) { + node->type()->SetAsLikelySmi(); + } + if (node->type()->IsLikelySmi()) { + // The type of this node changed to LIKELY_SMI. Propagate this knowledge + // down through the nodes. + if (node->left()->type()->IsUnknown()) { + node->left()->type()->SetAsLikelySmi(); + Visit(node->left()); + } + if (node->right()->type()->IsUnknown()) { + node->right()->type()->SetAsLikelySmi(); + Visit(node->right()); + } + } + } +} + + +void AstOptimizer::VisitCompareOperation(CompareOperation* node) { + if (node->type()->IsKnown()) { + // Propagate useful information down towards the leafs. + node->left()->type()->SetAsLikelySmiIfUnknown(); + node->right()->type()->SetAsLikelySmiIfUnknown(); + } + + Visit(node->left()); + Visit(node->right()); + + // After visiting the operand nodes we have to check if this node's type + // can be updated. If it does, then we can push that information down + // towards the leafs again if the new information is an upgrade over the + // previous type of the operand nodes. + if (node->type()->IsUnknown()) { + if (node->left()->type()->IsLikelySmi() || + node->right()->type()->IsLikelySmi()) { + node->type()->SetAsLikelySmi(); + } + if (node->type()->IsLikelySmi()) { + // The type of this node changed to LIKELY_SMI. Propagate this knowledge + // down through the nodes. + if (node->left()->type()->IsUnknown()) { + node->left()->type()->SetAsLikelySmi(); + Visit(node->left()); + } + if (node->right()->type()->IsUnknown()) { + node->right()->type()->SetAsLikelySmi(); + Visit(node->right()); + } + } + } +} + + +void AstOptimizer::VisitThisFunction(ThisFunction* node) { + USE(node); +} + + +class Processor: public AstVisitor { + public: + explicit Processor(VariableProxy* result) + : result_(result), + result_assigned_(false), + is_set_(false), + in_try_(false) { + } + + void Process(ZoneList<Statement*>* statements); + bool result_assigned() const { return result_assigned_; } + + private: + VariableProxy* result_; + + // We are not tracking result usage via the result_'s use + // counts (we leave the accurate computation to the + // usage analyzer). Instead we simple remember if + // there was ever an assignment to result_. + bool result_assigned_; + + // To avoid storing to .result all the time, we eliminate some of + // the stores by keeping track of whether or not we're sure .result + // will be overwritten anyway. This is a bit more tricky than what I + // was hoping for + bool is_set_; + bool in_try_; + + Expression* SetResult(Expression* value) { + result_assigned_ = true; + return new Assignment(Token::ASSIGN, result_, value, + RelocInfo::kNoPosition); + } + + // Node visitors. +#define DEF_VISIT(type) \ + virtual void Visit##type(type* node); + AST_NODE_LIST(DEF_VISIT) +#undef DEF_VISIT +}; + + +void Processor::Process(ZoneList<Statement*>* statements) { + for (int i = statements->length() - 1; i >= 0; --i) { + Visit(statements->at(i)); + } +} + + +void Processor::VisitBlock(Block* node) { + // An initializer block is the rewritten form of a variable declaration + // with initialization expressions. The initializer block contains the + // list of assignments corresponding to the initialization expressions. + // While unclear from the spec (ECMA-262, 3rd., 12.2), the value of + // a variable declaration with initialization expression is 'undefined' + // with some JS VMs: For instance, using smjs, print(eval('var x = 7')) + // returns 'undefined'. To obtain the same behavior with v8, we need + // to prevent rewriting in that case. + if (!node->is_initializer_block()) Process(node->statements()); +} + + +void Processor::VisitExpressionStatement(ExpressionStatement* node) { + // Rewrite : <x>; -> .result = <x>; + if (!is_set_) { + node->set_expression(SetResult(node->expression())); + if (!in_try_) is_set_ = true; + } +} + + +void Processor::VisitIfStatement(IfStatement* node) { + // Rewrite both then and else parts (reversed). + bool save = is_set_; + Visit(node->else_statement()); + bool set_after_then = is_set_; + is_set_ = save; + Visit(node->then_statement()); + is_set_ = is_set_ && set_after_then; +} + + + + +void Processor::VisitLoopStatement(LoopStatement* node) { + // Rewrite loop body statement. + bool set_after_loop = is_set_; + Visit(node->body()); + is_set_ = is_set_ && set_after_loop; +} + + +void Processor::VisitForInStatement(ForInStatement* node) { + // Rewrite for-in body statement. + bool set_after_for = is_set_; + Visit(node->body()); + is_set_ = is_set_ && set_after_for; +} + + +void Processor::VisitTryCatch(TryCatch* node) { + // Rewrite both try and catch blocks (reversed order). + bool set_after_catch = is_set_; + Visit(node->catch_block()); + is_set_ = is_set_ && set_after_catch; + bool save = in_try_; + in_try_ = true; + Visit(node->try_block()); + in_try_ = save; +} + + +void Processor::VisitTryFinally(TryFinally* node) { + // Rewrite both try and finally block (reversed order). + Visit(node->finally_block()); + bool save = in_try_; + in_try_ = true; + Visit(node->try_block()); + in_try_ = save; +} + + +void Processor::VisitSwitchStatement(SwitchStatement* node) { + // Rewrite statements in all case clauses in reversed order. + ZoneList<CaseClause*>* clauses = node->cases(); + bool set_after_switch = is_set_; + for (int i = clauses->length() - 1; i >= 0; --i) { + CaseClause* clause = clauses->at(i); + Process(clause->statements()); + } + is_set_ = is_set_ && set_after_switch; +} + + +void Processor::VisitContinueStatement(ContinueStatement* node) { + is_set_ = false; +} + + +void Processor::VisitBreakStatement(BreakStatement* node) { + is_set_ = false; +} + + +// Do nothing: +void Processor::VisitDeclaration(Declaration* node) {} +void Processor::VisitEmptyStatement(EmptyStatement* node) {} +void Processor::VisitReturnStatement(ReturnStatement* node) {} +void Processor::VisitWithEnterStatement(WithEnterStatement* node) {} +void Processor::VisitWithExitStatement(WithExitStatement* node) {} +void Processor::VisitDebuggerStatement(DebuggerStatement* node) {} + + +// Expressions are never visited yet. +void Processor::VisitFunctionLiteral(FunctionLiteral* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitFunctionBoilerplateLiteral( + FunctionBoilerplateLiteral* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitConditional(Conditional* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitSlot(Slot* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitVariableProxy(VariableProxy* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitLiteral(Literal* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitRegExpLiteral(RegExpLiteral* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitArrayLiteral(ArrayLiteral* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitObjectLiteral(ObjectLiteral* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitCatchExtensionObject(CatchExtensionObject* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitAssignment(Assignment* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitThrow(Throw* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitProperty(Property* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitCall(Call* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitCallNew(CallNew* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitCallRuntime(CallRuntime* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitUnaryOperation(UnaryOperation* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitCountOperation(CountOperation* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitBinaryOperation(BinaryOperation* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitCompareOperation(CompareOperation* node) { + USE(node); + UNREACHABLE(); +} + + +void Processor::VisitThisFunction(ThisFunction* node) { + USE(node); + UNREACHABLE(); +} + + +bool Rewriter::Process(FunctionLiteral* function) { + HistogramTimerScope timer(&Counters::rewriting); + Scope* scope = function->scope(); + if (scope->is_function_scope()) return true; + + ZoneList<Statement*>* body = function->body(); + if (body->is_empty()) return true; + + VariableProxy* result = scope->NewTemporary(Factory::result_symbol()); + Processor processor(result); + processor.Process(body); + if (processor.HasStackOverflow()) return false; + + if (processor.result_assigned()) body->Add(new ReturnStatement(result)); + return true; +} + + +bool Rewriter::Optimize(FunctionLiteral* function) { + ZoneList<Statement*>* body = function->body(); + + if (FLAG_optimize_ast && !body->is_empty()) { + HistogramTimerScope timer(&Counters::ast_optimization); + AstOptimizer optimizer(function->name()); + optimizer.Optimize(body); + if (optimizer.HasStackOverflow()) { + return false; + } + } + return true; +} + + +} } // namespace v8::internal |