Add support to the CFG builder for non-short-circuited binary...

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()),
 #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()->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) {
     BAILOUT("unsupported statement type");
   }
+  if (cfg->is_empty()) {
+    BAILOUT("function body produces empty cfg");
+  }
   if (cfg->has_exit()) {
     BAILOUT("control path without explicit return");
   }
   cfg->PrependEntryNode();
   return cfg;
 }
 
 #undef BAILOUT
 
 
 void Cfg::PrependEntryNode() {
   ASSERT(!is_empty());
   entry_ = new EntryNode(InstructionBlock::cast(entry()));
 }
 
 
 void Cfg::Append(Instruction* instr) {
-  ASSERT(has_exit());
-  ASSERT(!is_empty());
+  ASSERT(is_empty() || has_exit());
+  if (is_empty()) {
+    entry_ = exit_ = new InstructionBlock();
+  }
   InstructionBlock::cast(exit_)->Append(instr);
 }
 
 
 void Cfg::AppendReturnInstruction(Value* value) {
   Append(new ReturnInstr(value));
   ExitNode* global_exit = CfgGlobals::current()->exit();
   InstructionBlock::cast(exit_)->set_successor(global_exit);
   exit_ = NULL;
 }
 
 
+void Cfg::Concatenate(Cfg* other) {
+  ASSERT(is_empty() || has_exit());
+  if (other->is_empty()) return;
+
+  if (is_empty()) {
+    entry_ = other->entry();
+    exit_ = other->exit();
+  } else {
+    // We have a pair of nonempty fragments and this has an available exit.
+    // Destructively glue the fragments together.
+    InstructionBlock* first = InstructionBlock::cast(exit_);
+    InstructionBlock* second = InstructionBlock::cast(other->entry());
+    first->instructions()->AddAll(*second->instructions());
+    if (second->successor() != NULL) {
+      first->set_successor(second->successor());
+      exit_ = other->exit();
+    }
+  }
+}
+
+
 void InstructionBlock::Unmark() {
   if (is_marked_) {
     is_marked_ = false;
     successor_->Unmark();
   }
 }
 
 
 void EntryNode::Unmark() {
   if (is_marked_) {
@@ skipping 42 matching lines @@
     }
     PrintF("--- Code ---\n");
     code->Disassemble(*fun->name()->ToCString());
   }
 #endif
 
   return code;
 }
 
 
+void BinaryOpInstr::FastAllocate(TempLocation* temp) {
+  ASSERT(temp->where() == TempLocation::NOWHERE);
+  if (temp == val0_ || temp == val1_) {
+    temp->set_where(TempLocation::ACCUMULATOR);
+  } else {
+    temp->set_where(TempLocation::STACK);
+  }
+}
+
+
+void ReturnInstr::FastAllocate(TempLocation* temp) {
+  ASSERT(temp->where() == TempLocation::NOWHERE);
+  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 {                                          \
-    value_ = NULL;                              \
+    cfg_ = NULL;                                \
     return;                                     \
   } while (false)
 
-#define CHECK_BAILOUT()                         \
-  if (value_ == NULL) { return; } else {}
-
 void ExpressionBuilder::VisitFunctionLiteral(FunctionLiteral* expr) {
   BAILOUT("FunctionLiteral");
 }
 
 
 void ExpressionBuilder::VisitFunctionBoilerplateLiteral(
     FunctionBoilerplateLiteral* expr) {
   BAILOUT("FunctionBoilerplateLiteral");
 }
 
@@ skipping 85 matching lines @@
   BAILOUT("UnaryOperation");
 }
 
 
 void ExpressionBuilder::VisitCountOperation(CountOperation* expr) {
   BAILOUT("CountOperation");
 }
 
 
 void ExpressionBuilder::VisitBinaryOperation(BinaryOperation* expr) {
-  BAILOUT("BinaryOperation");
+  Token::Value op = expr->op();
+  switch (op) {
+    case Token::COMMA:
+    case Token::OR:
+    case Token::AND:
+      BAILOUT("unsupported binary operation");
+
+    case Token::BIT_OR:
+    case Token::BIT_XOR:
+    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) {
+        BAILOUT("unsupported left subexpression in binop");
+      }
+      right.Build(expr->right());
+      if (right.cfg() == 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()));
+
+      value_ = temp;
+      return;
+    }
+
+    default:
+      UNREACHABLE();
+  }
 }
 
 
 void ExpressionBuilder::VisitCompareOperation(CompareOperation* expr) {
   BAILOUT("CompareOperation");
 }
 
 
 void ExpressionBuilder::VisitThisFunction(ThisFunction* expr) {
   BAILOUT("ThisFunction");
 }
 
 #undef BAILOUT
-#undef CHECK_BAILOUT
 
 
 // Macros (temporarily) handling unsupported statement types.
 #define BAILOUT(reason)                         \
   do {                                          \
     cfg_ = NULL;                                \
     return;                                     \
   } while (false)
 
 #define CHECK_BAILOUT()                         \
@@ skipping 42 matching lines @@
 }
 
 
 void StatementBuilder::VisitBreakStatement(BreakStatement* stmt) {
   BAILOUT("BreakStatement");
 }
 
 
 void StatementBuilder::VisitReturnStatement(ReturnStatement* stmt) {
   ExpressionBuilder builder;
-  builder.Visit(stmt->expression());
-  Value* value = builder.value();
-  if (value == NULL) BAILOUT("unsupported expression type");
-  cfg_->AppendReturnInstruction(value);
+  builder.Build(stmt->expression());
+  if (builder.cfg() == NULL) {
+    BAILOUT("unsupported expression in return statement");
+  }
+
+  cfg_->Concatenate(builder.cfg());
+  cfg_->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 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 BinaryOpInstr::Print() {
+  PrintF("BinaryOp(");
+  loc_->Print();
+  PrintF(", %s, ", Token::Name(op_));
+  val0_->Print();
+  PrintF(", ");
+  val1_->Print();
+  PrintF(")\n");
+}
+
+
 void ReturnInstr::Print() {
-  PrintF("Return ");
+  PrintF("Return(");
   value_->Print();
-  PrintF("\n");
+  PrintF(")\n");
 }
 
 
 void InstructionBlock::Print() {
   if (!is_marked_) {
     is_marked_ = true;
     PrintF("L%d:\n", number());
     for (int i = 0, len = instructions_.length(); i < len; i++) {
       instructions_[i]->Print();
     }
@@ skipping 14 matching lines @@
 void ExitNode::Print() {
   if (!is_marked_) {
     is_marked_ = true;
     PrintF("L%d:\nExit\n\n", number());
   }
 }
 
 #endif  // DEBUG
 
 } }  // namespace v8::internal