Add support for (some) assignment expressions to the CFG builder and...

src/cfg.cc

 // Copyright 2009 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
@@ skipping 24 matching lines @@
 namespace v8 {
 namespace internal {
 
 
 CfgGlobals* CfgGlobals::top_ = NULL;
 
 
 CfgGlobals::CfgGlobals(FunctionLiteral* fun)
     : global_fun_(fun),
       global_exit_(new ExitNode()),
-      effect_(new Effect()),
+      nowhere_(new Nowhere()),
 #ifdef DEBUG
       node_counter_(0),
       temp_counter_(0),
 #endif
       previous_(top_) {
   top_ = this;
 }
 
 
 #define BAILOUT(reason)                         \
   do { return NULL; } while (false)
 
 Cfg* Cfg::Build() {
   FunctionLiteral* fun = CfgGlobals::current()->fun();
   if (fun->scope()->num_heap_slots() > 0) {
     BAILOUT("function has context slots");
   }
+  if (fun->scope()->num_stack_slots() > kPointerSize) {
+    BAILOUT("function has too many locals");
+  }
+  if (fun->scope()->num_parameters() > kPointerSize - 1) {
+    BAILOUT("function has too many parameters");
+  }
   if (fun->scope()->arguments() != NULL) {
     BAILOUT("function uses .arguments");
   }
 
   ZoneList<Statement*>* body = fun->body();
   if (body->is_empty()) {
     BAILOUT("empty function body");
   }
 
   StatementBuilder builder;
   builder.VisitStatements(body);
-  Cfg* cfg = builder.cfg();
-  if (cfg == NULL) {
+  Cfg* graph = builder.graph();
+  if (graph == NULL) {
     BAILOUT("unsupported statement type");
   }
-  if (cfg->is_empty()) {
+  if (graph->is_empty()) {
     BAILOUT("function body produces empty cfg");
   }
-  if (cfg->has_exit()) {
+  if (graph->has_exit()) {
     BAILOUT("control path without explicit return");
   }
-  cfg->PrependEntryNode();
-  return cfg;
+  graph->PrependEntryNode();
+  return graph;
 }
 
 #undef BAILOUT
 
 
 void Cfg::PrependEntryNode() {
   ASSERT(!is_empty());
   entry_ = new EntryNode(InstructionBlock::cast(entry()));
 }
 
@@ skipping 91 matching lines @@
     }
     PrintF("--- Code ---\n");
     code->Disassemble(*fun->name()->ToCString());
   }
 #endif
 
   return code;
 }
 
 
+void MoveInstr::FastAllocate(TempLocation* temp) {
+  ASSERT(temp->where() == TempLocation::NOT_ALLOCATED);
+  if (temp == value()) {
+    temp->set_where(TempLocation::ACCUMULATOR);
+  } else {
+    temp->set_where(TempLocation::STACK);
+  }
+}
+
+
 void BinaryOpInstr::FastAllocate(TempLocation* temp) {
-  ASSERT(temp->where() == TempLocation::NOWHERE);
-  if (temp == val0_ || temp == val1_) {
+  ASSERT(temp->where() == TempLocation::NOT_ALLOCATED);
+  if (temp == value0() || temp == value1()) {
     temp->set_where(TempLocation::ACCUMULATOR);
   } else {
     temp->set_where(TempLocation::STACK);
   }
 }
 
 
 void ReturnInstr::FastAllocate(TempLocation* temp) {
-  ASSERT(temp->where() == TempLocation::NOWHERE);
+  ASSERT(temp->where() == TempLocation::NOT_ALLOCATED);
   if (temp == value_) {
     temp->set_where(TempLocation::ACCUMULATOR);
   } else {
     temp->set_where(TempLocation::STACK);
   }
 }
 
 
 // The expression builder should not be used for declarations or statements.
 void ExpressionBuilder::VisitDeclaration(Declaration* decl) { UNREACHABLE(); }
 
 #define DEFINE_VISIT(type)                                              \
   void ExpressionBuilder::Visit##type(type* stmt) { UNREACHABLE(); }
 STATEMENT_NODE_LIST(DEFINE_VISIT)
 #undef DEFINE_VISIT
 
 
 // Macros (temporarily) handling unsupported expression types.
 #define BAILOUT(reason)                         \
   do {                                          \
-    cfg_ = NULL;                                \
+    graph_ = NULL;                              \
     return;                                     \
   } while (false)
 
 void ExpressionBuilder::VisitFunctionLiteral(FunctionLiteral* expr) {
   BAILOUT("FunctionLiteral");
 }
 
 
 void ExpressionBuilder::VisitFunctionBoilerplateLiteral(
     FunctionBoilerplateLiteral* expr) {
@@ skipping 13 matching lines @@
 
 void ExpressionBuilder::VisitVariableProxy(VariableProxy* expr) {
   Expression* rewrite = expr->var()->rewrite();
   if (rewrite == NULL || rewrite->AsSlot() == NULL) {
     BAILOUT("unsupported variable (not a slot)");
   }
   Slot* slot = rewrite->AsSlot();
   if (slot->type() != Slot::PARAMETER && slot->type() != Slot::LOCAL) {
     BAILOUT("unsupported slot type (not a parameter or local)");
   }
+  // Ignore the passed destination.
   value_ = new SlotLocation(slot->type(), slot->index());
 }
 
 
 void ExpressionBuilder::VisitLiteral(Literal* expr) {
+  // Ignore the passed destination.
   value_ = new Constant(expr->handle());
 }
 
 
 void ExpressionBuilder::VisitRegExpLiteral(RegExpLiteral* expr) {
   BAILOUT("RegExpLiteral");
 }
 
 
 void ExpressionBuilder::VisitObjectLiteral(ObjectLiteral* expr) {
   BAILOUT("ObjectLiteral");
 }
 
 
 void ExpressionBuilder::VisitArrayLiteral(ArrayLiteral* expr) {
   BAILOUT("ArrayLiteral");
 }
 
 
 void ExpressionBuilder::VisitCatchExtensionObject(CatchExtensionObject* expr) {
   BAILOUT("CatchExtensionObject");
 }
 
 
 void ExpressionBuilder::VisitAssignment(Assignment* expr) {
-  BAILOUT("Assignment");
+  if (expr->op() != Token::ASSIGN && expr->op() != Token::INIT_VAR) {
+    BAILOUT("unsupported compound assignment");
+  }
+  Expression* lhs = expr->target();
+  if (lhs->AsProperty() != NULL) {
+    BAILOUT("unsupported property assignment");
+  }
+  Variable* var = lhs->AsVariableProxy()->AsVariable();
+  if (var == NULL) {
+    BAILOUT("unsupported invalid left-hand side");
+  }
+  if (var->is_global()) {
+    BAILOUT("unsupported global variable");
+  }
+  Slot* slot = var->slot();
+  ASSERT(slot != NULL);
+  if (slot->type() != Slot::PARAMETER && slot->type() != Slot::LOCAL) {
+    BAILOUT("unsupported slot lhs (not a parameter or local)");
+  }
+
+  ExpressionBuilder builder;
+  SlotLocation* loc = new SlotLocation(slot->type(), slot->index());
+  builder.Build(expr->value(), loc);
+  if (builder.graph() == NULL) {
+    BAILOUT("unsupported expression in assignment");
+  }
+  // If the expression did not come back in the slot location, append
+  // a move to the CFG.
+  graph_ = builder.graph();
+  if (builder.value() != loc) {
+    graph()->Append(new MoveInstr(loc, builder.value()));
+  }
+  // Record the assignment.
+  assigned_vars_.AddElement(loc);
+  // Ignore the destination passed to us.
+  value_ = loc;
 }
 
 
 void ExpressionBuilder::VisitThrow(Throw* expr) {
   BAILOUT("Throw");
 }
 
 
 void ExpressionBuilder::VisitProperty(Property* expr) {
   BAILOUT("Property");
@@ skipping 43 matching lines @@
     case Token::BIT_AND:
     case Token::SHL:
     case Token::SAR:
     case Token::SHR:
     case Token::ADD:
     case Token::SUB:
     case Token::MUL:
     case Token::DIV:
     case Token::MOD: {
       ExpressionBuilder left, right;
-      left.Build(expr->left());
-      if (left.cfg() == NULL) {
+      left.Build(expr->left(), NULL);
+      if (left.graph() == NULL) {
         BAILOUT("unsupported left subexpression in binop");
       }
-      right.Build(expr->right());
-      if (right.cfg() == NULL) {
+      right.Build(expr->right(), NULL);
+      if (right.graph() == NULL) {
         BAILOUT("unsupported right subexpression in binop");
       }
 
-      Location* temp = new TempLocation();
-      cfg_ = left.cfg();
-      cfg_->Concatenate(right.cfg());
-      cfg_->Append(new BinaryOpInstr(temp, op, left.value(), right.value()));
+      if (destination_ == NULL) destination_ = new TempLocation();
 
-      value_ = temp;
+      graph_ = left.graph();
+      // Insert a move to a fresh temporary if the left value is in a
+      // slot that's assigned on the right.
+      Location* temp = NULL;
+      if (left.value()->is_slot() &&
+          right.assigned_vars()->Contains(SlotLocation::cast(left.value()))) {
+        temp = new TempLocation();
+        graph()->Append(new MoveInstr(temp, left.value()));
+      }
+      graph()->Concatenate(right.graph());
+      graph()->Append(new BinaryOpInstr(destination_, op,
+                                        temp == NULL ? left.value() : temp,
+                                        right.value()));
+
+      assigned_vars_ = *left.assigned_vars();
+      assigned_vars()->Union(right.assigned_vars());
+
+      value_ = destination_;
       return;
     }
 
     default:
       UNREACHABLE();
   }
 }
 
 
 void ExpressionBuilder::VisitCompareOperation(CompareOperation* expr) {
   BAILOUT("CompareOperation");
 }
 
 
 void ExpressionBuilder::VisitThisFunction(ThisFunction* expr) {
   BAILOUT("ThisFunction");
 }
 
 #undef BAILOUT
 
 
 // Macros (temporarily) handling unsupported statement types.
 #define BAILOUT(reason)                         \
   do {                                          \
-    cfg_ = NULL;                                \
+    graph_ = NULL;                              \
     return;                                     \
   } while (false)
 
 #define CHECK_BAILOUT()                         \
-  if (cfg_ == NULL) { return; } else {}
+  if (graph() == NULL) { return; } else {}
 
 void StatementBuilder::VisitStatements(ZoneList<Statement*>* stmts) {
   for (int i = 0, len = stmts->length(); i < len; i++) {
     Visit(stmts->at(i));
     CHECK_BAILOUT();
-    if (!cfg_->has_exit()) return;
+    if (!graph()->has_exit()) return;
   }
 }
 
 
 // The statement builder should not be used for declarations or expressions.
 void StatementBuilder::VisitDeclaration(Declaration* decl) { UNREACHABLE(); }
 
 #define DEFINE_VISIT(type)                                      \
   void StatementBuilder::Visit##type(type* expr) { UNREACHABLE(); }
 EXPRESSION_NODE_LIST(DEFINE_VISIT)
 #undef DEFINE_VISIT
 
 
 void StatementBuilder::VisitBlock(Block* stmt) {
   VisitStatements(stmt->statements());
 }
 
 
 void StatementBuilder::VisitExpressionStatement(ExpressionStatement* stmt) {
   ExpressionBuilder builder;
-  builder.Build(stmt->expression());
-  if (builder.cfg() == NULL) {
+  builder.Build(stmt->expression(), CfgGlobals::current()->nowhere());
+  if (builder.graph() == NULL) {
     BAILOUT("unsupported expression in expression statement");
   }
-  // Here's a temporary hack: we bang on the last instruction of the
-  // expression (if any) to set its location to Effect.
-  if (!builder.cfg()->is_empty()) {
-    InstructionBlock* block = InstructionBlock::cast(builder.cfg()->exit());
-    Instruction* instr = block->instructions()->last();
-    instr->set_location(CfgGlobals::current()->effect_location());
-  }
-  cfg_->Append(new PositionInstr(stmt->statement_pos()));
-  cfg_->Concatenate(builder.cfg());
+  graph()->Append(new PositionInstr(stmt->statement_pos()));
+  graph()->Concatenate(builder.graph());
 }
 
 
 void StatementBuilder::VisitEmptyStatement(EmptyStatement* stmt) {
   // Nothing to do.
 }
 
 
 void StatementBuilder::VisitIfStatement(IfStatement* stmt) {
   BAILOUT("IfStatement");
 }
 
 
 void StatementBuilder::VisitContinueStatement(ContinueStatement* stmt) {
   BAILOUT("ContinueStatement");
 }
 
 
 void StatementBuilder::VisitBreakStatement(BreakStatement* stmt) {
   BAILOUT("BreakStatement");
 }
 
 
 void StatementBuilder::VisitReturnStatement(ReturnStatement* stmt) {
   ExpressionBuilder builder;
-  builder.Build(stmt->expression());
-  if (builder.cfg() == NULL) {
+  builder.Build(stmt->expression(), NULL);
+  if (builder.graph() == NULL) {
     BAILOUT("unsupported expression in return statement");
   }
 
-  cfg_->Append(new PositionInstr(stmt->statement_pos()));
-  cfg_->Concatenate(builder.cfg());
-  cfg_->AppendReturnInstruction(builder.value());
+  graph()->Append(new PositionInstr(stmt->statement_pos()));
+  graph()->Concatenate(builder.graph());
+  graph()->AppendReturnInstruction(builder.value());
 }
 
 
 void StatementBuilder::VisitWithEnterStatement(WithEnterStatement* stmt) {
   BAILOUT("WithEnterStatement");
 }
 
 
 void StatementBuilder::VisitWithExitStatement(WithExitStatement* stmt) {
   BAILOUT("WithExitStatement");
@@ skipping 39 matching lines @@
 }
 
 
 void Constant::Print() {
   PrintF("Constant(");
   handle_->Print();
   PrintF(")");
 }
 
 
-void Effect::Print() {
-  PrintF("Effect");
+void Nowhere::Print() {
+  PrintF("Nowhere");
 }
 
 
 void SlotLocation::Print() {
   PrintF("Slot(");
   switch (type_) {
     case Slot::PARAMETER:
       PrintF("PARAMETER, %d)", index_);
       break;
     case Slot::LOCAL:
       PrintF("LOCAL, %d)", index_);
       break;
     default:
       UNREACHABLE();
   }
 }
 
 
 void TempLocation::Print() {
   PrintF("Temp(%d)", number());
 }
 
 
+void MoveInstr::Print() {
+  PrintF("Move(");
+  location()->Print();
+  PrintF(", ");
+  value_->Print();
+  PrintF(")\n");
+}
+
+
 void BinaryOpInstr::Print() {
   PrintF("BinaryOp(");
-  loc_->Print();
-  PrintF(", %s, ", Token::Name(op_));
-  val0_->Print();
+  location()->Print();
+  PrintF(", %s, ", Token::Name(op()));
+  value0()->Print();
   PrintF(", ");
-  val1_->Print();
+  value1()->Print();
   PrintF(")\n");
 }
 
 
 void ReturnInstr::Print() {
   PrintF("Return(");
   value_->Print();
   PrintF(")\n");
 }
 
@@ skipping 22 matching lines @@
 void ExitNode::Print() {
   if (!is_marked_) {
     is_marked_ = true;
     PrintF("L%d:\nExit\n\n", number());
   }
 }
 
 #endif  // DEBUG
 
 } }  // namespace v8::internal