diff options
author | Ryan Dahl <ry@tinyclouds.org> | 2010-03-26 09:09:40 -0700 |
---|---|---|
committer | Ryan Dahl <ry@tinyclouds.org> | 2010-03-26 09:09:40 -0700 |
commit | 6192b8659a3dedb86393cfb78121a26f2a3e31e6 (patch) | |
tree | 78b74bbdc1a7cdd8989e32db309050d6e51ba346 /deps/v8/src/data-flow.cc | |
parent | bb00fef3cd2ff446aa5c1894fb4830f83750018a (diff) | |
download | node-new-6192b8659a3dedb86393cfb78121a26f2a3e31e6.tar.gz |
Upgrade V8 to 2.1.10
Diffstat (limited to 'deps/v8/src/data-flow.cc')
-rw-r--r-- | deps/v8/src/data-flow.cc | 1321 |
1 files changed, 383 insertions, 938 deletions
diff --git a/deps/v8/src/data-flow.cc b/deps/v8/src/data-flow.cc index fe4b3db00e..1bc77c0338 100644 --- a/deps/v8/src/data-flow.cc +++ b/deps/v8/src/data-flow.cc @@ -28,6 +28,7 @@ #include "v8.h" #include "data-flow.h" +#include "flow-graph.h" #include "scopes.h" namespace v8 { @@ -50,561 +51,6 @@ void BitVector::Print() { #endif -void FlowGraph::AppendInstruction(AstNode* instruction) { - // Add a (non-null) AstNode to the end of the graph fragment. - ASSERT(instruction != NULL); - if (exit()->IsExitNode()) return; - if (!exit()->IsBlockNode()) AppendNode(new BlockNode()); - BlockNode::cast(exit())->AddInstruction(instruction); -} - - -void FlowGraph::AppendNode(Node* node) { - // Add a node to the end of the graph. An empty block is added to - // maintain edge-split form (that no join nodes or exit nodes as - // successors to branch nodes). - ASSERT(node != NULL); - if (exit()->IsExitNode()) return; - if (exit()->IsBranchNode() && (node->IsJoinNode() || node->IsExitNode())) { - AppendNode(new BlockNode()); - } - exit()->AddSuccessor(node); - node->AddPredecessor(exit()); - exit_ = node; -} - - -void FlowGraph::AppendGraph(FlowGraph* graph) { - // Add a flow graph fragment to the end of this one. An empty block is - // added to maintain edge-split form (that no join nodes or exit nodes as - // successors to branch nodes). - ASSERT(graph != NULL); - if (exit()->IsExitNode()) return; - Node* node = graph->entry(); - if (exit()->IsBranchNode() && (node->IsJoinNode() || node->IsExitNode())) { - AppendNode(new BlockNode()); - } - exit()->AddSuccessor(node); - node->AddPredecessor(exit()); - exit_ = graph->exit(); -} - - -void FlowGraph::Split(BranchNode* branch, - FlowGraph* left, - FlowGraph* right, - JoinNode* join) { - // Add the branch node, left flowgraph, join node. - AppendNode(branch); - AppendGraph(left); - AppendNode(join); - - // Splice in the right flowgraph. - right->AppendNode(join); - branch->AddSuccessor(right->entry()); - right->entry()->AddPredecessor(branch); -} - - -void FlowGraph::Loop(JoinNode* join, - FlowGraph* condition, - BranchNode* branch, - FlowGraph* body) { - // Add the join, condition and branch. Add join's predecessors in - // left-to-right order. - AppendNode(join); - body->AppendNode(join); - AppendGraph(condition); - AppendNode(branch); - - // Splice in the body flowgraph. - branch->AddSuccessor(body->entry()); - body->entry()->AddPredecessor(branch); -} - - -void ExitNode::Traverse(bool mark, - ZoneList<Node*>* preorder, - ZoneList<Node*>* postorder) { - preorder->Add(this); - postorder->Add(this); -} - - -void BlockNode::Traverse(bool mark, - ZoneList<Node*>* preorder, - ZoneList<Node*>* postorder) { - ASSERT(successor_ != NULL); - preorder->Add(this); - if (!successor_->IsMarkedWith(mark)) { - successor_->MarkWith(mark); - successor_->Traverse(mark, preorder, postorder); - } - 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); - } - postorder->Add(this); -} - - -void JoinNode::Traverse(bool mark, - ZoneList<Node*>* preorder, - ZoneList<Node*>* postorder) { - ASSERT(successor_ != NULL); - preorder->Add(this); - if (!successor_->IsMarkedWith(mark)) { - successor_->MarkWith(mark); - successor_->Traverse(mark, preorder, postorder); - } - postorder->Add(this); -} - - -void FlowGraphBuilder::Build(FunctionLiteral* lit) { - global_exit_ = new ExitNode(); - VisitStatements(lit->body()); - - if (HasStackOverflow()) return; - - // The graph can end with a branch node (if the function ended with a - // loop). Maintain edge-split form (no join nodes or exit nodes as - // successors to branch nodes). - if (graph_.exit()->IsBranchNode()) graph_.AppendNode(new BlockNode()); - graph_.AppendNode(global_exit_); - - // Build preorder and postorder traversal orders. All the nodes in - // the graph have the same mark flag. For the traversal, use that - // flag's negation. Traversal will flip all the flags. - bool mark = graph_.entry()->IsMarkedWith(false); - graph_.entry()->MarkWith(mark); - graph_.entry()->Traverse(mark, &preorder_, &postorder_); -} - - -// This function peels off one iteration of a for-loop. The return value -// is either a block statement containing the peeled loop or NULL in case -// there is a stack overflow. -static Statement* PeelForLoop(ForStatement* stmt) { - // Mark this for-statement as processed. - stmt->set_peel_this_loop(false); - - // Create new block containing the init statement of the for-loop and - // an if-statement containing the peeled iteration and the original - // loop without the init-statement. - Block* block = new Block(NULL, 2, false); - if (stmt->init() != NULL) { - Statement* init = stmt->init(); - // The init statement gets the statement position of the for-loop - // to make debugging of peeled loops possible. - init->set_statement_pos(stmt->statement_pos()); - block->AddStatement(init); - } - - // Copy the condition. - CopyAstVisitor copy_visitor; - Expression* cond_copy = stmt->cond() != NULL - ? copy_visitor.DeepCopyExpr(stmt->cond()) - : new Literal(Factory::true_value()); - if (copy_visitor.HasStackOverflow()) return NULL; - - // Construct a block with the peeled body and the rest of the for-loop. - Statement* body_copy = copy_visitor.DeepCopyStmt(stmt->body()); - if (copy_visitor.HasStackOverflow()) return NULL; - - Statement* next_copy = stmt->next() != NULL - ? copy_visitor.DeepCopyStmt(stmt->next()) - : new EmptyStatement(); - if (copy_visitor.HasStackOverflow()) return NULL; - - Block* peeled_body = new Block(NULL, 3, false); - peeled_body->AddStatement(body_copy); - peeled_body->AddStatement(next_copy); - peeled_body->AddStatement(stmt); - - // Remove the duplicated init statement from the for-statement. - stmt->set_init(NULL); - - // Create new test at the top and add it to the newly created block. - IfStatement* test = new IfStatement(cond_copy, - peeled_body, - new EmptyStatement()); - block->AddStatement(test); - return block; -} - - -void FlowGraphBuilder::VisitStatements(ZoneList<Statement*>* stmts) { - for (int i = 0, len = stmts->length(); i < len; i++) { - stmts->at(i) = ProcessStatement(stmts->at(i)); - } -} - - -Statement* FlowGraphBuilder::ProcessStatement(Statement* stmt) { - if (FLAG_loop_peeling && - stmt->AsForStatement() != NULL && - stmt->AsForStatement()->peel_this_loop()) { - Statement* tmp_stmt = PeelForLoop(stmt->AsForStatement()); - if (tmp_stmt == NULL) { - SetStackOverflow(); - } else { - stmt = tmp_stmt; - } - } - Visit(stmt); - return stmt; -} - - -void FlowGraphBuilder::VisitDeclaration(Declaration* decl) { - UNREACHABLE(); -} - - -void FlowGraphBuilder::VisitBlock(Block* stmt) { - VisitStatements(stmt->statements()); -} - - -void FlowGraphBuilder::VisitExpressionStatement(ExpressionStatement* stmt) { - Visit(stmt->expression()); -} - - -void FlowGraphBuilder::VisitEmptyStatement(EmptyStatement* stmt) { - // Nothing to do. -} - - -void FlowGraphBuilder::VisitIfStatement(IfStatement* stmt) { - Visit(stmt->condition()); - - BranchNode* branch = new BranchNode(); - FlowGraph original = graph_; - graph_ = FlowGraph::Empty(); - stmt->set_then_statement(ProcessStatement(stmt->then_statement())); - - FlowGraph left = graph_; - graph_ = FlowGraph::Empty(); - stmt->set_else_statement(ProcessStatement(stmt->else_statement())); - - if (HasStackOverflow()) return; - JoinNode* join = new JoinNode(); - original.Split(branch, &left, &graph_, join); - graph_ = original; -} - - -void FlowGraphBuilder::VisitContinueStatement(ContinueStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitBreakStatement(BreakStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitReturnStatement(ReturnStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitWithEnterStatement(WithEnterStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitWithExitStatement(WithExitStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitDoWhileStatement(DoWhileStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitWhileStatement(WhileStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitForStatement(ForStatement* stmt) { - if (stmt->init() != NULL) stmt->set_init(ProcessStatement(stmt->init())); - - JoinNode* join = new JoinNode(); - FlowGraph original = graph_; - graph_ = FlowGraph::Empty(); - if (stmt->cond() != NULL) Visit(stmt->cond()); - - BranchNode* branch = new BranchNode(); - FlowGraph condition = graph_; - graph_ = FlowGraph::Empty(); - stmt->set_body(ProcessStatement(stmt->body())); - - if (stmt->next() != NULL) stmt->set_next(ProcessStatement(stmt->next())); - - if (HasStackOverflow()) return; - original.Loop(join, &condition, branch, &graph_); - graph_ = original; -} - - -void FlowGraphBuilder::VisitForInStatement(ForInStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitTryCatchStatement(TryCatchStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitTryFinallyStatement(TryFinallyStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitDebuggerStatement(DebuggerStatement* stmt) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitFunctionLiteral(FunctionLiteral* expr) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitSharedFunctionInfoLiteral( - SharedFunctionInfoLiteral* expr) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitConditional(Conditional* expr) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitSlot(Slot* expr) { - UNREACHABLE(); -} - - -void FlowGraphBuilder::VisitVariableProxy(VariableProxy* expr) { - graph_.AppendInstruction(expr); -} - - -void FlowGraphBuilder::VisitLiteral(Literal* expr) { - graph_.AppendInstruction(expr); -} - - -void FlowGraphBuilder::VisitRegExpLiteral(RegExpLiteral* expr) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitObjectLiteral(ObjectLiteral* expr) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitArrayLiteral(ArrayLiteral* expr) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitCatchExtensionObject(CatchExtensionObject* expr) { - SetStackOverflow(); -} - - -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) { - if (expr->is_compound()) Visit(expr->target()); - Visit(expr->value()); - if (var->IsStackAllocated()) { - // The first definition in the body is numbered n, where n is the - // number of parameters and stack-allocated locals. - expr->set_num(body_definitions_.length() + variable_count_); - body_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); -} - - -void FlowGraphBuilder::VisitThrow(Throw* expr) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitProperty(Property* expr) { - Visit(expr->obj()); - if (!expr->key()->IsPropertyName()) Visit(expr->key()); - - if (HasStackOverflow()) return; - graph_.AppendInstruction(expr); -} - - -void FlowGraphBuilder::VisitCall(Call* expr) { - Visit(expr->expression()); - ZoneList<Expression*>* arguments = expr->arguments(); - for (int i = 0, len = arguments->length(); i < len; i++) { - Visit(arguments->at(i)); - } - - if (HasStackOverflow()) return; - graph_.AppendInstruction(expr); -} - - -void FlowGraphBuilder::VisitCallNew(CallNew* expr) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitCallRuntime(CallRuntime* expr) { - SetStackOverflow(); -} - - -void FlowGraphBuilder::VisitUnaryOperation(UnaryOperation* expr) { - switch (expr->op()) { - case Token::NOT: - case Token::BIT_NOT: - case Token::DELETE: - case Token::TYPEOF: - case Token::VOID: - SetStackOverflow(); - break; - - case Token::ADD: - case Token::SUB: - Visit(expr->expression()); - if (HasStackOverflow()) return; - graph_.AppendInstruction(expr); - break; - - default: - UNREACHABLE(); - } -} - - -void FlowGraphBuilder::VisitCountOperation(CountOperation* expr) { - Visit(expr->expression()); - Variable* var = expr->expression()->AsVariableProxy()->AsVariable(); - if (var != NULL && var->IsStackAllocated()) { - // The first definition in the body is numbered n, where n is the number - // of parameters and stack-allocated locals. - expr->set_num(body_definitions_.length() + variable_count_); - body_definitions_.Add(expr); - } - - if (HasStackOverflow()) return; - graph_.AppendInstruction(expr); -} - - -void FlowGraphBuilder::VisitBinaryOperation(BinaryOperation* expr) { - switch (expr->op()) { - case Token::COMMA: - case Token::OR: - case Token::AND: - SetStackOverflow(); - break; - - case Token::BIT_OR: - case Token::BIT_XOR: - case Token::BIT_AND: - case Token::SHL: - case Token::SHR: - case Token::ADD: - case Token::SUB: - case Token::MUL: - case Token::DIV: - case Token::MOD: - case Token::SAR: - Visit(expr->left()); - Visit(expr->right()); - if (HasStackOverflow()) return; - graph_.AppendInstruction(expr); - break; - - default: - UNREACHABLE(); - } -} - - -void FlowGraphBuilder::VisitCompareOperation(CompareOperation* expr) { - switch (expr->op()) { - case Token::EQ: - case Token::NE: - case Token::EQ_STRICT: - case Token::NE_STRICT: - case Token::INSTANCEOF: - case Token::IN: - SetStackOverflow(); - break; - - case Token::LT: - case Token::GT: - case Token::LTE: - case Token::GTE: - Visit(expr->left()); - Visit(expr->right()); - if (HasStackOverflow()) return; - graph_.AppendInstruction(expr); - break; - - default: - UNREACHABLE(); - } -} - - -void FlowGraphBuilder::VisitThisFunction(ThisFunction* expr) { - SetStackOverflow(); -} - - void AstLabeler::Label(CompilationInfo* info) { info_ = info; VisitStatements(info_->function()->body()); @@ -1300,6 +746,387 @@ void AssignedVariablesAnalyzer::VisitDeclaration(Declaration* decl) { } +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, + WorkList<Node>* worklist, + bool mark) { + ASSERT(!IsMarkedWith(mark)); + rd_.Initialize(definition_count); + MarkWith(mark); + worklist->Insert(this); +} + + +void BlockNode::InitializeReachingDefinitions(int definition_count, + List<BitVector*>* variables, + WorkList<Node>* worklist, + bool mark) { + ASSERT(!IsMarkedWith(mark)); + int instruction_count = instructions_.length(); + int variable_count = variables->length(); + + 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->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); + + // This one is generated. + rd_.gen()->Add(expr->num()); + } + + // Add all blocks except the entry node to the worklist. + if (predecessor_ != NULL) { + MarkWith(mark); + worklist->Insert(this); + } +} + + +void ExitNode::ComputeRDOut(BitVector* result) { + // Should not be the predecessor of any node. + UNREACHABLE(); +} + + +void BlockNode::ComputeRDOut(BitVector* result) { + // All definitions reaching this block ... + *result = *rd_.rd_in(); + // ... except those killed by the block ... + result->Subtract(*rd_.kill()); + // ... but including those generated by the block. + result->Union(*rd_.gen()); +} + + +void BranchNode::ComputeRDOut(BitVector* result) { + // Branch nodes don't kill or generate definitions. + *result = *rd_.rd_in(); +} + + +void JoinNode::ComputeRDOut(BitVector* result) { + // Join nodes don't kill or generate definitions. + *result = *rd_.rd_in(); +} + + +void ExitNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) { + // The exit node has no successors so we can just update in place. New + // RD_in is the union over all predecessors. + int definition_count = rd_.rd_in()->length(); + rd_.rd_in()->Clear(); + + BitVector temp(definition_count); + for (int i = 0, len = predecessors_.length(); i < len; i++) { + // Because ComputeRDOut always overwrites temp and its value is + // always read out before calling ComputeRDOut again, we do not + // have to clear it on each iteration of the loop. + predecessors_[i]->ComputeRDOut(&temp); + rd_.rd_in()->Union(temp); + } +} + + +void BlockNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) { + // The entry block has no predecessor. Its RD_in does not change. + if (predecessor_ == NULL) return; + + BitVector new_rd_in(rd_.rd_in()->length()); + predecessor_->ComputeRDOut(&new_rd_in); + + if (rd_.rd_in()->Equals(new_rd_in)) return; + + // Update RD_in. + *rd_.rd_in() = new_rd_in; + // Add the successor to the worklist if not already present. + if (!successor_->IsMarkedWith(mark)) { + successor_->MarkWith(mark); + worklist->Insert(successor_); + } +} + + +void BranchNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) { + BitVector new_rd_in(rd_.rd_in()->length()); + predecessor_->ComputeRDOut(&new_rd_in); + + if (rd_.rd_in()->Equals(new_rd_in)) return; + + // Update RD_in. + *rd_.rd_in() = new_rd_in; + // Add the successors to the worklist if not already present. + if (!successor0_->IsMarkedWith(mark)) { + successor0_->MarkWith(mark); + worklist->Insert(successor0_); + } + if (!successor1_->IsMarkedWith(mark)) { + successor1_->MarkWith(mark); + worklist->Insert(successor1_); + } +} + + +void JoinNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) { + int definition_count = rd_.rd_in()->length(); + BitVector new_rd_in(definition_count); + + // New RD_in is the union over all predecessors. + BitVector temp(definition_count); + for (int i = 0, len = predecessors_.length(); i < len; i++) { + predecessors_[i]->ComputeRDOut(&temp); + new_rd_in.Union(temp); + } + + if (rd_.rd_in()->Equals(new_rd_in)) return; + + // Update RD_in. + *rd_.rd_in() = new_rd_in; + // Add the successor to the worklist if not already present. + if (!successor_->IsMarkedWith(mark)) { + successor_->MarkWith(mark); + worklist->Insert(successor_); + } +} + + +void Node::PropagateReachingDefinitions(List<BitVector*>* variables) { + // Nothing to do. +} + + +void BlockNode::PropagateReachingDefinitions(List<BitVector*>* variables) { + // Propagate RD_in from the start of the block to all the variable + // references. + int variable_count = variables->length(); + BitVector rd = *rd_.rd_in(); + for (int i = 0, len = instructions_.length(); i < len; i++) { + Expression* expr = instructions_[i]->AsExpression(); + if (expr == NULL) continue; + + // Look for a variable reference to record its reaching definitions. + VariableProxy* proxy = expr->AsVariableProxy(); + if (proxy == NULL) { + // Not a VariableProxy? Maybe it's a count operation. + CountOperation* count_operation = expr->AsCountOperation(); + if (count_operation != NULL) { + proxy = count_operation->expression()->AsVariableProxy(); + } + } + if (proxy == NULL) { + // OK, Maybe it's a compound assignment. + Assignment* assignment = expr->AsAssignment(); + if (assignment != NULL && assignment->is_compound()) { + proxy = assignment->target()->AsVariableProxy(); + } + } + + if (proxy != NULL && + proxy->var()->IsStackAllocated() && + !proxy->var()->is_this()) { + // All definitions for this variable. + BitVector* definitions = + variables->at(ReachingDefinitions::IndexFor(proxy->var(), + 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->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()); + } +} + + +void ReachingDefinitions::Compute() { + // The definitions in the body plus an implicit definition for each + // variable at function entry. + int definition_count = body_definitions_->length() + variable_count_; + int node_count = postorder_->length(); + + // Step 1: For each stack-allocated variable, identify the set of all its + // definitions. + 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)->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, + &variables, + &worklist, + mark); + } + + // Step 3: Until the worklist is empty, remove an item compute and update + // its rd_in based on its predecessor's rd_out. If rd_in has changed, add + // all necessary successors to the worklist. + while (!worklist.is_empty()) { + Node* node = worklist.Remove(); + node->MarkWith(!mark); + node->UpdateRDIn(&worklist, mark); + } + + // Step 4: Based on RD_in for block nodes, propagate reaching definitions + // to all variable uses in the block. + for (int i = 0; i < node_count; i++) { + postorder_->at(i)->PropagateReachingDefinitions(&variables); + } +} + + +bool TypeAnalyzer::IsPrimitiveDef(int def_num) { + if (def_num < param_count_) return false; + if (def_num < variable_count_) return true; + return body_definitions_->at(def_num - variable_count_)->IsPrimitive(); +} + + +void TypeAnalyzer::Compute() { + bool changed; + int count = 0; + + do { + changed = false; + + if (FLAG_print_graph_text) { + PrintF("TypeAnalyzer::Compute - iteration %d\n", count++); + } + + for (int i = postorder_->length() - 1; i >= 0; --i) { + Node* node = postorder_->at(i); + if (node->IsBlockNode()) { + BlockNode* block = BlockNode::cast(node); + for (int j = 0; j < block->instructions()->length(); j++) { + Expression* expr = block->instructions()->at(j)->AsExpression(); + if (expr != NULL) { + // For variable uses: Compute new type from reaching definitions. + VariableProxy* proxy = expr->AsVariableProxy(); + if (proxy != NULL && proxy->reaching_definitions() != NULL) { + BitVector* rd = proxy->reaching_definitions(); + bool prim_type = true; + // TODO(fsc): A sparse set representation of reaching + // definitions would speed up iterating here. + for (int k = 0; k < rd->length(); k++) { + if (rd->Contains(k) && !IsPrimitiveDef(k)) { + prim_type = false; + break; + } + } + // Reset changed flag if new type information was computed. + if (prim_type != proxy->IsPrimitive()) { + changed = true; + proxy->SetIsPrimitive(prim_type); + } + } + } + } + } + } + } 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); + } + } +} + + #ifdef DEBUG // Print a textual representation of an instruction in a flow graph. Using @@ -1714,389 +1541,7 @@ void FlowGraph::PrintText(FunctionLiteral* fun, ZoneList<Node*>* postorder) { } } - -#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, - WorkList<Node>* worklist, - bool mark) { - ASSERT(!IsMarkedWith(mark)); - rd_.Initialize(definition_count); - MarkWith(mark); - worklist->Insert(this); -} - - -void BlockNode::InitializeReachingDefinitions(int definition_count, - List<BitVector*>* variables, - WorkList<Node>* worklist, - bool mark) { - ASSERT(!IsMarkedWith(mark)); - int instruction_count = instructions_.length(); - int variable_count = variables->length(); - - 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->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); - - // This one is generated. - rd_.gen()->Add(expr->num()); - } - - // Add all blocks except the entry node to the worklist. - if (predecessor_ != NULL) { - MarkWith(mark); - worklist->Insert(this); - } -} - - -void ExitNode::ComputeRDOut(BitVector* result) { - // Should not be the predecessor of any node. - UNREACHABLE(); -} - - -void BlockNode::ComputeRDOut(BitVector* result) { - // All definitions reaching this block ... - *result = *rd_.rd_in(); - // ... except those killed by the block ... - result->Subtract(*rd_.kill()); - // ... but including those generated by the block. - result->Union(*rd_.gen()); -} - - -void BranchNode::ComputeRDOut(BitVector* result) { - // Branch nodes don't kill or generate definitions. - *result = *rd_.rd_in(); -} - - -void JoinNode::ComputeRDOut(BitVector* result) { - // Join nodes don't kill or generate definitions. - *result = *rd_.rd_in(); -} - - -void ExitNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) { - // The exit node has no successors so we can just update in place. New - // RD_in is the union over all predecessors. - int definition_count = rd_.rd_in()->length(); - rd_.rd_in()->Clear(); - - BitVector temp(definition_count); - for (int i = 0, len = predecessors_.length(); i < len; i++) { - // Because ComputeRDOut always overwrites temp and its value is - // always read out before calling ComputeRDOut again, we do not - // have to clear it on each iteration of the loop. - predecessors_[i]->ComputeRDOut(&temp); - rd_.rd_in()->Union(temp); - } -} - - -void BlockNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) { - // The entry block has no predecessor. Its RD_in does not change. - if (predecessor_ == NULL) return; - - BitVector new_rd_in(rd_.rd_in()->length()); - predecessor_->ComputeRDOut(&new_rd_in); - - if (rd_.rd_in()->Equals(new_rd_in)) return; - - // Update RD_in. - *rd_.rd_in() = new_rd_in; - // Add the successor to the worklist if not already present. - if (!successor_->IsMarkedWith(mark)) { - successor_->MarkWith(mark); - worklist->Insert(successor_); - } -} - - -void BranchNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) { - BitVector new_rd_in(rd_.rd_in()->length()); - predecessor_->ComputeRDOut(&new_rd_in); - - if (rd_.rd_in()->Equals(new_rd_in)) return; - - // Update RD_in. - *rd_.rd_in() = new_rd_in; - // Add the successors to the worklist if not already present. - if (!successor0_->IsMarkedWith(mark)) { - successor0_->MarkWith(mark); - worklist->Insert(successor0_); - } - if (!successor1_->IsMarkedWith(mark)) { - successor1_->MarkWith(mark); - worklist->Insert(successor1_); - } -} - - -void JoinNode::UpdateRDIn(WorkList<Node>* worklist, bool mark) { - int definition_count = rd_.rd_in()->length(); - BitVector new_rd_in(definition_count); - - // New RD_in is the union over all predecessors. - BitVector temp(definition_count); - for (int i = 0, len = predecessors_.length(); i < len; i++) { - predecessors_[i]->ComputeRDOut(&temp); - new_rd_in.Union(temp); - } - - if (rd_.rd_in()->Equals(new_rd_in)) return; - - // Update RD_in. - *rd_.rd_in() = new_rd_in; - // Add the successor to the worklist if not already present. - if (!successor_->IsMarkedWith(mark)) { - successor_->MarkWith(mark); - worklist->Insert(successor_); - } -} - - -void Node::PropagateReachingDefinitions(List<BitVector*>* variables) { - // Nothing to do. -} - - -void BlockNode::PropagateReachingDefinitions(List<BitVector*>* variables) { - // Propagate RD_in from the start of the block to all the variable - // references. - int variable_count = variables->length(); - BitVector rd = *rd_.rd_in(); - for (int i = 0, len = instructions_.length(); i < len; i++) { - Expression* expr = instructions_[i]->AsExpression(); - if (expr == NULL) continue; - - // Look for a variable reference to record its reaching definitions. - VariableProxy* proxy = expr->AsVariableProxy(); - if (proxy == NULL) { - // Not a VariableProxy? Maybe it's a count operation. - CountOperation* count_operation = expr->AsCountOperation(); - if (count_operation != NULL) { - proxy = count_operation->expression()->AsVariableProxy(); - } - } - if (proxy == NULL) { - // OK, Maybe it's a compound assignment. - Assignment* assignment = expr->AsAssignment(); - if (assignment != NULL && assignment->is_compound()) { - proxy = assignment->target()->AsVariableProxy(); - } - } - - if (proxy != NULL && - proxy->var()->IsStackAllocated() && - !proxy->var()->is_this()) { - // All definitions for this variable. - BitVector* definitions = - variables->at(ReachingDefinitions::IndexFor(proxy->var(), - 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->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()); - } -} - - -void ReachingDefinitions::Compute() { - // The definitions in the body plus an implicit definition for each - // variable at function entry. - int definition_count = body_definitions_->length() + variable_count_; - int node_count = postorder_->length(); - - // Step 1: For each stack-allocated variable, identify the set of all its - // definitions. - 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)->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, - &variables, - &worklist, - mark); - } - - // Step 3: Until the worklist is empty, remove an item compute and update - // its rd_in based on its predecessor's rd_out. If rd_in has changed, add - // all necessary successors to the worklist. - while (!worklist.is_empty()) { - Node* node = worklist.Remove(); - node->MarkWith(!mark); - node->UpdateRDIn(&worklist, mark); - } - - // Step 4: Based on RD_in for block nodes, propagate reaching definitions - // to all variable uses in the block. - for (int i = 0; i < node_count; i++) { - postorder_->at(i)->PropagateReachingDefinitions(&variables); - } -} - - -bool TypeAnalyzer::IsPrimitiveDef(int def_num) { - if (def_num < param_count_) return false; - if (def_num < variable_count_) return true; - return body_definitions_->at(def_num - variable_count_)->IsPrimitive(); -} - - -void TypeAnalyzer::Compute() { - bool changed; - int count = 0; - - do { - changed = false; - - if (FLAG_print_graph_text) { - PrintF("TypeAnalyzer::Compute - iteration %d\n", count++); - } - - for (int i = postorder_->length() - 1; i >= 0; --i) { - Node* node = postorder_->at(i); - if (node->IsBlockNode()) { - BlockNode* block = BlockNode::cast(node); - for (int j = 0; j < block->instructions()->length(); j++) { - Expression* expr = block->instructions()->at(j)->AsExpression(); - if (expr != NULL) { - // For variable uses: Compute new type from reaching definitions. - VariableProxy* proxy = expr->AsVariableProxy(); - if (proxy != NULL && proxy->reaching_definitions() != NULL) { - BitVector* rd = proxy->reaching_definitions(); - bool prim_type = true; - // TODO(fsc): A sparse set representation of reaching - // definitions would speed up iterating here. - for (int k = 0; k < rd->length(); k++) { - if (rd->Contains(k) && !IsPrimitiveDef(k)) { - prim_type = false; - break; - } - } - // Reset changed flag if new type information was computed. - if (prim_type != proxy->IsPrimitive()) { - changed = true; - proxy->SetIsPrimitive(prim_type); - } - } - } - } - } - } - } 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); - } - } -} +#endif // DEBUG } } // namespace v8::internal |