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