Revision: 2604 Author: [email protected] Date: Mon Aug 3 00:55:48 2009 Log: Restructure to support recursive invocation of the CFG builder. Add support for stack-allocated variables when run with multipass.
There is no liveness analysis and they are currently always allocated to memory. Review URL: http://codereview.chromium.org/159701 http://code.google.com/p/v8/source/detail?r=2604 Modified: /branches/bleeding_edge/src/arm/cfg-arm.cc /branches/bleeding_edge/src/cfg.cc /branches/bleeding_edge/src/cfg.h /branches/bleeding_edge/src/compiler.cc /branches/bleeding_edge/src/ia32/cfg-ia32.cc /branches/bleeding_edge/src/x64/cfg-x64.cc ======================================= --- /branches/bleeding_edge/src/arm/cfg-arm.cc Fri Jul 31 04:27:14 2009 +++ /branches/bleeding_edge/src/arm/cfg-arm.cc Mon Aug 3 00:55:48 2009 @@ -56,9 +56,10 @@ Comment cmnt(masm, "[ EntryNode"); __ stm(db_w, sp, r1.bit() | cp.bit() | fp.bit() | lr.bit()); __ add(fp, sp, Operand(2 * kPointerSize)); - if (local_count_ > 0) { + int count = CfgGlobals::current()->fun()->scope()->num_stack_slots(); + if (count > 0) { __ mov(ip, Operand(Factory::undefined_value())); - for (int i = 0; i < local_count_; i++) { + for (int i = 0; i < count; i++) { __ push(ip); } } @@ -84,7 +85,8 @@ } __ mov(sp, fp); __ ldm(ia_w, sp, fp.bit() | lr.bit()); - __ add(sp, sp, Operand((parameter_count_ + 1) * kPointerSize)); + int count = CfgGlobals::current()->fun()->scope()->num_parameters(); + __ add(sp, sp, Operand((count + 1) * kPointerSize)); __ Jump(lr); } @@ -98,6 +100,24 @@ void Constant::ToRegister(MacroAssembler* masm, Register reg) { __ mov(reg, Operand(handle_)); } + + +void SlotLocation::ToRegister(MacroAssembler* masm, Register reg) { + switch (type_) { + case Slot::PARAMETER: { + int count = CfgGlobals::current()->fun()->scope()->num_parameters(); + __ ldr(reg, MemOperand(fp, (1 + count - index_) * kPointerSize)); + break; + } + case Slot::LOCAL: { + const int kOffset = JavaScriptFrameConstants::kLocal0Offset; + __ ldr(reg, MemOperand(fp, kOffset - index_ * kPointerSize)); + break; + } + default: + UNREACHABLE(); + } +} #undef __ ======================================= --- /branches/bleeding_edge/src/cfg.cc Fri Jul 31 04:27:14 2009 +++ /branches/bleeding_edge/src/cfg.cc Mon Aug 3 00:55:48 2009 @@ -36,32 +36,37 @@ namespace internal { -ExitNode* Cfg::global_exit_ = NULL; +CfgGlobals* CfgGlobals::top_ = NULL; -void CfgNode::Reset() { +CfgGlobals::CfgGlobals(FunctionLiteral* fun) + : global_fun_(fun), + global_exit_(new ExitNode()), #ifdef DEBUG - node_counter_ = 0; + node_counter_(0), #endif -} - - -void Cfg::Reset(FunctionLiteral* fun) { - global_exit_ = new ExitNode(fun); - CfgNode::Reset(); + previous_(top_) { + top_ = this; } #define BAILOUT(reason) \ do { return NULL; } while (false) -Cfg* Cfg::Build(FunctionLiteral* fun) { +Cfg* Cfg::Build() { + FunctionLiteral* fun = CfgGlobals::current()->fun(); + if (fun->scope()->num_heap_slots() > 0) { + BAILOUT("function has context slots"); + } + if (fun->scope()->arguments() != NULL) { + BAILOUT("function uses .arguments"); + } + ZoneList<Statement*>* body = fun->body(); if (body->is_empty()) { BAILOUT("empty function body"); } - Cfg::Reset(fun); StatementBuilder builder; builder.VisitStatements(body); Cfg* cfg = builder.cfg(); @@ -71,16 +76,16 @@ if (cfg->has_exit()) { BAILOUT("control path without explicit return"); } - cfg->PrependEntryNode(fun); + cfg->PrependEntryNode(); return cfg; } #undef BAILOUT -void Cfg::PrependEntryNode(FunctionLiteral* fun) { +void Cfg::PrependEntryNode() { ASSERT(!is_empty()); - entry_ = new EntryNode(fun, InstructionBlock::cast(entry())); + entry_ = new EntryNode(InstructionBlock::cast(entry())); } @@ -93,19 +98,10 @@ void Cfg::AppendReturnInstruction(Value* value) { Append(new ReturnInstr(value)); - InstructionBlock::cast(exit_)->set_successor(global_exit_); + ExitNode* global_exit = CfgGlobals::current()->exit(); + InstructionBlock::cast(exit_)->set_successor(global_exit); exit_ = NULL; } - - -EntryNode::EntryNode(FunctionLiteral* fun, InstructionBlock* succ) - : successor_(succ), local_count_(fun->scope()->num_stack_slots()) { -} - - -ExitNode::ExitNode(FunctionLiteral* fun) - : parameter_count_(fun->scope()->num_parameters()) { -} void InstructionBlock::Unmark() { @@ -124,16 +120,19 @@ } -void ExitNode::Unmark() {} +void ExitNode::Unmark() { + is_marked_ = false; +} -Handle<Code> Cfg::Compile(FunctionLiteral* fun, Handle<Script> script) { +Handle<Code> Cfg::Compile(Handle<Script> script) { const int kInitialBufferSize = 4 * KB; MacroAssembler* masm = new MacroAssembler(NULL, kInitialBufferSize); entry()->Compile(masm); entry()->Unmark(); CodeDesc desc; masm->GetCode(&desc); + FunctionLiteral* fun = CfgGlobals::current()->fun(); ZoneScopeInfo info(fun->scope()); InLoopFlag in_loop = fun->loop_nesting() ? IN_LOOP : NOT_IN_LOOP; Code::Flags flags = Code::ComputeFlags(Code::FUNCTION, in_loop); @@ -149,8 +148,9 @@ PrintF("--- Raw source ---\n"); StringInputBuffer stream(String::cast(script->source())); stream.Seek(fun->start_position()); - // fun->end_position() points to the last character in the stream. We - // need to compensate by adding one to calculate the length. + // fun->end_position() points to the last character in the + // stream. We need to compensate by adding one to calculate the + // length. int source_len = fun->end_position() - fun->start_position() + 1; for (int i = 0; i < source_len; i++) { if (stream.has_more()) PrintF("%c", stream.GetNext()); @@ -207,7 +207,15 @@ void ExpressionBuilder::VisitVariableProxy(VariableProxy* expr) { - BAILOUT("VariableProxy"); + Expression* rewrite = expr->var()->rewrite(); + if (rewrite == NULL || rewrite->AsSlot() == NULL) { + BAILOUT("unsupported variable (not a slot)"); + } + Slot* slot = rewrite->AsSlot(); + if (slot->type() != Slot::PARAMETER && slot->type() != Slot::LOCAL) { + BAILOUT("unsupported slot type (not a parameter or local)"); + } + value_ = new SlotLocation(slot->type(), slot->index()); } @@ -416,7 +424,24 @@ void Constant::Print() { + PrintF("Constant("); handle_->Print(); + PrintF(")"); +} + + +void SlotLocation::Print() { + PrintF("Slot("); + switch (type_) { + case Slot::PARAMETER: + PrintF("PARAMETER, %d)", index_); + break; + case Slot::LOCAL: + PrintF("LOCAL, %d)", index_); + break; + default: + UNREACHABLE(); + } } @@ -425,9 +450,6 @@ value_->Print(); PrintF("\n"); } - - -int CfgNode::node_counter_ = 0; void InstructionBlock::Print() { ======================================= --- /branches/bleeding_edge/src/cfg.h Fri Jul 31 04:34:47 2009 +++ /branches/bleeding_edge/src/cfg.h Mon Aug 3 00:55:48 2009 @@ -33,6 +33,47 @@ namespace v8 { namespace internal { +class ExitNode; + +// A convenient class to keep 'global' values when building a CFG. Since +// CFG construction can be invoked recursively, CFG globals are stacked. +class CfgGlobals BASE_EMBEDDED { + public: + explicit CfgGlobals(FunctionLiteral* fun); + + ~CfgGlobals() { top_ = previous_; } + + static CfgGlobals* current() { + ASSERT(top_ != NULL); + return top_; + } + + FunctionLiteral* fun() { return global_fun_; } + + ExitNode* exit() { return global_exit_; } + +#ifdef DEBUG + int next_number() { return node_counter_++; } +#endif + + private: + static CfgGlobals* top_; + + // Function literal currently compiling. + FunctionLiteral* global_fun_; + + // Shared global exit node for all returns from the same function. + ExitNode* global_exit_; + +#ifdef DEBUG + // Used to number nodes when printing. + int node_counter_; +#endif + + CfgGlobals* previous_; +}; + + // Values appear in instructions. They represent trivial source // expressions: ones with no side effects and that do not require code to be // generated. @@ -66,6 +107,37 @@ }; +// Locations are values that can be stored into ('lvalues'). +class Location : public Value { + public: + virtual ~Location() {} + + virtual void ToRegister(MacroAssembler* masm, Register reg) = 0; + +#ifdef DEBUG + virtual void Print() = 0; +#endif +}; + + +// SlotLocations represent parameters and stack-allocated (i.e., +// non-context) local variables. +class SlotLocation : public Location { + public: + SlotLocation(Slot::Type type, int index) : type_(type), index_(index) {} + + void ToRegister(MacroAssembler* masm, Register reg); + +#ifdef DEBUG + void Print(); +#endif + + private: + Slot::Type type_; + int index_; +}; + + // Instructions are computations. The represent non-trivial source // expressions: typically ones that have side effects and require code to // be generated. @@ -113,8 +185,6 @@ virtual ~CfgNode() {} bool is_marked() { return is_marked_; } - - static void Reset(); virtual bool is_block() { return false; } @@ -124,7 +194,7 @@ #ifdef DEBUG int number() { - if (number_ == -1) number_ = node_counter_++; + if (number_ == -1) number_ = CfgGlobals::current()->next_number(); return number_; } @@ -136,8 +206,6 @@ #ifdef DEBUG int number_; - - static int node_counter_; #endif }; @@ -182,7 +250,7 @@ // containing the function's first instruction. class EntryNode : public CfgNode { public: - EntryNode(FunctionLiteral* fun, InstructionBlock* succ); + explicit EntryNode(InstructionBlock* succ) : successor_(succ) {} virtual ~EntryNode() {} @@ -196,7 +264,6 @@ private: InstructionBlock* successor_; - int local_count_; }; @@ -205,7 +272,7 @@ // the blocks returning from the function. class ExitNode : public CfgNode { public: - explicit ExitNode(FunctionLiteral* fun); + ExitNode() {} virtual ~ExitNode() {} @@ -216,16 +283,13 @@ #ifdef DEBUG void Print(); #endif - - private: - int parameter_count_; }; -// A CFG is a consists of a linked structure of nodes. It has a single -// entry node and optionally an exit node. There is a distinguished global -// exit node that is used as the successor of all blocks that return from -// the function. +// A CFG consists of a linked structure of nodes. It has a single entry +// node and optionally an exit node. There is a distinguished global exit +// node that is used as the successor of all blocks that return from the +// function. // // Fragments of control-flow graphs, produced when traversing the statements // and expressions in the source AST, are represented by the same class. @@ -241,7 +305,7 @@ explicit Cfg(InstructionBlock* block) : entry_(block), exit_(block) {} // Build the CFG for a function. - static Cfg* Build(FunctionLiteral* fun); + static Cfg* Build(); // The entry and exit nodes. CfgNode* entry() { return entry_; } @@ -256,7 +320,7 @@ // Add an entry node to a CFG fragment. It is no longer a fragment // (instructions cannot be prepended). - void PrependEntryNode(FunctionLiteral* fun); + void PrependEntryNode(); // Append an instruction to the end of a CFG fragment. Assumes it has an // available exit. @@ -266,7 +330,7 @@ // longer has an available exit node. void AppendReturnInstruction(Value* value); - Handle<Code> Compile(FunctionLiteral* fun, Handle<Script> script); + Handle<Code> Compile(Handle<Script> script); #ifdef DEBUG // Support for printing. @@ -274,12 +338,6 @@ #endif private: - // Reset static variables before building the CFG for a function. - static void Reset(FunctionLiteral* fun); - - // Shared global exit nodes for all returns from the same function. - static ExitNode* global_exit_; - // Entry and exit nodes. CfgNode* entry_; CfgNode* exit_; ======================================= --- /branches/bleeding_edge/src/compiler.cc Fri Jul 31 04:06:17 2009 +++ /branches/bleeding_edge/src/compiler.cc Mon Aug 3 00:55:48 2009 @@ -80,7 +80,8 @@ } if (FLAG_multipass) { - Cfg* cfg = Cfg::Build(literal); + CfgGlobals scope(literal); + Cfg* cfg = Cfg::Build(); #ifdef DEBUG if (FLAG_print_cfg && cfg != NULL) { SmartPointer<char> name = literal->name()->ToCString(); @@ -90,7 +91,7 @@ } #endif if (cfg != NULL) { - return cfg->Compile(literal, script); + return cfg->Compile(script); } } ======================================= --- /branches/bleeding_edge/src/ia32/cfg-ia32.cc Fri Jul 31 04:27:14 2009 +++ /branches/bleeding_edge/src/ia32/cfg-ia32.cc Mon Aug 3 00:55:48 2009 @@ -59,9 +59,10 @@ __ mov(ebp, esp); __ push(esi); __ push(edi); - if (local_count_ > 0) { + int count = CfgGlobals::current()->fun()->scope()->num_stack_slots(); + if (count > 0) { __ Set(eax, Immediate(Factory::undefined_value())); - for (int i = 0; i < local_count_; i++) { + for (int i = 0; i < count; i++) { __ push(eax); } } @@ -97,7 +98,8 @@ __ RecordJSReturn(); __ mov(esp, ebp); __ pop(ebp); - __ ret((parameter_count_ + 1) * kPointerSize); + int count = CfgGlobals::current()->fun()->scope()->num_parameters(); + __ ret((count + 1) * kPointerSize); } @@ -110,6 +112,25 @@ void Constant::ToRegister(MacroAssembler* masm, Register reg) { __ mov(reg, Immediate(handle_)); } + + +void SlotLocation::ToRegister(MacroAssembler* masm, Register reg) { + switch (type_) { + case Slot::PARAMETER: { + int count = CfgGlobals::current()->fun()->scope()->num_parameters(); + __ mov(reg, Operand(ebp, (1 + count - index_) * kPointerSize)); + break; + } + case Slot::LOCAL: { + const int kOffset = JavaScriptFrameConstants::kLocal0Offset; + __ mov(reg, Operand(ebp, kOffset - index_ * kPointerSize)); + break; + } + default: + UNREACHABLE(); + } +} + #undef __ ======================================= --- /branches/bleeding_edge/src/x64/cfg-x64.cc Fri Jul 31 04:27:14 2009 +++ /branches/bleeding_edge/src/x64/cfg-x64.cc Mon Aug 3 00:55:48 2009 @@ -60,10 +60,11 @@ __ movq(rbp, rsp); __ push(rsi); __ push(rdi); - if (local_count_ > 0) { + int count = CfgGlobals::current()->fun()->scope()->num_stack_slots(); + if (count > 0) { __ movq(kScratchRegister, Factory::undefined_value(), RelocInfo::EMBEDDED_OBJECT); - for (int i = 0; i < local_count_; i++) { + for (int i = 0; i < count; i++) { __ push(kScratchRegister); } } @@ -101,7 +102,8 @@ __ RecordJSReturn(); __ movq(rsp, rbp); __ pop(rbp); - __ ret((parameter_count_ + 1) * kPointerSize); + int count = CfgGlobals::current()->fun()->scope()->num_parameters(); + __ ret((count + 1) * kPointerSize); // Add padding that will be overwritten by a debugger breakpoint. // "movq rsp, rbp; pop rbp" has length 5. "ret k" has length 2. const int kPadding = Debug::kX64JSReturnSequenceLength - 5 - 2; @@ -120,6 +122,24 @@ void Constant::ToRegister(MacroAssembler* masm, Register reg) { __ Move(reg, handle_); } + + +void SlotLocation::ToRegister(MacroAssembler* masm, Register reg) { + switch (type_) { + case Slot::PARAMETER: { + int count = CfgGlobals::current()->fun()->scope()->num_parameters(); + __ movq(reg, Operand(rbp, (1 + count - index_) * kPointerSize)); + break; + } + case Slot::LOCAL: { + const int kOffset = JavaScriptFrameConstants::kLocal0Offset; + __ movq(reg, Operand(rbp, kOffset - index_ * kPointerSize)); + break; + } + default: + UNREACHABLE(); + } +} #undef __ --~--~---------~--~----~------------~-------~--~----~ v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev -~----------~----~----~----~------~----~------~--~---
