Revision: 2596 Author: [email protected] Date: Fri Jul 31 04:06:17 2009 Log: Basic infrastructure for fast two-pass compilation. A CFG is generated in one-pass from the source AST, code is generated from the CFG. Enabled by the flag --multipass and disabled by default.
Rudimentary and currently only supports literal expressions and return statements. There are some other known limitations (e.g., missing support for tracing). Review URL: http://codereview.chromium.org/159695 http://code.google.com/p/v8/source/detail?r=2596 Added: /branches/bleeding_edge/src/arm/cfg-arm.cc /branches/bleeding_edge/src/cfg.cc /branches/bleeding_edge/src/cfg.h /branches/bleeding_edge/src/ia32/cfg-ia32.cc /branches/bleeding_edge/src/x64/cfg-x64.cc Modified: /branches/bleeding_edge/src/SConscript /branches/bleeding_edge/src/compiler.cc /branches/bleeding_edge/src/flag-definitions.h /branches/bleeding_edge/tools/gyp/v8.gyp /branches/bleeding_edge/tools/visual_studio/v8_base.vcproj /branches/bleeding_edge/tools/visual_studio/v8_base_arm.vcproj ======================================= --- /dev/null +++ /branches/bleeding_edge/src/arm/cfg-arm.cc Fri Jul 31 04:06:17 2009 @@ -0,0 +1,97 @@ +// Copyright 2009 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include "v8.h" + +#include "cfg.h" +#include "codegen-inl.h" +#include "macro-assembler-arm.h" + +namespace v8 { +namespace internal { + +#define __ ACCESS_MASM(masm) + +void InstructionBlock::Compile(MacroAssembler* masm) { + ASSERT(!is_marked()); + is_marked_ = true; + { + Comment cmt(masm, "[ InstructionBlock"); + for (int i = 0, len = instructions_.length(); i < len; i++) { + instructions_[i]->Compile(masm); + } + } + successor_->Compile(masm); +} + + +void EntryNode::Compile(MacroAssembler* masm) { + ASSERT(!is_marked()); + is_marked_ = true; + { + 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) { + __ mov(ip, Operand(Factory::undefined_value())); + for (int i = 0; i < local_count_; i++) { + __ push(ip); + } + } + if (FLAG_check_stack) { + StackCheckStub stub; + __ CallStub(&stub); + } + } + successor_->Compile(masm); +} + + +void ExitNode::Compile(MacroAssembler* masm) { + ASSERT(!is_marked()); + is_marked_ = true; + Comment cmnt(masm, "[ ExitNode"); + __ mov(sp, fp); + __ ldm(ia_w, sp, fp.bit() | lr.bit()); + __ add(sp, sp, Operand((parameter_count_ + 1) * kPointerSize)); + __ Jump(lr); +} + + +void ReturnInstr::Compile(MacroAssembler* masm) { + Comment cmnt(masm, "[ ReturnInstr"); + value_->ToRegister(masm, r0); +} + + +void Constant::ToRegister(MacroAssembler* masm, Register reg) { + __ mov(reg, Operand(handle_)); +} + +#undef __ + +} } // namespace v8::internal ======================================= --- /dev/null +++ /branches/bleeding_edge/src/cfg.cc Fri Jul 31 04:06:17 2009 @@ -0,0 +1,462 @@ +// Copyright 2009 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include "v8.h" + +#include "bootstrapper.h" +#include "cfg.h" +#include "scopeinfo.h" +#include "scopes.h" + +namespace v8 { +namespace internal { + + +ExitNode* Cfg::global_exit_ = NULL; + + +void CfgNode::Reset() { +#ifdef DEBUG + node_counter_ = 0; +#endif +} + + +void Cfg::Reset(FunctionLiteral* fun) { + global_exit_ = new ExitNode(fun); + CfgNode::Reset(); +} + + +#define BAILOUT(reason) \ + do { return NULL; } while (false) + +Cfg* Cfg::Build(FunctionLiteral* fun) { + 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(); + if (cfg == NULL) { + BAILOUT("unsupported statement type"); + } + + ASSERT(!cfg->has_exit()); // Return on all paths. + cfg->PrependEntryNode(fun); + return cfg; +} + +#undef BAILOUT + + +void Cfg::PrependEntryNode(FunctionLiteral* fun) { + ASSERT(!is_empty()); + entry_ = new EntryNode(fun, InstructionBlock::cast(entry())); +} + + +void Cfg::Append(Instruction* instr) { + ASSERT(has_exit()); + ASSERT(!is_empty()); + InstructionBlock::cast(exit_)->Append(instr); +} + + +void Cfg::AppendReturnInstruction(Value* value) { + Append(new ReturnInstr(value)); + 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() { + if (is_marked_) { + is_marked_ = false; + successor_->Unmark(); + } +} + + +void EntryNode::Unmark() { + if (is_marked_) { + is_marked_ = false; + successor_->Unmark(); + } +} + + +void ExitNode::Unmark() {} + + +Handle<Code> Cfg::Compile(FunctionLiteral* fun, Handle<Script> script) { + const int kInitialBufferSize = 4 * KB; + MacroAssembler* masm = new MacroAssembler(NULL, kInitialBufferSize); + entry()->Compile(masm); + entry()->Unmark(); + CodeDesc desc; + masm->GetCode(&desc); + ZoneScopeInfo info(fun->scope()); + InLoopFlag in_loop = fun->loop_nesting() ? IN_LOOP : NOT_IN_LOOP; + Code::Flags flags = Code::ComputeFlags(Code::FUNCTION, in_loop); + Handle<Code> code = Factory::NewCode(desc, &info, flags, masm->CodeObject()); + + // Add unresolved entries in the code to the fixup list. + Bootstrapper::AddFixup(*code, masm); + +#ifdef ENABLE_DISASSEMBLER + if (FLAG_print_code) { + // Print the source code if available. + if (!script->IsUndefined() && !script->source()->IsUndefined()) { + 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. + 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()); + } + PrintF("\n\n"); + } + PrintF("--- Code ---\n"); + code->Disassemble(*fun->name()->ToCString()); + } +#endif + + return code; +} + + +// The expression builder should not be used for declarations or statements. +void ExpressionBuilder::VisitDeclaration(Declaration* decl) { UNREACHABLE(); } + +#define DEFINE_VISIT(type) \ + void ExpressionBuilder::Visit##type(type* stmt) { UNREACHABLE(); } +STATEMENT_NODE_LIST(DEFINE_VISIT) +#undef DEFINE_VISIT + + +// Macros (temporarily) handling unsupported expression types. +#define BAILOUT(reason) \ + do { \ + value_ = NULL; \ + return; \ + } while (false) + +#define CHECK_BAILOUT() \ + if (value_ == NULL) { return; } else {} + +void ExpressionBuilder::VisitFunctionLiteral(FunctionLiteral* expr) { + BAILOUT("FunctionLiteral"); +} + + +void ExpressionBuilder::VisitFunctionBoilerplateLiteral( + FunctionBoilerplateLiteral* expr) { + BAILOUT("FunctionBoilerplateLiteral"); +} + + +void ExpressionBuilder::VisitConditional(Conditional* expr) { + BAILOUT("Conditional"); +} + + +void ExpressionBuilder::VisitSlot(Slot* expr) { + BAILOUT("Slot"); +} + + +void ExpressionBuilder::VisitVariableProxy(VariableProxy* expr) { + BAILOUT("VariableProxy"); +} + + +void ExpressionBuilder::VisitLiteral(Literal* expr) { + value_ = new Constant(expr->handle()); +} + + +void ExpressionBuilder::VisitRegExpLiteral(RegExpLiteral* expr) { + BAILOUT("RegExpLiteral"); +} + + +void ExpressionBuilder::VisitObjectLiteral(ObjectLiteral* expr) { + BAILOUT("ObjectLiteral"); +} + + +void ExpressionBuilder::VisitArrayLiteral(ArrayLiteral* expr) { + BAILOUT("ArrayLiteral"); +} + + +void ExpressionBuilder::VisitCatchExtensionObject(CatchExtensionObject* expr) { + BAILOUT("CatchExtensionObject"); +} + + +void ExpressionBuilder::VisitAssignment(Assignment* expr) { + BAILOUT("Assignment"); +} + + +void ExpressionBuilder::VisitThrow(Throw* expr) { + BAILOUT("Throw"); +} + + +void ExpressionBuilder::VisitProperty(Property* expr) { + BAILOUT("Property"); +} + + +void ExpressionBuilder::VisitCall(Call* expr) { + BAILOUT("Call"); +} + + +void ExpressionBuilder::VisitCallEval(CallEval* expr) { + BAILOUT("CallEval"); +} + + +void ExpressionBuilder::VisitCallNew(CallNew* expr) { + BAILOUT("CallNew"); +} + + +void ExpressionBuilder::VisitCallRuntime(CallRuntime* expr) { + BAILOUT("CallRuntime"); +} + + +void ExpressionBuilder::VisitUnaryOperation(UnaryOperation* expr) { + BAILOUT("UnaryOperation"); +} + + +void ExpressionBuilder::VisitCountOperation(CountOperation* expr) { + BAILOUT("CountOperation"); +} + + +void ExpressionBuilder::VisitBinaryOperation(BinaryOperation* expr) { + BAILOUT("BinaryOperation"); +} + + +void ExpressionBuilder::VisitCompareOperation(CompareOperation* expr) { + BAILOUT("CompareOperation"); +} + + +void ExpressionBuilder::VisitThisFunction(ThisFunction* expr) { + BAILOUT("ThisFunction"); +} + +#undef BAILOUT +#undef CHECK_BAILOUT + + +// Macros (temporarily) handling unsupported statement types. +#define BAILOUT(reason) \ + do { \ + cfg_ = NULL; \ + return; \ + } while (false) + +#define CHECK_BAILOUT() \ + if (cfg_ == NULL) { return; } else {} + +void StatementBuilder::VisitStatements(ZoneList<Statement*>* stmts) { + for (int i = 0, len = stmts->length(); i < len; i++) { + Visit(stmts->at(i)); + CHECK_BAILOUT(); + if (!cfg_->has_exit()) return; + } +} + + +// The statement builder should not be used for declarations or expressions. +void StatementBuilder::VisitDeclaration(Declaration* decl) { UNREACHABLE(); } + +#define DEFINE_VISIT(type) \ + void StatementBuilder::Visit##type(type* expr) { UNREACHABLE(); } +EXPRESSION_NODE_LIST(DEFINE_VISIT) +#undef DEFINE_VISIT + + +void StatementBuilder::VisitBlock(Block* stmt) { + VisitStatements(stmt->statements()); +} + + +void StatementBuilder::VisitExpressionStatement(ExpressionStatement* stmt) { + BAILOUT("ExpressionStatement"); +} + + +void StatementBuilder::VisitEmptyStatement(EmptyStatement* stmt) { + // Nothing to do. +} + + +void StatementBuilder::VisitIfStatement(IfStatement* stmt) { + BAILOUT("IfStatement"); +} + + +void StatementBuilder::VisitContinueStatement(ContinueStatement* stmt) { + BAILOUT("ContinueStatement"); +} + + +void StatementBuilder::VisitBreakStatement(BreakStatement* stmt) { + BAILOUT("BreakStatement"); +} + + +void StatementBuilder::VisitReturnStatement(ReturnStatement* stmt) { + ExpressionBuilder builder; + builder.Visit(stmt->expression()); + Value* value = builder.value(); + if (value == NULL) BAILOUT("unsupported expression type"); + cfg_->AppendReturnInstruction(value); +} + + +void StatementBuilder::VisitWithEnterStatement(WithEnterStatement* stmt) { + BAILOUT("WithEnterStatement"); +} + + +void StatementBuilder::VisitWithExitStatement(WithExitStatement* stmt) { + BAILOUT("WithExitStatement"); +} + + +void StatementBuilder::VisitSwitchStatement(SwitchStatement* stmt) { + BAILOUT("SwitchStatement"); +} + + +void StatementBuilder::VisitLoopStatement(LoopStatement* stmt) { + BAILOUT("LoopStatement"); +} + + +void StatementBuilder::VisitForInStatement(ForInStatement* stmt) { + BAILOUT("ForInStatement"); +} + + +void StatementBuilder::VisitTryCatch(TryCatch* stmt) { + BAILOUT("TryCatch"); +} + + +void StatementBuilder::VisitTryFinally(TryFinally* stmt) { + BAILOUT("TryFinally"); +} + + +void StatementBuilder::VisitDebuggerStatement(DebuggerStatement* stmt) { + BAILOUT("DebuggerStatement"); +} + + +#ifdef DEBUG +// CFG printing support (via depth-first, preorder block traversal). + +void Cfg::Print() { + entry_->Print(); + entry_->Unmark(); +} + + +void Constant::Print() { + handle_->Print(); +} + + +void ReturnInstr::Print() { + PrintF("Return "); + value_->Print(); + PrintF("\n"); +} + + +int CfgNode::node_counter_ = 0; + + +void InstructionBlock::Print() { + if (!is_marked_) { + is_marked_ = true; + PrintF("L%d:\n", number()); + for (int i = 0, len = instructions_.length(); i < len; i++) { + instructions_[i]->Print(); + } + PrintF("Goto L%d\n\n", successor_->number()); + successor_->Print(); + } +} + + +void EntryNode::Print() { + if (!is_marked_) { + is_marked_ = true; + successor_->Print(); + } +} + + +void ExitNode::Print() { + if (!is_marked_) { + is_marked_ = true; + PrintF("L%d:\nExit\n\n", number()); + } +} + +#endif // DEBUG + +} } // namespace v8::internal ======================================= --- /dev/null +++ /branches/bleeding_edge/src/cfg.h Fri Jul 31 04:06:17 2009 @@ -0,0 +1,311 @@ +// Copyright 2009 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef V8_CFG_H_ +#define V8_CFG_H_ + +#include "ast.h" + +namespace v8 { +namespace internal { + +// Values appear in instructions. They represent trivial source +// expressions: ones with no side effects and that do not require code to be +// generated. +class Value : public ZoneObject { + public: + virtual void ToRegister(MacroAssembler* masm, Register reg) = 0; + +#ifdef DEBUG + virtual void Print() = 0; +#endif +}; + + +// A compile-time constant that appeared as a literal in the source AST. +class Constant : public Value { + public: + explicit Constant(Handle<Object> handle) : handle_(handle) {} + + virtual void ToRegister(MacroAssembler* masm, Register reg); + +#ifdef DEBUG + void Print(); +#endif + + private: + Handle<Object> handle_; +}; + + +// Instructions are computations. The represent non-trivial source +// expressions: typically ones that have side effects and require code to +// be generated. +class Instruction : public ZoneObject { + public: + virtual void Compile(MacroAssembler* masm) = 0; + +#ifdef DEBUG + virtual void Print() = 0; +#endif +}; + + +// Return a value. +class ReturnInstr : public Instruction { + public: + explicit ReturnInstr(Value* value) : value_(value) {} + + void Compile(MacroAssembler* masm); + +#ifdef DEBUG + void Print(); +#endif + + private: + Value* value_; +}; + + +// Nodes make up control-flow graphs. They contain single-entry, +// single-exit blocks of instructions and administrative nodes making up the +// graph structure. +class CfgNode : public ZoneObject { + public: + CfgNode() : is_marked_(false) { +#ifdef DEBUG + number_ = -1; +#endif + } + + bool is_marked() { return is_marked_; } + + static void Reset(); + + virtual bool is_block() { return false; } + + virtual void Unmark() = 0; + + virtual void Compile(MacroAssembler* masm) = 0; + +#ifdef DEBUG + int number() { + if (number_ == -1) number_ = node_counter_++; + return number_; + } + + virtual void Print() = 0; +#endif + + protected: + bool is_marked_; + +#ifdef DEBUG + int number_; + + static int node_counter_; +#endif +}; + + +// A block is a single-entry, single-exit block of instructions. +class InstructionBlock : public CfgNode { + public: + InstructionBlock() : successor_(NULL), instructions_(4) {} + + static InstructionBlock* cast(CfgNode* node) { + ASSERT(node->is_block()); + return reinterpret_cast<InstructionBlock*>(node); + } + + void set_successor(CfgNode* succ) { + ASSERT(successor_ == NULL); + successor_ = succ; + } + + bool is_block() { return true; } + + void Unmark(); + + void Compile(MacroAssembler* masm); + + void Append(Instruction* instr) { instructions_.Add(instr); } + +#ifdef DEBUG + void Print(); +#endif + + private: + CfgNode* successor_; + ZoneList<Instruction*> instructions_; +}; + + +// The CFG for a function has a distinguished entry node. It has no +// predecessors and a single successor. The successor is the block +// containing the function's first instruction. +class EntryNode : public CfgNode { + public: + EntryNode(FunctionLiteral* fun, InstructionBlock* succ); + + void Unmark(); + + void Compile(MacroAssembler* masm); + +#ifdef DEBUG + void Print(); +#endif + + private: + InstructionBlock* successor_; + int local_count_; +}; + + +// The CFG for a function has a distinguished exit node. It has no +// successor and arbitrarily many predecessors. The predecessors are all +// the blocks returning from the function. +class ExitNode : public CfgNode { + public: + explicit ExitNode(FunctionLiteral* fun); + + void Unmark(); + + void Compile(MacroAssembler* masm); + +#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. +// +// Fragments of control-flow graphs, produced when traversing the statements +// and expressions in the source AST, are represented by the same class. +// They have instruction blocks as both their entry and exit (if there is +// one). Instructions can always be prepended or appended to fragments, and +// fragments can always be concatenated. +// +// A singleton CFG fragment (i.e., with only one node) has the same node as +// both entry and exit (if the exit is available). +class Cfg : public ZoneObject { + public: + // Create a singleton CFG fragment. + explicit Cfg(InstructionBlock* block) : entry_(block), exit_(block) {} + + // Build the CFG for a function. + static Cfg* Build(FunctionLiteral* fun); + + // The entry and exit nodes. + CfgNode* entry() { return entry_; } + CfgNode* exit() { return exit_; } + + // True if the CFG has no nodes. + bool is_empty() { return entry_ == NULL; } + + // True if the CFG has an available exit node (i.e., it can be appended or + // concatenated to). + bool has_exit() { return exit_ != NULL; } + + // Add an entry node to a CFG fragment. It is no longer a fragment + // (instructions cannot be prepended). + void PrependEntryNode(FunctionLiteral* fun); + + // Append an instruction to the end of a CFG fragment. Assumes it has an + // available exit. + void Append(Instruction* instr); + + // Appends a return instruction to the end of a CFG fragment. It no + // longer has an available exit node. + void AppendReturnInstruction(Value* value); + + Handle<Code> Compile(FunctionLiteral* fun, Handle<Script> script); + +#ifdef DEBUG + // Support for printing. + void Print(); +#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_; +}; + + +// An Expression Builder traverses a trivial expression and returns a value. +class ExpressionBuilder : public AstVisitor { + public: + ExpressionBuilder() : value_(new Constant(Handle<Object>::null())) {} + + Value* value() { return value_; } + + // AST node visitors. +#define DECLARE_VISIT(type) void Visit##type(type* node); + AST_NODE_LIST(DECLARE_VISIT) +#undef DECLARE_VISIT + + private: + Value* value_; +}; + + +// A StatementBuilder traverses a statement and returns a CFG. +class StatementBuilder : public AstVisitor { + public: + StatementBuilder() : cfg_(new Cfg(new InstructionBlock())) {} + + Cfg* cfg() { return cfg_; } + + void VisitStatements(ZoneList<Statement*>* stmts); + + // AST node visitors. +#define DECLARE_VISIT(type) void Visit##type(type* node); + AST_NODE_LIST(DECLARE_VISIT) +#undef DECLARE_VISIT + + private: + Cfg* cfg_; +}; + + +} } // namespace v8::internal + +#endif // V8_CFG_H_ ======================================= --- /dev/null +++ /branches/bleeding_edge/src/ia32/cfg-ia32.cc Fri Jul 31 04:06:17 2009 @@ -0,0 +1,109 @@ +// Copyright 2009 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include "v8.h" + +#include "cfg.h" +#include "codegen-inl.h" +#include "macro-assembler-ia32.h" + +namespace v8 { +namespace internal { + +#define __ ACCESS_MASM(masm) + +void InstructionBlock::Compile(MacroAssembler* masm) { + ASSERT(!is_marked()); + is_marked_ = true; + { + Comment cmt(masm, "[ InstructionBlock"); + for (int i = 0, len = instructions_.length(); i < len; i++) { + instructions_[i]->Compile(masm); + } + } + successor_->Compile(masm); +} + + +void EntryNode::Compile(MacroAssembler* masm) { + ASSERT(!is_marked()); + is_marked_ = true; + Label deferred_enter, deferred_exit; + { + Comment cmnt(masm, "[ EntryNode"); + __ push(ebp); + __ mov(ebp, esp); + __ push(esi); + __ push(edi); + if (local_count_ > 0) { + __ Set(eax, Immediate(Factory::undefined_value())); + for (int i = 0; i < local_count_; i++) { + __ push(eax); + } + } + if (FLAG_check_stack) { + ExternalReference stack_limit = + ExternalReference::address_of_stack_guard_limit(); + __ cmp(esp, Operand::StaticVariable(stack_limit)); + __ j(below, &deferred_enter); + __ bind(&deferred_exit); + } + } + successor_->Compile(masm); + if (FLAG_check_stack) { + __ bind(&deferred_enter); + StackCheckStub stub; + __ CallStub(&stub); + __ jmp(&deferred_exit); + } +} + + +void ExitNode::Compile(MacroAssembler* masm) { + ASSERT(!is_marked()); + is_marked_ = true; + Comment cmnt(masm, "[ ExitNode"); + __ RecordJSReturn(); + __ mov(esp, ebp); + __ pop(ebp); + __ ret((parameter_count_ + 1) * kPointerSize); +} + + +void ReturnInstr::Compile(MacroAssembler* masm) { + Comment cmnt(masm, "[ ReturnInstr"); + value_->ToRegister(masm, eax); +} + + +void Constant::ToRegister(MacroAssembler* masm, Register reg) { + __ mov(reg, Immediate(handle_)); +} + +#undef __ + +} } // namespace v8::internal ======================================= --- /dev/null +++ /branches/bleeding_edge/src/x64/cfg-x64.cc Fri Jul 31 04:06:17 2009 @@ -0,0 +1,119 @@ +// Copyright 2009 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include "v8.h" + +#include "cfg.h" +#include "codegen-inl.h" +#include "debug.h" +#include "macro-assembler-x64.h" + +namespace v8 { +namespace internal { + +#define __ ACCESS_MASM(masm) + +void InstructionBlock::Compile(MacroAssembler* masm) { + ASSERT(!is_marked()); + is_marked_ = true; + { + Comment cmt(masm, "[ InstructionBlock"); + for (int i = 0, len = instructions_.length(); i < len; i++) { + instructions_[i]->Compile(masm); + } + } + successor_->Compile(masm); +} + + +void EntryNode::Compile(MacroAssembler* masm) { + ASSERT(!is_marked()); + is_marked_ = true; + Label deferred_enter, deferred_exit; + { + Comment cmnt(masm, "[ EntryNode"); + __ push(rbp); + __ movq(rbp, rsp); + __ push(rsi); + __ push(rdi); + if (local_count_ > 0) { + __ movq(kScratchRegister, Factory::undefined_value(), + RelocInfo::EMBEDDED_OBJECT); + for (int i = 0; i < local_count_; i++) { + __ push(kScratchRegister); + } + } + if (FLAG_check_stack) { + ExternalReference stack_limit = + ExternalReference::address_of_stack_guard_limit(); + __ movq(kScratchRegister, stack_limit); + __ cmpq(rsp, Operand(kScratchRegister, 0)); + __ j(below, &deferred_enter); + __ bind(&deferred_exit); + } + } + successor_->Compile(masm); + if (FLAG_check_stack) { + __ bind(&deferred_enter); + StackCheckStub stub; + __ CallStub(&stub); + __ jmp(&deferred_exit); + } +} + + +void ExitNode::Compile(MacroAssembler* masm) { + ASSERT(!is_marked()); + is_marked_ = true; + + Comment cmnt(masm, "[ ExitNode"); + __ RecordJSReturn(); + __ movq(rsp, rbp); + __ pop(rbp); + __ ret((parameter_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; + for (int i = 0; i < kPadding; ++i) { + __ int3(); + } +} + + +void ReturnInstr::Compile(MacroAssembler* masm) { + Comment cmnt(masm, "[ ReturnInstr"); + value_->ToRegister(masm, rax); +} + + +void Constant::ToRegister(MacroAssembler* masm, Register reg) { + __ Move(reg, handle_); +} + +#undef __ + +} } // namespace v8::internal ======================================= --- /branches/bleeding_edge/src/SConscript Thu Jul 16 22:37:09 2009 +++ /branches/bleeding_edge/src/SConscript Fri Jul 31 04:06:17 2009 @@ -36,25 +36,26 @@ SOURCES = { 'all': [ 'accessors.cc', 'allocation.cc', 'api.cc', 'assembler.cc', 'ast.cc', - 'bootstrapper.cc', 'builtins.cc', 'checks.cc', 'code-stubs.cc', - 'codegen.cc', 'compilation-cache.cc', 'compiler.cc', 'contexts.cc', - 'conversions.cc', 'counters.cc', 'dateparser.cc', 'debug.cc', - 'debug-agent.cc', 'disassembler.cc', 'execution.cc', 'factory.cc', - 'flags.cc', 'frame-element.cc', 'frames.cc', 'func-name-inferrer.cc', - 'global-handles.cc', 'handles.cc', 'hashmap.cc', - 'heap.cc', 'ic.cc', 'interpreter-irregexp.cc', 'jsregexp.cc', - 'jump-target.cc', 'log.cc', 'log-utils.cc', 'mark-compact.cc', 'messages.cc', - 'objects.cc', 'oprofile-agent.cc', 'parser.cc', 'property.cc', - 'regexp-macro-assembler.cc', 'regexp-macro-assembler-irregexp.cc', - 'regexp-stack.cc', 'register-allocator.cc', 'rewriter.cc', 'runtime.cc', - 'scanner.cc', 'scopeinfo.cc', 'scopes.cc', 'serialize.cc', - 'snapshot-common.cc', 'spaces.cc', 'string-stream.cc', 'stub-cache.cc', - 'token.cc', 'top.cc', 'unicode.cc', 'usage-analyzer.cc', 'utils.cc', - 'v8-counters.cc', 'v8.cc', 'v8threads.cc', 'variables.cc', 'version.cc', + 'bootstrapper.cc', 'builtins.cc', 'checks.cc', 'cfg.cc', + 'code-stubs.cc', 'codegen.cc', 'compilation-cache.cc', 'compiler.cc', + 'contexts.cc', 'conversions.cc', 'counters.cc', 'dateparser.cc', + 'debug.cc', 'debug-agent.cc', 'disassembler.cc', 'execution.cc', + 'factory.cc', 'flags.cc', 'frame-element.cc', 'frames.cc', + 'func-name-inferrer.cc', 'global-handles.cc', 'handles.cc', + 'hashmap.cc', 'heap.cc', 'ic.cc', 'interpreter-irregexp.cc', + 'jsregexp.cc', 'jump-target.cc', 'log.cc', 'log-utils.cc', + 'mark-compact.cc', 'messages.cc', 'objects.cc', 'oprofile-agent.cc', + 'parser.cc', 'property.cc', 'regexp-macro-assembler.cc', + 'regexp-macro-assembler-irregexp.cc', 'regexp-stack.cc', + 'register-allocator.cc', 'rewriter.cc', 'runtime.cc', 'scanner.cc', + 'scopeinfo.cc', 'scopes.cc', 'serialize.cc', 'snapshot-common.cc', + 'spaces.cc', 'string-stream.cc', 'stub-cache.cc', 'token.cc', 'top.cc', + 'unicode.cc', 'usage-analyzer.cc', 'utils.cc', 'v8-counters.cc', + 'v8.cc', 'v8threads.cc', 'variables.cc', 'version.cc', 'virtual-frame.cc', 'zone.cc' ], 'arch:arm': [ - 'arm/assembler-arm.cc', 'arm/builtins-arm.cc', + 'arm/assembler-arm.cc', 'arm/builtins-arm.cc', 'arm/cfg-arm.cc', 'arm/codegen-arm.cc', 'arm/cpu-arm.cc', 'arm/disasm-arm.cc', 'arm/debug-arm.cc', 'arm/frames-arm.cc', 'arm/ic-arm.cc', 'arm/jump-target-arm.cc', 'arm/macro-assembler-arm.cc', @@ -63,7 +64,7 @@ 'arm/virtual-frame-arm.cc' ], 'arch:ia32': [ - 'ia32/assembler-ia32.cc', 'ia32/builtins-ia32.cc', + 'ia32/assembler-ia32.cc', 'ia32/builtins-ia32.cc', 'ia32/cfg-ia32.cc', 'ia32/codegen-ia32.cc', 'ia32/cpu-ia32.cc', 'ia32/disasm-ia32.cc', 'ia32/debug-ia32.cc', 'ia32/frames-ia32.cc', 'ia32/ic-ia32.cc', 'ia32/jump-target-ia32.cc', 'ia32/macro-assembler-ia32.cc', @@ -72,7 +73,7 @@ 'ia32/virtual-frame-ia32.cc' ], 'arch:x64': [ - 'x64/assembler-x64.cc', 'x64/builtins-x64.cc', + 'x64/assembler-x64.cc', 'x64/builtins-x64.cc', 'x64/cfg-x64.cc', 'x64/codegen-x64.cc', 'x64/cpu-x64.cc', 'x64/disasm-x64.cc', 'x64/debug-x64.cc', 'x64/frames-x64.cc', 'x64/ic-x64.cc', 'x64/jump-target-x64.cc', 'x64/macro-assembler-x64.cc', ======================================= --- /branches/bleeding_edge/src/compiler.cc Wed Jun 24 06:09:34 2009 +++ /branches/bleeding_edge/src/compiler.cc Fri Jul 31 04:06:17 2009 @@ -28,6 +28,7 @@ #include "v8.h" #include "bootstrapper.h" +#include "cfg.h" #include "codegen-inl.h" #include "compilation-cache.h" #include "compiler.h" @@ -77,6 +78,21 @@ // overflow exception will be thrown by the caller. return Handle<Code>::null(); } + + if (FLAG_multipass) { + Cfg* cfg = Cfg::Build(literal); +#ifdef DEBUG + if (FLAG_print_cfg && cfg != NULL) { + SmartPointer<char> name = literal->name()->ToCString(); + PrintF("Function \"%s\":\n", *name); + cfg->Print(); + PrintF("\n"); + } +#endif + if (cfg != NULL) { + return cfg->Compile(literal, script); + } + } // Generate code and return it. Handle<Code> result = CodeGenerator::MakeCode(literal, script, is_eval); ======================================= --- /branches/bleeding_edge/src/flag-definitions.h Mon Jul 13 16:41:17 2009 +++ /branches/bleeding_edge/src/flag-definitions.h Fri Jul 31 04:06:17 2009 @@ -133,6 +133,7 @@ DEFINE_bool(strict, false, "strict error checking") DEFINE_int(min_preparse_length, 1024, "Minimum length for automatic enable preparsing") +DEFINE_bool(multipass, false, "use the multipass code generator") // compilation-cache.cc DEFINE_bool(compilation_cache, true, "enable compilation cache") @@ -267,6 +268,7 @@ // compiler.cc DEFINE_bool(print_builtin_scopes, false, "print scopes for builtins") DEFINE_bool(print_scopes, false, "print scopes") +DEFINE_bool(print_cfg, false, "print control-flow graph") // contexts.cc DEFINE_bool(trace_contexts, false, "trace contexts operations") ======================================= --- /branches/bleeding_edge/tools/gyp/v8.gyp Fri Jul 31 00:55:07 2009 +++ /branches/bleeding_edge/tools/gyp/v8.gyp Fri Jul 31 04:06:17 2009 @@ -40,7 +40,7 @@ 'defines': [ 'ENABLE_LOGGING_AND_PROFILING', ], - 'conditions': [ + 'conditions': [ ['target_arch=="arm"', { 'defines': [ 'V8_TARGET_ARCH_ARM', @@ -216,6 +216,8 @@ '../../src/builtins.cc', '../../src/builtins.h', '../../src/bytecodes-irregexp.h', + '../../src/cfg.cc', + '../../src/cfg.h', '../../src/char-predicates-inl.h', '../../src/char-predicates.h', '../../src/checks.cc', @@ -383,6 +385,7 @@ '../../src/arm/assembler-arm.cc', '../../src/arm/assembler-arm.h', '../../src/arm/builtins-arm.cc', + '../../src/arm/cfg-arm.cc', '../../src/arm/codegen-arm.cc', '../../src/arm/codegen-arm.h', '../../src/arm/constants-arm.h', @@ -413,6 +416,7 @@ '../../src/ia32/assembler-ia32.cc', '../../src/ia32/assembler-ia32.h', '../../src/ia32/builtins-ia32.cc', + '../../src/ia32/cfg-ia32.cc', '../../src/ia32/codegen-ia32.cc', '../../src/ia32/codegen-ia32.h', '../../src/ia32/cpu-ia32.cc', @@ -441,6 +445,7 @@ '../../src/x64/assembler-x64.cc', '../../src/x64/assembler-x64.h', '../../src/x64/builtins-x64.cc', + '../../src/x64/cfg-x64.cc', '../../src/x64/codegen-x64.cc', '../../src/x64/codegen-x64.h', '../../src/x64/cpu-x64.cc', ======================================= --- /branches/bleeding_edge/tools/visual_studio/v8_base.vcproj Wed Jul 29 01:10:19 2009 +++ /branches/bleeding_edge/tools/visual_studio/v8_base.vcproj Fri Jul 31 04:06:17 2009 @@ -235,6 +235,18 @@ <File RelativePath="..\..\src\bytecodes-irregexp.h" > + </File> + <File + RelativePath="..\..\src\ia32\cfg-ia32.cc" + > + </File> + <File + RelativePath="..\..\src\cfg.cc" + > + </File> + <File + RelativePath="..\..\src\cfg.h" + > </File> <File RelativePath="..\..\src\char-predicates-inl.h" ======================================= --- /branches/bleeding_edge/tools/visual_studio/v8_base_arm.vcproj Wed Jul 29 01:10:19 2009 +++ /branches/bleeding_edge/tools/visual_studio/v8_base_arm.vcproj Fri Jul 31 04:06:17 2009 @@ -235,6 +235,18 @@ <File RelativePath="..\..\src\bytecodes-irregexp.h" > + </File> + <File + RelativePath="..\..\src\arm\cfg-arm.cc" + > + </File> + <File + RelativePath="..\..\src\cfg.cc" + > + </File> + <File + RelativePath="..\..\src\cfg.h" + > </File> <File RelativePath="..\..\src\char-predicates-inl.h" --~--~---------~--~----~------------~-------~--~----~ v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev -~----------~----~----~----~------~----~------~--~---
