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/compiler/instruction.h" 9014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/ostreams.h" 10014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/register-configuration.h" 11958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include "src/zone-containers.h" 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace compiler { 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochenum RegisterKind { 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GENERAL_REGISTERS, 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DOUBLE_REGISTERS 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 22b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// This class represents a single point of a InstructionOperand's lifetime. For 24014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// each instruction there are four lifetime positions: 25014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// 26014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// [[START, END], [START, END]] 27014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// 28014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Where the first half position corresponds to 29014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// 30014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// [GapPosition::START, GapPosition::END] 31014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// 32014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// and the second half position corresponds to 33014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// 34014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// [Lifetime::USED_AT_START, Lifetime::USED_AT_END] 35014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// 36014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass LifetimePosition final { 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Return the lifetime position that corresponds to the beginning of 39014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // the gap with the given index. 40014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static LifetimePosition GapFromInstructionIndex(int index) { 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return LifetimePosition(index * kStep); 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 43014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Return the lifetime position that corresponds to the beginning of 44014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // the instruction with the given index. 45014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static LifetimePosition InstructionFromInstructionIndex(int index) { 46014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return LifetimePosition(index * kStep + kHalfStep); 47014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns a numeric representation of this lifetime position. 50014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int value() const { return value_; } 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns the index of the instruction to which this lifetime position 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // corresponds. 54014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int ToInstructionIndex() const { 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsValid()); 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return value_ / kStep; 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 59014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns true if this lifetime position corresponds to a START value 60014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsStart() const { return (value_ & (kHalfStep - 1)) == 0; } 61014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns true if this lifetime position corresponds to an END value 62014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsEnd() const { return (value_ & (kHalfStep - 1)) == 1; } 63014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns true if this lifetime position corresponds to a gap START value 64014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsFullStart() const { return (value_ & (kStep - 1)) == 0; } 65014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 66014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsGapPosition() const { return (value_ & 0x2) == 0; } 67014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsInstructionPosition() const { return !IsGapPosition(); } 68014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 69014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns the lifetime position for the current START. 70014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition Start() const { 71014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(IsValid()); 72014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return LifetimePosition(value_ & ~(kHalfStep - 1)); 73014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 75014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns the lifetime position for the current gap START. 76014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition FullStart() const { 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsValid()); 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return LifetimePosition(value_ & ~(kStep - 1)); 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 81014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns the lifetime position for the current END. 82014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition End() const { 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsValid()); 84014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return LifetimePosition(Start().value_ + kHalfStep / 2); 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 87014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns the lifetime position for the beginning of the next START. 88014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition NextStart() const { 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsValid()); 90014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return LifetimePosition(Start().value_ + kHalfStep); 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 93014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns the lifetime position for the beginning of the next gap START. 94014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition NextFullStart() const { 95014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(IsValid()); 96014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return LifetimePosition(FullStart().value_ + kStep); 97014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 98014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 99014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns the lifetime position for the beginning of the previous START. 100014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition PrevStart() const { 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsValid()); 102014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(value_ >= kHalfStep); 103014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return LifetimePosition(Start().value_ - kHalfStep); 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Constructs the lifetime position which does not correspond to any 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // instruction. 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition() : value_(-1) {} 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns true if this lifetime positions corrensponds to some 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // instruction. 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsValid() const { return value_ != -1; } 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 114014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator<(const LifetimePosition& that) const { 115014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return this->value_ < that.value_; 116014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 117014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 118014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator<=(const LifetimePosition& that) const { 119014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return this->value_ <= that.value_; 120014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 121014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 122014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator==(const LifetimePosition& that) const { 123014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return this->value_ == that.value_; 124014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 125014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 126014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator!=(const LifetimePosition& that) const { 127014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return this->value_ != that.value_; 128014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 129014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 130014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator>(const LifetimePosition& that) const { 131014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return this->value_ > that.value_; 132014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 133014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 134014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator>=(const LifetimePosition& that) const { 135014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return this->value_ >= that.value_; 136014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 137014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 138014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Print() const; 139014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static inline LifetimePosition Invalid() { return LifetimePosition(); } 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static inline LifetimePosition MaxPosition() { 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // We have to use this kind of getter instead of static member due to 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // crash bug in GDB. 145b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return LifetimePosition(kMaxInt); 146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 148014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static inline LifetimePosition FromInt(int value) { 149014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return LifetimePosition(value); 150014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 151014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 153014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static const int kHalfStep = 2; 154014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static const int kStep = 2 * kHalfStep; 155b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 156014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Code relies on kStep and kHalfStep being a power of two. 157014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch STATIC_ASSERT(IS_POWER_OF_TWO(kHalfStep)); 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 159b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit LifetimePosition(int value) : value_(value) {} 160b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 161b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int value_; 162b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 163b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 165014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstd::ostream& operator<<(std::ostream& os, const LifetimePosition pos); 166014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 167014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Representation of the non-empty interval [start,end[. 169014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass UseInterval final : public ZoneObject { 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UseInterval(LifetimePosition start, LifetimePosition end) 172958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : start_(start), end_(end), next_(nullptr) { 173014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(start < end); 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition start() const { return start_; } 177014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_start(LifetimePosition start) { start_ = start; } 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end() const { return end_; } 179014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_end(LifetimePosition end) { end_ = end; } 180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UseInterval* next() const { return next_; } 181014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_next(UseInterval* next) { next_ = next; } 182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Split this interval at the given position without effecting the 184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // live range that owns it. The interval must contain the position. 185014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UseInterval* SplitAt(LifetimePosition pos, Zone* zone); 186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 187b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If this interval intersects with other return smallest position 188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // that belongs to both of them. 189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition Intersect(const UseInterval* other) const { 190014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (other->start() < start_) return other->Intersect(this); 191014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (other->start() < end_) return other->start(); 192b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return LifetimePosition::Invalid(); 193b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 194b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 195b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool Contains(LifetimePosition point) const { 196014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return start_ <= point && point < end_; 197b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 198b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 199014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns the index of the first gap covered by this interval. 200014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int FirstGapIndex() const { 201014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int ret = start_.ToInstructionIndex(); 202014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (start_.IsInstructionPosition()) { 203014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ++ret; 204014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 205014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return ret; 206014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 207b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 208014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns the index of the last gap covered by this interval. 209014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int LastGapIndex() const { 210014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int ret = end_.ToInstructionIndex(); 211014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (end_.IsGapPosition() && end_.IsStart()) { 212014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch --ret; 213014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 214014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return ret; 215014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 216014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 217014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 218b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition start_; 219b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end_; 220b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UseInterval* next_; 221958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 222958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DISALLOW_COPY_AND_ASSIGN(UseInterval); 223b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 224b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 225958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 226014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochenum class UsePositionType : uint8_t { kAny, kRequiresRegister, kRequiresSlot }; 227014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 228014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 229014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochenum class UsePositionHintType : uint8_t { 230014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kNone, 231014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kOperand, 232014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kUsePos, 233014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kPhi, 234014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kUnresolved 235014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 236014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 237014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 238014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstatic const int32_t kUnassignedRegister = 239014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterConfiguration::kMaxGeneralRegisters; 240014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 241014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 242014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstatic_assert(kUnassignedRegister <= RegisterConfiguration::kMaxDoubleRegisters, 243014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch "kUnassignedRegister too small"); 244014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 245014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 246b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Representation of a use position. 247014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass UsePosition final : public ZoneObject { 248b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 249014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition(LifetimePosition pos, InstructionOperand* operand, void* hint, 250014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePositionHintType hint_type); 251b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 252b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* operand() const { return operand_; } 253958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool HasOperand() const { return operand_ != nullptr; } 254b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 255014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool RegisterIsBeneficial() const { 256014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return RegisterBeneficialField::decode(flags_); 257014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 258014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePositionType type() const { return TypeField::decode(flags_); } 259014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_type(UsePositionType type, bool register_beneficial); 260b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 261b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition pos() const { return pos_; } 262b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 263014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* next() const { return next_; } 264b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void set_next(UsePosition* next) { next_ = next; } 265b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 266014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // For hinting only. 267014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_assigned_register(int register_code) { 268014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch flags_ = AssignedRegisterField::update(flags_, register_code); 269014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 270014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 271014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePositionHintType hint_type() const { 272014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return HintTypeField::decode(flags_); 273014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 274014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool HasHint() const; 275014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool HintRegister(int* register_code) const; 276014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ResolveHint(UsePosition* use_pos); 277014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsResolved() const { 278014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return hint_type() != UsePositionHintType::kUnresolved; 279014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 280014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static UsePositionHintType HintTypeForOperand(const InstructionOperand& op); 281014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 282014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 283014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<UsePositionType, 0, 2> TypeField; 284014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<UsePositionHintType, 2, 3> HintTypeField; 285014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<bool, 5, 1> RegisterBeneficialField; 286014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<int32_t, 6, 6> AssignedRegisterField; 287014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 288b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstructionOperand* const operand_; 289014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void* hint_; 290b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* next_; 291014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition const pos_; 292014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch uint32_t flags_; 293958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 294958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DISALLOW_COPY_AND_ASSIGN(UsePosition); 295b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 296b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 297014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 298958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass SpillRange; 299014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass RegisterAllocationData; 300014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass TopLevelLiveRange; 301014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass LiveRangeGroup; 302958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 303b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Representation of SSA values' live ranges as a collection of (continuous) 304b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// intervals over the instruction ordering. 305014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass LiveRange : public ZoneObject { 306b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 307b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UseInterval* first_interval() const { return first_interval_; } 308b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* first_pos() const { return first_pos_; } 309014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* TopLevel() { return top_level_; } 310014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const TopLevelLiveRange* TopLevel() const { return top_level_; } 311014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 312014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsTopLevel() const; 313014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 314b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* next() const { return next_; } 315014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 316014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int relative_id() const { return relative_id_; } 317014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 318958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool IsEmpty() const { return first_interval() == nullptr; } 319014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 320014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionOperand GetAssignedOperand() const; 321014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 322014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch MachineRepresentation representation() const { 323014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return RepresentationField::decode(bits_); 324014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 325014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 326014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int assigned_register() const { return AssignedRegisterField::decode(bits_); } 327014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool HasRegisterAssigned() const { 328014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return assigned_register() != kUnassignedRegister; 329b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 330014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_assigned_register(int reg); 331014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void UnsetAssignedRegister(); 332014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 333014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool spilled() const { return SpilledField::decode(bits_); } 334014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Spill(); 335014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 336014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterKind kind() const; 337b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 338b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns use position in this live range that follows both start 339b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // and last processed use position. 340014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* NextUsePosition(LifetimePosition start) const; 341b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 342b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns use position for which register is required in this live 343b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // range and which follows both start and last processed use position 344014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* NextRegisterPosition(LifetimePosition start) const; 345014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 346014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns the first use position requiring stack slot, or nullptr. 347014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* NextSlotPosition(LifetimePosition start) const; 348b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 349b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns use position for which register is beneficial in this live 350b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // range and which follows both start and last processed use position 351014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* NextUsePositionRegisterIsBeneficial( 352014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition start) const; 353b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 354b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns use position for which register is beneficial in this live 355b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // range and which precedes start. 356014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* PreviousUsePositionRegisterIsBeneficial( 357014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition start) const; 358b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 359b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Can this live range be spilled at this position. 360014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool CanBeSpilled(LifetimePosition pos) const; 361b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 362014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Splitting primitive used by both splitting and splintering members. 363014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Performs the split, but does not link the resulting ranges. 364014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // The given position must follow the start of the range. 365b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // All uses following the given position will be moved from this 366b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // live range to the result live range. 367014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // The current range will terminate at position, while result will start from 368014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // position. 369014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* DetachAt(LifetimePosition position, LiveRange* result, 370014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* zone); 371014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 372014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Detaches at position, and then links the resulting ranges. Returns the 373014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // child, which starts at position. 374014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LiveRange* SplitAt(LifetimePosition position, Zone* zone); 375014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 376014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns nullptr when no register is hinted, otherwise sets register_index. 377014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* FirstHintPosition(int* register_index) const; 378014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* FirstHintPosition() const { 379014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int register_index; 380014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return FirstHintPosition(®ister_index); 381b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 382b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 383014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* current_hint_position() const { 384014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(current_hint_position_ == FirstHintPosition()); 385014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return current_hint_position_; 386b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 387b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 388b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition Start() const { 389b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsEmpty()); 390b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return first_interval()->start(); 391b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 392b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 393b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition End() const { 394b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsEmpty()); 395b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return last_interval_->end(); 396b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 397b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 398014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool ShouldBeAllocatedBefore(const LiveRange* other) const; 399014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool CanCover(LifetimePosition position) const; 400014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool Covers(LifetimePosition position) const; 401014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition FirstIntersection(LiveRange* other) const; 402014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 403014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void VerifyChildStructure() const { 404014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch VerifyIntervals(); 405014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch VerifyPositions(); 406014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 407014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 408014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ConvertUsesToOperand(const InstructionOperand& op, 409014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const InstructionOperand& spill_op); 410014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void SetUseHints(int register_index); 411014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void UnsetUseHints() { SetUseHints(kUnassignedRegister); } 412014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 413014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Used solely by the Greedy Allocator: 414014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch unsigned GetSize(); 415014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch float weight() const { return weight_; } 416014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_weight(float weight) { weight_ = weight; } 417014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LiveRangeGroup* group() const { return group_; } 418014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_group(LiveRangeGroup* group) { group_ = group; } 419014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Print(const RegisterConfiguration* config, bool with_children) const; 420014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Print(bool with_children) const; 421014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 422014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static const int kInvalidSize = -1; 423014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static const float kInvalidWeight; 424014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static const float kMaxWeight; 425014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 426014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 427014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch friend class TopLevelLiveRange; 428014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit LiveRange(int relative_id, MachineRepresentation rep, 429014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* top_level); 430014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 431014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void UpdateParentForAllChildren(TopLevelLiveRange* new_top_level); 432014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 433014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_spilled(bool value) { bits_ = SpilledField::update(bits_, value); } 434014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 435014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; 436014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AdvanceLastProcessedMarker(UseInterval* to_start_of, 437014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition but_not_past) const; 438014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 439014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void VerifyPositions() const; 440014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void VerifyIntervals() const; 441014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 442014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<bool, 0, 1> SpilledField; 443014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<int32_t, 6, 6> AssignedRegisterField; 444014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<MachineRepresentation, 12, 8> RepresentationField; 445014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 446014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Unique among children and splinters of the same virtual register. 447014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int relative_id_; 448014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch uint32_t bits_; 449014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UseInterval* last_interval_; 450014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UseInterval* first_interval_; 451014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* first_pos_; 452014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* top_level_; 453014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LiveRange* next_; 454014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // This is used as a cache, it doesn't affect correctness. 455014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch mutable UseInterval* current_interval_; 456014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // This is used as a cache, it doesn't affect correctness. 457014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch mutable UsePosition* last_processed_use_; 458014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // This is used as a cache, it's invalid outside of BuildLiveRanges. 459014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch mutable UsePosition* current_hint_position_; 460014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Cache the last position splintering stopped at. 461014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch mutable UsePosition* splitting_pointer_; 462014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // greedy: the number of LifetimePositions covered by this range. Used to 463014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // prioritize selecting live ranges for register assignment, as well as 464014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // in weight calculations. 465014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int size_; 466014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 467014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // greedy: a metric for resolving conflicts between ranges with an assigned 468014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // register and ranges that intersect them and need a register. 469014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch float weight_; 470014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 471014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // greedy: groupping 472014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LiveRangeGroup* group_; 473014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 474014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(LiveRange); 475014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 476014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 477014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 478014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass LiveRangeGroup final : public ZoneObject { 479014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 480014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit LiveRangeGroup(Zone* zone) : ranges_(zone) {} 481014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<LiveRange*>& ranges() { return ranges_; } 482014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const ZoneVector<LiveRange*>& ranges() const { return ranges_; } 483014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 484014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // TODO(mtrofin): populate assigned register and use in weight calculation. 485014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int assigned_register() const { return assigned_register_; } 486014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_assigned_register(int reg) { assigned_register_ = reg; } 487014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 488014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 489014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<LiveRange*> ranges_; 490014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int assigned_register_; 491014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(LiveRangeGroup); 492014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 493014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 494014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 495014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass TopLevelLiveRange final : public LiveRange { 496014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 497014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit TopLevelLiveRange(int vreg, MachineRepresentation rep); 498014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int spill_start_index() const { return spill_start_index_; } 499014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 500014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsFixed() const { return vreg_ < 0; } 501014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 502014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool is_phi() const { return IsPhiField::decode(bits_); } 503014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_is_phi(bool value) { bits_ = IsPhiField::update(bits_, value); } 504014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 505014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool is_non_loop_phi() const { return IsNonLoopPhiField::decode(bits_); } 506014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_is_non_loop_phi(bool value) { 507014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bits_ = IsNonLoopPhiField::update(bits_, value); 508014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 509014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 510014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool has_slot_use() const { return HasSlotUseField::decode(bits_); } 511014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_has_slot_use(bool value) { 512014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bits_ = HasSlotUseField::update(bits_, value); 513014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 514014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 515014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Add a new interval or a new use position to this live range. 516014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); 517014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); 518014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddUsePosition(UsePosition* pos); 519014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 520014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Shorten the most recently added interval by setting a new start. 521014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ShortenTo(LifetimePosition start); 522014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 523014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Detaches between start and end, and attributes the resulting range to 524014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // result. 525014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // The current range is pointed to as "splintered_from". No parent/child 526014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // relationship is established between this and result. 527014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Splinter(LifetimePosition start, LifetimePosition end, Zone* zone); 528014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 529014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Assuming other was splintered from this range, embeds other and its 530014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // children as part of the children sequence of this range. 531014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Merge(TopLevelLiveRange* other, Zone* zone); 532014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 533014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Spill range management. 534014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void SetSpillRange(SpillRange* spill_range); 535958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier enum class SpillType { kNoSpillType, kSpillOperand, kSpillRange }; 536014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_spill_type(SpillType value) { 537014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bits_ = SpillTypeField::update(bits_, value); 538014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 539014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SpillType spill_type() const { return SpillTypeField::decode(bits_); } 540958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier InstructionOperand* GetSpillOperand() const { 541014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(spill_type() == SpillType::kSpillOperand); 542014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return spill_operand_; 543014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 544014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 545014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SpillRange* GetAllocatedSpillRange() const { 546014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(spill_type() != SpillType::kSpillOperand); 547014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return spill_range_; 548958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 549014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 550958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SpillRange* GetSpillRange() const { 551014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(spill_type() == SpillType::kSpillRange); 552014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return spill_range_; 553014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 554014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool HasNoSpillType() const { 555014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return spill_type() == SpillType::kNoSpillType; 556958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 557958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool HasSpillOperand() const { 558014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return spill_type() == SpillType::kSpillOperand; 559958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 560014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool HasSpillRange() const { return spill_type() == SpillType::kSpillRange; } 561958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 562014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch AllocatedOperand GetSpillRangeOperand() const; 563b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 564014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void RecordSpillLocation(Zone* zone, int gap_index, 565014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionOperand* operand); 566014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void SetSpillOperand(InstructionOperand* operand); 567b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SetSpillStartIndex(int start) { 568b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch spill_start_index_ = Min(start, spill_start_index_); 569b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 570b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 571014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void CommitSpillMoves(InstructionSequence* sequence, 572014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const InstructionOperand& operand, 573014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool might_be_duplicated); 574014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 575014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // If all the children of this range are spilled in deferred blocks, and if 576014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // for any non-spilled child with a use position requiring a slot, that range 577014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // is contained in a deferred block, mark the range as 578014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // IsSpilledOnlyInDeferredBlocks, so that we avoid spilling at definition, 579014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // and instead let the LiveRangeConnector perform the spills within the 580014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // deferred blocks. If so, we insert here spills for non-spilled ranges 581014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // with slot use positions. 582014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void MarkSpilledInDeferredBlock() { 583014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch spill_start_index_ = -1; 584014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch spilled_in_deferred_blocks_ = true; 585014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch spill_move_insertion_locations_ = nullptr; 586014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 587b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 588014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool TryCommitSpillInDeferredBlock(InstructionSequence* code, 589014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const InstructionOperand& spill_operand); 590b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 591014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* splintered_from() const { return splintered_from_; } 592014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsSplinter() const { return splintered_from_ != nullptr; } 593014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool MayRequireSpillRange() const { 594014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(!IsSplinter()); 595014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return !HasSpillOperand() && spill_range_ == nullptr; 596014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 597014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void UpdateSpillRangePostMerge(TopLevelLiveRange* merged); 598014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int vreg() const { return vreg_; } 599b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 600014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#if DEBUG 601014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int debug_virt_reg() const; 602b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 603b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 604014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Verify() const; 605014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void VerifyChildrenInOrder() const; 606014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 607014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int GetNextChildId() { 608014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return IsSplinter() ? splintered_from()->GetNextChildId() 609014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : ++last_child_id_; 610014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 611014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 612014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int GetChildCount() const { return last_child_id_ + 1; } 613014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 614014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsSpilledOnlyInDeferredBlocks() const { 615014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return spilled_in_deferred_blocks_; 616014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 617014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 618014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch struct SpillMoveInsertionList; 619014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 620014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SpillMoveInsertionList* spill_move_insertion_locations() const { 621014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return spill_move_insertion_locations_; 622014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 623014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* splinter() const { return splinter_; } 624014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void SetSplinter(TopLevelLiveRange* splinter) { 625014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_NULL(splinter_); 626014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_NOT_NULL(splinter); 627014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 628014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch splinter_ = splinter; 629014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch splinter->relative_id_ = GetNextChildId(); 630014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch splinter->set_spill_type(spill_type()); 631014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch splinter->SetSplinteredFrom(this); 632014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 633014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 634014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void MarkHasPreassignedSlot() { has_preassigned_slot_ = true; } 635014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool has_preassigned_slot() const { return has_preassigned_slot_; } 636014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 637b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 638014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void SetSplinteredFrom(TopLevelLiveRange* splinter_parent); 639958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 640014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<bool, 1, 1> HasSlotUseField; 641014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<bool, 2, 1> IsPhiField; 642014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<bool, 3, 1> IsNonLoopPhiField; 643014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<SpillType, 4, 2> SpillTypeField; 644b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 645014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int vreg_; 646014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int last_child_id_; 647014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* splintered_from_; 648958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier union { 649014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Correct value determined by spill_type() 650958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier InstructionOperand* spill_operand_; 651958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SpillRange* spill_range_; 652958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier }; 653014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SpillMoveInsertionList* spill_move_insertion_locations_; 654014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // TODO(mtrofin): generalize spilling after definition, currently specialized 655014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // just for spill in a single deferred block. 656014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool spilled_in_deferred_blocks_; 657014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int spill_start_index_; 658014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* last_pos_; 659014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* splinter_; 660014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool has_preassigned_slot_; 661b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 662014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(TopLevelLiveRange); 663014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 664958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 665014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 666014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstruct PrintableLiveRange { 667014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const RegisterConfiguration* register_configuration_; 668014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const LiveRange* range_; 669b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 670b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 671b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 672014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstd::ostream& operator<<(std::ostream& os, 673014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const PrintableLiveRange& printable_range); 674014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 675014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 676014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass SpillRange final : public ZoneObject { 677b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 678014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static const int kUnassignedSlot = -1; 679014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SpillRange(TopLevelLiveRange* range, Zone* zone); 680b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 681958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier UseInterval* interval() const { return use_interval_; } 682014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Currently, only 4 or 8 byte slots are supported. 683014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int ByteWidth() const; 684958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool IsEmpty() const { return live_ranges_.empty(); } 685958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool TryMerge(SpillRange* other); 686014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool HasSlot() const { return assigned_slot_ != kUnassignedSlot; } 687014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 688014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_assigned_slot(int index) { 689014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(kUnassignedSlot, assigned_slot_); 690014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch assigned_slot_ = index; 691014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 692014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int assigned_slot() { 693014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_NE(kUnassignedSlot, assigned_slot_); 694014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return assigned_slot_; 695014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 696014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const ZoneVector<TopLevelLiveRange*>& live_ranges() const { 697014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return live_ranges_; 698014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 699014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<TopLevelLiveRange*>& live_ranges() { return live_ranges_; } 700014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int byte_width() const { return byte_width_; } 701014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterKind kind() const { return kind_; } 702014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Print() const; 703b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 704958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 705958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier LifetimePosition End() const { return end_position_; } 706958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool IsIntersectingWith(SpillRange* other) const; 707958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Merge intervals, making sure the use intervals are sorted 708958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void MergeDisjointIntervals(UseInterval* other); 709b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 710014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<TopLevelLiveRange*> live_ranges_; 711958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier UseInterval* use_interval_; 712958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier LifetimePosition end_position_; 713014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int assigned_slot_; 714014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int byte_width_; 715014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterKind kind_; 716958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 717958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DISALLOW_COPY_AND_ASSIGN(SpillRange); 718958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier}; 719958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 720958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 721014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass RegisterAllocationData final : public ZoneObject { 722958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 723014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch class PhiMapValue : public ZoneObject { 724014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 725014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone); 726014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 727014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const PhiInstruction* phi() const { return phi_; } 728014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const InstructionBlock* block() const { return block_; } 729014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 730014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // For hinting. 731014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int assigned_register() const { return assigned_register_; } 732014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_assigned_register(int register_code) { 733014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(assigned_register_, kUnassignedRegister); 734014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch assigned_register_ = register_code; 735014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 736014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void UnsetAssignedRegister() { assigned_register_ = kUnassignedRegister; } 737b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 738014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddOperand(InstructionOperand* operand); 739014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void CommitAssignment(const InstructionOperand& operand); 740b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 741014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 742014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PhiInstruction* const phi_; 743014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const InstructionBlock* const block_; 744014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<InstructionOperand*> incoming_operands_; 745014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int assigned_register_; 746014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch }; 747014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef ZoneMap<int, PhiMapValue*> PhiMap; 748014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 749014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch struct DelayedReference { 750014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ReferenceMap* map; 751014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionOperand* operand; 752014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch }; 753014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef ZoneVector<DelayedReference> DelayedReferences; 754014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef ZoneVector<std::pair<TopLevelLiveRange*, int>> 755014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RangesWithPreassignedSlots; 756014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 757014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData(const RegisterConfiguration* config, 758014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* allocation_zone, Frame* frame, 759014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionSequence* code, 760014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const char* debug_name = nullptr); 761014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 762014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const ZoneVector<TopLevelLiveRange*>& live_ranges() const { 763014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return live_ranges_; 764014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 765014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<TopLevelLiveRange*>& live_ranges() { return live_ranges_; } 766014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const ZoneVector<TopLevelLiveRange*>& fixed_live_ranges() const { 767014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return fixed_live_ranges_; 768014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 769014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<TopLevelLiveRange*>& fixed_live_ranges() { 770958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return fixed_live_ranges_; 771b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 772014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<TopLevelLiveRange*>& fixed_double_live_ranges() { 773958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return fixed_double_live_ranges_; 774b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 775014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const ZoneVector<TopLevelLiveRange*>& fixed_double_live_ranges() const { 776014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return fixed_double_live_ranges_; 777014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 778014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<BitVector*>& live_in_sets() { return live_in_sets_; } 779014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<BitVector*>& live_out_sets() { return live_out_sets_; } 780014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; } 781014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DelayedReferences& delayed_references() { return delayed_references_; } 782958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier InstructionSequence* code() const { return code_; } 783014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // This zone is for datastructures only needed during register allocation 784014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // phases. 785014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* allocation_zone() const { return allocation_zone_; } 786014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // This zone is for InstructionOperands and moves that live beyond register 787014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // allocation. 788014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* code_zone() const { return code()->zone(); } 789014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Frame* frame() const { return frame_; } 790014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const char* debug_name() const { return debug_name_; } 791014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const RegisterConfiguration* config() const { return config_; } 792014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 793014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch MachineRepresentation RepresentationFor(int virtual_register); 794014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 795014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* GetOrCreateLiveRangeFor(int index); 796014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Creates a new live range. 797014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* NewLiveRange(int index, MachineRepresentation rep); 798014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* NextLiveRange(MachineRepresentation rep); 799014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 800014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SpillRange* AssignSpillRangeToLiveRange(TopLevelLiveRange* range); 801014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SpillRange* CreateSpillRangeForLiveRange(TopLevelLiveRange* range); 802014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 803014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch MoveOperands* AddGapMove(int index, Instruction::GapPosition position, 804014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const InstructionOperand& from, 805014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const InstructionOperand& to); 806014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 807014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsReference(TopLevelLiveRange* top_range) const { 808014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return code()->IsReference(top_range->vreg()); 809014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 810014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 811014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool ExistsUseWithoutDefinition(); 812014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool RangesDefinedInDeferredStayInDeferred(); 813014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 814014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void MarkAllocated(RegisterKind kind, int index); 815014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 816014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PhiMapValue* InitializePhiMap(const InstructionBlock* block, 817014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PhiInstruction* phi); 818014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PhiMapValue* GetPhiMapValueFor(TopLevelLiveRange* top_range); 819014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PhiMapValue* GetPhiMapValueFor(int virtual_register); 820014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsBlockBoundary(LifetimePosition pos) const; 821014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 822014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RangesWithPreassignedSlots& preassigned_slot_ranges() { 823014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return preassigned_slot_ranges_; 824014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 825014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 826014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 827014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int GetNextLiveRangeId(); 828014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 829014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* const allocation_zone_; 830014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Frame* const frame_; 831014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionSequence* const code_; 832014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const char* const debug_name_; 833014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const RegisterConfiguration* const config_; 834014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PhiMap phi_map_; 835014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<int> allocatable_codes_; 836014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<int> allocatable_double_codes_; 837014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<BitVector*> live_in_sets_; 838014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<BitVector*> live_out_sets_; 839014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<TopLevelLiveRange*> live_ranges_; 840014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<TopLevelLiveRange*> fixed_live_ranges_; 841014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<TopLevelLiveRange*> fixed_double_live_ranges_; 842014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<SpillRange*> spill_ranges_; 843014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DelayedReferences delayed_references_; 844014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BitVector* assigned_registers_; 845014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BitVector* assigned_double_registers_; 846014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int virtual_register_count_; 847014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RangesWithPreassignedSlots preassigned_slot_ranges_; 848014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 849014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(RegisterAllocationData); 850014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 851014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 852014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 853014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass ConstraintBuilder final : public ZoneObject { 854014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 855014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit ConstraintBuilder(RegisterAllocationData* data); 856b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 857958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Phase 1 : insert moves to account for fixed register operands. 858958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void MeetRegisterConstraints(); 859b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 860958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Phase 2: deconstruct SSA by inserting moves in successors and the headers 861958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // of blocks containing phis. 862958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void ResolvePhis(); 863b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 864014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 865014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* data() const { return data_; } 866014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionSequence* code() const { return data()->code(); } 867014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* allocation_zone() const { return data()->allocation_zone(); } 868958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 869014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos, 870014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool is_tagged); 871014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void MeetRegisterConstraints(const InstructionBlock* block); 872014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void MeetConstraintsBefore(int index); 873014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void MeetConstraintsAfter(int index); 874014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void MeetRegisterConstraintsForLastInstructionInBlock( 875014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const InstructionBlock* block); 876014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ResolvePhis(const InstructionBlock* block); 877958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 878014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* const data_; 879958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 880014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(ConstraintBuilder); 881014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 882b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 883958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 884014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass LiveRangeBuilder final : public ZoneObject { 885014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 886014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit LiveRangeBuilder(RegisterAllocationData* data, Zone* local_zone); 887958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 888014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Phase 3: compute liveness of all virtual register. 889014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void BuildLiveRanges(); 890014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static BitVector* ComputeLiveOut(const InstructionBlock* block, 891014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* data); 892958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 893958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 894014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* data() const { return data_; } 895014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionSequence* code() const { return data()->code(); } 896014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* allocation_zone() const { return data()->allocation_zone(); } 897958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Zone* code_zone() const { return code()->zone(); } 898014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const RegisterConfiguration* config() const { return data()->config(); } 899014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<BitVector*>& live_in_sets() const { 900014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return data()->live_in_sets(); 901014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 902b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 903958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void Verify() const; 904b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 905b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Liveness analysis support. 906958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out); 907958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void ProcessInstructions(const InstructionBlock* block, BitVector* live); 908014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ProcessPhis(const InstructionBlock* block, BitVector* live); 909014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ProcessLoopHeader(const InstructionBlock* block, BitVector* live); 910b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 911014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static int FixedLiveRangeID(int index) { return -index - 1; } 912014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int FixedDoubleLiveRangeID(int index); 913014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* FixedLiveRangeFor(int index); 914014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* FixedDoubleLiveRangeFor(int index); 915014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 916014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void MapPhiHint(InstructionOperand* operand, UsePosition* use_pos); 917014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ResolvePhiHint(InstructionOperand* operand, UsePosition* use_pos); 918014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 919014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* NewUsePosition(LifetimePosition pos, InstructionOperand* operand, 920014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void* hint, UsePositionHintType hint_type); 921014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* NewUsePosition(LifetimePosition pos) { 922014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return NewUsePosition(pos, nullptr, nullptr, UsePositionHintType::kNone); 923014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 924014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch TopLevelLiveRange* LiveRangeFor(InstructionOperand* operand); 925b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Helper methods for building intervals. 926014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* Define(LifetimePosition position, InstructionOperand* operand, 927014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void* hint, UsePositionHintType hint_type); 928014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Define(LifetimePosition position, InstructionOperand* operand) { 929014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Define(position, operand, nullptr, UsePositionHintType::kNone); 930014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 931014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePosition* Use(LifetimePosition block_start, LifetimePosition position, 932014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionOperand* operand, void* hint, 933014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UsePositionHintType hint_type); 934b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Use(LifetimePosition block_start, LifetimePosition position, 935014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionOperand* operand) { 936014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Use(block_start, position, operand, nullptr, UsePositionHintType::kNone); 937014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 938b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 939014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* const data_; 940014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneMap<InstructionOperand*, UsePosition*> phi_hints_; 941b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 942014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder); 943014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 944014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 945014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 946014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass RegisterAllocator : public ZoneObject { 947014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 948014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit RegisterAllocator(RegisterAllocationData* data, RegisterKind kind); 949014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 950014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch protected: 951014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* data() const { return data_; } 952014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionSequence* code() const { return data()->code(); } 953014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterKind mode() const { return mode_; } 954014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int num_registers() const { return num_registers_; } 955014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int num_allocatable_registers() const { return num_allocatable_registers_; } 956014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int allocatable_register_code(int allocatable_index) const { 957014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return allocatable_register_codes_[allocatable_index]; 958014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 959b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 960014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // TODO(mtrofin): explain why splitting in gap START is always OK. 961014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition GetSplitPositionForInstruction(const LiveRange* range, 962014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int instruction_index); 963014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 964014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* allocation_zone() const { return data()->allocation_zone(); } 965014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 966014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Find the optimal split for ranges defined by a memory operand, e.g. 967014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // constants or function parameters passed on the stack. 968014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void SplitAndSpillRangesDefinedByMemoryOperand(bool operands_only); 969b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 970b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Split the given range at the given position. 971b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If range starts at or after the given position then the 972b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // original range is returned. 973b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Otherwise returns the live range that starts at pos and contains 974b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // all uses from the original range that follow pos. Uses at pos will 975b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // still be owned by the original range after splitting. 976b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); 977b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 978014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool CanProcessRange(LiveRange* range) const { 979014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return range != nullptr && !range->IsEmpty() && range->kind() == mode(); 980014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 981014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 982014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 983b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Split the given range in a position from the interval [start, end]. 984b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* SplitBetween(LiveRange* range, LifetimePosition start, 985b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end); 986b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 987b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Find a lifetime position in the interval [start, end] which 988b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // is optimal for splitting: it is either header of the outermost 989b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // loop covered by this interval or the latest possible position. 990b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition FindOptimalSplitPos(LifetimePosition start, 991b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end); 992b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 993014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Spill(LiveRange* range); 994014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 995014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // If we are trying to spill a range inside the loop try to 996014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // hoist spill position out to the point just before the loop. 997014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition FindOptimalSpillingPos(LiveRange* range, 998014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition pos); 999014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1000014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const ZoneVector<TopLevelLiveRange*>& GetFixedRegisters() const; 1001014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const char* RegisterName(int allocation_index) const; 1002014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1003014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 1004014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* const data_; 1005014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const RegisterKind mode_; 1006014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const int num_registers_; 1007014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int num_allocatable_registers_; 1008014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const int* allocatable_register_codes_; 1009014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1010014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); 1011014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 1012014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1013014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1014014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass LinearScanAllocator final : public RegisterAllocator { 1015014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 1016014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LinearScanAllocator(RegisterAllocationData* data, RegisterKind kind, 1017014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* local_zone); 1018014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1019014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Phase 4: compute register assignments. 1020014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AllocateRegisters(); 1021014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1022014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 1023014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<LiveRange*>& unhandled_live_ranges() { 1024014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return unhandled_live_ranges_; 1025014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 1026014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; } 1027014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<LiveRange*>& inactive_live_ranges() { 1028014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return inactive_live_ranges_; 1029014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 1030014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1031014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void SetLiveRangeAssignedRegister(LiveRange* range, int reg); 1032014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1033014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Helper methods for updating the life range lists. 1034014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddToActive(LiveRange* range); 1035014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddToInactive(LiveRange* range); 1036014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddToUnhandledSorted(LiveRange* range); 1037014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddToUnhandledUnsorted(LiveRange* range); 1038014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void SortUnhandled(); 1039014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool UnhandledIsSorted(); 1040014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ActiveToHandled(LiveRange* range); 1041014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ActiveToInactive(LiveRange* range); 1042014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void InactiveToHandled(LiveRange* range); 1043014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void InactiveToActive(LiveRange* range); 1044014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1045014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Helper methods for allocating registers. 1046014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool TryReuseSpillForPhi(TopLevelLiveRange* range); 1047014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool TryAllocateFreeReg(LiveRange* range); 1048014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AllocateBlockedReg(LiveRange* range); 1049014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1050b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Spill the given life range after position pos. 1051b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SpillAfter(LiveRange* range, LifetimePosition pos); 1052b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1053b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Spill the given life range after position [start] and up to position [end]. 1054b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SpillBetween(LiveRange* range, LifetimePosition start, 1055b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end); 1056b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1057b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Spill the given life range after position [start] and up to position [end]. 1058b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Range is guaranteed to be spilled at least until position [until]. 1059b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SpillBetweenUntil(LiveRange* range, LifetimePosition start, 1060b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition until, LifetimePosition end); 1061b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1062b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void SplitAndSpillIntersecting(LiveRange* range); 1063b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1064014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<LiveRange*> unhandled_live_ranges_; 1065014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<LiveRange*> active_live_ranges_; 1066014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<LiveRange*> inactive_live_ranges_; 1067b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1068014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#ifdef DEBUG 1069014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition allocation_finger_; 1070014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#endif 1071b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1072014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(LinearScanAllocator); 1073014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 1074b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1075b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1076014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass SpillSlotLocator final : public ZoneObject { 1077014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 1078014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit SpillSlotLocator(RegisterAllocationData* data); 1079b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1080014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void LocateSpillSlots(); 1081b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1082014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 1083014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* data() const { return data_; } 1084b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1085014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* const data_; 1086b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1087014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(SpillSlotLocator); 1088014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 1089958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 1090958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 1091014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass OperandAssigner final : public ZoneObject { 1092014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 1093014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit OperandAssigner(RegisterAllocationData* data); 1094958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 1095014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Phase 5: assign spill splots. 1096014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AssignSpillSlots(); 1097b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1098014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Phase 6: commit assignment. 1099014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void CommitAssignment(); 1100958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 1101014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 1102014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* data() const { return data_; } 1103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1104014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* const data_; 1105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1106014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(OperandAssigner); 1107014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 1108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1110014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass ReferenceMapPopulator final : public ZoneObject { 1111014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 1112014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit ReferenceMapPopulator(RegisterAllocationData* data); 1113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1114014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Phase 7: compute values for pointer maps. 1115014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void PopulateReferenceMaps(); 1116014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1117014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 1118014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* data() const { return data_; } 1119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1120014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool SafePointsAreInOrder() const; 1121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1122014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* const data_; 1123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1124014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(ReferenceMapPopulator); 1125014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 1126014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1127014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1128014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Insert moves of the form 1129014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// 1130014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Operand(child_(k+1)) = Operand(child_k) 1131014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// 1132014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// where child_k and child_(k+1) are consecutive children of a range (so 1133014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// child_k->next() == child_(k+1)), and Operand(...) refers to the 1134014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// assigned operand, be it a register or a slot. 1135014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass LiveRangeConnector final : public ZoneObject { 1136014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 1137014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit LiveRangeConnector(RegisterAllocationData* data); 1138014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1139014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Phase 8: reconnect split ranges with moves, when the control flow 1140014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // between the ranges is trivial (no branches). 1141014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ConnectRanges(Zone* local_zone); 1142014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1143014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Phase 9: insert moves to connect ranges across basic blocks, when the 1144014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // control flow between them cannot be trivially resolved, such as joining 1145014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // branches. 1146014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ResolveControlFlow(Zone* local_zone); 1147014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1148014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 1149014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* data() const { return data_; } 1150014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionSequence* code() const { return data()->code(); } 1151014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* code_zone() const { return code()->zone(); } 1152014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1153014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool CanEagerlyResolveControlFlow(const InstructionBlock* block) const; 1154014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1155014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int ResolveControlFlow(const InstructionBlock* block, 1156014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const InstructionOperand& cur_op, 1157014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const InstructionBlock* pred, 1158014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const InstructionOperand& pred_op); 1159014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1160014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterAllocationData* const data_; 1161014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1162014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector); 1163b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 1164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1165958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace compiler 1166958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace internal 1167958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace v8 1168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif // V8_REGISTER_ALLOCATOR_H_ 1170