CSE2410 Fall 2014 Bounce

// 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(&registers_);

  }

 private:

  CodeGenerator* cgen_;

  RegisterFile registers_;

};

} }  // namespace v8::internal

#endif  // V8_REGISTER_ALLOCATOR_H_