| // 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 "scopes.h" |
| #include "usage-analyzer.h" |
| |
| namespace v8 { namespace internal { |
| |
| // Weight boundaries |
| static const int MinWeight = 1; |
| static const int MaxWeight = 1000000; |
| static const int InitialWeight = 100; |
| |
| |
| class UsageComputer: public AstVisitor { |
| public: |
| static bool Traverse(Node* node); |
| |
| void VisitBlock(Block* node); |
| void VisitDeclaration(Declaration* node); |
| void VisitExpressionStatement(ExpressionStatement* node); |
| void VisitEmptyStatement(EmptyStatement* node); |
| void VisitIfStatement(IfStatement* node); |
| void VisitContinueStatement(ContinueStatement* node); |
| void VisitBreakStatement(BreakStatement* node); |
| void VisitReturnStatement(ReturnStatement* node); |
| void VisitWithEnterStatement(WithEnterStatement* node); |
| void VisitWithExitStatement(WithExitStatement* node); |
| void VisitSwitchStatement(SwitchStatement* node); |
| void VisitLoopStatement(LoopStatement* node); |
| void VisitForInStatement(ForInStatement* node); |
| void VisitTryCatch(TryCatch* node); |
| void VisitTryFinally(TryFinally* node); |
| void VisitDebuggerStatement(DebuggerStatement* node); |
| void VisitFunctionLiteral(FunctionLiteral* node); |
| void VisitFunctionBoilerplateLiteral(FunctionBoilerplateLiteral* node); |
| void VisitConditional(Conditional* node); |
| void VisitSlot(Slot* node); |
| void VisitVariable(Variable* node); |
| void VisitVariableProxy(VariableProxy* node); |
| void VisitLiteral(Literal* node); |
| void VisitRegExpLiteral(RegExpLiteral* node); |
| void VisitObjectLiteral(ObjectLiteral* node); |
| void VisitArrayLiteral(ArrayLiteral* node); |
| void VisitCatchExtensionObject(CatchExtensionObject* node); |
| void VisitAssignment(Assignment* node); |
| void VisitThrow(Throw* node); |
| void VisitProperty(Property* node); |
| void VisitCall(Call* node); |
| void VisitCallEval(CallEval* node); |
| void VisitCallNew(CallNew* node); |
| void VisitCallRuntime(CallRuntime* node); |
| void VisitUnaryOperation(UnaryOperation* node); |
| void VisitCountOperation(CountOperation* node); |
| void VisitBinaryOperation(BinaryOperation* node); |
| void VisitCompareOperation(CompareOperation* node); |
| void VisitThisFunction(ThisFunction* node); |
| |
| private: |
| int weight_; |
| bool is_write_; |
| |
| UsageComputer(int weight, bool is_write); |
| virtual ~UsageComputer(); |
| |
| // Helper functions |
| void RecordUses(UseCount* uses); |
| void Read(Expression* x); |
| void Write(Expression* x); |
| void ReadList(ZoneList<Expression*>* list); |
| void ReadList(ZoneList<ObjectLiteral::Property*>* list); |
| |
| friend class WeightScaler; |
| }; |
| |
| |
| class WeightScaler BASE_EMBEDDED { |
| public: |
| WeightScaler(UsageComputer* uc, float scale); |
| ~WeightScaler(); |
| |
| private: |
| UsageComputer* uc_; |
| int old_weight_; |
| }; |
| |
| |
| // ---------------------------------------------------------------------------- |
| // Implementation of UsageComputer |
| |
| bool UsageComputer::Traverse(Node* node) { |
| UsageComputer uc(InitialWeight, false); |
| uc.Visit(node); |
| return !uc.HasStackOverflow(); |
| } |
| |
| |
| void UsageComputer::VisitBlock(Block* node) { |
| VisitStatements(node->statements()); |
| } |
| |
| |
| void UsageComputer::VisitDeclaration(Declaration* node) { |
| Write(node->proxy()); |
| if (node->fun() != NULL) |
| VisitFunctionLiteral(node->fun()); |
| } |
| |
| |
| void UsageComputer::VisitExpressionStatement(ExpressionStatement* node) { |
| Visit(node->expression()); |
| } |
| |
| |
| void UsageComputer::VisitEmptyStatement(EmptyStatement* node) { |
| // nothing to do |
| } |
| |
| |
| void UsageComputer::VisitIfStatement(IfStatement* node) { |
| Read(node->condition()); |
| { WeightScaler ws(this, 0.5); // executed 50% of the time |
| Visit(node->then_statement()); |
| Visit(node->else_statement()); |
| } |
| } |
| |
| |
| void UsageComputer::VisitContinueStatement(ContinueStatement* node) { |
| // nothing to do |
| } |
| |
| |
| void UsageComputer::VisitBreakStatement(BreakStatement* node) { |
| // nothing to do |
| } |
| |
| |
| void UsageComputer::VisitReturnStatement(ReturnStatement* node) { |
| Read(node->expression()); |
| } |
| |
| |
| void UsageComputer::VisitWithEnterStatement(WithEnterStatement* node) { |
| Read(node->expression()); |
| } |
| |
| |
| void UsageComputer::VisitWithExitStatement(WithExitStatement* node) { |
| // nothing to do |
| } |
| |
| |
| void UsageComputer::VisitSwitchStatement(SwitchStatement* node) { |
| Read(node->tag()); |
| ZoneList<CaseClause*>* cases = node->cases(); |
| for (int i = cases->length(); i-- > 0;) { |
| WeightScaler ws(this, static_cast<float>(1.0 / cases->length())); |
| CaseClause* clause = cases->at(i); |
| if (!clause->is_default()) |
| Read(clause->label()); |
| VisitStatements(clause->statements()); |
| } |
| } |
| |
| |
| void UsageComputer::VisitLoopStatement(LoopStatement* node) { |
| if (node->init() != NULL) |
| Visit(node->init()); |
| { WeightScaler ws(this, 10.0); // executed in each iteration |
| if (node->cond() != NULL) |
| Read(node->cond()); |
| if (node->next() != NULL) |
| Visit(node->next()); |
| Visit(node->body()); |
| } |
| } |
| |
| |
| void UsageComputer::VisitForInStatement(ForInStatement* node) { |
| WeightScaler ws(this, 10.0); |
| Write(node->each()); |
| Read(node->enumerable()); |
| Visit(node->body()); |
| } |
| |
| |
| void UsageComputer::VisitTryCatch(TryCatch* node) { |
| Visit(node->try_block()); |
| { WeightScaler ws(this, 0.25); |
| Write(node->catch_var()); |
| Visit(node->catch_block()); |
| } |
| } |
| |
| |
| void UsageComputer::VisitTryFinally(TryFinally* node) { |
| Visit(node->try_block()); |
| Visit(node->finally_block()); |
| } |
| |
| |
| void UsageComputer::VisitDebuggerStatement(DebuggerStatement* node) { |
| } |
| |
| |
| void UsageComputer::VisitFunctionLiteral(FunctionLiteral* node) { |
| ZoneList<Declaration*>* decls = node->scope()->declarations(); |
| for (int i = 0; i < decls->length(); i++) VisitDeclaration(decls->at(i)); |
| VisitStatements(node->body()); |
| } |
| |
| |
| void UsageComputer::VisitFunctionBoilerplateLiteral( |
| FunctionBoilerplateLiteral* node) { |
| // Do nothing. |
| } |
| |
| |
| void UsageComputer::VisitConditional(Conditional* node) { |
| Read(node->condition()); |
| { WeightScaler ws(this, 0.5); |
| Read(node->then_expression()); |
| Read(node->else_expression()); |
| } |
| } |
| |
| |
| void UsageComputer::VisitSlot(Slot* node) { |
| UNREACHABLE(); |
| } |
| |
| |
| void UsageComputer::VisitVariable(Variable* node) { |
| RecordUses(node->var_uses()); |
| } |
| |
| |
| void UsageComputer::VisitVariableProxy(VariableProxy* node) { |
| // The proxy may refer to a variable in which case it was bound via |
| // VariableProxy::BindTo. |
| RecordUses(node->var_uses()); |
| } |
| |
| |
| void UsageComputer::VisitLiteral(Literal* node) { |
| // nothing to do |
| } |
| |
| void UsageComputer::VisitRegExpLiteral(RegExpLiteral* node) { |
| // nothing to do |
| } |
| |
| |
| void UsageComputer::VisitObjectLiteral(ObjectLiteral* node) { |
| ReadList(node->properties()); |
| } |
| |
| |
| void UsageComputer::VisitArrayLiteral(ArrayLiteral* node) { |
| ReadList(node->values()); |
| } |
| |
| |
| void UsageComputer::VisitCatchExtensionObject(CatchExtensionObject* node) { |
| Read(node->value()); |
| } |
| |
| |
| void UsageComputer::VisitAssignment(Assignment* node) { |
| if (node->op() != Token::ASSIGN) |
| Read(node->target()); |
| Write(node->target()); |
| Read(node->value()); |
| } |
| |
| |
| void UsageComputer::VisitThrow(Throw* node) { |
| Read(node->exception()); |
| } |
| |
| |
| void UsageComputer::VisitProperty(Property* node) { |
| // In any case (read or write) we read both the |
| // node's object and the key. |
| Read(node->obj()); |
| Read(node->key()); |
| // If the node's object is a variable proxy, |
| // we have a 'simple' object property access. We count |
| // the access via the variable or proxy's object uses. |
| VariableProxy* proxy = node->obj()->AsVariableProxy(); |
| if (proxy != NULL) { |
| RecordUses(proxy->obj_uses()); |
| } |
| } |
| |
| |
| void UsageComputer::VisitCall(Call* node) { |
| Read(node->expression()); |
| ReadList(node->arguments()); |
| } |
| |
| |
| void UsageComputer::VisitCallEval(CallEval* node) { |
| VisitCall(node); |
| } |
| |
| |
| void UsageComputer::VisitCallNew(CallNew* node) { |
| VisitCall(node); |
| } |
| |
| |
| void UsageComputer::VisitCallRuntime(CallRuntime* node) { |
| ReadList(node->arguments()); |
| } |
| |
| |
| void UsageComputer::VisitUnaryOperation(UnaryOperation* node) { |
| Read(node->expression()); |
| } |
| |
| |
| void UsageComputer::VisitCountOperation(CountOperation* node) { |
| Read(node->expression()); |
| Write(node->expression()); |
| } |
| |
| |
| void UsageComputer::VisitBinaryOperation(BinaryOperation* node) { |
| Read(node->left()); |
| Read(node->right()); |
| } |
| |
| |
| void UsageComputer::VisitCompareOperation(CompareOperation* node) { |
| Read(node->left()); |
| Read(node->right()); |
| } |
| |
| |
| void UsageComputer::VisitThisFunction(ThisFunction* node) { |
| } |
| |
| |
| UsageComputer::UsageComputer(int weight, bool is_write) { |
| weight_ = weight; |
| is_write_ = is_write; |
| } |
| |
| |
| UsageComputer::~UsageComputer() { |
| // nothing to do |
| } |
| |
| |
| void UsageComputer::RecordUses(UseCount* uses) { |
| if (is_write_) |
| uses->RecordWrite(weight_); |
| else |
| uses->RecordRead(weight_); |
| } |
| |
| |
| void UsageComputer::Read(Expression* x) { |
| if (is_write_) { |
| UsageComputer uc(weight_, false); |
| uc.Visit(x); |
| } else { |
| Visit(x); |
| } |
| } |
| |
| |
| void UsageComputer::Write(Expression* x) { |
| if (!is_write_) { |
| UsageComputer uc(weight_, true); |
| uc.Visit(x); |
| } else { |
| Visit(x); |
| } |
| } |
| |
| |
| void UsageComputer::ReadList(ZoneList<Expression*>* list) { |
| for (int i = list->length(); i-- > 0; ) |
| Read(list->at(i)); |
| } |
| |
| |
| void UsageComputer::ReadList(ZoneList<ObjectLiteral::Property*>* list) { |
| for (int i = list->length(); i-- > 0; ) |
| Read(list->at(i)->value()); |
| } |
| |
| |
| // ---------------------------------------------------------------------------- |
| // Implementation of WeightScaler |
| |
| WeightScaler::WeightScaler(UsageComputer* uc, float scale) { |
| uc_ = uc; |
| old_weight_ = uc->weight_; |
| int new_weight = static_cast<int>(uc->weight_ * scale); |
| if (new_weight <= 0) new_weight = MinWeight; |
| else if (new_weight > MaxWeight) new_weight = MaxWeight; |
| uc->weight_ = new_weight; |
| } |
| |
| |
| WeightScaler::~WeightScaler() { |
| uc_->weight_ = old_weight_; |
| } |
| |
| |
| // ---------------------------------------------------------------------------- |
| // Interface to variable usage analysis |
| |
| bool AnalyzeVariableUsage(FunctionLiteral* lit) { |
| if (!FLAG_usage_computation) return true; |
| return UsageComputer::Traverse(lit); |
| } |
| |
| } } // namespace v8::internal |