lithium-allocator.h revision 3fb3ca8c7ca439d408449a395897395c0faae8d1
1257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch// Copyright 2011 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 NONE, 150b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch GENERAL_REGISTERS, 151b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch DOUBLE_REGISTERS 152b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 153b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 154b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1551e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block// A register-allocator view of a Lithium instruction. It contains the id of 1561e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block// the output operand and a list of input operand uses. 157b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1581e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass LInstruction; 1591e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass LEnvironment; 160b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1611e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block// Iterator for non-null temp operands. 1621e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass TempIterator BASE_EMBEDDED { 163b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 1641e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline explicit TempIterator(LInstruction* instr); 1653fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline bool Done(); 1663fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline LOperand* Current(); 1671e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline void Advance(); 168b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 169b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 1703fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline void SkipUninteresting(); 1711e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr_; 1721e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block int limit_; 1731e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block int current_; 174b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 175b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 176b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1771e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block// Iterator for non-constant input operands. 1781e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass InputIterator BASE_EMBEDDED { 179b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 1801e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline explicit InputIterator(LInstruction* instr); 1813fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline bool Done(); 1823fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline LOperand* Current(); 1831e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline void Advance(); 184b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 185b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 1863fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline void SkipUninteresting(); 1871e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr_; 1881e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block int limit_; 1891e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block int current_; 190b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 191b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 192b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1931e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockclass UseIterator BASE_EMBEDDED { 194b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 1951e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline explicit UseIterator(LInstruction* instr); 1963fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline bool Done(); 1973fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch inline LOperand* Current(); 1981e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline void Advance(); 199b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 200b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 2011e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block InputIterator input_iterator_; 2021e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block DeepIterator env_iterator_; 203b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 204b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 205b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 206b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Representation of the non-empty interval [start,end[. 207b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass UseInterval: public ZoneObject { 208b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 209b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval(LifetimePosition start, LifetimePosition end) 210b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch : start_(start), end_(end), next_(NULL) { 211b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(start.Value() < end.Value()); 212b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 213b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 214b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start() const { return start_; } 215b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end() const { return end_; } 216b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* next() const { return next_; } 217b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 218b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split this interval at the given position without effecting the 219b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // live range that owns it. The interval must contain the position. 220b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SplitAt(LifetimePosition pos); 221b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 222b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If this interval intersects with other return smallest position 223b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // that belongs to both of them. 224b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition Intersect(const UseInterval* other) const { 225b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (other->start().Value() < start_.Value()) return other->Intersect(this); 226b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (other->start().Value() < end_.Value()) return other->start(); 227b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition::Invalid(); 228b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 229b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 230b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool Contains(LifetimePosition point) const { 231b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return start_.Value() <= point.Value() && point.Value() < end_.Value(); 232b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 233b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 234b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 235b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void set_start(LifetimePosition start) { start_ = start; } 236b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void set_next(UseInterval* next) { next_ = next; } 237b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 238b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start_; 239b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end_; 240b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* next_; 241b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 242b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch friend class LiveRange; // Assigns to start_. 243b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 244b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 245b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Representation of a use position. 246b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass UsePosition: public ZoneObject { 247b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 2481e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block UsePosition(LifetimePosition pos, LOperand* operand); 249b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 250b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand() const { return operand_; } 251b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool HasOperand() const { return operand_ != NULL; } 252b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 253b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint() const { return hint_; } 254b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void set_hint(LOperand* hint) { hint_ = hint; } 2551e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block bool HasHint() const; 256b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool RequiresRegister() const; 257b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool RegisterIsBeneficial() const; 258b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 259b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos() const { return pos_; } 260b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next() const { return next_; } 261b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 262b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 263b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void set_next(UsePosition* next) { next_ = next; } 264b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 265b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand_; 266b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint_; 267b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos_; 268b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_; 269b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool requires_reg_; 270b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool register_beneficial_; 271b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 272b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch friend class LiveRange; 273b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 274b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 275b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Representation of SSA values' live ranges as a collection of (continuous) 276b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// intervals over the instruction ordering. 277b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LiveRange: public ZoneObject { 278b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 279b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static const int kInvalidAssignment = 0x7fffffff; 280b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2811e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block explicit LiveRange(int id); 282b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 283b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* first_interval() const { return first_interval_; } 284b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* first_pos() const { return first_pos_; } 285b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* parent() const { return parent_; } 286b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* TopLevel() { return (parent_ == NULL) ? this : parent_; } 287b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* next() const { return next_; } 288b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsChild() const { return parent() != NULL; } 289b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int id() const { return id_; } 290b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsFixed() const { return id_ < 0; } 291b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsEmpty() const { return first_interval() == NULL; } 292b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* CreateAssignedOperand(); 293b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int assigned_register() const { return assigned_register_; } 294b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int spill_start_index() const { return spill_start_index_; } 2951e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block void set_assigned_register(int reg, RegisterKind register_kind); 2961e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block void MakeSpilled(); 297b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 298b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns use position in this live range that follows both start 299b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // and last processed use position. 300b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Modifies internal state of live range! 301b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* NextUsePosition(LifetimePosition start); 302b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 303b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns use position for which register is required in this live 304b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // range and which follows both start and last processed use position 305b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Modifies internal state of live range! 306b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* NextRegisterPosition(LifetimePosition start); 307b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 308b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns use position for which register is beneficial in this live 309b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // range and which follows both start and last processed use position 310b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Modifies internal state of live range! 311b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start); 312b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 313b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Can this live range be spilled at this position. 314b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool CanBeSpilled(LifetimePosition pos); 315b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 316b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split this live range at the given position which must follow the start of 317b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the range. 318b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All uses following the given position will be moved from this 319b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // live range to the result live range. 320b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SplitAt(LifetimePosition position, LiveRange* result); 321b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 322b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsDouble() const { return assigned_register_kind_ == DOUBLE_REGISTERS; } 323b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool HasRegisterAssigned() const { 324b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return assigned_register_ != kInvalidAssignment; 325b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 326b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsSpilled() const { return spilled_; } 327b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* FirstPosWithHint() const; 328b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 329b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* FirstHint() const { 330b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = FirstPosWithHint(); 331b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos != NULL) return pos->hint(); 332b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 333b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 334b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 335b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition Start() const { 336b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!IsEmpty()); 337b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return first_interval()->start(); 338b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 339b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 340b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition End() const { 341b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!IsEmpty()); 342b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return last_interval_->end(); 343b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 344b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3451e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block bool HasAllocatedSpillOperand() const; 346b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* GetSpillOperand() const { return spill_operand_; } 3471e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block void SetSpillOperand(LOperand* operand); 348b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 349b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SetSpillStartIndex(int start) { 350b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch spill_start_index_ = Min(start, spill_start_index_); 351b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 352b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 353b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool ShouldBeAllocatedBefore(const LiveRange* other) const; 354b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool CanCover(LifetimePosition position) const; 355b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool Covers(LifetimePosition position); 356b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition FirstIntersection(LiveRange* other); 357b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 358b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Add a new interval or a new use position to this live range. 359b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void EnsureInterval(LifetimePosition start, LifetimePosition end); 360b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddUseInterval(LifetimePosition start, LifetimePosition end); 361b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* AddUsePosition(LifetimePosition pos, LOperand* operand); 362b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 363b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Shorten the most recently added interval by setting a new start. 364b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ShortenTo(LifetimePosition start); 365b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 366b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 367b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // True if target overlaps an existing interval. 368b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool HasOverlap(UseInterval* target) const; 369b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void Verify() const; 370b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 371b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 372b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 373b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ConvertOperands(); 374b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; 375b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AdvanceLastProcessedMarker(UseInterval* to_start_of, 376b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition but_not_past) const; 377b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 378b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int id_; 379b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool spilled_; 380b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int assigned_register_; 381b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterKind assigned_register_kind_; 382b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* last_interval_; 383b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* first_interval_; 384b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* first_pos_; 385b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* parent_; 386b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* next_; 387b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This is used as a cache, it doesn't affect correctness. 388b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch mutable UseInterval* current_interval_; 389b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* last_processed_use_; 390b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* spill_operand_; 391b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int spill_start_index_; 392b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 393b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 394b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3959fac840a46e8b7e26894f4792ba26dde14c56b04Steve Blockclass GrowableBitVector BASE_EMBEDDED { 3969fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block public: 3979fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block GrowableBitVector() : bits_(NULL) { } 3989fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 3999fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block bool Contains(int value) const { 4009fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (!InBitsRange(value)) return false; 4019fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block return bits_->Contains(value); 4029fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 4039fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4049fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block void Add(int value) { 4059fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block EnsureCapacity(value); 4069fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block bits_->Add(value); 4079fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 4089fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4099fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block private: 4109fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block static const int kInitialLength = 1024; 4119fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4129fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block bool InBitsRange(int value) const { 4139fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block return bits_ != NULL && bits_->length() > value; 4149fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 4159fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4169fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block void EnsureCapacity(int value) { 4179fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (InBitsRange(value)) return; 4189fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block int new_length = bits_ == NULL ? kInitialLength : bits_->length(); 4199fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block while (new_length <= value) new_length *= 2; 4209fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block BitVector* new_bits = new BitVector(new_length); 4219fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (bits_ != NULL) new_bits->CopyFrom(*bits_); 4229fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block bits_ = new_bits; 4239fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 4249fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4259fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block BitVector* bits_; 4269fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block}; 4279fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 4289fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 429b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass LAllocator BASE_EMBEDDED { 430b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 43144f0eee88ff00398ff7f715fab053374d808c90dSteve Block LAllocator(int first_virtual_register, HGraph* graph); 43244f0eee88ff00398ff7f715fab053374d808c90dSteve Block 433b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static void TraceAlloc(const char* msg, ...); 434b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 435b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Lithium translation support. 436b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Record a use of an input operand in the current instruction. 437b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void RecordUse(HValue* value, LUnallocated* operand); 438b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Record the definition of the output operand. 439b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void RecordDefinition(HInstruction* instr, LUnallocated* operand); 440b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Record a temporary operand. 441b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void RecordTemporary(LUnallocated* operand); 442b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 443b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Checks whether the value of a given virtual register is tagged. 444b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool HasTaggedValue(int virtual_register) const; 445b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 446b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Returns the register kind required by the given virtual register. 447b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterKind RequiredRegisterKind(int virtual_register) const; 448b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 449b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Control max function size. 450b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static int max_initial_value_ids(); 451b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 452b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void Allocate(LChunk* chunk); 453b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 454b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; } 45544f0eee88ff00398ff7f715fab053374d808c90dSteve Block const Vector<LiveRange*>* fixed_live_ranges() const { 456b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return &fixed_live_ranges_; 457b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 45844f0eee88ff00398ff7f715fab053374d808c90dSteve Block const Vector<LiveRange*>* fixed_double_live_ranges() const { 459b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return &fixed_double_live_ranges_; 460b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 461b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 462b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LChunk* chunk() const { return chunk_; } 463b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HGraph* graph() const { return graph_; } 464b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 465b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void MarkAsOsrEntry() { 466b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // There can be only one. 467b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!has_osr_entry_); 468b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Simply set a flag to find and process instruction later. 469b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch has_osr_entry_ = true; 470b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 471b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 472b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 473b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void Verify() const; 474b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 475b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 476b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 477b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void MeetRegisterConstraints(); 478b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ResolvePhis(); 479b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void BuildLiveRanges(); 480b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AllocateGeneralRegisters(); 481b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AllocateDoubleRegisters(); 482b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ConnectRanges(); 483b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ResolveControlFlow(); 484b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void PopulatePointerMaps(); 485b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ProcessOsrEntry(); 486b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AllocateRegisters(); 487b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool CanEagerlyResolveControlFlow(HBasicBlock* block) const; 488b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inline bool SafePointsAreInOrder() const; 489b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 490b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Liveness analysis support. 491b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void InitializeLivenessAnalysis(); 492b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* ComputeLiveOut(HBasicBlock* block); 493b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddInitialIntervals(HBasicBlock* block, BitVector* live_out); 494b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ProcessInstructions(HBasicBlock* block, BitVector* live); 495b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void MeetRegisterConstraints(HBasicBlock* block); 4961e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block void MeetConstraintsBetween(LInstruction* first, 4971e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* second, 498b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int gap_index); 499b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ResolvePhis(HBasicBlock* block); 500b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 501b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Helper methods for building intervals. 502b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* AllocateFixed(LUnallocated* operand, int pos, bool is_tagged); 503b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* LiveRangeFor(LOperand* operand); 504b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void Define(LifetimePosition position, LOperand* operand, LOperand* hint); 505b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void Use(LifetimePosition block_start, 506b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position, 507b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand, 508b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint); 509b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddConstraintsGapMove(int index, LOperand* from, LOperand* to); 510b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 511b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Helper methods for updating the life range lists. 512b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddToActive(LiveRange* range); 513b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddToInactive(LiveRange* range); 514b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddToUnhandledSorted(LiveRange* range); 515b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AddToUnhandledUnsorted(LiveRange* range); 516b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SortUnhandled(); 517b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool UnhandledIsSorted(); 518b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ActiveToHandled(LiveRange* range); 519b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ActiveToInactive(LiveRange* range); 520b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void InactiveToHandled(LiveRange* range); 521b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void InactiveToActive(LiveRange* range); 522b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void FreeSpillSlot(LiveRange* range); 523b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* TryReuseSpillSlot(LiveRange* range); 524b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 525b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Helper methods for allocating registers. 526b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool TryAllocateFreeReg(LiveRange* range); 527b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void AllocateBlockedReg(LiveRange* range); 528b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 529b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Live range splitting helpers. 530b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 531b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split the given range at the given position. 532b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If range starts at or after the given position then the 533b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // original range is returned. 534b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Otherwise returns the live range that starts at pos and contains 535b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // all uses from the original range that follow pos. Uses at pos will 536b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // still be owned by the original range after splitting. 537b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* SplitAt(LiveRange* range, LifetimePosition pos); 538b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 539b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split the given range in a position from the interval [start, end]. 540b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* SplitBetween(LiveRange* range, 541b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 542b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end); 543b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 544b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find a lifetime position in the interval [start, end] which 545b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // is optimal for splitting: it is either header of the outermost 546b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // loop covered by this interval or the latest possible position. 547b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition FindOptimalSplitPos(LifetimePosition start, 548b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end); 549b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 550b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Spill the given life range after position pos. 551b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SpillAfter(LiveRange* range, LifetimePosition pos); 552b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 553b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Spill the given life range after position start and up to position end. 554b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SpillBetween(LiveRange* range, 555b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 556b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end); 557b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 558b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void SplitAndSpillIntersecting(LiveRange* range); 559b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 560b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void Spill(LiveRange* range); 561b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool IsBlockBoundary(LifetimePosition pos); 562b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 563b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Helper methods for resolving control flow. 564b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void ResolveControlFlow(LiveRange* range, 565b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block, 566b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* pred); 567b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 568b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Return parallel move that should be used to connect ranges split at the 569b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // given position. 570b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LParallelMove* GetConnectingParallelMove(LifetimePosition pos); 571b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 572b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Return the block which contains give lifetime position. 573b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* GetBlock(LifetimePosition pos); 574b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 575b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Helper methods for the fixed registers. 576b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int RegisterCount() const; 577b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static int FixedLiveRangeID(int index) { return -index - 1; } 578b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static int FixedDoubleLiveRangeID(int index); 579b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* FixedLiveRangeFor(int index); 580b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* FixedDoubleLiveRangeFor(int index); 581b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* LiveRangeFor(int index); 582b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* LookupPhi(LOperand* operand) const; 5831e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* GetLastGap(HBasicBlock* block); 584b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 585b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const char* RegisterName(int allocation_index); 586b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 5871e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline bool IsGapAt(int index); 5881e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 5891e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline LInstruction* InstructionAt(int index); 590b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 5911e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block inline LGap* GapAt(int index); 5921e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 5931e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LChunk* chunk_; 594b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 595b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // During liveness analysis keep a mapping from block id to live_in sets 596b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // for blocks already analyzed. 597b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<BitVector*> live_in_sets_; 598b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 599b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Liveness analysis results. 600b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<LiveRange*> live_ranges_; 601b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 602b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Lists of live ranges 60344f0eee88ff00398ff7f715fab053374d808c90dSteve Block EmbeddedVector<LiveRange*, Register::kNumAllocatableRegisters> 60444f0eee88ff00398ff7f715fab053374d808c90dSteve Block fixed_live_ranges_; 60544f0eee88ff00398ff7f715fab053374d808c90dSteve Block EmbeddedVector<LiveRange*, DoubleRegister::kNumAllocatableRegisters> 60644f0eee88ff00398ff7f715fab053374d808c90dSteve Block fixed_double_live_ranges_; 607b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<LiveRange*> unhandled_live_ranges_; 608b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<LiveRange*> active_live_ranges_; 609b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<LiveRange*> inactive_live_ranges_; 610b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ZoneList<LiveRange*> reusable_slots_; 611b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 612b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Next virtual register number to be assigned to temporaries. 613b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int next_virtual_register_; 6149fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block int first_artificial_register_; 6159fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block GrowableBitVector double_artificial_registers_; 616b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 617b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterKind mode_; 618b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int num_registers_; 619b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 620b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HGraph* graph_; 621b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 622b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool has_osr_entry_; 623b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 624b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch DISALLOW_COPY_AND_ASSIGN(LAllocator); 625b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 626b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 627b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 628b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} } // namespace v8::internal 629b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 630b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif // V8_LITHIUM_ALLOCATOR_H_ 631