13ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// Copyright 2012 the V8 project authors. All rights reserved. 2b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Redistribution and use in source and binary forms, with or without 3b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// modification, are permitted provided that the following conditions are 4b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// met: 5b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// 6b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// * Redistributions of source code must retain the above copyright 7b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// notice, this list of conditions and the following disclaimer. 8b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// * Redistributions in binary form must reproduce the above 9b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// copyright notice, this list of conditions and the following 10b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// disclaimer in the documentation and/or other materials provided 11b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// with the distribution. 12b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// * Neither the name of Google Inc. nor the names of its 13b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// contributors may be used to endorse or promote products derived 14b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// from this software without specific prior written permission. 15b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// 16b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 28b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifndef V8_LITHIUM_ALLOCATOR_H_ 29b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#define V8_LITHIUM_ALLOCATOR_H_ 30b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 31b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#include "v8.h" 32b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 33257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch#include "allocation.h" 341e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block#include "lithium.h" 35b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#include "zone.h" 36b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 37b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochnamespace v8 { 38b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochnamespace internal { 39b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 40b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Forward declarations. 41b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass HBasicBlock; 42b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass HGraph; 43b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass HInstruction; 44b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass HPhi; 45b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass HTracer; 46b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass HValue; 47b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass BitVector; 48b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass StringStream; 49b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 50b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LArgument; 51b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LChunk; 521e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass LOperand; 531e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass LUnallocated; 54b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LConstantOperand; 55b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LGap; 56b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LParallelMove; 57b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LPointerMap; 58b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LStackSlot; 59b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LRegister; 60b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 61b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 62b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// This class represents a single point of a LOperand's lifetime. 63b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// For each lithium instruction there are exactly two lifetime positions: 64b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// the beginning and the end of the instruction. Lifetime positions for 65b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// different lithium instructions are disjoint. 66b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LifetimePosition { 67b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 68b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Return the lifetime position that corresponds to the beginning of 69b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the instruction with the given index. 70b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static LifetimePosition FromInstructionIndex(int index) { 71b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition(index * kStep); 72b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 73b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 74b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns a numeric representation of this lifetime position. 75b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int Value() const { 76b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return value_; 77b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 78b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 79b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns the index of the instruction to which this lifetime position 80b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // corresponds. 81b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int InstructionIndex() const { 82b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(IsValid()); 83b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return value_ / kStep; 84b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 85b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 86b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns true if this lifetime position corresponds to the instruction 87b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // start. 88b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsInstructionStart() const { 89b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return (value_ & (kStep - 1)) == 0; 90b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 91b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 92b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns the lifetime position for the start of the instruction which 93b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // corresponds to this lifetime position. 94b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition InstructionStart() const { 95b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(IsValid()); 96b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition(value_ & ~(kStep - 1)); 97b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 98b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 99b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns the lifetime position for the end of the instruction which 100b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // corresponds to this lifetime position. 101b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition InstructionEnd() const { 102b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(IsValid()); 103b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition(InstructionStart().Value() + kStep/2); 104b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 105b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 106b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns the lifetime position for the beginning of the next instruction. 107b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition NextInstruction() const { 108b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(IsValid()); 109b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition(InstructionStart().Value() + kStep); 110b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 111b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 112b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns the lifetime position for the beginning of the previous 113b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // instruction. 114b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition PrevInstruction() const { 115b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(IsValid()); 116b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(value_ > 1); 117b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition(InstructionStart().Value() - kStep); 118b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 119b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 120b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Constructs the lifetime position which does not correspond to any 121b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // instruction. 122b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition() : value_(-1) {} 123b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 124b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns true if this lifetime positions corrensponds to some 125b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // instruction. 126b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsValid() const { return value_ != -1; } 127b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 128b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static inline LifetimePosition Invalid() { return LifetimePosition(); } 129b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 130b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static inline LifetimePosition MaxPosition() { 131b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We have to use this kind of getter instead of static member due to 132b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // crash bug in GDB. 133b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition(kMaxInt); 134b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 135b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 136b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 137b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static const int kStep = 2; 138b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 139b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Code relies on kStep being a power of two. 140b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch STATIC_ASSERT(IS_POWER_OF_TWO(kStep)); 141b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 142b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch explicit LifetimePosition(int value) : value_(value) { } 143b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 144b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int value_; 145b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 146b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 147b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 148b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochenum RegisterKind { 149b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch GENERAL_REGISTERS, 150b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch DOUBLE_REGISTERS 151b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 152b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 153b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1541e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block// A register-allocator view of a Lithium instruction. It contains the id of 1551e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block// the output operand and a list of input operand uses. 156b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1571e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass LInstruction; 1581e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass LEnvironment; 159b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1601e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block// Iterator for non-null temp operands. 1611e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass TempIterator BASE_EMBEDDED { 162b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 1631e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline explicit TempIterator(LInstruction* instr); 1643fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline bool Done(); 1653fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline LOperand* Current(); 1661e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline void Advance(); 167b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 168b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 1693fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline void SkipUninteresting(); 1701e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr_; 1711e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block int limit_; 1721e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block int current_; 173b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 174b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 175b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1761e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block// Iterator for non-constant input operands. 1771e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass InputIterator BASE_EMBEDDED { 178b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 1791e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline explicit InputIterator(LInstruction* instr); 1803fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline bool Done(); 1813fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline LOperand* Current(); 1821e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline void Advance(); 183b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 184b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 1853fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline void SkipUninteresting(); 1861e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr_; 1871e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block int limit_; 1881e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block int current_; 189b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 190b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 191b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1921e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass UseIterator BASE_EMBEDDED { 193b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 1941e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline explicit UseIterator(LInstruction* instr); 1953fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline bool Done(); 1963fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline LOperand* Current(); 1971e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline void Advance(); 198b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 199b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 2001e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block InputIterator input_iterator_; 2011e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block DeepIterator env_iterator_; 202b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 203b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 204b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 205b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Representation of the non-empty interval [start,end[. 206b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass UseInterval: public ZoneObject { 207b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 208b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval(LifetimePosition start, LifetimePosition end) 209b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch : start_(start), end_(end), next_(NULL) { 210b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(start.Value() < end.Value()); 211b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 212b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 213b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start() const { return start_; } 214b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end() const { return end_; } 215b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* next() const { return next_; } 216b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 217b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split this interval at the given position without effecting the 218b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // live range that owns it. The interval must contain the position. 2193ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void SplitAt(LifetimePosition pos, Zone* zone); 220b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 221b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If this interval intersects with other return smallest position 222b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // that belongs to both of them. 223b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition Intersect(const UseInterval* other) const { 224b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (other->start().Value() < start_.Value()) return other->Intersect(this); 225b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (other->start().Value() < end_.Value()) return other->start(); 226b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition::Invalid(); 227b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 228b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 229b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool Contains(LifetimePosition point) const { 230b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return start_.Value() <= point.Value() && point.Value() < end_.Value(); 231b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 232b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 233b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 234b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void set_start(LifetimePosition start) { start_ = start; } 235b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void set_next(UseInterval* next) { next_ = next; } 236b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 237b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start_; 238b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end_; 239b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* next_; 240b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 241b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch friend class LiveRange; // Assigns to start_. 242b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 243b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 244b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Representation of a use position. 245b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass UsePosition: public ZoneObject { 246b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 2471e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block UsePosition(LifetimePosition pos, LOperand* operand); 248b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 249b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand() const { return operand_; } 250b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool HasOperand() const { return operand_ != NULL; } 251b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 252b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint() const { return hint_; } 253b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void set_hint(LOperand* hint) { hint_ = hint; } 2541e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block bool HasHint() const; 255b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool RequiresRegister() const; 256b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool RegisterIsBeneficial() const; 257b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 258b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos() const { return pos_; } 259b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next() const { return next_; } 260b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 261b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 262b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void set_next(UsePosition* next) { next_ = next; } 263b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 264b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand_; 265b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint_; 266b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos_; 267b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_; 268b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool requires_reg_; 269b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool register_beneficial_; 270b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 271b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch friend class LiveRange; 272b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 273b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 274b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Representation of SSA values' live ranges as a collection of (continuous) 275b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// intervals over the instruction ordering. 276b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LiveRange: public ZoneObject { 277b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 278b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static const int kInvalidAssignment = 0x7fffffff; 279b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange(int id, Zone* zone); 281b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 282b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* first_interval() const { return first_interval_; } 283b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* first_pos() const { return first_pos_; } 284b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* parent() const { return parent_; } 285b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* TopLevel() { return (parent_ == NULL) ? this : parent_; } 286b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* next() const { return next_; } 287b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsChild() const { return parent() != NULL; } 288b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int id() const { return id_; } 289b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsFixed() const { return id_ < 0; } 290b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsEmpty() const { return first_interval() == NULL; } 2913ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* CreateAssignedOperand(Zone* zone); 292b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int assigned_register() const { return assigned_register_; } 293b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int spill_start_index() const { return spill_start_index_; } 2943ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void set_assigned_register(int reg, 2953ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch RegisterKind register_kind, 2963ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone); 2973ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void MakeSpilled(Zone* zone); 298b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 299b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns use position in this live range that follows both start 300b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // and last processed use position. 301b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Modifies internal state of live range! 302b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* NextUsePosition(LifetimePosition start); 303b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 304b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns use position for which register is required in this live 305b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // range and which follows both start and last processed use position 306b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Modifies internal state of live range! 307b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* NextRegisterPosition(LifetimePosition start); 308b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 309b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns use position for which register is beneficial in this live 310b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // range and which follows both start and last processed use position 311b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Modifies internal state of live range! 312b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start); 313b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 314b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Can this live range be spilled at this position. 315b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool CanBeSpilled(LifetimePosition pos); 316b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 317b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split this live range at the given position which must follow the start of 318b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the range. 319b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All uses following the given position will be moved from this 320b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // live range to the result live range. 3213ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone); 322b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3233ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool IsDouble() const { return is_double_; } 324b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool HasRegisterAssigned() const { 325b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return assigned_register_ != kInvalidAssignment; 326b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 327b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsSpilled() const { return spilled_; } 328b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* FirstPosWithHint() const; 329b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 330b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* FirstHint() const { 331b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = FirstPosWithHint(); 332b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos != NULL) return pos->hint(); 333b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 334b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 335b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 336b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition Start() const { 337b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!IsEmpty()); 338b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return first_interval()->start(); 339b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 340b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 341b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition End() const { 342b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!IsEmpty()); 343b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return last_interval_->end(); 344b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 345b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3461e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block bool HasAllocatedSpillOperand() const; 347b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* GetSpillOperand() const { return spill_operand_; } 3481e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block void SetSpillOperand(LOperand* operand); 349b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 350b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SetSpillStartIndex(int start) { 351b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch spill_start_index_ = Min(start, spill_start_index_); 352b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 353b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 354b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool ShouldBeAllocatedBefore(const LiveRange* other) const; 355b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool CanCover(LifetimePosition position) const; 356b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool Covers(LifetimePosition position); 357b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition FirstIntersection(LiveRange* other); 358b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 359b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Add a new interval or a new use position to this live range. 3603ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void EnsureInterval(LifetimePosition start, 3613ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LifetimePosition end, 3623ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone); 3633ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void AddUseInterval(LifetimePosition start, 3643ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LifetimePosition end, 3653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone); 3663ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UsePosition* AddUsePosition(LifetimePosition pos, 3673ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* operand, 3683ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone); 369b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 370b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Shorten the most recently added interval by setting a new start. 371b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ShortenTo(LifetimePosition start); 372b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 373b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 374b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // True if target overlaps an existing interval. 375b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool HasOverlap(UseInterval* target) const; 376b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void Verify() const; 377b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 378b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 379b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 3803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void ConvertOperands(Zone* zone); 381b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; 382b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AdvanceLastProcessedMarker(UseInterval* to_start_of, 383b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition but_not_past) const; 384b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 385b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int id_; 386b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool spilled_; 3873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool is_double_; 388b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int assigned_register_; 389b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* last_interval_; 390b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* first_interval_; 391b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* first_pos_; 392b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* parent_; 393b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* next_; 394b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This is used as a cache, it doesn't affect correctness. 395b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch mutable UseInterval* current_interval_; 396b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* last_processed_use_; 397b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* spill_operand_; 398b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int spill_start_index_; 399b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 400b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 401b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 4029fac840a46e8b7e26894f4792ba26dde14c56b04Steve Blockclass GrowableBitVector BASE_EMBEDDED { 4039fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block public: 4049fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block GrowableBitVector() : bits_(NULL) { } 4059fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4069fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block bool Contains(int value) const { 4079fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (!InBitsRange(value)) return false; 4089fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block return bits_->Contains(value); 4099fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 4109fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4113ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void Add(int value, Zone* zone) { 4123ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch EnsureCapacity(value, zone); 4139fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block bits_->Add(value); 4149fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 4159fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4169fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block private: 4179fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block static const int kInitialLength = 1024; 4189fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4199fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block bool InBitsRange(int value) const { 4209fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block return bits_ != NULL && bits_->length() > value; 4219fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 4229fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4233ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void EnsureCapacity(int value, Zone* zone) { 4249fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (InBitsRange(value)) return; 4259fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block int new_length = bits_ == NULL ? kInitialLength : bits_->length(); 4269fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block while (new_length <= value) new_length *= 2; 4273ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch BitVector* new_bits = new(zone) BitVector(new_length, zone); 4289fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (bits_ != NULL) new_bits->CopyFrom(*bits_); 4299fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block bits_ = new_bits; 4309fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 4319fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4329fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block BitVector* bits_; 4339fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block}; 4349fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4359fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 436b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LAllocator BASE_EMBEDDED { 437b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 43844f0eee88ff00398ff7f715fab053374d808c90dSteve Block LAllocator(int first_virtual_register, HGraph* graph); 43944f0eee88ff00398ff7f715fab053374d808c90dSteve Block 440b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static void TraceAlloc(const char* msg, ...); 441b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 442b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Checks whether the value of a given virtual register is tagged. 443b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool HasTaggedValue(int virtual_register) const; 444b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 445b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns the register kind required by the given virtual register. 446b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterKind RequiredRegisterKind(int virtual_register) const; 447b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 4483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool Allocate(LChunk* chunk); 449b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 450b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; } 45144f0eee88ff00398ff7f715fab053374d808c90dSteve Block const Vector<LiveRange*>* fixed_live_ranges() const { 452b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return &fixed_live_ranges_; 453b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 45444f0eee88ff00398ff7f715fab053374d808c90dSteve Block const Vector<LiveRange*>* fixed_double_live_ranges() const { 455b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return &fixed_double_live_ranges_; 456b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 457b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 458b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LChunk* chunk() const { return chunk_; } 459b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HGraph* graph() const { return graph_; } 460b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 4613ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int GetVirtualRegister() { 4623ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (next_virtual_register_ > LUnallocated::kMaxVirtualRegisters) { 4633ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch allocation_ok_ = false; 4643ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 4653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return next_virtual_register_++; 4663ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 4673ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 4683ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool AllocationOk() { return allocation_ok_; } 4693ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 470b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void MarkAsOsrEntry() { 471b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // There can be only one. 472b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!has_osr_entry_); 473b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Simply set a flag to find and process instruction later. 474b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch has_osr_entry_ = true; 475b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 476b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 477b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 478b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void Verify() const; 479b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 480b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 481b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 482b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void MeetRegisterConstraints(); 483b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ResolvePhis(); 484b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void BuildLiveRanges(); 485b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AllocateGeneralRegisters(); 486b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AllocateDoubleRegisters(); 487b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ConnectRanges(); 488b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ResolveControlFlow(); 489b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void PopulatePointerMaps(); 490b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ProcessOsrEntry(); 491b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AllocateRegisters(); 492b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool CanEagerlyResolveControlFlow(HBasicBlock* block) const; 493b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inline bool SafePointsAreInOrder() const; 494b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 495b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Liveness analysis support. 496b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void InitializeLivenessAnalysis(); 497b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* ComputeLiveOut(HBasicBlock* block); 498b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddInitialIntervals(HBasicBlock* block, BitVector* live_out); 499b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ProcessInstructions(HBasicBlock* block, BitVector* live); 500b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void MeetRegisterConstraints(HBasicBlock* block); 5011e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block void MeetConstraintsBetween(LInstruction* first, 5021e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* second, 503b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int gap_index); 504b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ResolvePhis(HBasicBlock* block); 505b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 506b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Helper methods for building intervals. 507b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* AllocateFixed(LUnallocated* operand, int pos, bool is_tagged); 508b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* LiveRangeFor(LOperand* operand); 509b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void Define(LifetimePosition position, LOperand* operand, LOperand* hint); 510b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void Use(LifetimePosition block_start, 511b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position, 512b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand, 513b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint); 514b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddConstraintsGapMove(int index, LOperand* from, LOperand* to); 515b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 516b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Helper methods for updating the life range lists. 517b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddToActive(LiveRange* range); 518b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddToInactive(LiveRange* range); 519b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddToUnhandledSorted(LiveRange* range); 520b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddToUnhandledUnsorted(LiveRange* range); 521b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SortUnhandled(); 522b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool UnhandledIsSorted(); 523b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ActiveToHandled(LiveRange* range); 524b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ActiveToInactive(LiveRange* range); 525b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void InactiveToHandled(LiveRange* range); 526b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void InactiveToActive(LiveRange* range); 527b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void FreeSpillSlot(LiveRange* range); 528b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* TryReuseSpillSlot(LiveRange* range); 529b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 530b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Helper methods for allocating registers. 531b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool TryAllocateFreeReg(LiveRange* range); 532b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AllocateBlockedReg(LiveRange* range); 533b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 534b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Live range splitting helpers. 535b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 536b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split the given range at the given position. 537b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If range starts at or after the given position then the 538b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // original range is returned. 539b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Otherwise returns the live range that starts at pos and contains 540b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // all uses from the original range that follow pos. Uses at pos will 541b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // still be owned by the original range after splitting. 5423ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); 543b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 544b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split the given range in a position from the interval [start, end]. 545b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* SplitBetween(LiveRange* range, 546b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 547b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end); 548b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 549b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find a lifetime position in the interval [start, end] which 550b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // is optimal for splitting: it is either header of the outermost 551b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // loop covered by this interval or the latest possible position. 552b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition FindOptimalSplitPos(LifetimePosition start, 553b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end); 554b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 555b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Spill the given life range after position pos. 556b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SpillAfter(LiveRange* range, LifetimePosition pos); 557b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 558b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Spill the given life range after position start and up to position end. 559b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SpillBetween(LiveRange* range, 560b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 561b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end); 562b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 563b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SplitAndSpillIntersecting(LiveRange* range); 564b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 565b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void Spill(LiveRange* range); 566b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsBlockBoundary(LifetimePosition pos); 567b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 568b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Helper methods for resolving control flow. 569b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ResolveControlFlow(LiveRange* range, 570b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block, 571b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* pred); 572b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 573b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Return parallel move that should be used to connect ranges split at the 574b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // given position. 575b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LParallelMove* GetConnectingParallelMove(LifetimePosition pos); 576b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 577b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Return the block which contains give lifetime position. 578b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* GetBlock(LifetimePosition pos); 579b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 580b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Helper methods for the fixed registers. 581b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int RegisterCount() const; 582b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static int FixedLiveRangeID(int index) { return -index - 1; } 583b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static int FixedDoubleLiveRangeID(int index); 584b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* FixedLiveRangeFor(int index); 585b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* FixedDoubleLiveRangeFor(int index); 586b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* LiveRangeFor(int index); 587b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* LookupPhi(LOperand* operand) const; 5881e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* GetLastGap(HBasicBlock* block); 589b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 590b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const char* RegisterName(int allocation_index); 591b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 5921e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline bool IsGapAt(int index); 5931e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 5941e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline LInstruction* InstructionAt(int index); 595b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 5961e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline LGap* GapAt(int index); 5971e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 5983ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone_; 5993ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 6001e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LChunk* chunk_; 601b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 602b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // During liveness analysis keep a mapping from block id to live_in sets 603b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // for blocks already analyzed. 604b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<BitVector*> live_in_sets_; 605b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 606b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Liveness analysis results. 607b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<LiveRange*> live_ranges_; 608b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 609b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Lists of live ranges 61044f0eee88ff00398ff7f715fab053374d808c90dSteve Block EmbeddedVector<LiveRange*, Register::kNumAllocatableRegisters> 61144f0eee88ff00398ff7f715fab053374d808c90dSteve Block fixed_live_ranges_; 61244f0eee88ff00398ff7f715fab053374d808c90dSteve Block EmbeddedVector<LiveRange*, DoubleRegister::kNumAllocatableRegisters> 61344f0eee88ff00398ff7f715fab053374d808c90dSteve Block fixed_double_live_ranges_; 614b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<LiveRange*> unhandled_live_ranges_; 615b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<LiveRange*> active_live_ranges_; 616b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<LiveRange*> inactive_live_ranges_; 617b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<LiveRange*> reusable_slots_; 618b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 619b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Next virtual register number to be assigned to temporaries. 620b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int next_virtual_register_; 6219fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block int first_artificial_register_; 6229fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block GrowableBitVector double_artificial_registers_; 623b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 624b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterKind mode_; 625b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int num_registers_; 626b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 627b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HGraph* graph_; 628b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 629b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool has_osr_entry_; 630b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 6313ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Indicates success or failure during register allocation. 6323ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool allocation_ok_; 6333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 634b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch DISALLOW_COPY_AND_ASSIGN(LAllocator); 635b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 636b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 637b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 638b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} } // namespace v8::internal 639b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 640b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif // V8_LITHIUM_ALLOCATOR_H_ 641