1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2014 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifndef V8_REGISTER_ALLOCATOR_H_ 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define V8_REGISTER_ALLOCATOR_H_ 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/allocation.h" 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/compiler/instruction.h" 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/compiler/node.h" 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/compiler/schedule.h" 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/macro-assembler.h" 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/zone.h" 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Forward declarations. 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass BitVector; 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass InstructionOperand; 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass UnallocatedOperand; 22b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass ParallelMove; 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass PointerMap; 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace compiler { 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochenum RegisterKind { 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UNALLOCATED_REGISTERS, 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GENERAL_REGISTERS, 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DOUBLE_REGISTERS 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// This class represents a single point of a InstructionOperand's lifetime. For 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// each instruction there are exactly two lifetime positions: the beginning and 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// the end of the instruction. Lifetime positions for different instructions are 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// disjoint. 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass LifetimePosition { 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Return the lifetime position that corresponds to the beginning of 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // the instruction with the given index. 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static LifetimePosition FromInstructionIndex(int index) { 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return LifetimePosition(index * kStep); 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns a numeric representation of this lifetime position. 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int Value() const { return value_; } 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns the index of the instruction to which this lifetime position 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // corresponds. 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int InstructionIndex() const { 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsValid()); 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return value_ / kStep; 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns true if this lifetime position corresponds to the instruction 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // start. 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsInstructionStart() const { return (value_ & (kStep - 1)) == 0; } 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns the lifetime position for the start of the instruction which 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // corresponds to this lifetime position. 62b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition InstructionStart() const { 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsValid()); 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return LifetimePosition(value_ & ~(kStep - 1)); 65b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 67b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns the lifetime position for the end of the instruction which 68b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // corresponds to this lifetime position. 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition InstructionEnd() const { 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsValid()); 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return LifetimePosition(InstructionStart().Value() + kStep / 2); 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns the lifetime position for the beginning of the next instruction. 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition NextInstruction() const { 76b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsValid()); 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return LifetimePosition(InstructionStart().Value() + kStep); 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns the lifetime position for the beginning of the previous 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // instruction. 82b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition PrevInstruction() const { 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsValid()); 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(value_ > 1); 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return LifetimePosition(InstructionStart().Value() - kStep); 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 87b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Constructs the lifetime position which does not correspond to any 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // instruction. 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition() : value_(-1) {} 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns true if this lifetime positions corrensponds to some 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // instruction. 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsValid() const { return value_ != -1; } 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static inline LifetimePosition Invalid() { return LifetimePosition(); } 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static inline LifetimePosition MaxPosition() { 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // We have to use this kind of getter instead of static member due to 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // crash bug in GDB. 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return LifetimePosition(kMaxInt); 102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static const int kStep = 2; 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Code relies on kStep being a power of two. 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch STATIC_ASSERT(IS_POWER_OF_TWO(kStep)); 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit LifetimePosition(int value) : value_(value) {} 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int value_; 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Representation of the non-empty interval [start,end[. 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass UseInterval : public ZoneObject { 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UseInterval(LifetimePosition start, LifetimePosition end) 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : start_(start), end_(end), next_(NULL) { 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(start.Value() < end.Value()); 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition start() const { return start_; } 125b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end() const { return end_; } 126b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UseInterval* next() const { return next_; } 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Split this interval at the given position without effecting the 129b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // live range that owns it. The interval must contain the position. 130b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SplitAt(LifetimePosition pos, Zone* zone); 131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If this interval intersects with other return smallest position 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // that belongs to both of them. 134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition Intersect(const UseInterval* other) const { 135b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (other->start().Value() < start_.Value()) return other->Intersect(this); 136b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (other->start().Value() < end_.Value()) return other->start(); 137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return LifetimePosition::Invalid(); 138b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool Contains(LifetimePosition point) const { 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return start_.Value() <= point.Value() && point.Value() < end_.Value(); 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void set_start(LifetimePosition start) { start_ = start; } 145b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void set_next(UseInterval* next) { next_ = next; } 146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition start_; 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end_; 149b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UseInterval* next_; 150b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 151b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Representation of a use position. 153b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass UsePosition : public ZoneObject { 154b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 155b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition(LifetimePosition pos, InstructionOperand* operand, 156b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* hint); 157b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* operand() const { return operand_; } 159b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool HasOperand() const { return operand_ != NULL; } 160b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 161b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* hint() const { return hint_; } 162b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool HasHint() const; 163b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool RequiresRegister() const; 164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool RegisterIsBeneficial() const; 165b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition pos() const { return pos_; } 167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* next() const { return next_; } 168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void set_next(UsePosition* next) { next_ = next; } 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* const operand_; 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* const hint_; 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition const pos_; 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* next_; 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool requires_reg_; 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool register_beneficial_; 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Representation of SSA values' live ranges as a collection of (continuous) 180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// intervals over the instruction ordering. 181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass LiveRange : public ZoneObject { 182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static const int kInvalidAssignment = 0x7fffffff; 184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 185b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange(int id, Zone* zone); 186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 187b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UseInterval* first_interval() const { return first_interval_; } 188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* first_pos() const { return first_pos_; } 189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* parent() const { return parent_; } 190b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* TopLevel() { return (parent_ == NULL) ? this : parent_; } 191b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* next() const { return next_; } 192b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsChild() const { return parent() != NULL; } 193b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int id() const { return id_; } 194b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsFixed() const { return id_ < 0; } 195b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsEmpty() const { return first_interval() == NULL; } 196b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* CreateAssignedOperand(Zone* zone); 197b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int assigned_register() const { return assigned_register_; } 198b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int spill_start_index() const { return spill_start_index_; } 199b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void set_assigned_register(int reg, Zone* zone); 200b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void MakeSpilled(Zone* zone); 201b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool is_phi() const { return is_phi_; } 202b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void set_is_phi(bool is_phi) { is_phi_ = is_phi; } 203b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool is_non_loop_phi() const { return is_non_loop_phi_; } 204b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void set_is_non_loop_phi(bool is_non_loop_phi) { 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch is_non_loop_phi_ = is_non_loop_phi; 206b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 207b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 208b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns use position in this live range that follows both start 209b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // and last processed use position. 210b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Modifies internal state of live range! 211b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* NextUsePosition(LifetimePosition start); 212b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 213b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns use position for which register is required in this live 214b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // range and which follows both start and last processed use position 215b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Modifies internal state of live range! 216b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* NextRegisterPosition(LifetimePosition start); 217b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 218b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns use position for which register is beneficial in this live 219b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // range and which follows both start and last processed use position 220b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Modifies internal state of live range! 221b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start); 222b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 223b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns use position for which register is beneficial in this live 224b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // range and which precedes start. 225b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* PreviousUsePositionRegisterIsBeneficial(LifetimePosition start); 226b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 227b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Can this live range be spilled at this position. 228b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool CanBeSpilled(LifetimePosition pos); 229b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 230b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Split this live range at the given position which must follow the start of 231b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // the range. 232b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // All uses following the given position will be moved from this 233b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // live range to the result live range. 234b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone); 235b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 236b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterKind Kind() const { return kind_; } 237b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool HasRegisterAssigned() const { 238b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return assigned_register_ != kInvalidAssignment; 239b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 240b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsSpilled() const { return spilled_; } 241b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 242b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* current_hint_operand() const { 243b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(current_hint_operand_ == FirstHint()); 244b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return current_hint_operand_; 245b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 246b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* FirstHint() const { 247b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* pos = first_pos_; 248b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (pos != NULL && !pos->HasHint()) pos = pos->next(); 249b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (pos != NULL) return pos->hint(); 250b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return NULL; 251b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 252b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 253b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition Start() const { 254b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsEmpty()); 255b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return first_interval()->start(); 256b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 257b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 258b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition End() const { 259b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsEmpty()); 260b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return last_interval_->end(); 261b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 262b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 263b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool HasAllocatedSpillOperand() const; 264b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* GetSpillOperand() const { return spill_operand_; } 265b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SetSpillOperand(InstructionOperand* operand); 266b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 267b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SetSpillStartIndex(int start) { 268b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch spill_start_index_ = Min(start, spill_start_index_); 269b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 270b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 271b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool ShouldBeAllocatedBefore(const LiveRange* other) const; 272b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool CanCover(LifetimePosition position) const; 273b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool Covers(LifetimePosition position); 274b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition FirstIntersection(LiveRange* other); 275b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 276b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Add a new interval or a new use position to this live range. 277b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); 278b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); 279b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AddUsePosition(LifetimePosition pos, InstructionOperand* operand, 280b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* hint, Zone* zone); 281b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 282b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Shorten the most recently added interval by setting a new start. 283b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ShortenTo(LifetimePosition start); 284b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 285b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifdef DEBUG 286b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // True if target overlaps an existing interval. 287b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool HasOverlap(UseInterval* target) const; 288b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Verify() const; 289b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 290b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 291b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 292b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ConvertOperands(Zone* zone); 293b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; 294b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AdvanceLastProcessedMarker(UseInterval* to_start_of, 295b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition but_not_past) const; 296b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 297b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int id_; 298b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool spilled_; 299b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool is_phi_; 300b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool is_non_loop_phi_; 301b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterKind kind_; 302b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int assigned_register_; 303b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UseInterval* last_interval_; 304b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UseInterval* first_interval_; 305b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* first_pos_; 306b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* parent_; 307b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* next_; 308b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This is used as a cache, it doesn't affect correctness. 309b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch mutable UseInterval* current_interval_; 310b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* last_processed_use_; 311b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This is used as a cache, it's invalid outside of BuildLiveRanges. 312b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* current_hint_operand_; 313b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* spill_operand_; 314b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int spill_start_index_; 315b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 316b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch friend class RegisterAllocator; // Assigns to kind_. 317b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 318b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 319b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 320b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass RegisterAllocator BASE_EMBEDDED { 321b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 322b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit RegisterAllocator(InstructionSequence* code); 323b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 324b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static void TraceAlloc(const char* msg, ...); 325b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 326b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Checks whether the value of a given virtual register is a reference. 327b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // TODO(titzer): rename this to IsReference. 328b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool HasTaggedValue(int virtual_register) const; 329b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 330b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns the register kind required by the given virtual register. 331b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterKind RequiredRegisterKind(int virtual_register) const; 332b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 333b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool Allocate(); 334b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 335b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; } 336b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const Vector<LiveRange*>* fixed_live_ranges() const { 337b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return &fixed_live_ranges_; 338b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 339b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const Vector<LiveRange*>* fixed_double_live_ranges() const { 340b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return &fixed_double_live_ranges_; 341b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 342b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 343b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inline InstructionSequence* code() const { return code_; } 344b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 345b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This zone is for datastructures only needed during register allocation. 346b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inline Zone* zone() { return &zone_; } 347b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 348b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This zone is for InstructionOperands and moves that live beyond register 349b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // allocation. 350b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inline Zone* code_zone() { return code()->zone(); } 351b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 352b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int GetVirtualRegister() { 353b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int vreg = code()->NextVirtualRegister(); 354b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) { 355b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocation_ok_ = false; 356b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Maintain the invariant that we return something below the maximum. 357b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return 0; 358b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 359b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return vreg; 360b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 361b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 362b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool AllocationOk() { return allocation_ok_; } 363b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 364b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifdef DEBUG 365b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Verify() const; 366b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 367b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 368b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BitVector* assigned_registers() { return assigned_registers_; } 369b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BitVector* assigned_double_registers() { return assigned_double_registers_; } 370b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 371b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 372b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void MeetRegisterConstraints(); 373b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ResolvePhis(); 374b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void BuildLiveRanges(); 375b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AllocateGeneralRegisters(); 376b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AllocateDoubleRegisters(); 377b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ConnectRanges(); 378b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ResolveControlFlow(); 379b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void PopulatePointerMaps(); // TODO(titzer): rename to PopulateReferenceMaps. 380b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AllocateRegisters(); 381b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool CanEagerlyResolveControlFlow(BasicBlock* block) const; 382b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inline bool SafePointsAreInOrder() const; 383b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 384b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Liveness analysis support. 385b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void InitializeLivenessAnalysis(); 386b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BitVector* ComputeLiveOut(BasicBlock* block); 387b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AddInitialIntervals(BasicBlock* block, BitVector* live_out); 388b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsOutputRegisterOf(Instruction* instr, int index); 389b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsOutputDoubleRegisterOf(Instruction* instr, int index); 390b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ProcessInstructions(BasicBlock* block, BitVector* live); 391b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void MeetRegisterConstraints(BasicBlock* block); 392b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void MeetConstraintsBetween(Instruction* first, Instruction* second, 393b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int gap_index); 394b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void MeetRegisterConstraintsForLastInstructionInBlock(BasicBlock* block); 395b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ResolvePhis(BasicBlock* block); 396b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 397b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Helper methods for building intervals. 398b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos, 399b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool is_tagged); 400b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* LiveRangeFor(InstructionOperand* operand); 401b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Define(LifetimePosition position, InstructionOperand* operand, 402b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* hint); 403b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Use(LifetimePosition block_start, LifetimePosition position, 404b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* operand, InstructionOperand* hint); 405b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AddConstraintsGapMove(int index, InstructionOperand* from, 406b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* to); 407b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 408b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Helper methods for updating the life range lists. 409b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AddToActive(LiveRange* range); 410b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AddToInactive(LiveRange* range); 411b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AddToUnhandledSorted(LiveRange* range); 412b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AddToUnhandledUnsorted(LiveRange* range); 413b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SortUnhandled(); 414b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool UnhandledIsSorted(); 415b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ActiveToHandled(LiveRange* range); 416b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ActiveToInactive(LiveRange* range); 417b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void InactiveToHandled(LiveRange* range); 418b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void InactiveToActive(LiveRange* range); 419b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void FreeSpillSlot(LiveRange* range); 420b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* TryReuseSpillSlot(LiveRange* range); 421b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 422b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Helper methods for allocating registers. 423b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool TryAllocateFreeReg(LiveRange* range); 424b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AllocateBlockedReg(LiveRange* range); 425b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 426b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Live range splitting helpers. 427b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 428b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Split the given range at the given position. 429b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If range starts at or after the given position then the 430b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // original range is returned. 431b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Otherwise returns the live range that starts at pos and contains 432b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // all uses from the original range that follow pos. Uses at pos will 433b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // still be owned by the original range after splitting. 434b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); 435b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 436b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Split the given range in a position from the interval [start, end]. 437b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* SplitBetween(LiveRange* range, LifetimePosition start, 438b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end); 439b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 440b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Find a lifetime position in the interval [start, end] which 441b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // is optimal for splitting: it is either header of the outermost 442b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // loop covered by this interval or the latest possible position. 443b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition FindOptimalSplitPos(LifetimePosition start, 444b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end); 445b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 446b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Spill the given life range after position pos. 447b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SpillAfter(LiveRange* range, LifetimePosition pos); 448b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 449b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Spill the given life range after position [start] and up to position [end]. 450b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SpillBetween(LiveRange* range, LifetimePosition start, 451b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end); 452b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 453b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Spill the given life range after position [start] and up to position [end]. 454b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Range is guaranteed to be spilled at least until position [until]. 455b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SpillBetweenUntil(LiveRange* range, LifetimePosition start, 456b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition until, LifetimePosition end); 457b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 458b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SplitAndSpillIntersecting(LiveRange* range); 459b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 460b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If we are trying to spill a range inside the loop try to 461b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // hoist spill position out to the point just before the loop. 462b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition FindOptimalSpillingPos(LiveRange* range, 463b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition pos); 464b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 465b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Spill(LiveRange* range); 466b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsBlockBoundary(LifetimePosition pos); 467b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 468b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Helper methods for resolving control flow. 469b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ResolveControlFlow(LiveRange* range, BasicBlock* block, 470b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BasicBlock* pred); 471b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 472b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inline void SetLiveRangeAssignedRegister(LiveRange* range, int reg); 473b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 474b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Return parallel move that should be used to connect ranges split at the 475b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // given position. 476b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ParallelMove* GetConnectingParallelMove(LifetimePosition pos); 477b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 478b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Return the block which contains give lifetime position. 479b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BasicBlock* GetBlock(LifetimePosition pos); 480b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 481b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Helper methods for the fixed registers. 482b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int RegisterCount() const; 483b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static int FixedLiveRangeID(int index) { return -index - 1; } 484b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static int FixedDoubleLiveRangeID(int index); 485b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* FixedLiveRangeFor(int index); 486b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* FixedDoubleLiveRangeFor(int index); 487b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* LiveRangeFor(int index); 488b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GapInstruction* GetLastGap(BasicBlock* block); 489b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 490b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const char* RegisterName(int allocation_index); 491b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 492b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inline Instruction* InstructionAt(int index) { 493b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return code()->InstructionAt(index); 494b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 495b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 496b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone zone_; 497b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionSequence* code_; 498b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 499b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // During liveness analysis keep a mapping from block id to live_in sets 500b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // for blocks already analyzed. 501b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ZoneList<BitVector*> live_in_sets_; 502b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 503b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Liveness analysis results. 504b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ZoneList<LiveRange*> live_ranges_; 505b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 506b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Lists of live ranges 507b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters> 508b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch fixed_live_ranges_; 509b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters> 510b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch fixed_double_live_ranges_; 511b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ZoneList<LiveRange*> unhandled_live_ranges_; 512b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ZoneList<LiveRange*> active_live_ranges_; 513b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ZoneList<LiveRange*> inactive_live_ranges_; 514b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ZoneList<LiveRange*> reusable_slots_; 515b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 516b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterKind mode_; 517b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int num_registers_; 518b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 519b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BitVector* assigned_registers_; 520b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BitVector* assigned_double_registers_; 521b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 522b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Indicates success or failure during register allocation. 523b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool allocation_ok_; 524b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 525b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifdef DEBUG 526b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition allocation_finger_; 527b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 528b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 529b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); 530b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 531b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 532b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 533b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass RegisterAllocatorPhase : public CompilationPhase { 534b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 535b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterAllocatorPhase(const char* name, RegisterAllocator* allocator); 536b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ~RegisterAllocatorPhase(); 537b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 538b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 539b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterAllocator* allocator_; 540b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unsigned allocator_zone_start_allocation_size_; 541b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 542b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorPhase); 543b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 544b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 545b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 546b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace v8::internal::compiler 547b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 548b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif // V8_REGISTER_ALLOCATOR_H_ 549