Initialize reaching definitions state for all flow graph nodes.

src/data-flow.cc

 // Copyright 2010 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 115 matching lines @@
   }
   postorder->Add(this);
 }
 
 
 void BranchNode::Traverse(bool mark,
                           ZoneList<Node*>* preorder,
                           ZoneList<Node*>* postorder) {
   ASSERT(successor0_ != NULL && successor1_ != NULL);
   preorder->Add(this);
+  if (!successor1_->IsMarkedWith(mark)) {
+    successor1_->MarkWith(mark);
+    successor1_->Traverse(mark, preorder, postorder);
+  }
   if (!successor0_->IsMarkedWith(mark)) {
     successor0_->MarkWith(mark);
     successor0_->Traverse(mark, preorder, postorder);
   }
-  if (!successor1_->IsMarkedWith(mark)) {
-    successor1_->MarkWith(mark);
-    successor1_->Traverse(mark, preorder, postorder);
-  }
   postorder->Add(this);
 }
 
 
 void JoinNode::Traverse(bool mark,
                         ZoneList<Node*>* preorder,
                         ZoneList<Node*>* postorder) {
   ASSERT(successor_ != NULL);
   preorder->Add(this);
   if (!successor_->IsMarkedWith(mark)) {
@@ skipping 197 matching lines @@
 
 
 void FlowGraphBuilder::VisitAssignment(Assignment* expr) {
   Variable* var = expr->target()->AsVariableProxy()->AsVariable();
   Property* prop = expr->target()->AsProperty();
   // Left-hand side can be a variable or property (or reference error) but
   // not both.
   ASSERT(var == NULL || prop == NULL);
   if (var != NULL) {
     Visit(expr->value());
-    if (var->IsStackAllocated()) definitions_.Add(expr);
+    if (var->IsStackAllocated()) {
+      expr->set_num(definitions_.length());
+      definitions_.Add(expr);
+    }
 
   } else if (prop != NULL) {
     Visit(prop->obj());
     if (!prop->key()->IsPropertyName()) Visit(prop->key());
     Visit(expr->value());
   }
 
   if (HasStackOverflow()) return;
   graph_.AppendInstruction(expr);
 }
@@ skipping 55 matching lines @@
     default:
       UNREACHABLE();
   }
 }
 
 
 void FlowGraphBuilder::VisitCountOperation(CountOperation* expr) {
   Visit(expr->expression());
   Variable* var = expr->expression()->AsVariableProxy()->AsVariable();
   if (var != NULL && var->IsStackAllocated()) {
+    expr->set_num(definitions_.length());
     definitions_.Add(expr);
   }
 
   if (HasStackOverflow()) return;
   graph_.AppendInstruction(expr);
 }
 
 
 void FlowGraphBuilder::VisitBinaryOperation(BinaryOperation* expr) {
   switch (expr->op()) {
@@ skipping 1029 matching lines @@
 }
 
 
 #ifdef DEBUG
 
 // Print a textual representation of an instruction in a flow graph.  Using
 // the AstVisitor is overkill because there is no recursion here.  It is
 // only used for printing in debug mode.
 class TextInstructionPrinter: public AstVisitor {
  public:
-  TextInstructionPrinter() {}
+  TextInstructionPrinter() : number_(0) {}
+
+  int NextNumber() { return number_; }
+  void AssignNumber(AstNode* node) { node->set_num(number_++); }
 
  private:
   // AST node visit functions.
 #define DECLARE_VISIT(type) virtual void Visit##type(type* node);
   AST_NODE_LIST(DECLARE_VISIT)
 #undef DECLARE_VISIT
 
+  int number_;
+
   DISALLOW_COPY_AND_ASSIGN(TextInstructionPrinter);
 };
 
 
 void TextInstructionPrinter::VisitDeclaration(Declaration* decl) {
   UNREACHABLE();
 }
 
 
 void TextInstructionPrinter::VisitBlock(Block* stmt) {
@@ skipping 100 matching lines @@
 
 
 void TextInstructionPrinter::VisitSlot(Slot* expr) {
   UNREACHABLE();
 }
 
 
 void TextInstructionPrinter::VisitVariableProxy(VariableProxy* expr) {
   Variable* var = expr->AsVariable();
   if (var != NULL) {
-    SmartPointer<char> name = var->name()->ToCString();
-    PrintF("%s", *name);
+    PrintF("%s", *var->name()->ToCString());
   } else {
     ASSERT(expr->AsProperty() != NULL);
     VisitProperty(expr->AsProperty());
   }
 }
 
 
 void TextInstructionPrinter::VisitLiteral(Literal* expr) {
   expr->handle()->ShortPrint();
 }
@@ skipping 18 matching lines @@
     CatchExtensionObject* expr) {
   PrintF("CatchExtensionObject");
 }
 
 
 void TextInstructionPrinter::VisitAssignment(Assignment* expr) {
   Variable* var = expr->target()->AsVariableProxy()->AsVariable();
   Property* prop = expr->target()->AsProperty();
 
   if (var != NULL) {
-    SmartPointer<char> name = var->name()->ToCString();
     PrintF("%s %s @%d",
-           *name,
+           *var->name()->ToCString(),
            Token::String(expr->op()),
            expr->value()->num());
   } else if (prop != NULL) {
     if (prop->key()->IsPropertyName()) {
       PrintF("@%d.", prop->obj()->num());
       ASSERT(prop->key()->AsLiteral() != NULL);
       prop->key()->AsLiteral()->handle()->Print();
       PrintF(" %s @%d",
              Token::String(expr->op()),
              expr->value()->num());
     } else {
       PrintF("@%d[@%d] %s @%d",
              prop->obj()->num(),
              prop->key()->num(),
              Token::String(expr->op()),
              expr->value()->num());
     }
   } else {
     // Throw reference error.
     Visit(expr->target());
   }
+
+  if (expr->num() != AstNode::kNoNumber) {
+    PrintF(" ;; D%d", expr->num());
+  }
 }
 
 
 void TextInstructionPrinter::VisitThrow(Throw* expr) {
   PrintF("throw @%d", expr->exception()->num());
 }
 
 
 void TextInstructionPrinter::VisitProperty(Property* expr) {
   if (expr->key()->IsPropertyName()) {
@@ skipping 22 matching lines @@
   ZoneList<Expression*>* arguments = expr->arguments();
   for (int i = 0, len = arguments->length(); i < len; i++) {
     if (i != 0) PrintF(", ");
     PrintF("@%d", arguments->at(i)->num());
   }
   PrintF(")");
 }
 
 
 void TextInstructionPrinter::VisitCallRuntime(CallRuntime* expr) {
-  SmartPointer<char> name = expr->name()->ToCString();
-  PrintF("%s(", *name);
+  PrintF("%s(", *expr->name()->ToCString());
   ZoneList<Expression*>* arguments = expr->arguments();
   for (int i = 0, len = arguments->length(); i < len; i++) {
     if (i != 0) PrintF(", ");
     PrintF("@%d", arguments->at(i)->num());
   }
   PrintF(")");
 }
 
 
 void TextInstructionPrinter::VisitUnaryOperation(UnaryOperation* expr) {
   PrintF("%s(@%d)", Token::String(expr->op()), expr->expression()->num());
 }
 
 
 void TextInstructionPrinter::VisitCountOperation(CountOperation* expr) {
   if (expr->is_prefix()) {
     PrintF("%s@%d", Token::String(expr->op()), expr->expression()->num());
   } else {
     PrintF("@%d%s", expr->expression()->num(), Token::String(expr->op()));
   }
+
+  if (expr->num() != AstNode::kNoNumber) {
+    PrintF(" ;; D%d", expr->num());
+  }
 }
 
 
 void TextInstructionPrinter::VisitBinaryOperation(BinaryOperation* expr) {
   ASSERT(expr->op() != Token::COMMA);
   ASSERT(expr->op() != Token::OR);
   ASSERT(expr->op() != Token::AND);
   PrintF("@%d %s @%d",
          expr->left()->num(),
          Token::String(expr->op()),
@@ skipping 11 matching lines @@
 
 void TextInstructionPrinter::VisitThisFunction(ThisFunction* expr) {
   PrintF("ThisFunction");
 }
 
 
 static int node_count = 0;
 static int instruction_count = 0;
 
 
-void Node::AssignNumbers() {
+void Node::AssignNodeNumber() {
   set_number(node_count++);
 }
 
 
-void BlockNode::AssignNumbers() {
-  set_number(node_count++);
-  for (int i = 0, len = instructions_.length(); i < len; i++) {
-    instructions_[i]->set_num(instruction_count++);
+void Node::PrintReachingDefinitions() {
+  if (rd_.rd_in() != NULL) {
+    ASSERT(rd_.kill() != NULL && rd_.gen() != NULL);
+
+    PrintF("RD_in = {");
+    bool first = true;
+    for (int i = 0; i < rd_.rd_in()->length(); i++) {
+      if (rd_.rd_in()->Contains(i)) {
+        if (!first) PrintF(",");
+        PrintF("%d");
+        first = false;
+      }
+    }
+    PrintF("}\n");
+
+    PrintF("RD_kill = {");
+    first = true;
+    for (int i = 0; i < rd_.kill()->length(); i++) {
+      if (rd_.kill()->Contains(i)) {
+        if (!first) PrintF(",");
+        PrintF("%d");
+        first = false;
+      }
+    }
+    PrintF("}\n");
+
+    PrintF("RD_gen = {");
+    first = true;
+    for (int i = 0; i < rd_.gen()->length(); i++) {
+      if (rd_.gen()->Contains(i)) {
+        if (!first) PrintF(",");
+        PrintF("%d");
+        first = false;
+      }
+    }
+    PrintF("}\n");
   }
 }
 
 
 void ExitNode::PrintText() {
+  PrintReachingDefinitions();
   PrintF("L%d: Exit\n\n", number());
 }
 
 
 void BlockNode::PrintText() {
+  PrintReachingDefinitions();
   // Print the instructions in the block.
   PrintF("L%d: Block\n", number());
   TextInstructionPrinter printer;
   for (int i = 0, len = instructions_.length(); i < len; i++) {
-    PrintF("%d ", instructions_[i]->num());
+    PrintF("%d ", printer.NextNumber());
     printer.Visit(instructions_[i]);
+    printer.AssignNumber(instructions_[i]);
     PrintF("\n");
   }
   PrintF("goto L%d\n\n", successor_->number());
 }
 
 
 void BranchNode::PrintText() {
+  PrintReachingDefinitions();
   PrintF("L%d: Branch\n", number());
   PrintF("goto (L%d, L%d)\n\n", successor0_->number(), successor1_->number());
 }
 
 
 void JoinNode::PrintText() {
+  PrintReachingDefinitions();
   PrintF("L%d: Join(", number());
   for (int i = 0, len = predecessors_.length(); i < len; i++) {
     if (i != 0) PrintF(", ");
     PrintF("L%d", predecessors_[i]->number());
   }
   PrintF(")\ngoto L%d\n\n", successor_->number());
 }
 
 
 void FlowGraph::PrintText(ZoneList<Node*>* postorder) {
   PrintF("\n========\n");
 
   // Number nodes and instructions in reverse postorder.
   node_count = 0;
   instruction_count = 0;
   for (int i = postorder->length() - 1; i >= 0; i--) {
-    postorder->at(i)->AssignNumbers();
+    postorder->at(i)->AssignNodeNumber();
   }
 
   // Print basic blocks in reverse postorder.
   for (int i = postorder->length() - 1; i >= 0; i--) {
     postorder->at(i)->PrintText();
   }
 }
 
 
 #endif  // defined(DEBUG)
 
 
+int ReachingDefinitions::IndexFor(Variable* var, int variable_count) {
+  // Parameters are numbered left-to-right from the beginning of the bit
+  // set.  Stack-allocated locals are allocated right-to-left from the end.
+  ASSERT(var != NULL && var->IsStackAllocated());
+  Slot* slot = var->slot();
+  if (slot->type() == Slot::PARAMETER) {
+    return slot->index();
+  } else {
+    return (variable_count - 1) - slot->index();
+  }
+}
+
+
+void Node::InitializeReachingDefinitions(int definition_count,
+                                         List<BitVector*>* variables) {
+  rd_.Initialize(definition_count);
+}
+
+
+void BlockNode::InitializeReachingDefinitions(int definition_count,
+                                              List<BitVector*>* variables) {
+  int instruction_count = instructions_.length();
+  int variable_count = variables->length();
+
+  rd_.Initialize(definition_count);
+
+  for (int i = 0; i < instruction_count; i++) {
+    Expression* expr = instructions_[i]->AsExpression();
+    if (expr == NULL) continue;
+    Variable* var = expr->AssignedVar();
+    if (var == NULL) continue;
+
+    // All definitions of this variable are killed.
+    BitVector* def_set =
+        variables->at(ReachingDefinitions::IndexFor(var, variable_count));
+    rd_.kill()->Union(*def_set);
+
+    // All previously generated definitions are not generated.
+    rd_.gen()->Subtract(*def_set);
+
+    // This one is generated.
+    rd_.gen()->Add(expr->num());
+  }
+}
+
+
+void ReachingDefinitions::Compute() {
+  if (definitions_->is_empty()) return;
+
+  int variable_count = variables_.length();
+  int definition_count = definitions_->length();
+  int block_count = postorder_->length();
+
+  // Step 1: For each variable, identify the set of all its definitions in
+  // the body.
+  for (int i = 0; i < definition_count; i++) {
+    Variable* var = definitions_->at(i)->AssignedVar();
+    variables_[IndexFor(var, variable_count)]->Add(i);
+  }
+
+  if (FLAG_print_graph_text) {
+    for (int i = 0; i < variable_count; i++) {
+      BitVector* def_set = variables_[i];
+      if (!def_set->IsEmpty()) {
+        // At least one definition.
+        bool first = true;
+        for (int j = 0; j < definition_count; j++) {
+          if (def_set->Contains(j)) {
+            if (first) {
+              Variable* var = definitions_->at(j)->AssignedVar();
+              ASSERT(var != NULL);
+              PrintF("Def[%s] = {%d", *var->name()->ToCString(), j);
+              first = false;
+            } else {
+              PrintF(", %d", j);
+            }
+          }
+        }
+        PrintF("}\n");
+      }
+    }
+  }
+
+  // Step 2: Compute KILL and GEN for each block node, initialize RD.
+  for (int i = block_count - 1; i >= 0; i--) {
+    postorder_->at(i)->InitializeReachingDefinitions(definition_count,
+                                                     &variables_);
+  }
+}
+
+
 } }  // namespace v8::internal