Initial support for marking live code.

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 1645 matching lines @@
   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++) {
+    AstNode* instr = instructions_[i];
+    // Print a star next to dead instructions.
+    if (instr->AsExpression() != NULL && instr->AsExpression()->is_live()) {
+      PrintF("  ");
+    } else {
+      PrintF("* ");
+    }
     PrintF("%d ", printer.NextNumber());
-    printer.Visit(instructions_[i]);
-    printer.AssignNumber(instructions_[i]);
+    printer.Visit(instr);
+    printer.AssignNumber(instr);
     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());
@@ skipping 67 matching lines @@
   rd_.Initialize(definition_count);
   // The RD_in set for the entry node has a definition for each parameter
   // and local.
   if (predecessor_ == NULL) {
     for (int i = 0; i < variable_count; i++) rd_.rd_in()->Add(i);
   }
 
   for (int i = 0; i < instruction_count; i++) {
     Expression* expr = instructions_[i]->AsExpression();
     if (expr == NULL) continue;
-    Variable* var = expr->AssignedVar();
+    Variable* var = expr->AssignedVariable();
     if (var == NULL || !var->IsStackAllocated()) 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);
 
@@ skipping 156 matching lines @@
                                                       variable_count));
       BitVector* reaching_definitions = new BitVector(*definitions);
       // Intersected with all definitions (of any variable) reaching this
       // instruction.
       reaching_definitions->Intersect(rd);
       proxy->set_reaching_definitions(reaching_definitions);
     }
 
     // It may instead (or also) be a definition.  If so update the running
     // value of reaching definitions for the block.
-    Variable* var = expr->AssignedVar();
+    Variable* var = expr->AssignedVariable();
     if (var == NULL || !var->IsStackAllocated()) continue;
 
     // All definitions of this variable are killed.
     BitVector* def_set =
         variables->at(ReachingDefinitions::IndexFor(var, variable_count));
     rd.Subtract(*def_set);
     // This definition is generated.
     rd.Add(expr->num());
   }
 }
@@ skipping 10 matching lines @@
   List<BitVector*> variables;
   for (int i = 0; i < variable_count_; i++) {
     // Add the initial definition for each variable.
     BitVector* initial = new BitVector(definition_count);
     initial->Add(i);
     variables.Add(initial);
   }
   for (int i = 0, len = body_definitions_->length(); i < len; i++) {
     // Account for each definition in the body as a definition of the
     // defined variable.
-    Variable* var = body_definitions_->at(i)->AssignedVar();
+    Variable* var = body_definitions_->at(i)->AssignedVariable();
     variables[IndexFor(var, variable_count_)]->Add(i + variable_count_);
   }
 
   // Step 2: Compute KILL and GEN for each block node, initialize RD_in for
   // all nodes, and mark and add all nodes to the worklist in reverse
   // postorder.  All nodes should currently have the same mark.
   bool mark = postorder_->at(0)->IsMarkedWith(false);  // Negation of current.
   WorkList<Node> worklist(node_count);
   for (int i = node_count - 1; i >= 0; i--) {
     postorder_->at(i)->InitializeReachingDefinitions(definition_count,
@@ skipping 64 matching lines @@
               }
             }
           }
         }
       }
     }
   } while (changed);
 }
 
 
+void Node::MarkCriticalInstructions(
+    List<AstNode*>* stack,
+    ZoneList<Expression*>* body_definitions,
+    int variable_count) {
+}
+
+
+void BlockNode::MarkCriticalInstructions(
+    List<AstNode*>* stack,
+    ZoneList<Expression*>* body_definitions,
+    int variable_count) {
+  for (int i = instructions_.length() - 1; i >= 0; i--) {
+    // Only expressions can appear in the flow graph for now.
+    Expression* expr = instructions_[i]->AsExpression();
+    if (expr != NULL && !expr->is_live() &&
+        (expr->is_loop_condition() || expr->IsCritical())) {
+      expr->mark_as_live();
+      expr->ProcessNonLiveChildren(stack, body_definitions, variable_count);
+    }
+  }
+}
+
+
+void MarkLiveCode(ZoneList<Node*>* nodes,
+                  ZoneList<Expression*>* body_definitions,
+                  int variable_count) {
+  List<AstNode*> stack(20);
+
+  // Mark the critical AST nodes as live; mark their dependencies and
+  // add them to the marking stack.
+  for (int i = nodes->length() - 1; i >= 0; i--) {
+    nodes->at(i)->MarkCriticalInstructions(&stack, body_definitions,
+                                           variable_count);
+  }
+
+  // Continue marking dependencies until no more.
+  while (!stack.is_empty()) {
+  // Only expressions can appear in the flow graph for now.
+    Expression* expr = stack.RemoveLast()->AsExpression();
+    if (expr != NULL) {
+      expr->ProcessNonLiveChildren(&stack, body_definitions, variable_count);
+    }
+  }
+}
+
+
 } }  // namespace v8::internal