1 files changed, 450 insertions, 0 deletions
diff --git a/deps/v8/src/usage-analyzer.cc b/deps/v8/src/usage-analyzer.cc
new file mode 100644
index 000000000..13176f7a4
--- /dev/null
+++ b/deps/v8/src/usage-analyzer.cc
@@ -0,0 +1,450 @@
+// 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