| // Copyright 2008 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_REGISTER_ALLOCATOR_H_ |
| #define V8_REGISTER_ALLOCATOR_H_ |
| |
| #include "macro-assembler.h" |
| |
| namespace v8 { namespace internal { |
| |
| |
| // ------------------------------------------------------------------------- |
| // StaticType |
| // |
| // StaticType represent the type of an expression or a word at runtime. |
| // The types are ordered by knowledge, so that if a value can come about |
| // in more than one way, and there are different static types inferred |
| // for the different ways, the types can be combined to a type that we |
| // are still certain of (possibly just "unknown"). |
| |
| class StaticType BASE_EMBEDDED { |
| public: |
| StaticType() : static_type_(UNKNOWN_TYPE) {} |
| |
| static StaticType unknown() { return StaticType(); } |
| static StaticType smi() { return StaticType(SMI_TYPE); } |
| static StaticType jsstring() { return StaticType(STRING_TYPE); } |
| static StaticType heap_object() { return StaticType(HEAP_OBJECT_TYPE); } |
| |
| // Accessors |
| bool is_unknown() { return static_type_ == UNKNOWN_TYPE; } |
| bool is_smi() { return static_type_ == SMI_TYPE; } |
| bool is_heap_object() { return (static_type_ & HEAP_OBJECT_TYPE) != 0; } |
| bool is_jsstring() { return static_type_ == STRING_TYPE; } |
| |
| bool operator==(StaticType other) const { |
| return static_type_ == other.static_type_; |
| } |
| |
| // Find the best approximating type for a value. |
| // The argument must not be NULL. |
| static StaticType TypeOf(Object* object) { |
| // Remember to make the most specific tests first. A string is also a heap |
| // object, so test for string-ness first. |
| if (object->IsSmi()) return smi(); |
| if (object->IsString()) return jsstring(); |
| if (object->IsHeapObject()) return heap_object(); |
| return unknown(); |
| } |
| |
| // Merges two static types to a type that combines the knowledge |
| // of both. If there is no way to combine (e.g., being a string *and* |
| // being a smi), the resulting type is unknown. |
| StaticType merge(StaticType other) { |
| StaticType x( |
| static_cast<StaticTypeEnum>(static_type_ & other.static_type_)); |
| return x; |
| } |
| |
| private: |
| enum StaticTypeEnum { |
| // Numbers are chosen so that least upper bound of the following |
| // partial order is implemented by bitwise "and": |
| // |
| // string |
| // | |
| // heap-object smi |
| // \ / |
| // unknown |
| // |
| UNKNOWN_TYPE = 0x00, |
| SMI_TYPE = 0x01, |
| HEAP_OBJECT_TYPE = 0x02, |
| STRING_TYPE = 0x04 | HEAP_OBJECT_TYPE |
| }; |
| explicit StaticType(StaticTypeEnum static_type) : static_type_(static_type) {} |
| |
| // StaticTypeEnum static_type_; |
| byte static_type_; |
| }; |
| |
| |
| // ------------------------------------------------------------------------- |
| // Results |
| // |
| // Results encapsulate the compile-time values manipulated by the code |
| // generator. They can represent registers or constants. |
| |
| class Result BASE_EMBEDDED { |
| public: |
| enum Type { |
| INVALID, |
| REGISTER, |
| CONSTANT |
| }; |
| |
| // Construct an invalid result. |
| explicit Result(CodeGenerator* cgen) |
| : static_type_(), |
| type_(INVALID), |
| cgen_(cgen) {} |
| |
| // Construct a register Result. |
| Result(Register reg, |
| CodeGenerator* cgen); |
| |
| // Construct a register Result with a known static type. |
| Result(Register reg, |
| CodeGenerator* cgen, |
| StaticType static_type); |
| |
| // Construct a Result whose value is a compile-time constant. |
| Result(Handle<Object> value, CodeGenerator * cgen) |
| : static_type_(StaticType::TypeOf(*value)), |
| type_(CONSTANT), |
| cgen_(cgen) { |
| data_.handle_ = value.location(); |
| } |
| |
| // The copy constructor and assignment operators could each create a new |
| // register reference. |
| Result(const Result& other) { |
| other.CopyTo(this); |
| } |
| |
| Result& operator=(const Result& other) { |
| if (this != &other) { |
| Unuse(); |
| other.CopyTo(this); |
| } |
| return *this; |
| } |
| |
| inline ~Result(); |
| |
| inline void Unuse(); |
| |
| StaticType static_type() const { return static_type_; } |
| void set_static_type(StaticType static_type) { static_type_ = static_type; } |
| |
| Type type() const { return static_cast<Type>(type_); } |
| |
| bool is_valid() const { return type() != INVALID; } |
| bool is_register() const { return type() == REGISTER; } |
| bool is_constant() const { return type() == CONSTANT; } |
| |
| Register reg() const { |
| ASSERT(type() == REGISTER); |
| return data_.reg_; |
| } |
| |
| Handle<Object> handle() const { |
| ASSERT(type() == CONSTANT); |
| return Handle<Object>(data_.handle_); |
| } |
| |
| // Move this result to an arbitrary register. The register is not |
| // necessarily spilled from the frame or even singly-referenced outside |
| // it. |
| void ToRegister(); |
| |
| // Move this result to a specified register. The register is spilled from |
| // the frame, and the register is singly-referenced (by this result) |
| // outside the frame. |
| void ToRegister(Register reg); |
| |
| private: |
| StaticType static_type_; |
| byte type_; |
| |
| union { |
| Register reg_; |
| Object** handle_; |
| } data_; |
| |
| CodeGenerator* cgen_; |
| |
| void CopyTo(Result* destination) const; |
| }; |
| |
| |
| // ------------------------------------------------------------------------- |
| // Register file |
| // |
| // The register file tracks reference counts for the processor registers. |
| // It is used by both the register allocator and the virtual frame. |
| |
| class RegisterFile BASE_EMBEDDED { |
| public: |
| RegisterFile() { Reset(); } |
| |
| void Reset() { |
| for (int i = 0; i < kNumRegisters; i++) { |
| ref_counts_[i] = 0; |
| } |
| } |
| |
| // Predicates and accessors for the reference counts. The versions |
| // that take a register code rather than a register are for |
| // convenience in loops over the register codes. |
| bool is_used(int reg_code) const { return ref_counts_[reg_code] > 0; } |
| bool is_used(Register reg) const { return is_used(reg.code()); } |
| int count(int reg_code) const { return ref_counts_[reg_code]; } |
| int count(Register reg) const { return count(reg.code()); } |
| |
| // Record a use of a register by incrementing its reference count. |
| void Use(Register reg) { |
| ref_counts_[reg.code()]++; |
| } |
| |
| // Record that a register will no longer be used by decrementing its |
| // reference count. |
| void Unuse(Register reg) { |
| ASSERT(!reg.is(no_reg)); |
| ASSERT(is_used(reg.code())); |
| ref_counts_[reg.code()]--; |
| } |
| |
| // Copy the reference counts from this register file to the other. |
| void CopyTo(RegisterFile* other); |
| |
| private: |
| int ref_counts_[kNumRegisters]; |
| |
| // Very fast inlined loop to find a free register. |
| // Used in RegisterAllocator::AllocateWithoutSpilling. |
| // Returns kNumRegisters if no free register found. |
| inline int ScanForFreeRegister() { |
| int i = 0; |
| for (; i < kNumRegisters ; ++i) { |
| if (ref_counts_[i] == 0) break; |
| } |
| return i; |
| } |
| |
| friend class RegisterAllocator; |
| }; |
| |
| |
| // ------------------------------------------------------------------------- |
| // Register allocator |
| // |
| |
| class RegisterAllocator BASE_EMBEDDED { |
| public: |
| explicit RegisterAllocator(CodeGenerator* cgen) : cgen_(cgen) {} |
| |
| // A register file with each of the reserved registers counted once. |
| static RegisterFile Reserved(); |
| |
| // Unuse all the reserved registers in a register file. |
| static void UnuseReserved(RegisterFile* register_file); |
| |
| // Predicates and accessors for the registers' reference counts. |
| bool is_used(int reg_code) const { return registers_.is_used(reg_code); } |
| bool is_used(Register reg) const { return registers_.is_used(reg.code()); } |
| int count(int reg_code) const { return registers_.count(reg_code); } |
| int count(Register reg) const { return registers_.count(reg.code()); } |
| |
| // Explicitly record a reference to a register. |
| void Use(Register reg) { registers_.Use(reg); } |
| |
| // Explicitly record that a register will no longer be used. |
| void Unuse(Register reg) { registers_.Unuse(reg); } |
| |
| // Initialize the register allocator for entry to a JS function. On |
| // entry, the registers used by the JS calling convention are |
| // externally referenced (ie, outside the virtual frame); and the |
| // other registers are free. |
| void Initialize(); |
| |
| // Reset the register reference counts to free all non-reserved registers. |
| // A frame-external reference is kept to each of the reserved registers. |
| void Reset(); |
| |
| // Allocate a free register and return a register result if possible or |
| // fail and return an invalid result. |
| Result Allocate(); |
| |
| // Allocate a specific register if possible, spilling it from the frame if |
| // necessary, or else fail and return an invalid result. |
| Result Allocate(Register target); |
| |
| // Allocate a free register without spilling any from the current frame or |
| // fail and return an invalid result. |
| Result AllocateWithoutSpilling(); |
| |
| // Allocate a free byte register without spilling any from the |
| // current frame or fail and return an invalid result. |
| Result AllocateByteRegisterWithoutSpilling(); |
| |
| // Copy the internal state to a register file, to be restored later by |
| // RestoreFrom. |
| void SaveTo(RegisterFile* register_file) { |
| registers_.CopyTo(register_file); |
| } |
| |
| void RestoreFrom(RegisterFile* register_file) { |
| register_file->CopyTo(®isters_); |
| } |
| |
| private: |
| CodeGenerator* cgen_; |
| RegisterFile registers_; |
| }; |
| |
| } } // namespace v8::internal |
| |
| #endif // V8_REGISTER_ALLOCATOR_H_ |