From 6192b8659a3dedb86393cfb78121a26f2a3e31e6 Mon Sep 17 00:00:00 2001 From: Ryan Dahl Date: Fri, 26 Mar 2010 09:09:40 -0700 Subject: Upgrade V8 to 2.1.10 --- deps/v8/src/data-flow.cc | 1709 ++++++++++++++++------------------------------ 1 file changed, 577 insertions(+), 1132 deletions(-) (limited to 'deps/v8/src/data-flow.cc') 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* preorder, - ZoneList* postorder) { - preorder->Add(this); - postorder->Add(this); -} - - -void BlockNode::Traverse(bool mark, - ZoneList* preorder, - ZoneList* 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* preorder, - ZoneList* 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* preorder, - ZoneList* 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* 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* 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,803 +746,802 @@ void AssignedVariablesAnalyzer::VisitDeclaration(Declaration* decl) { } -#ifdef 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(); + } +} -// 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() : number_(0) {} - int NextNumber() { return number_; } - void AssignNumber(AstNode* node) { node->set_num(number_++); } +void Node::InitializeReachingDefinitions(int definition_count, + List* variables, + WorkList* worklist, + bool mark) { + ASSERT(!IsMarkedWith(mark)); + rd_.Initialize(definition_count); + MarkWith(mark); + worklist->Insert(this); +} - 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) { - PrintF("Block"); -} +void BlockNode::InitializeReachingDefinitions(int definition_count, + List* variables, + WorkList* 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); + } -void TextInstructionPrinter::VisitExpressionStatement( - ExpressionStatement* stmt) { - PrintF("ExpressionStatement"); -} + 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); -void TextInstructionPrinter::VisitEmptyStatement(EmptyStatement* stmt) { - PrintF("EmptyStatement"); -} + // All previously generated definitions are not generated. + rd_.gen()->Subtract(*def_set); + // This one is generated. + rd_.gen()->Add(expr->num()); + } -void TextInstructionPrinter::VisitIfStatement(IfStatement* stmt) { - PrintF("IfStatement"); + // Add all blocks except the entry node to the worklist. + if (predecessor_ != NULL) { + MarkWith(mark); + worklist->Insert(this); + } } -void TextInstructionPrinter::VisitContinueStatement(ContinueStatement* stmt) { +void ExitNode::ComputeRDOut(BitVector* result) { + // Should not be the predecessor of any node. UNREACHABLE(); } -void TextInstructionPrinter::VisitBreakStatement(BreakStatement* stmt) { - 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 TextInstructionPrinter::VisitReturnStatement(ReturnStatement* stmt) { - PrintF("return @%d", stmt->expression()->num()); +void BranchNode::ComputeRDOut(BitVector* result) { + // Branch nodes don't kill or generate definitions. + *result = *rd_.rd_in(); } -void TextInstructionPrinter::VisitWithEnterStatement(WithEnterStatement* stmt) { - PrintF("WithEnterStatement"); +void JoinNode::ComputeRDOut(BitVector* result) { + // Join nodes don't kill or generate definitions. + *result = *rd_.rd_in(); } -void TextInstructionPrinter::VisitWithExitStatement(WithExitStatement* stmt) { - PrintF("WithExitStatement"); -} - +void ExitNode::UpdateRDIn(WorkList* 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(); -void TextInstructionPrinter::VisitSwitchStatement(SwitchStatement* stmt) { - UNREACHABLE(); + 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 TextInstructionPrinter::VisitDoWhileStatement(DoWhileStatement* stmt) { - PrintF("DoWhileStatement"); -} - +void BlockNode::UpdateRDIn(WorkList* worklist, bool mark) { + // The entry block has no predecessor. Its RD_in does not change. + if (predecessor_ == NULL) return; -void TextInstructionPrinter::VisitWhileStatement(WhileStatement* stmt) { - PrintF("WhileStatement"); -} + BitVector new_rd_in(rd_.rd_in()->length()); + predecessor_->ComputeRDOut(&new_rd_in); + if (rd_.rd_in()->Equals(new_rd_in)) return; -void TextInstructionPrinter::VisitForStatement(ForStatement* stmt) { - PrintF("ForStatement"); + // 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 TextInstructionPrinter::VisitForInStatement(ForInStatement* stmt) { - PrintF("ForInStatement"); -} +void BranchNode::UpdateRDIn(WorkList* 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; -void TextInstructionPrinter::VisitTryCatchStatement(TryCatchStatement* stmt) { - UNREACHABLE(); + // 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 TextInstructionPrinter::VisitTryFinallyStatement( - TryFinallyStatement* stmt) { - UNREACHABLE(); -} - +void JoinNode::UpdateRDIn(WorkList* worklist, bool mark) { + int definition_count = rd_.rd_in()->length(); + BitVector new_rd_in(definition_count); -void TextInstructionPrinter::VisitDebuggerStatement(DebuggerStatement* stmt) { - PrintF("DebuggerStatement"); -} + // 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; -void TextInstructionPrinter::VisitFunctionLiteral(FunctionLiteral* expr) { - PrintF("FunctionLiteral"); + // 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 TextInstructionPrinter::VisitSharedFunctionInfoLiteral( - SharedFunctionInfoLiteral* expr) { - PrintF("SharedFunctionInfoLiteral"); +void Node::PropagateReachingDefinitions(List* variables) { + // Nothing to do. } -void TextInstructionPrinter::VisitConditional(Conditional* expr) { - PrintF("Conditional"); -} +void BlockNode::PropagateReachingDefinitions(List* 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(); + } + } -void TextInstructionPrinter::VisitSlot(Slot* expr) { - UNREACHABLE(); -} + 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; -void TextInstructionPrinter::VisitVariableProxy(VariableProxy* expr) { - Variable* var = expr->AsVariable(); - if (var != NULL) { - PrintF("%s", *var->name()->ToCString()); - if (var->IsStackAllocated() && expr->reaching_definitions() != NULL) { - expr->reaching_definitions()->Print(); - } - } else { - ASSERT(expr->AsProperty() != NULL); - VisitProperty(expr->AsProperty()); + // 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 TextInstructionPrinter::VisitLiteral(Literal* expr) { - expr->handle()->ShortPrint(); -} +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 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_); + } -void TextInstructionPrinter::VisitRegExpLiteral(RegExpLiteral* expr) { - PrintF("RegExpLiteral"); -} - - -void TextInstructionPrinter::VisitObjectLiteral(ObjectLiteral* expr) { - PrintF("ObjectLiteral"); -} + // 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 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); + } -void TextInstructionPrinter::VisitArrayLiteral(ArrayLiteral* expr) { - PrintF("ArrayLiteral"); + // 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); + } } -void TextInstructionPrinter::VisitCatchExtensionObject( - CatchExtensionObject* expr) { - PrintF("CatchExtensionObject"); +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 TextInstructionPrinter::VisitAssignment(Assignment* expr) { - Variable* var = expr->target()->AsVariableProxy()->AsVariable(); - Property* prop = expr->target()->AsProperty(); +void TypeAnalyzer::Compute() { + bool changed; + int count = 0; - if (var == NULL && prop == NULL) { - // Throw reference error. - Visit(expr->target()); - return; - } + do { + changed = false; - // Print the left-hand side. - if (var != NULL) { - PrintF("%s", *var->name()->ToCString()); - } else if (prop != NULL) { - PrintF("@%d", prop->obj()->num()); - if (prop->key()->IsPropertyName()) { - PrintF("."); - ASSERT(prop->key()->AsLiteral() != NULL); - prop->key()->AsLiteral()->handle()->Print(); - } else { - PrintF("[@%d]", prop->key()->num()); + if (FLAG_print_graph_text) { + PrintF("TypeAnalyzer::Compute - iteration %d\n", count++); } - } - // Print the operation. - if (expr->is_compound()) { - PrintF(" = "); - // Print the left-hand side again when compound. - if (var != NULL) { - PrintF("@%d", expr->target()->num()); - } else { - PrintF("@%d", prop->obj()->num()); - if (prop->key()->IsPropertyName()) { - PrintF("."); - ASSERT(prop->key()->AsLiteral() != NULL); - prop->key()->AsLiteral()->handle()->Print(); - } else { - PrintF("[@%d]", prop->key()->num()); + 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); + } + } + } + } } } - // Print the corresponding binary operator. - PrintF(" %s ", Token::String(expr->binary_op())); - } else { - PrintF(" %s ", Token::String(expr->op())); - } - - // Print the right-hand side. - PrintF("@%d", expr->value()->num()); - - if (expr->num() != AstNode::kNoNumber) { - PrintF(" ;; D%d", expr->num()); - } + } while (changed); } -void TextInstructionPrinter::VisitThrow(Throw* expr) { - PrintF("throw @%d", expr->exception()->num()); +void Node::MarkCriticalInstructions( + List* stack, + ZoneList* body_definitions, + int variable_count) { } -void TextInstructionPrinter::VisitProperty(Property* expr) { - if (expr->key()->IsPropertyName()) { - PrintF("@%d.", expr->obj()->num()); - ASSERT(expr->key()->AsLiteral() != NULL); - expr->key()->AsLiteral()->handle()->Print(); - } else { - PrintF("@%d[@%d]", expr->obj()->num(), expr->key()->num()); +void BlockNode::MarkCriticalInstructions( + List* stack, + ZoneList* 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 TextInstructionPrinter::VisitCall(Call* expr) { - PrintF("@%d(", expr->expression()->num()); - ZoneList* 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 MarkLiveCode(ZoneList* nodes, + ZoneList* body_definitions, + int variable_count) { + List 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); + } -void TextInstructionPrinter::VisitCallNew(CallNew* expr) { - PrintF("new @%d(", expr->expression()->num()); - ZoneList* arguments = expr->arguments(); - for (int i = 0, len = arguments->length(); i < len; i++) { - if (i != 0) PrintF(", "); - PrintF("@%d", arguments->at(i)->num()); + // 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); + } } - PrintF(")"); } -void TextInstructionPrinter::VisitCallRuntime(CallRuntime* expr) { - PrintF("%s(", *expr->name()->ToCString()); - ZoneList* arguments = expr->arguments(); - for (int i = 0, len = arguments->length(); i < len; i++) { - if (i != 0) PrintF(", "); - PrintF("@%d", arguments->at(i)->num()); - } - PrintF(")"); -} +#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() : number_(0) {} + int NextNumber() { return number_; } + void AssignNumber(AstNode* node) { node->set_num(number_++); } -void TextInstructionPrinter::VisitUnaryOperation(UnaryOperation* expr) { - PrintF("%s(@%d)", Token::String(expr->op()), expr->expression()->num()); -} + 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_; -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())); - } + DISALLOW_COPY_AND_ASSIGN(TextInstructionPrinter); +}; - if (expr->num() != AstNode::kNoNumber) { - PrintF(" ;; D%d", expr->num()); - } + +void TextInstructionPrinter::VisitDeclaration(Declaration* decl) { + UNREACHABLE(); } -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()), - expr->right()->num()); +void TextInstructionPrinter::VisitBlock(Block* stmt) { + PrintF("Block"); } -void TextInstructionPrinter::VisitCompareOperation(CompareOperation* expr) { - PrintF("@%d %s @%d", - expr->left()->num(), - Token::String(expr->op()), - expr->right()->num()); +void TextInstructionPrinter::VisitExpressionStatement( + ExpressionStatement* stmt) { + PrintF("ExpressionStatement"); } -void TextInstructionPrinter::VisitThisFunction(ThisFunction* expr) { - PrintF("ThisFunction"); +void TextInstructionPrinter::VisitEmptyStatement(EmptyStatement* stmt) { + PrintF("EmptyStatement"); } -static int node_count = 0; -static int instruction_count = 0; +void TextInstructionPrinter::VisitIfStatement(IfStatement* stmt) { + PrintF("IfStatement"); +} -void Node::AssignNodeNumber() { - set_number(node_count++); +void TextInstructionPrinter::VisitContinueStatement(ContinueStatement* stmt) { + UNREACHABLE(); } -void Node::PrintReachingDefinitions() { - if (rd_.rd_in() != NULL) { - ASSERT(rd_.kill() != NULL && rd_.gen() != NULL); - - PrintF("RD_in = "); - rd_.rd_in()->Print(); - PrintF("\n"); - - PrintF("RD_kill = "); - rd_.kill()->Print(); - PrintF("\n"); - - PrintF("RD_gen = "); - rd_.gen()->Print(); - PrintF("\n"); - } +void TextInstructionPrinter::VisitBreakStatement(BreakStatement* stmt) { + UNREACHABLE(); } -void ExitNode::PrintText() { - PrintReachingDefinitions(); - PrintF("L%d: Exit\n\n", number()); +void TextInstructionPrinter::VisitReturnStatement(ReturnStatement* stmt) { + PrintF("return @%d", stmt->expression()->num()); } -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(instr); - printer.AssignNumber(instr); - PrintF("\n"); - } - PrintF("goto L%d\n\n", successor_->number()); +void TextInstructionPrinter::VisitWithEnterStatement(WithEnterStatement* stmt) { + PrintF("WithEnterStatement"); } -void BranchNode::PrintText() { - PrintReachingDefinitions(); - PrintF("L%d: Branch\n", number()); - PrintF("goto (L%d, L%d)\n\n", successor0_->number(), successor1_->number()); +void TextInstructionPrinter::VisitWithExitStatement(WithExitStatement* stmt) { + PrintF("WithExitStatement"); } -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 TextInstructionPrinter::VisitSwitchStatement(SwitchStatement* stmt) { + UNREACHABLE(); } -void FlowGraph::PrintText(FunctionLiteral* fun, ZoneList* postorder) { - PrintF("\n========\n"); - PrintF("name = %s\n", *fun->name()->ToCString()); - - // 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)->AssignNodeNumber(); - } - - // Print basic blocks in reverse postorder. - for (int i = postorder->length() - 1; i >= 0; i--) { - postorder->at(i)->PrintText(); - } +void TextInstructionPrinter::VisitDoWhileStatement(DoWhileStatement* stmt) { + PrintF("DoWhileStatement"); } -#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 TextInstructionPrinter::VisitWhileStatement(WhileStatement* stmt) { + PrintF("WhileStatement"); } -void Node::InitializeReachingDefinitions(int definition_count, - List* variables, - WorkList* worklist, - bool mark) { - ASSERT(!IsMarkedWith(mark)); - rd_.Initialize(definition_count); - MarkWith(mark); - worklist->Insert(this); +void TextInstructionPrinter::VisitForStatement(ForStatement* stmt) { + PrintF("ForStatement"); } -void BlockNode::InitializeReachingDefinitions(int definition_count, - List* variables, - WorkList* 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); +void TextInstructionPrinter::VisitForInStatement(ForInStatement* stmt) { + PrintF("ForInStatement"); +} - // 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 TextInstructionPrinter::VisitTryCatchStatement(TryCatchStatement* stmt) { + UNREACHABLE(); } -void ExitNode::ComputeRDOut(BitVector* result) { - // Should not be the predecessor of any node. +void TextInstructionPrinter::VisitTryFinallyStatement( + TryFinallyStatement* stmt) { 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 TextInstructionPrinter::VisitDebuggerStatement(DebuggerStatement* stmt) { + PrintF("DebuggerStatement"); } -void BranchNode::ComputeRDOut(BitVector* result) { - // Branch nodes don't kill or generate definitions. - *result = *rd_.rd_in(); +void TextInstructionPrinter::VisitFunctionLiteral(FunctionLiteral* expr) { + PrintF("FunctionLiteral"); } -void JoinNode::ComputeRDOut(BitVector* result) { - // Join nodes don't kill or generate definitions. - *result = *rd_.rd_in(); +void TextInstructionPrinter::VisitSharedFunctionInfoLiteral( + SharedFunctionInfoLiteral* expr) { + PrintF("SharedFunctionInfoLiteral"); } -void ExitNode::UpdateRDIn(WorkList* 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 TextInstructionPrinter::VisitConditional(Conditional* expr) { + PrintF("Conditional"); } -void BlockNode::UpdateRDIn(WorkList* 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); +void TextInstructionPrinter::VisitSlot(Slot* expr) { + UNREACHABLE(); +} - 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 TextInstructionPrinter::VisitVariableProxy(VariableProxy* expr) { + Variable* var = expr->AsVariable(); + if (var != NULL) { + PrintF("%s", *var->name()->ToCString()); + if (var->IsStackAllocated() && expr->reaching_definitions() != NULL) { + expr->reaching_definitions()->Print(); + } + } else { + ASSERT(expr->AsProperty() != NULL); + VisitProperty(expr->AsProperty()); } } -void BranchNode::UpdateRDIn(WorkList* worklist, bool mark) { - BitVector new_rd_in(rd_.rd_in()->length()); - predecessor_->ComputeRDOut(&new_rd_in); +void TextInstructionPrinter::VisitLiteral(Literal* expr) { + expr->handle()->ShortPrint(); +} - 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 TextInstructionPrinter::VisitRegExpLiteral(RegExpLiteral* expr) { + PrintF("RegExpLiteral"); } -void JoinNode::UpdateRDIn(WorkList* 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); - } +void TextInstructionPrinter::VisitObjectLiteral(ObjectLiteral* expr) { + PrintF("ObjectLiteral"); +} - 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 TextInstructionPrinter::VisitArrayLiteral(ArrayLiteral* expr) { + PrintF("ArrayLiteral"); } -void Node::PropagateReachingDefinitions(List* variables) { - // Nothing to do. +void TextInstructionPrinter::VisitCatchExtensionObject( + CatchExtensionObject* expr) { + PrintF("CatchExtensionObject"); } -void BlockNode::PropagateReachingDefinitions(List* 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; +void TextInstructionPrinter::VisitAssignment(Assignment* expr) { + Variable* var = expr->target()->AsVariableProxy()->AsVariable(); + Property* prop = expr->target()->AsProperty(); - // 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 (var == NULL && prop == NULL) { + // Throw reference error. + Visit(expr->target()); + return; + } + + // Print the left-hand side. + if (var != NULL) { + PrintF("%s", *var->name()->ToCString()); + } else if (prop != NULL) { + PrintF("@%d", prop->obj()->num()); + if (prop->key()->IsPropertyName()) { + PrintF("."); + ASSERT(prop->key()->AsLiteral() != NULL); + prop->key()->AsLiteral()->handle()->Print(); + } else { + PrintF("[@%d]", prop->key()->num()); } + } - 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); + // Print the operation. + if (expr->is_compound()) { + PrintF(" = "); + // Print the left-hand side again when compound. + if (var != NULL) { + PrintF("@%d", expr->target()->num()); + } else { + PrintF("@%d", prop->obj()->num()); + if (prop->key()->IsPropertyName()) { + PrintF("."); + ASSERT(prop->key()->AsLiteral() != NULL); + prop->key()->AsLiteral()->handle()->Print(); + } else { + PrintF("[@%d]", prop->key()->num()); + } } + // Print the corresponding binary operator. + PrintF(" %s ", Token::String(expr->binary_op())); + } else { + PrintF(" %s ", Token::String(expr->op())); + } - // 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; + // Print the right-hand side. + PrintF("@%d", expr->value()->num()); - // 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()); + if (expr->num() != AstNode::kNoNumber) { + PrintF(" ;; D%d", 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(); +void TextInstructionPrinter::VisitThrow(Throw* expr) { + PrintF("throw @%d", expr->exception()->num()); +} - // Step 1: For each stack-allocated variable, identify the set of all its - // definitions. - List 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); + +void TextInstructionPrinter::VisitProperty(Property* expr) { + if (expr->key()->IsPropertyName()) { + PrintF("@%d.", expr->obj()->num()); + ASSERT(expr->key()->AsLiteral() != NULL); + expr->key()->AsLiteral()->handle()->Print(); + } else { + PrintF("@%d[@%d]", expr->obj()->num(), expr->key()->num()); } - 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_); +} + + +void TextInstructionPrinter::VisitCall(Call* expr) { + PrintF("@%d(", expr->expression()->num()); + ZoneList* arguments = expr->arguments(); + for (int i = 0, len = arguments->length(); i < len; i++) { + if (i != 0) PrintF(", "); + PrintF("@%d", arguments->at(i)->num()); } + PrintF(")"); +} - // 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 worklist(node_count); - for (int i = node_count - 1; i >= 0; i--) { - postorder_->at(i)->InitializeReachingDefinitions(definition_count, - &variables, - &worklist, - mark); + +void TextInstructionPrinter::VisitCallNew(CallNew* expr) { + PrintF("new @%d(", expr->expression()->num()); + ZoneList* arguments = expr->arguments(); + for (int i = 0, len = arguments->length(); i < len; i++) { + if (i != 0) PrintF(", "); + PrintF("@%d", arguments->at(i)->num()); } + PrintF(")"); +} - // 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); + +void TextInstructionPrinter::VisitCallRuntime(CallRuntime* expr) { + PrintF("%s(", *expr->name()->ToCString()); + ZoneList* arguments = expr->arguments(); + for (int i = 0, len = arguments->length(); i < len; i++) { + if (i != 0) PrintF(", "); + PrintF("@%d", arguments->at(i)->num()); } + PrintF(")"); +} - // 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); + +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()); } } -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 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()), + expr->right()->num()); } -void TypeAnalyzer::Compute() { - bool changed; - int count = 0; +void TextInstructionPrinter::VisitCompareOperation(CompareOperation* expr) { + PrintF("@%d %s @%d", + expr->left()->num(), + Token::String(expr->op()), + expr->right()->num()); +} - do { - changed = false; - if (FLAG_print_graph_text) { - PrintF("TypeAnalyzer::Compute - iteration %d\n", count++); - } +void TextInstructionPrinter::VisitThisFunction(ThisFunction* expr) { + PrintF("ThisFunction"); +} - 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); + +static int node_count = 0; +static int instruction_count = 0; + + +void Node::AssignNodeNumber() { + set_number(node_count++); } -void Node::MarkCriticalInstructions( - List* stack, - ZoneList* body_definitions, - int variable_count) { +void Node::PrintReachingDefinitions() { + if (rd_.rd_in() != NULL) { + ASSERT(rd_.kill() != NULL && rd_.gen() != NULL); + + PrintF("RD_in = "); + rd_.rd_in()->Print(); + PrintF("\n"); + + PrintF("RD_kill = "); + rd_.kill()->Print(); + PrintF("\n"); + + PrintF("RD_gen = "); + rd_.gen()->Print(); + PrintF("\n"); + } } -void BlockNode::MarkCriticalInstructions( - List* stack, - ZoneList* 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 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++) { + 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(instr); + printer.AssignNumber(instr); + PrintF("\n"); } + PrintF("goto L%d\n\n", successor_->number()); } -void MarkLiveCode(ZoneList* nodes, - ZoneList* body_definitions, - int variable_count) { - List stack(20); +void BranchNode::PrintText() { + PrintReachingDefinitions(); + PrintF("L%d: Branch\n", number()); + PrintF("goto (L%d, L%d)\n\n", successor0_->number(), successor1_->number()); +} - // 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); + +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()); +} - // 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); - } + +void FlowGraph::PrintText(FunctionLiteral* fun, ZoneList* postorder) { + PrintF("\n========\n"); + PrintF("name = %s\n", *fun->name()->ToCString()); + + // 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)->AssignNodeNumber(); + } + + // Print basic blocks in reverse postorder. + for (int i = postorder->length() - 1; i >= 0; i--) { + postorder->at(i)->PrintText(); } } +#endif // DEBUG + } } // namespace v8::internal -- cgit v1.2.1