| Index: src/cfg.h
|
| ===================================================================
|
| --- src/cfg.h (revision 2994)
|
| +++ src/cfg.h (working copy)
|
| @@ -1,871 +0,0 @@
|
| -// 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 {
|
| -
|
| -class ExitNode;
|
| -class Location;
|
| -
|
| -// Translate a source AST into a control-flow graph (CFG). The CFG contains
|
| -// single-entry, single-exit blocks of straight-line instructions and
|
| -// administrative nodes.
|
| -//
|
| -// Instructions are described by the following grammar.
|
| -//
|
| -// <Instruction> ::=
|
| -// Move <Location> <Value>
|
| -// | PropLoad <Location> <Value> <Value>
|
| -// | BinaryOp <Location> Token::Value <Value> <Value>
|
| -// | Return Nowhere <Value>
|
| -// | Position <Int>
|
| -//
|
| -// Values are trivial expressions:
|
| -//
|
| -// <Value> ::= Constant | <Location>
|
| -//
|
| -// Locations are storable values ('lvalues'). They can be slots,
|
| -// compiler-generated temporaries, or the special location 'Nowhere'
|
| -// indicating that no value is needed.
|
| -//
|
| -// <Location> ::=
|
| -// SlotLocation Slot::Type <Index>
|
| -// | TempLocation
|
| -// | Nowhere
|
| -
|
| -
|
| -// Administrative nodes: There are several types of 'administrative' nodes
|
| -// that do not contain instructions and do not necessarily have a single
|
| -// predecessor and a single successor.
|
| -//
|
| -// EntryNode: there is a distinguished entry node that has no predecessors
|
| -// and a single successor.
|
| -//
|
| -// ExitNode: there is a distinguished exit node that has arbitrarily many
|
| -// predecessors and no successor.
|
| -//
|
| -// JoinNode: join nodes have multiple predecessors and a single successor.
|
| -//
|
| -// BranchNode: branch nodes have a single predecessor and multiple
|
| -// successors.
|
| -
|
| -
|
| -// 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_;
|
| - }
|
| -
|
| - // The function currently being compiled.
|
| - FunctionLiteral* fun() { return global_fun_; }
|
| -
|
| - // The shared global exit node for all exits from the function.
|
| - ExitNode* exit() { return global_exit_; }
|
| -
|
| - // A singleton.
|
| - Location* nowhere() { return nowhere_; }
|
| -
|
| -#ifdef DEBUG
|
| - int next_node_number() { return node_counter_++; }
|
| - int next_temp_number() { return temp_counter_++; }
|
| -#endif
|
| -
|
| - private:
|
| - static CfgGlobals* top_;
|
| - FunctionLiteral* global_fun_;
|
| - ExitNode* global_exit_;
|
| - Location* nowhere_;
|
| -
|
| -#ifdef DEBUG
|
| - // Used to number nodes and temporaries when printing.
|
| - int node_counter_;
|
| - int temp_counter_;
|
| -#endif
|
| -
|
| - CfgGlobals* previous_;
|
| -};
|
| -
|
| -
|
| -class SlotLocation;
|
| -
|
| -// Values represent trivial source expressions: ones with no side effects
|
| -// and that do not require code to be generated.
|
| -class Value : public ZoneObject {
|
| - public:
|
| - virtual ~Value() {}
|
| -
|
| - // Predicates:
|
| -
|
| - virtual bool is_temporary() { return false; }
|
| - virtual bool is_slot() { return false; }
|
| - virtual bool is_constant() { return false; }
|
| -
|
| - // True if the value is a temporary allocated to the stack in
|
| - // fast-compilation mode.
|
| - virtual bool is_on_stack() { return false; }
|
| -
|
| - // Support for fast-compilation mode:
|
| -
|
| - // Move the value into a register.
|
| - virtual void Get(MacroAssembler* masm, Register reg) = 0;
|
| -
|
| - // Push the value on the stack.
|
| - virtual void Push(MacroAssembler* masm) = 0;
|
| -
|
| - // Move the value into a slot location.
|
| - virtual void MoveToSlot(MacroAssembler* masm, SlotLocation* loc) = 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) {}
|
| -
|
| - // Cast accessor.
|
| - static Constant* cast(Value* value) {
|
| - ASSERT(value->is_constant());
|
| - return reinterpret_cast<Constant*>(value);
|
| - }
|
| -
|
| - // Accessors.
|
| - Handle<Object> handle() { return handle_; }
|
| -
|
| - // Predicates.
|
| - bool is_constant() { return true; }
|
| -
|
| - // Support for fast-compilation mode.
|
| - void Get(MacroAssembler* masm, Register reg);
|
| - void Push(MacroAssembler* masm);
|
| - void MoveToSlot(MacroAssembler* masm, SlotLocation* loc);
|
| -
|
| -#ifdef DEBUG
|
| - void Print();
|
| -#endif
|
| -
|
| - private:
|
| - Handle<Object> handle_;
|
| -};
|
| -
|
| -
|
| -// Locations are values that can be stored into ('lvalues').
|
| -class Location : public Value {
|
| - public:
|
| - virtual ~Location() {}
|
| -
|
| - // Static factory function returning the singleton nowhere location.
|
| - static Location* Nowhere() {
|
| - return CfgGlobals::current()->nowhere();
|
| - }
|
| -
|
| - // Support for fast-compilation mode:
|
| -
|
| - // Assumes temporaries have been allocated.
|
| - virtual void Get(MacroAssembler* masm, Register reg) = 0;
|
| -
|
| - // Store the value in a register to the location. Assumes temporaries
|
| - // have been allocated.
|
| - virtual void Set(MacroAssembler* masm, Register reg) = 0;
|
| -
|
| - // Assumes temporaries have been allocated, and if the value is a
|
| - // temporary it was not allocated to the stack.
|
| - virtual void Push(MacroAssembler* masm) = 0;
|
| -
|
| - // Emit code to move a value into this location.
|
| - virtual void Move(MacroAssembler* masm, Value* value) = 0;
|
| -
|
| -#ifdef DEBUG
|
| - virtual void Print() = 0;
|
| -#endif
|
| -};
|
| -
|
| -
|
| -// Nowhere is a special (singleton) location that indicates the value of a
|
| -// computation is not needed (though its side effects are).
|
| -class Nowhere : public Location {
|
| - public:
|
| - // We should not try to emit code to read Nowhere.
|
| - void Get(MacroAssembler* masm, Register reg) { UNREACHABLE(); }
|
| - void Push(MacroAssembler* masm) { UNREACHABLE(); }
|
| - void MoveToSlot(MacroAssembler* masm, SlotLocation* loc) { UNREACHABLE(); }
|
| -
|
| - // Setting Nowhere is ignored.
|
| - void Set(MacroAssembler* masm, Register reg) {}
|
| - void Move(MacroAssembler* masm, Value* value) {}
|
| -
|
| -#ifdef DEBUG
|
| - void Print();
|
| -#endif
|
| -
|
| - private:
|
| - Nowhere() {}
|
| -
|
| - friend class CfgGlobals;
|
| -};
|
| -
|
| -
|
| -// 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) {}
|
| -
|
| - // Cast accessor.
|
| - static SlotLocation* cast(Value* value) {
|
| - ASSERT(value->is_slot());
|
| - return reinterpret_cast<SlotLocation*>(value);
|
| - }
|
| -
|
| - // Accessors.
|
| - Slot::Type type() { return type_; }
|
| - int index() { return index_; }
|
| -
|
| - // Predicates.
|
| - bool is_slot() { return true; }
|
| -
|
| - // Support for fast-compilation mode.
|
| - void Get(MacroAssembler* masm, Register reg);
|
| - void Set(MacroAssembler* masm, Register reg);
|
| - void Push(MacroAssembler* masm);
|
| - void Move(MacroAssembler* masm, Value* value);
|
| - void MoveToSlot(MacroAssembler* masm, SlotLocation* loc);
|
| -
|
| -#ifdef DEBUG
|
| - void Print();
|
| -#endif
|
| -
|
| - private:
|
| - Slot::Type type_;
|
| - int index_;
|
| -};
|
| -
|
| -
|
| -// TempLocations represent compiler generated temporaries. They are
|
| -// allocated to registers or memory either before code generation (in the
|
| -// optimized-for-speed compiler) or on the fly during code generation (in
|
| -// the optimized-for-space compiler).
|
| -class TempLocation : public Location {
|
| - public:
|
| - // Fast-compilation mode allocation decisions.
|
| - enum Where {
|
| - NOT_ALLOCATED, // Not yet allocated.
|
| - ACCUMULATOR, // Allocated to the dedicated accumulator register.
|
| - STACK // " " " " stack.
|
| - };
|
| -
|
| - TempLocation() : where_(NOT_ALLOCATED) {
|
| -#ifdef DEBUG
|
| - number_ = -1;
|
| -#endif
|
| - }
|
| -
|
| - // Cast accessor.
|
| - static TempLocation* cast(Value* value) {
|
| - ASSERT(value->is_temporary());
|
| - return reinterpret_cast<TempLocation*>(value);
|
| - }
|
| -
|
| - // Accessors.
|
| - Where where() { return where_; }
|
| - void set_where(Where where) {
|
| - ASSERT(where_ == TempLocation::NOT_ALLOCATED);
|
| - where_ = where;
|
| - }
|
| -
|
| - // Predicates.
|
| - bool is_on_stack() { return where_ == STACK; }
|
| - bool is_temporary() { return true; }
|
| -
|
| - // Support for fast-compilation mode. Assume the temp has been allocated.
|
| - void Get(MacroAssembler* masm, Register reg);
|
| - void Set(MacroAssembler* masm, Register reg);
|
| - void Push(MacroAssembler* masm);
|
| - void Move(MacroAssembler* masm, Value* value);
|
| - void MoveToSlot(MacroAssembler* masm, SlotLocation* loc);
|
| -
|
| -#ifdef DEBUG
|
| - int number() {
|
| - if (number_ == -1) number_ = CfgGlobals::current()->next_temp_number();
|
| - return number_;
|
| - }
|
| -
|
| - void Print();
|
| -#endif
|
| -
|
| - private:
|
| - Where where_;
|
| -
|
| -#ifdef DEBUG
|
| - int number_;
|
| -#endif
|
| -};
|
| -
|
| -
|
| -// 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:
|
| - // Accessors.
|
| - Location* location() { return location_; }
|
| - void set_location(Location* location) { location_ = location; }
|
| -
|
| - // Support for fast-compilation mode:
|
| -
|
| - // Emit code to perform the instruction.
|
| - virtual void Compile(MacroAssembler* masm) = 0;
|
| -
|
| - // Allocate a temporary which is the result of the immediate predecessor
|
| - // instruction. It is allocated to the accumulator register if it is used
|
| - // as an operand to this instruction, otherwise to the stack.
|
| - virtual void FastAllocate(TempLocation* temp) = 0;
|
| -
|
| -#ifdef DEBUG
|
| - virtual void Print() = 0;
|
| -#endif
|
| -
|
| - protected:
|
| - // Every instruction has a location where its result is stored (which may
|
| - // be Nowhere).
|
| - explicit Instruction(Location* location) : location_(location) {}
|
| -
|
| - virtual ~Instruction() {}
|
| -
|
| - Location* location_;
|
| -};
|
| -
|
| -
|
| -// Base class of instructions that have no input operands.
|
| -class ZeroOperandInstruction : public Instruction {
|
| - public:
|
| - // Support for fast-compilation mode:
|
| - virtual void Compile(MacroAssembler* masm) = 0;
|
| - void FastAllocate(TempLocation* temp);
|
| -
|
| -#ifdef DEBUG
|
| - // Printing support: print the operands (nothing).
|
| - virtual void Print() {}
|
| -#endif
|
| -
|
| - protected:
|
| - explicit ZeroOperandInstruction(Location* loc) : Instruction(loc) {}
|
| -};
|
| -
|
| -
|
| -// Base class of instructions that have a single input operand.
|
| -class OneOperandInstruction : public Instruction {
|
| - public:
|
| - // Support for fast-compilation mode:
|
| - virtual void Compile(MacroAssembler* masm) = 0;
|
| - void FastAllocate(TempLocation* temp);
|
| -
|
| -#ifdef DEBUG
|
| - // Printing support: print the operands.
|
| - virtual void Print();
|
| -#endif
|
| -
|
| - protected:
|
| - OneOperandInstruction(Location* loc, Value* value)
|
| - : Instruction(loc), value_(value) {
|
| - }
|
| -
|
| - Value* value_;
|
| -};
|
| -
|
| -
|
| -// Base class of instructions that have two input operands.
|
| -class TwoOperandInstruction : public Instruction {
|
| - public:
|
| - // Support for fast-compilation mode:
|
| - virtual void Compile(MacroAssembler* masm) = 0;
|
| - void FastAllocate(TempLocation* temp);
|
| -
|
| -#ifdef DEBUG
|
| - // Printing support: print the operands.
|
| - virtual void Print();
|
| -#endif
|
| -
|
| - protected:
|
| - TwoOperandInstruction(Location* loc, Value* value0, Value* value1)
|
| - : Instruction(loc), value0_(value0), value1_(value1) {
|
| - }
|
| -
|
| - Value* value0_;
|
| - Value* value1_;
|
| -};
|
| -
|
| -
|
| -// A phantom instruction that indicates the start of a statement. It
|
| -// causes the statement position to be recorded in the relocation
|
| -// information but generates no code.
|
| -class PositionInstr : public ZeroOperandInstruction {
|
| - public:
|
| - explicit PositionInstr(int pos)
|
| - : ZeroOperandInstruction(CfgGlobals::current()->nowhere()), pos_(pos) {
|
| - }
|
| -
|
| - // Support for fast-compilation mode.
|
| - void Compile(MacroAssembler* masm);
|
| -
|
| - // This should not be called. The last instruction of the previous
|
| - // statement should not have a temporary as its location.
|
| - void FastAllocate(TempLocation* temp) { UNREACHABLE(); }
|
| -
|
| -#ifdef DEBUG
|
| - // Printing support. Print nothing.
|
| - void Print() {}
|
| -#endif
|
| -
|
| - private:
|
| - int pos_;
|
| -};
|
| -
|
| -
|
| -// Move a value to a location.
|
| -class MoveInstr : public OneOperandInstruction {
|
| - public:
|
| - MoveInstr(Location* loc, Value* value)
|
| - : OneOperandInstruction(loc, value) {
|
| - }
|
| -
|
| - // Accessors.
|
| - Value* value() { return value_; }
|
| -
|
| - // Support for fast-compilation mode.
|
| - void Compile(MacroAssembler* masm);
|
| -
|
| -#ifdef DEBUG
|
| - // Printing support.
|
| - void Print();
|
| -#endif
|
| -};
|
| -
|
| -
|
| -// Load a property from a receiver, leaving the result in a location.
|
| -class PropLoadInstr : public TwoOperandInstruction {
|
| - public:
|
| - PropLoadInstr(Location* loc, Value* object, Value* key)
|
| - : TwoOperandInstruction(loc, object, key) {
|
| - }
|
| -
|
| - // Accessors.
|
| - Value* object() { return value0_; }
|
| - Value* key() { return value1_; }
|
| -
|
| - // Support for fast-compilation mode.
|
| - void Compile(MacroAssembler* masm);
|
| -
|
| -#ifdef DEBUG
|
| - void Print();
|
| -#endif
|
| -};
|
| -
|
| -
|
| -// Perform a (non-short-circuited) binary operation on a pair of values,
|
| -// leaving the result in a location.
|
| -class BinaryOpInstr : public TwoOperandInstruction {
|
| - public:
|
| - BinaryOpInstr(Location* loc, Token::Value op, Value* left, Value* right)
|
| - : TwoOperandInstruction(loc, left, right), op_(op) {
|
| - }
|
| -
|
| - // Accessors.
|
| - Value* left() { return value0_; }
|
| - Value* right() { return value1_; }
|
| - Token::Value op() { return op_; }
|
| -
|
| - // Support for fast-compilation mode.
|
| - void Compile(MacroAssembler* masm);
|
| -
|
| -#ifdef DEBUG
|
| - void Print();
|
| -#endif
|
| -
|
| - private:
|
| - Token::Value op_;
|
| -};
|
| -
|
| -
|
| -// Return a value. Has the side effect of moving its value into the return
|
| -// value register. Can only occur as the last instruction in an instruction
|
| -// block, and implies that the block is closed (cannot have instructions
|
| -// appended or graph fragments concatenated to the end) and that the block's
|
| -// successor is the global exit node for the current function.
|
| -class ReturnInstr : public OneOperandInstruction {
|
| - public:
|
| - explicit ReturnInstr(Value* value)
|
| - : OneOperandInstruction(CfgGlobals::current()->nowhere(), value) {
|
| - }
|
| -
|
| - virtual ~ReturnInstr() {}
|
| -
|
| - // Accessors.
|
| - Value* value() { return value_; }
|
| -
|
| - // Support for fast-compilation mode.
|
| - void Compile(MacroAssembler* masm);
|
| -
|
| -#ifdef DEBUG
|
| - void Print();
|
| -#endif
|
| -};
|
| -
|
| -
|
| -// Nodes make up control-flow graphs.
|
| -class CfgNode : public ZoneObject {
|
| - public:
|
| - CfgNode() : is_marked_(false) {
|
| -#ifdef DEBUG
|
| - number_ = -1;
|
| -#endif
|
| - }
|
| -
|
| - virtual ~CfgNode() {}
|
| -
|
| - // Because CFGs contain cycles, nodes support marking during traversal
|
| - // (e.g., for printing or compilation). The traversal functions will mark
|
| - // unmarked nodes and backtrack if they encounter a marked one. After a
|
| - // traversal, the graph should be explicitly unmarked by calling Unmark on
|
| - // the entry node.
|
| - bool is_marked() { return is_marked_; }
|
| - virtual void Unmark() = 0;
|
| -
|
| - // Predicates:
|
| -
|
| - // True if the node is an instruction block.
|
| - virtual bool is_block() { return false; }
|
| -
|
| - // Support for fast-compilation mode. Emit the instructions or control
|
| - // flow represented by the node.
|
| - virtual void Compile(MacroAssembler* masm) = 0;
|
| -
|
| -#ifdef DEBUG
|
| - int number() {
|
| - if (number_ == -1) number_ = CfgGlobals::current()->next_node_number();
|
| - return number_;
|
| - }
|
| -
|
| - virtual void Print() = 0;
|
| -#endif
|
| -
|
| - protected:
|
| - bool is_marked_;
|
| -
|
| -#ifdef DEBUG
|
| - int number_;
|
| -#endif
|
| -};
|
| -
|
| -
|
| -// A block is a single-entry, single-exit block of instructions.
|
| -class InstructionBlock : public CfgNode {
|
| - public:
|
| - InstructionBlock() : successor_(NULL), instructions_(4) {}
|
| -
|
| - virtual ~InstructionBlock() {}
|
| -
|
| - void Unmark();
|
| -
|
| - // Cast accessor.
|
| - static InstructionBlock* cast(CfgNode* node) {
|
| - ASSERT(node->is_block());
|
| - return reinterpret_cast<InstructionBlock*>(node);
|
| - }
|
| -
|
| - bool is_block() { return true; }
|
| -
|
| - // Accessors.
|
| - CfgNode* successor() { return successor_; }
|
| -
|
| - void set_successor(CfgNode* succ) {
|
| - ASSERT(successor_ == NULL);
|
| - successor_ = succ;
|
| - }
|
| -
|
| - ZoneList<Instruction*>* instructions() { return &instructions_; }
|
| -
|
| - // Support for fast-compilation mode.
|
| - void Compile(MacroAssembler* masm);
|
| -
|
| - // Add an instruction to the end of the block.
|
| - void Append(Instruction* instr) { instructions_.Add(instr); }
|
| -
|
| -#ifdef DEBUG
|
| - void Print();
|
| -#endif
|
| -
|
| - private:
|
| - CfgNode* successor_;
|
| - ZoneList<Instruction*> instructions_;
|
| -};
|
| -
|
| -
|
| -// An entry node (one per function).
|
| -class EntryNode : public CfgNode {
|
| - public:
|
| - explicit EntryNode(InstructionBlock* succ) : successor_(succ) {}
|
| -
|
| - virtual ~EntryNode() {}
|
| -
|
| - void Unmark();
|
| -
|
| - // Support for fast-compilation mode.
|
| - void Compile(MacroAssembler* masm);
|
| -
|
| -#ifdef DEBUG
|
| - void Print();
|
| -#endif
|
| -
|
| - private:
|
| - InstructionBlock* successor_;
|
| -};
|
| -
|
| -
|
| -// An exit node (one per function).
|
| -class ExitNode : public CfgNode {
|
| - public:
|
| - ExitNode() {}
|
| -
|
| - virtual ~ExitNode() {}
|
| -
|
| - void Unmark();
|
| -
|
| - // Support for fast-compilation mode.
|
| - void Compile(MacroAssembler* masm);
|
| -
|
| -#ifdef DEBUG
|
| - void Print();
|
| -#endif
|
| -};
|
| -
|
| -
|
| -// A CFG consists of a linked structure of nodes. Nodes are linked by
|
| -// pointing to their successors, always beginning with a (single) entry node
|
| -// (not necessarily of type EntryNode). If it is still possible to add
|
| -// nodes to the end of the graph (i.e., there is a (single) path that does
|
| -// not end with the global exit node), then the CFG has an exit node as
|
| -// well.
|
| -//
|
| -// The empty CFG is represented by a NULL entry and a NULL exit.
|
| -//
|
| -// We use the term 'open fragment' to mean a CFG whose entry and exits are
|
| -// both instruction blocks. It is always possible to add instructions and
|
| -// nodes to the beginning or end of an open fragment.
|
| -//
|
| -// We use the term 'closed fragment' to mean a CFG whose entry is an
|
| -// instruction block and whose exit is NULL (all paths go to the global
|
| -// exit).
|
| -//
|
| -// We use the term 'fragment' to refer to a CFG that is known to be an open
|
| -// or closed fragment.
|
| -class Cfg : public ZoneObject {
|
| - public:
|
| - // Create an empty CFG fragment.
|
| - Cfg() : entry_(NULL), exit_(NULL) {}
|
| -
|
| - // Build the CFG for a function. The returned CFG begins with an
|
| - // EntryNode and all paths end with the ExitNode.
|
| - static Cfg* Build();
|
| -
|
| - // The entry and exit nodes of the CFG (not necessarily EntryNode and
|
| - // ExitNode).
|
| - 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 EntryNode to a CFG fragment. It is no longer a fragment
|
| - // (instructions can no longer be prepended).
|
| - void PrependEntryNode();
|
| -
|
| - // Append an instruction to the end of an open fragment.
|
| - void Append(Instruction* instr);
|
| -
|
| - // Appends a return instruction to the end of an open fragment and make
|
| - // it a closed fragment (the exit's successor becomes global exit node).
|
| - void AppendReturnInstruction(Value* value);
|
| -
|
| - // Glue an other CFG fragment to the end of this (open) fragment.
|
| - void Concatenate(Cfg* other);
|
| -
|
| - // Support for compilation. Compile the entire CFG.
|
| - Handle<Code> Compile(Handle<Script> script);
|
| -
|
| -#ifdef DEBUG
|
| - // Support for printing.
|
| - void Print();
|
| -#endif
|
| -
|
| - private:
|
| - // Entry and exit nodes.
|
| - CfgNode* entry_;
|
| - CfgNode* exit_;
|
| -};
|
| -
|
| -
|
| -// An implementation of a set of locations (currently slot locations), most
|
| -// of the operations are destructive.
|
| -class LocationSet BASE_EMBEDDED {
|
| - public:
|
| - // Construct an empty location set.
|
| - LocationSet() : parameters_(0), locals_(0) {}
|
| -
|
| - // Raw accessors.
|
| - uintptr_t parameters() { return parameters_; }
|
| - uintptr_t locals() { return locals_; }
|
| -
|
| - // Make this the empty set.
|
| - void Empty() {
|
| - parameters_ = locals_ = 0;
|
| - }
|
| -
|
| - // Insert an element.
|
| - void AddElement(SlotLocation* location) {
|
| - if (location->type() == Slot::PARAMETER) {
|
| - // Parameter indexes begin with -1 ('this').
|
| - ASSERT(location->index() < kBitsPerPointer - 1);
|
| - parameters_ |= (1 << (location->index() + 1));
|
| - } else {
|
| - ASSERT(location->type() == Slot::LOCAL);
|
| - ASSERT(location->index() < kBitsPerPointer);
|
| - locals_ |= (1 << location->index());
|
| - }
|
| - }
|
| -
|
| - // (Destructively) compute the union with another set.
|
| - void Union(LocationSet* other) {
|
| - parameters_ |= other->parameters();
|
| - locals_ |= other->locals();
|
| - }
|
| -
|
| - bool Contains(SlotLocation* location) {
|
| - if (location->type() == Slot::PARAMETER) {
|
| - ASSERT(location->index() < kBitsPerPointer - 1);
|
| - return (parameters_ & (1 << (location->index() + 1)));
|
| - } else {
|
| - ASSERT(location->type() == Slot::LOCAL);
|
| - ASSERT(location->index() < kBitsPerPointer);
|
| - return (locals_ & (1 << location->index()));
|
| - }
|
| - }
|
| -
|
| - private:
|
| - uintptr_t parameters_;
|
| - uintptr_t locals_;
|
| -};
|
| -
|
| -
|
| -// An ExpressionCfgBuilder traverses an expression and returns an open CFG
|
| -// fragment (currently a possibly empty list of instructions represented by
|
| -// a singleton instruction block) and the expression's value.
|
| -//
|
| -// Failure to build the CFG is indicated by a NULL CFG.
|
| -class ExpressionCfgBuilder : public AstVisitor {
|
| - public:
|
| - ExpressionCfgBuilder() : destination_(NULL), value_(NULL), graph_(NULL) {}
|
| -
|
| - // Result accessors.
|
| - Value* value() { return value_; }
|
| - Cfg* graph() { return graph_; }
|
| - LocationSet* assigned_vars() { return &assigned_vars_; }
|
| -
|
| - // Build the cfg for an expression and remember its value. The
|
| - // destination is a 'hint' where the value should go which may be ignored.
|
| - // NULL is used to indicate no preference.
|
| - //
|
| - // Concretely, if the expression needs to generate a temporary for its
|
| - // value, it should use the passed destination or generate one if NULL.
|
| - void Build(Expression* expr, Location* destination) {
|
| - value_ = NULL;
|
| - graph_ = new Cfg();
|
| - assigned_vars_.Empty();
|
| - destination_ = destination;
|
| - Visit(expr);
|
| - }
|
| -
|
| - // AST node visitors.
|
| -#define DECLARE_VISIT(type) void Visit##type(type* node);
|
| - AST_NODE_LIST(DECLARE_VISIT)
|
| -#undef DECLARE_VISIT
|
| -
|
| - private:
|
| - // State for the visitor. Input parameter:
|
| - Location* destination_;
|
| -
|
| - // Output parameters:
|
| - Value* value_;
|
| - Cfg* graph_;
|
| - LocationSet assigned_vars_;
|
| -};
|
| -
|
| -
|
| -// A StatementCfgBuilder maintains a CFG fragment accumulator. When it
|
| -// visits a statement, it concatenates the CFG for the statement to the end
|
| -// of the accumulator.
|
| -class StatementCfgBuilder : public AstVisitor {
|
| - public:
|
| - StatementCfgBuilder() : graph_(new Cfg()) {}
|
| -
|
| - Cfg* graph() { return graph_; }
|
| -
|
| - 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:
|
| - // State for the visitor. Input/output parameter:
|
| - Cfg* graph_;
|
| -};
|
| -
|
| -
|
| -} } // namespace v8::internal
|
| -
|
| -#endif // V8_CFG_H_
|
|
|