1be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org// Copyright 2012 the V8 project authors. All rights reserved. 2a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// Redistribution and use in source and binary forms, with or without 3a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// modification, are permitted provided that the following conditions are 4a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// met: 5a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// 6a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// * Redistributions of source code must retain the above copyright 7a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// notice, this list of conditions and the following disclaimer. 8a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// * Redistributions in binary form must reproduce the above 9a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// copyright notice, this list of conditions and the following 10a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// disclaimer in the documentation and/or other materials provided 11a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// with the distribution. 12a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// * Neither the name of Google Inc. nor the names of its 13a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// contributors may be used to endorse or promote products derived 14a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// from this software without specific prior written permission. 15a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// 16a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 28ea88ce93dcb41a9200ec8747ae7642a5db1f4ce7sgjesse@chromium.org#include "v8.h" 2983aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org#include "lithium-allocator-inl.h" 30a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 31a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#include "hydrogen.h" 32a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#include "string-stream.h" 33a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 34a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#if V8_TARGET_ARCH_IA32 35a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#include "ia32/lithium-ia32.h" 36a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#elif V8_TARGET_ARCH_X64 37a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#include "x64/lithium-x64.h" 38a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#elif V8_TARGET_ARCH_ARM 39a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#include "arm/lithium-arm.h" 407516f05132429850aa326421ed3e25f23b4c071blrn@chromium.org#elif V8_TARGET_ARCH_MIPS 417516f05132429850aa326421ed3e25f23b4c071blrn@chromium.org#include "mips/lithium-mips.h" 42a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#else 43a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#error "Unknown architecture." 44a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#endif 45a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 46a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgnamespace v8 { 47a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgnamespace internal { 48a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 49a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgstatic inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) { 50a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return a.Value() < b.Value() ? a : b; 51a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 52a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 53a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 54a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgstatic inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) { 55a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return a.Value() > b.Value() ? a : b; 56a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 57a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 58a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 59f005df6c3232e65028420519fbab7284bc9b33aedanno@chromium.orgUsePosition::UsePosition(LifetimePosition pos, 60f005df6c3232e65028420519fbab7284bc9b33aedanno@chromium.org LOperand* operand, 61f005df6c3232e65028420519fbab7284bc9b33aedanno@chromium.org LOperand* hint) 620a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org : operand_(operand), 63f005df6c3232e65028420519fbab7284bc9b33aedanno@chromium.org hint_(hint), 640a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org pos_(pos), 650a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org next_(NULL), 660a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org requires_reg_(false), 670a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org register_beneficial_(true) { 680a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org if (operand_ != NULL && operand_->IsUnallocated()) { 690a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org LUnallocated* unalloc = LUnallocated::cast(operand_); 700a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org requires_reg_ = unalloc->HasRegisterPolicy(); 710a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org register_beneficial_ = !unalloc->HasAnyPolicy(); 72a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 730a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org ASSERT(pos_.IsValid()); 74a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 75a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 760a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org 770a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.orgbool UsePosition::HasHint() const { 780a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org return hint_ != NULL && !hint_->IsUnallocated(); 79a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 80a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 81a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 82a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool UsePosition::RequiresRegister() const { 83a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return requires_reg_; 84a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 85a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 86a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 87a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool UsePosition::RegisterIsBeneficial() const { 88a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return register_beneficial_; 89a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 90a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 91a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 92be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.orgvoid UseInterval::SplitAt(LifetimePosition pos, Zone* zone) { 93a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(Contains(pos) && pos.Value() != start().Value()); 94be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org UseInterval* after = new(zone) UseInterval(pos, end_); 95a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org after->next_ = next_; 96a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org next_ = after; 97a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org end_ = pos; 98a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 99a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 100a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 101a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#ifdef DEBUG 102a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 103a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 104a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LiveRange::Verify() const { 105a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* cur = first_pos_; 106a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (cur != NULL) { 107a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(Start().Value() <= cur->pos().Value() && 108a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org cur->pos().Value() <= End().Value()); 109a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org cur = cur->next(); 110a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 111a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 112a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 113a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 114a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool LiveRange::HasOverlap(UseInterval* target) const { 115a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UseInterval* current_interval = first_interval_; 116a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (current_interval != NULL) { 117a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Intervals overlap if the start of one is contained in the other. 118a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (current_interval->Contains(target->start()) || 119a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org target->Contains(current_interval->start())) { 120a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return true; 121a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 122a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org current_interval = current_interval->next(); 123a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 124a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return false; 125a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 126a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 127a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 128a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#endif 129a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 130a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 131be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.orgLiveRange::LiveRange(int id, Zone* zone) 1320a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org : id_(id), 1330a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org spilled_(false), 1342c4567981e65b51f161283f8635e110a73629c9ddanno@chromium.org is_double_(false), 1350a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org assigned_register_(kInvalidAssignment), 1360a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org last_interval_(NULL), 1370a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org first_interval_(NULL), 1380a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org first_pos_(NULL), 1390a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org parent_(NULL), 1400a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org next_(NULL), 1410a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org current_interval_(NULL), 1420a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org last_processed_use_(NULL), 14357ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org current_hint_operand_(NULL), 144be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org spill_operand_(new(zone) LOperand()), 145659ceec4628056d3c6e7076c850fba1c412cbb8ayangguo@chromium.org spill_start_index_(kMaxInt) { } 1460a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org 1470a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org 148be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.orgvoid LiveRange::set_assigned_register(int reg, 149be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org RegisterKind register_kind, 150be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org Zone* zone) { 1510a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org ASSERT(!HasRegisterAssigned() && !IsSpilled()); 1520a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org assigned_register_ = reg; 1532c4567981e65b51f161283f8635e110a73629c9ddanno@chromium.org is_double_ = (register_kind == DOUBLE_REGISTERS); 154be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org ConvertOperands(zone); 1550a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org} 1560a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org 1570a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org 158be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.orgvoid LiveRange::MakeSpilled(Zone* zone) { 1590a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org ASSERT(!IsSpilled()); 1600a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org ASSERT(TopLevel()->HasAllocatedSpillOperand()); 1610a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org spilled_ = true; 1620a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org assigned_register_ = kInvalidAssignment; 163be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org ConvertOperands(zone); 1640a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org} 1650a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org 1660a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org 1670a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.orgbool LiveRange::HasAllocatedSpillOperand() const { 168659ceec4628056d3c6e7076c850fba1c412cbb8ayangguo@chromium.org ASSERT(spill_operand_ != NULL); 169659ceec4628056d3c6e7076c850fba1c412cbb8ayangguo@chromium.org return !spill_operand_->IsIgnored(); 1700a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org} 1710a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org 1720a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org 1730a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.orgvoid LiveRange::SetSpillOperand(LOperand* operand) { 1740a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org ASSERT(!operand->IsUnallocated()); 1750a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org ASSERT(spill_operand_ != NULL); 176659ceec4628056d3c6e7076c850fba1c412cbb8ayangguo@chromium.org ASSERT(spill_operand_->IsIgnored()); 1770a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org spill_operand_->ConvertTo(operand->kind(), operand->index()); 1780a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org} 1790a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org 1800a4e901cdfb5505a896d30aa8c2e04fce0fbe069vegorov@chromium.org 181a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgUsePosition* LiveRange::NextUsePosition(LifetimePosition start) { 182a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* use_pos = last_processed_use_; 183a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (use_pos == NULL) use_pos = first_pos(); 184a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (use_pos != NULL && use_pos->pos().Value() < start.Value()) { 185a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos = use_pos->next(); 186a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 187a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org last_processed_use_ = use_pos; 188a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return use_pos; 189a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 190a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 191a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 192a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgUsePosition* LiveRange::NextUsePositionRegisterIsBeneficial( 193a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition start) { 194a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* pos = NextUsePosition(start); 195a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (pos != NULL && !pos->RegisterIsBeneficial()) { 196a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org pos = pos->next(); 197a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 198a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return pos; 199a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 200a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 201a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 202876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.orgUsePosition* LiveRange::PreviousUsePositionRegisterIsBeneficial( 203876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org LifetimePosition start) { 204876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org UsePosition* pos = first_pos(); 205876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org UsePosition* prev = NULL; 206876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org while (pos != NULL && pos->pos().Value() < start.Value()) { 207876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org if (pos->RegisterIsBeneficial()) prev = pos; 208876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org pos = pos->next(); 209876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org } 210876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org return prev; 211876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org} 212876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org 213876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org 214a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgUsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) { 215a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* pos = NextUsePosition(start); 216a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (pos != NULL && !pos->RequiresRegister()) { 217a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org pos = pos->next(); 218a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 219a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return pos; 220a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 221a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 222a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 223a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool LiveRange::CanBeSpilled(LifetimePosition pos) { 224a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // We cannot spill a live range that has a use requiring a register 225a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // at the current or the immediate next position. 226a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* use_pos = NextRegisterPosition(pos); 227a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (use_pos == NULL) return true; 228ecb9dd69014d1d8aad1a08bd8b593fbf94107324svenpanne@chromium.org return 229ecb9dd69014d1d8aad1a08bd8b593fbf94107324svenpanne@chromium.org use_pos->pos().Value() > pos.NextInstruction().InstructionEnd().Value(); 230a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 231a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 232a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 233be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.orgLOperand* LiveRange::CreateAssignedOperand(Zone* zone) { 234a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* op = NULL; 235a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (HasRegisterAssigned()) { 236a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!IsSpilled()); 2375f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (IsDouble()) { 2387028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org op = LDoubleRegister::Create(assigned_register(), zone); 239a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 2407028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org op = LRegister::Create(assigned_register(), zone); 241a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 242a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else if (IsSpilled()) { 243a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!HasRegisterAssigned()); 244a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org op = TopLevel()->GetSpillOperand(); 245a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!op->IsUnallocated()); 246a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 247be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org LUnallocated* unalloc = new(zone) LUnallocated(LUnallocated::NONE); 248a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org unalloc->set_virtual_register(id_); 249a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org op = unalloc; 250a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 251a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return op; 252a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 253a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 254a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 255a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgUseInterval* LiveRange::FirstSearchIntervalForPosition( 256a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition position) const { 257a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (current_interval_ == NULL) return first_interval_; 258a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (current_interval_->start().Value() > position.Value()) { 259a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org current_interval_ = NULL; 260a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return first_interval_; 261a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 262a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return current_interval_; 263a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 264a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 265a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 266a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LiveRange::AdvanceLastProcessedMarker( 267a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UseInterval* to_start_of, LifetimePosition but_not_past) const { 268a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (to_start_of == NULL) return; 269a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (to_start_of->start().Value() > but_not_past.Value()) return; 270a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition start = 271a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org current_interval_ == NULL ? LifetimePosition::Invalid() 272a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org : current_interval_->start(); 273a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (to_start_of->start().Value() > start.Value()) { 274a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org current_interval_ = to_start_of; 275a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 276a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 277a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 278a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 279be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.orgvoid LiveRange::SplitAt(LifetimePosition position, 280be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org LiveRange* result, 281be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org Zone* zone) { 2825f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org ASSERT(Start().Value() < position.Value()); 283a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(result->IsEmpty()); 284a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Find the last interval that ends before the position. If the 285a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // position is contained in one of the intervals in the chain, we 286a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // split that interval and use the first part. 287a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UseInterval* current = FirstSearchIntervalForPosition(position); 2885f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 2895f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // If the split position coincides with the beginning of a use interval 2905f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // we need to split use positons in a special way. 2915f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org bool split_at_start = false; 2925f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 293d2be901879306d8ff27e78e37783028d581d46fcricow@chromium.org if (current->start().Value() == position.Value()) { 294d2be901879306d8ff27e78e37783028d581d46fcricow@chromium.org // When splitting at start we need to locate the previous use interval. 295d2be901879306d8ff27e78e37783028d581d46fcricow@chromium.org current = first_interval_; 296d2be901879306d8ff27e78e37783028d581d46fcricow@chromium.org } 297d2be901879306d8ff27e78e37783028d581d46fcricow@chromium.org 298a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (current != NULL) { 299a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (current->Contains(position)) { 300be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org current->SplitAt(position, zone); 301a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org break; 302a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 303a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UseInterval* next = current->next(); 3045f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (next->start().Value() >= position.Value()) { 3055f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org split_at_start = (next->start().Value() == position.Value()); 3065f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org break; 3075f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } 308a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org current = next; 309a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 310a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 311a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Partition original use intervals to the two live ranges. 312a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UseInterval* before = current; 313a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UseInterval* after = before->next(); 314a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org result->last_interval_ = (last_interval_ == before) 315a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ? after // Only interval in the range after split. 316a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org : last_interval_; // Last interval of the original range. 317a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org result->first_interval_ = after; 318a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org last_interval_ = before; 319a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 320a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Find the last use position before the split and the first use 321a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // position after it. 322a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* use_after = first_pos_; 323a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* use_before = NULL; 3245f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (split_at_start) { 3255f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // The split position coincides with the beginning of a use interval (the 3265f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // end of a lifetime hole). Use at this position should be attributed to 3275f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // the split child because split child owns use interval covering it. 3285f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org while (use_after != NULL && use_after->pos().Value() < position.Value()) { 3295f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org use_before = use_after; 3305f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org use_after = use_after->next(); 3315f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } 3325f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } else { 3335f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org while (use_after != NULL && use_after->pos().Value() <= position.Value()) { 3345f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org use_before = use_after; 3355f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org use_after = use_after->next(); 3365f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } 337a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 338a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 339a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Partition original use positions to the two live ranges. 340a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (use_before != NULL) { 341a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_before->next_ = NULL; 342a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 343a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_pos_ = NULL; 344a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 345a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org result->first_pos_ = use_after; 346a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 347d2be901879306d8ff27e78e37783028d581d46fcricow@chromium.org // Discard cached iteration state. It might be pointing 348d2be901879306d8ff27e78e37783028d581d46fcricow@chromium.org // to the use that no longer belongs to this live range. 349d2be901879306d8ff27e78e37783028d581d46fcricow@chromium.org last_processed_use_ = NULL; 350d2be901879306d8ff27e78e37783028d581d46fcricow@chromium.org current_interval_ = NULL; 351d2be901879306d8ff27e78e37783028d581d46fcricow@chromium.org 352a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Link the new live range in the chain before any of the other 353a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // ranges linked from the range before the split. 354a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org result->parent_ = (parent_ == NULL) ? this : parent_; 355a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org result->next_ = next_; 356a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org next_ = result; 357a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 358a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#ifdef DEBUG 359a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org Verify(); 360a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org result->Verify(); 361a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#endif 362a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 363a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 364a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 365a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// This implements an ordering on live ranges so that they are ordered by their 366a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// start positions. This is needed for the correctness of the register 367a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// allocation algorithm. If two live ranges start at the same offset then there 368a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// is a tie breaker based on where the value is first used. This part of the 369a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// ordering is merely a heuristic. 370a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const { 371a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition start = Start(); 372a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition other_start = other->Start(); 373a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (start.Value() == other_start.Value()) { 37457ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org UsePosition* pos = first_pos(); 375a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (pos == NULL) return false; 376a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* other_pos = other->first_pos(); 377a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (other_pos == NULL) return true; 378a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return pos->pos().Value() < other_pos->pos().Value(); 379a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 380a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return start.Value() < other_start.Value(); 381a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 382a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 383a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 384a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LiveRange::ShortenTo(LifetimePosition start) { 385a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LAllocator::TraceAlloc("Shorten live range %d to [%d\n", id_, start.Value()); 386a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(first_interval_ != NULL); 387a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(first_interval_->start().Value() <= start.Value()); 388a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(start.Value() < first_interval_->end().Value()); 389a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_interval_->set_start(start); 390a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 391a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 392a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 393be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.orgvoid LiveRange::EnsureInterval(LifetimePosition start, 394be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org LifetimePosition end, 395be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org Zone* zone) { 396a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LAllocator::TraceAlloc("Ensure live range %d in interval [%d %d[\n", 397a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org id_, 398a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org start.Value(), 399a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org end.Value()); 400a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition new_end = end; 401a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (first_interval_ != NULL && 402a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_interval_->start().Value() <= end.Value()) { 403a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (first_interval_->end().Value() > end.Value()) { 404a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org new_end = first_interval_->end(); 405a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 406a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_interval_ = first_interval_->next(); 407a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 408a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 409be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org UseInterval* new_interval = new(zone) UseInterval(start, new_end); 410a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org new_interval->next_ = first_interval_; 411a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_interval_ = new_interval; 412a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (new_interval->next() == NULL) { 413a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org last_interval_ = new_interval; 414a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 415a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 416a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 417a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 418be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.orgvoid LiveRange::AddUseInterval(LifetimePosition start, 419be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org LifetimePosition end, 420be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org Zone* zone) { 421a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LAllocator::TraceAlloc("Add to live range %d interval [%d %d[\n", 422a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org id_, 423a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org start.Value(), 424a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org end.Value()); 425a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (first_interval_ == NULL) { 426be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org UseInterval* interval = new(zone) UseInterval(start, end); 427a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_interval_ = interval; 428a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org last_interval_ = interval; 429a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 430a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (end.Value() == first_interval_->start().Value()) { 431a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_interval_->set_start(start); 432a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else if (end.Value() < first_interval_->start().Value()) { 433be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org UseInterval* interval = new(zone) UseInterval(start, end); 434a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org interval->set_next(first_interval_); 435a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_interval_ = interval; 436a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 437a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Order of instruction's processing (see ProcessInstructions) guarantees 438a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // that each new use interval either precedes or intersects with 439a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // last added interval. 440a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(start.Value() < first_interval_->end().Value()); 441a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_interval_->start_ = Min(start, first_interval_->start_); 442a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_interval_->end_ = Max(end, first_interval_->end_); 443a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 444a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 445a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 446a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 447a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 448f005df6c3232e65028420519fbab7284bc9b33aedanno@chromium.orgvoid LiveRange::AddUsePosition(LifetimePosition pos, 449f005df6c3232e65028420519fbab7284bc9b33aedanno@chromium.org LOperand* operand, 450f005df6c3232e65028420519fbab7284bc9b33aedanno@chromium.org LOperand* hint, 451f005df6c3232e65028420519fbab7284bc9b33aedanno@chromium.org Zone* zone) { 452a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LAllocator::TraceAlloc("Add to live range %d use position %d\n", 453a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org id_, 454a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org pos.Value()); 455f005df6c3232e65028420519fbab7284bc9b33aedanno@chromium.org UsePosition* use_pos = new(zone) UsePosition(pos, operand, hint); 45657ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org UsePosition* prev_hint = NULL; 457a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* prev = NULL; 458a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* current = first_pos_; 459a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (current != NULL && current->pos().Value() < pos.Value()) { 46057ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org prev_hint = current->HasHint() ? current : prev_hint; 461a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org prev = current; 462a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org current = current->next(); 463a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 464a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 465a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (prev == NULL) { 466a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos->set_next(first_pos_); 467a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_pos_ = use_pos; 468a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 469a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos->next_ = prev->next_; 470a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org prev->next_ = use_pos; 471a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 47257ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org 47357ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org if (prev_hint == NULL && use_pos->HasHint()) { 47457ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org current_hint_operand_ = hint; 47557ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org } 476a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 477a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 478a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 479be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.orgvoid LiveRange::ConvertOperands(Zone* zone) { 480be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org LOperand* op = CreateAssignedOperand(zone); 481a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* use_pos = first_pos(); 482a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (use_pos != NULL) { 483a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(Start().Value() <= use_pos->pos().Value() && 484a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos->pos().Value() <= End().Value()); 485a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 486a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (use_pos->HasOperand()) { 487a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(op->IsRegister() || op->IsDoubleRegister() || 488a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org !use_pos->RequiresRegister()); 489a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos->operand()->ConvertTo(op->kind(), op->index()); 490a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 491a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos = use_pos->next(); 492a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 493a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 494a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 495a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 496a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool LiveRange::CanCover(LifetimePosition position) const { 497a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (IsEmpty()) return false; 498a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return Start().Value() <= position.Value() && 499a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org position.Value() < End().Value(); 500a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 501a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 502a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 503a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool LiveRange::Covers(LifetimePosition position) { 504a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!CanCover(position)) return false; 505a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UseInterval* start_search = FirstSearchIntervalForPosition(position); 506a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (UseInterval* interval = start_search; 507a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org interval != NULL; 508a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org interval = interval->next()) { 509a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(interval->next() == NULL || 510a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org interval->next()->start().Value() >= interval->start().Value()); 511a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AdvanceLastProcessedMarker(interval, position); 512a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (interval->Contains(position)) return true; 513a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (interval->start().Value() > position.Value()) return false; 514a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 515a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return false; 516a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 517a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 518a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 519a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgLifetimePosition LiveRange::FirstIntersection(LiveRange* other) { 520a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UseInterval* b = other->first_interval(); 521a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (b == NULL) return LifetimePosition::Invalid(); 522a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition advance_last_processed_up_to = b->start(); 523a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UseInterval* a = FirstSearchIntervalForPosition(b->start()); 524a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (a != NULL && b != NULL) { 525a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (a->start().Value() > other->End().Value()) break; 526a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (b->start().Value() > End().Value()) break; 527a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition cur_intersection = a->Intersect(b); 528a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (cur_intersection.IsValid()) { 529a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return cur_intersection; 530a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 531a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (a->start().Value() < b->start().Value()) { 532a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org a = a->next(); 5335f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (a == NULL || a->start().Value() > other->End().Value()) break; 534a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AdvanceLastProcessedMarker(a, advance_last_processed_up_to); 535a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 536a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org b = b->next(); 537a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 538a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 539a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return LifetimePosition::Invalid(); 540a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 541a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 542a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 543b08986cb66c3f6687247cb6da186c1e73057e399whesse@chromium.orgLAllocator::LAllocator(int num_values, HGraph* graph) 5441510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org : zone_(graph->isolate()), 545be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org chunk_(NULL), 5461510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org live_in_sets_(graph->blocks()->length(), zone()), 5471510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org live_ranges_(num_values * 2, zone()), 548b08986cb66c3f6687247cb6da186c1e73057e399whesse@chromium.org fixed_live_ranges_(NULL), 549b08986cb66c3f6687247cb6da186c1e73057e399whesse@chromium.org fixed_double_live_ranges_(NULL), 5501510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org unhandled_live_ranges_(num_values * 2, zone()), 5511510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org active_live_ranges_(8, zone()), 5521510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org inactive_live_ranges_(8, zone()), 5531510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org reusable_slots_(8, zone()), 554b08986cb66c3f6687247cb6da186c1e73057e399whesse@chromium.org next_virtual_register_(num_values), 555b08986cb66c3f6687247cb6da186c1e73057e399whesse@chromium.org first_artificial_register_(num_values), 5562c4567981e65b51f161283f8635e110a73629c9ddanno@chromium.org mode_(GENERAL_REGISTERS), 557b08986cb66c3f6687247cb6da186c1e73057e399whesse@chromium.org num_registers_(-1), 558b08986cb66c3f6687247cb6da186c1e73057e399whesse@chromium.org graph_(graph), 559be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org has_osr_entry_(false), 560be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org allocation_ok_(true) { } 561b08986cb66c3f6687247cb6da186c1e73057e399whesse@chromium.org 562b08986cb66c3f6687247cb6da186c1e73057e399whesse@chromium.org 563a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::InitializeLivenessAnalysis() { 564a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Initialize the live_in sets for each block to NULL. 56583aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org int block_count = graph_->blocks()->length(); 5667028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org live_in_sets_.Initialize(block_count, zone()); 5677028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org live_in_sets_.AddBlock(NULL, block_count, zone()); 568a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 569a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 570a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 571a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgBitVector* LAllocator::ComputeLiveOut(HBasicBlock* block) { 572a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Compute live out for the given block, except not including backward 573a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // successor edges. 5741510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org BitVector* live_out = new(zone()) BitVector(next_virtual_register_, zone()); 575a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 576a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Process all successor blocks. 5776d786c9805481bd13ecb29c3155540f2f32950e1svenpanne@chromium.org for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) { 578a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Add values live on entry to the successor. Note the successor's 579a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // live_in will not be computed yet for backwards edges. 5806d786c9805481bd13ecb29c3155540f2f32950e1svenpanne@chromium.org HBasicBlock* successor = it.Current(); 581a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org BitVector* live_in = live_in_sets_[successor->block_id()]; 582a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (live_in != NULL) live_out->Union(*live_in); 583a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 584a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // All phi input operands corresponding to this successor edge are live 585a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // out from this block. 586a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int index = successor->PredecessorIndexOf(block); 587a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org const ZoneList<HPhi*>* phis = successor->phis(); 588a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < phis->length(); ++i) { 589a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HPhi* phi = phis->at(i); 590a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!phi->OperandAt(index)->IsConstant()) { 591a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org live_out->Add(phi->OperandAt(index)->id()); 592a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 593a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 594a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 595a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 596a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return live_out; 597a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 598a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 599a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 600a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::AddInitialIntervals(HBasicBlock* block, 601a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org BitVector* live_out) { 602a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Add an interval that includes the entire block to the live range for 603a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // each live_out value. 604a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition start = LifetimePosition::FromInstructionIndex( 605a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org block->first_instruction_index()); 606a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition end = LifetimePosition::FromInstructionIndex( 6075f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org block->last_instruction_index()).NextInstruction(); 608a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org BitVector::Iterator iterator(live_out); 609a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (!iterator.Done()) { 610a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int operand_index = iterator.Current(); 611a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = LiveRangeFor(operand_index); 6121510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org range->AddUseInterval(start, end, zone()); 613a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org iterator.Advance(); 614a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 615a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 616a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 617a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 618a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgint LAllocator::FixedDoubleLiveRangeID(int index) { 619a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org return -index - 1 - Register::kMaxNumAllocatableRegisters; 620a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 621a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 622a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 623a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgLOperand* LAllocator::AllocateFixed(LUnallocated* operand, 624a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int pos, 625a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool is_tagged) { 626a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Allocating fixed reg for op %d\n", operand->virtual_register()); 627a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(operand->HasFixedPolicy()); 62857ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org if (operand->HasFixedSlotPolicy()) { 62957ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org operand->ConvertTo(LOperand::STACK_SLOT, operand->fixed_slot_index()); 63057ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org } else if (operand->HasFixedRegisterPolicy()) { 63157ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org int reg_index = operand->fixed_register_index(); 632a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org operand->ConvertTo(LOperand::REGISTER, reg_index); 63357ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org } else if (operand->HasFixedDoubleRegisterPolicy()) { 63457ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org int reg_index = operand->fixed_register_index(); 635a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org operand->ConvertTo(LOperand::DOUBLE_REGISTER, reg_index); 636a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 637a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UNREACHABLE(); 638a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 639a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (is_tagged) { 640a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Fixed reg is tagged at %d\n", pos); 64183aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LInstruction* instr = InstructionAt(pos); 642a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (instr->HasPointerMap()) { 6431510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org instr->pointer_map()->RecordPointer(operand, chunk()->zone()); 644a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 645a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 646a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return operand; 647a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 648a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 649a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 650a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgLiveRange* LAllocator::FixedLiveRangeFor(int index) { 651a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org ASSERT(index < Register::kMaxNumAllocatableRegisters); 652a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* result = fixed_live_ranges_[index]; 653a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (result == NULL) { 6541510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org result = new(zone()) LiveRange(FixedLiveRangeID(index), chunk()->zone()); 655a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(result->IsFixed()); 6561510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org SetLiveRangeAssignedRegister(result, index, GENERAL_REGISTERS); 657a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org fixed_live_ranges_[index] = result; 658a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 659a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return result; 660a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 661a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 662a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 663a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgLiveRange* LAllocator::FixedDoubleLiveRangeFor(int index) { 664a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org ASSERT(index < DoubleRegister::NumAllocatableRegisters()); 665a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* result = fixed_double_live_ranges_[index]; 666a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (result == NULL) { 6671510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org result = new(zone()) LiveRange(FixedDoubleLiveRangeID(index), 6681510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 669a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(result->IsFixed()); 6701510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org SetLiveRangeAssignedRegister(result, index, DOUBLE_REGISTERS); 671a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org fixed_double_live_ranges_[index] = result; 672a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 673a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return result; 674a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 675a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 676b08986cb66c3f6687247cb6da186c1e73057e399whesse@chromium.org 677a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgLiveRange* LAllocator::LiveRangeFor(int index) { 678a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (index >= live_ranges_.length()) { 6797028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org live_ranges_.AddBlock(NULL, index - live_ranges_.length() + 1, zone()); 680a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 681a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* result = live_ranges_[index]; 682a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (result == NULL) { 6831510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org result = new(zone()) LiveRange(index, chunk()->zone()); 684a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org live_ranges_[index] = result; 685a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 686a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return result; 687a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 688a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 689a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 69083aa54905e559090bea7771b83f188762cfcf082ricow@chromium.orgLGap* LAllocator::GetLastGap(HBasicBlock* block) { 691a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int last_instruction = block->last_instruction_index(); 692a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int index = chunk_->NearestGapPos(last_instruction); 69383aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org return GapAt(index); 694a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 695a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 696a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 697a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgHPhi* LAllocator::LookupPhi(LOperand* operand) const { 698a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!operand->IsUnallocated()) return NULL; 699fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org int index = LUnallocated::cast(operand)->virtual_register(); 70083aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org HValue* instr = graph_->LookupValue(index); 701a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (instr != NULL && instr->IsPhi()) { 702a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return HPhi::cast(instr); 703a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 704a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return NULL; 705a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 706a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 707a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 708a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgLiveRange* LAllocator::LiveRangeFor(LOperand* operand) { 709a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (operand->IsUnallocated()) { 710a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return LiveRangeFor(LUnallocated::cast(operand)->virtual_register()); 711a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else if (operand->IsRegister()) { 712a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return FixedLiveRangeFor(operand->index()); 713a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else if (operand->IsDoubleRegister()) { 714a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return FixedDoubleLiveRangeFor(operand->index()); 715a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 716a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return NULL; 717a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 718a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 719a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 720a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 721a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::Define(LifetimePosition position, 722a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* operand, 723a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* hint) { 724a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = LiveRangeFor(operand); 725a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range == NULL) return; 726a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 727a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range->IsEmpty() || range->Start().Value() > position.Value()) { 728a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Can happen if there is a definition without use. 7291510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org range->AddUseInterval(position, position.NextInstruction(), zone()); 7301510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org range->AddUsePosition(position.NextInstruction(), NULL, NULL, zone()); 731a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 732a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org range->ShortenTo(position); 733a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 734a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 735a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (operand->IsUnallocated()) { 736a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LUnallocated* unalloc_operand = LUnallocated::cast(operand); 7371510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org range->AddUsePosition(position, unalloc_operand, hint, zone()); 738a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 739a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 740a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 741a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 742a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::Use(LifetimePosition block_start, 743a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition position, 744a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* operand, 745a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* hint) { 746a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = LiveRangeFor(operand); 747a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range == NULL) return; 748a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (operand->IsUnallocated()) { 749a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LUnallocated* unalloc_operand = LUnallocated::cast(operand); 7501510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org range->AddUsePosition(position, unalloc_operand, hint, zone()); 751a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 7521510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org range->AddUseInterval(block_start, position, zone()); 753a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 754a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 755a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 756a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::AddConstraintsGapMove(int index, 757a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* from, 758a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* to) { 75983aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LGap* gap = GapAt(index); 7601510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, 7611510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 762a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (from->IsUnallocated()) { 763a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org const ZoneList<LMoveOperands>* move_operands = move->move_operands(); 764a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < move_operands->length(); ++i) { 765a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LMoveOperands cur = move_operands->at(i); 7660511e24c6ebf94594a7e03bdcd58157ac2971d69erik.corry@gmail.com LOperand* cur_to = cur.destination(); 767a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (cur_to->IsUnallocated()) { 768fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org if (LUnallocated::cast(cur_to)->virtual_register() == 769fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org LUnallocated::cast(from)->virtual_register()) { 7701510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org move->AddMove(cur.source(), to, chunk()->zone()); 771a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return; 772a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 773a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 774a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 775a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 7761510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org move->AddMove(from, to, chunk()->zone()); 777a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 778a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 779a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 780a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::MeetRegisterConstraints(HBasicBlock* block) { 781a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int start = block->first_instruction_index(); 782a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int end = block->last_instruction_index(); 783a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org if (start == -1) return; 784a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = start; i <= end; ++i) { 78583aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org if (IsGapAt(i)) { 78683aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LInstruction* instr = NULL; 78783aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LInstruction* prev_instr = NULL; 78883aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org if (i < end) instr = InstructionAt(i + 1); 78983aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org if (i > start) prev_instr = InstructionAt(i - 1); 79083aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org MeetConstraintsBetween(prev_instr, instr, i); 791994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return; 792a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 793a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 794a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 795a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 796a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 79783aa54905e559090bea7771b83f188762cfcf082ricow@chromium.orgvoid LAllocator::MeetConstraintsBetween(LInstruction* first, 79883aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LInstruction* second, 799a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int gap_index) { 800a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Handle fixed temporaries. 801a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (first != NULL) { 802e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org for (TempIterator it(first); !it.Done(); it.Advance()) { 803e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org LUnallocated* temp = LUnallocated::cast(it.Current()); 804a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (temp->HasFixedPolicy()) { 805a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AllocateFixed(temp, gap_index - 1, false); 806a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 807a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 808a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 809a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 810a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Handle fixed output operand. 811a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (first != NULL && first->Output() != NULL) { 812a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LUnallocated* first_output = LUnallocated::cast(first->Output()); 813fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org LiveRange* range = LiveRangeFor(first_output->virtual_register()); 814a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool assigned = false; 815a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (first_output->HasFixedPolicy()) { 8161510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LUnallocated* output_copy = first_output->CopyUnconstrained( 8171510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 818fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org bool is_tagged = HasTaggedValue(first_output->virtual_register()); 819a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AllocateFixed(first_output, gap_index, is_tagged); 820a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 821a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // This value is produced on the stack, we never need to spill it. 822a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (first_output->IsStackSlot()) { 823a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org range->SetSpillOperand(first_output); 824a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org range->SetSpillStartIndex(gap_index - 1); 825a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org assigned = true; 826a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 827a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org chunk_->AddGapMove(gap_index, first_output, output_copy); 828a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 829a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 830a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!assigned) { 831a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org range->SetSpillStartIndex(gap_index); 832a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 833a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // This move to spill operand is not a real use. Liveness analysis 834a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // and splitting of live ranges do not account for it. 835a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Thus it should be inserted to a lifetime position corresponding to 836a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // the instruction end. 83783aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LGap* gap = GapAt(gap_index); 8381510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LParallelMove* move = gap->GetOrCreateParallelMove(LGap::BEFORE, 8391510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 8401510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org move->AddMove(first_output, range->GetSpillOperand(), 8411510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 842a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 843a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 844a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 845a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Handle fixed input operands of second instruction. 846a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (second != NULL) { 847e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org for (UseIterator it(second); !it.Done(); it.Advance()) { 848e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org LUnallocated* cur_input = LUnallocated::cast(it.Current()); 849a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (cur_input->HasFixedPolicy()) { 8501510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LUnallocated* input_copy = cur_input->CopyUnconstrained( 8511510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 852fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org bool is_tagged = HasTaggedValue(cur_input->virtual_register()); 853a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AllocateFixed(cur_input, gap_index + 1, is_tagged); 854a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AddConstraintsGapMove(gap_index, input_copy, cur_input); 85557ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org } else if (cur_input->HasWritableRegisterPolicy()) { 856c6c5718277d4047fad1e034396228ce15571b5a4sgjesse@chromium.org // The live range of writable input registers always goes until the end 857c6c5718277d4047fad1e034396228ce15571b5a4sgjesse@chromium.org // of the instruction. 858c6c5718277d4047fad1e034396228ce15571b5a4sgjesse@chromium.org ASSERT(!cur_input->IsUsedAtStart()); 859c6c5718277d4047fad1e034396228ce15571b5a4sgjesse@chromium.org 8601510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LUnallocated* input_copy = cur_input->CopyUnconstrained( 8611510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 8622bda543d75374afd8d7e98f56ca99a57ae1b7bd1svenpanne@chromium.org int vreg = GetVirtualRegister(); 863994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return; 8642bda543d75374afd8d7e98f56ca99a57ae1b7bd1svenpanne@chromium.org cur_input->set_virtual_register(vreg); 8655d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org 8665d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org if (RequiredRegisterKind(input_copy->virtual_register()) == 8675d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org DOUBLE_REGISTERS) { 8685d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org double_artificial_registers_.Add( 869be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org cur_input->virtual_register() - first_artificial_register_, 8701510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org zone()); 8715d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org } 8725d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org 873a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AddConstraintsGapMove(gap_index, input_copy, cur_input); 874a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 875a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 876a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 877a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 878a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Handle "output same as input" for second instruction. 879a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (second != NULL && second->Output() != NULL) { 880a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LUnallocated* second_output = LUnallocated::cast(second->Output()); 881a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (second_output->HasSameAsInputPolicy()) { 88283aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LUnallocated* cur_input = LUnallocated::cast(second->FirstInput()); 883fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org int output_vreg = second_output->virtual_register(); 884fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org int input_vreg = cur_input->virtual_register(); 885a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 8861510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LUnallocated* input_copy = cur_input->CopyUnconstrained( 8871510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 888a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org cur_input->set_virtual_register(second_output->virtual_register()); 889a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AddConstraintsGapMove(gap_index, input_copy, cur_input); 890a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 891a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (HasTaggedValue(input_vreg) && !HasTaggedValue(output_vreg)) { 892a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int index = gap_index + 1; 89383aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LInstruction* instr = InstructionAt(index); 894a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (instr->HasPointerMap()) { 8951510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org instr->pointer_map()->RecordPointer(input_copy, chunk()->zone()); 896a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 897a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else if (!HasTaggedValue(input_vreg) && HasTaggedValue(output_vreg)) { 898a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // The input is assumed to immediately have a tagged representation, 899a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // before the pointer map can be used. I.e. the pointer map at the 900a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // instruction will include the output operand (whose value at the 901a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // beginning of the instruction is equal to the input operand). If 902a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // this is not desired, then the pointer map at this instruction needs 903a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // to be adjusted manually. 904a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 905a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 906a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 907a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 908a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 909a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 910a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) { 911a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int block_start = block->first_instruction_index(); 912a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int index = block->last_instruction_index(); 913a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 914a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition block_start_position = 915a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition::FromInstructionIndex(block_start); 916a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 917a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (index >= block_start) { 918a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition curr_position = 919a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition::FromInstructionIndex(index); 920a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 92183aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org if (IsGapAt(index)) { 922a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // We have a gap at this position. 92383aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LGap* gap = GapAt(index); 9241510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, 9251510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 926a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org const ZoneList<LMoveOperands>* move_operands = move->move_operands(); 927a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < move_operands->length(); ++i) { 928a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LMoveOperands* cur = &move_operands->at(i); 929a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (cur->IsIgnored()) continue; 9300511e24c6ebf94594a7e03bdcd58157ac2971d69erik.corry@gmail.com LOperand* from = cur->source(); 9310511e24c6ebf94594a7e03bdcd58157ac2971d69erik.corry@gmail.com LOperand* to = cur->destination(); 932a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HPhi* phi = LookupPhi(to); 933a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* hint = to; 934a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (phi != NULL) { 935a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // This is a phi resolving move. 936a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!phi->block()->IsLoopHeader()) { 93757ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org hint = LiveRangeFor(phi->id())->current_hint_operand(); 938a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 939a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 940a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (to->IsUnallocated()) { 941fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org if (live->Contains(LUnallocated::cast(to)->virtual_register())) { 942a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org Define(curr_position, to, from); 943fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org live->Remove(LUnallocated::cast(to)->virtual_register()); 944a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 945a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org cur->Eliminate(); 946a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org continue; 947a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 948a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 949a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org Define(curr_position, to, from); 950a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 951a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 952a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org Use(block_start_position, curr_position, from, hint); 953a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (from->IsUnallocated()) { 954fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org live->Add(LUnallocated::cast(from)->virtual_register()); 955a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 956a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 957a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 95883aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org ASSERT(!IsGapAt(index)); 95983aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LInstruction* instr = InstructionAt(index); 960a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 96183aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org if (instr != NULL) { 96283aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LOperand* output = instr->Output(); 963a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (output != NULL) { 964fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org if (output->IsUnallocated()) { 965fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org live->Remove(LUnallocated::cast(output)->virtual_register()); 966fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org } 967a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org Define(curr_position, output, NULL); 968a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 969a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 970a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org if (instr->ClobbersRegisters()) { 971a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org for (int i = 0; i < Register::kMaxNumAllocatableRegisters; ++i) { 972a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (output == NULL || !output->IsRegister() || 973a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org output->index() != i) { 974a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = FixedLiveRangeFor(i); 975a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org range->AddUseInterval(curr_position, 976be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org curr_position.InstructionEnd(), 9771510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org zone()); 978a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 979a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 980d2c22f0121ebc55ee26a9e742f0fd7c0b8397730kmillikin@chromium.org } 981d2c22f0121ebc55ee26a9e742f0fd7c0b8397730kmillikin@chromium.org 982a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org if (instr->ClobbersDoubleRegisters()) { 983a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org for (int i = 0; i < DoubleRegister::NumAllocatableRegisters(); ++i) { 984a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (output == NULL || !output->IsDoubleRegister() || 985a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org output->index() != i) { 986a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = FixedDoubleLiveRangeFor(i); 987a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org range->AddUseInterval(curr_position, 988be6bd10d8264b7a05e0a04407eb98b253bc0f152kmillikin@chromium.org curr_position.InstructionEnd(), 9891510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org zone()); 990a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 991a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 992a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 993a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 994e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org for (UseIterator it(instr); !it.Done(); it.Advance()) { 995e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org LOperand* input = it.Current(); 996a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 997a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition use_pos; 998a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (input->IsUnallocated() && 999a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LUnallocated::cast(input)->IsUsedAtStart()) { 1000a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos = curr_position; 1001a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 1002a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos = curr_position.InstructionEnd(); 1003a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1004a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1005a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org Use(block_start_position, use_pos, input, NULL); 1006fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org if (input->IsUnallocated()) { 1007fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org live->Add(LUnallocated::cast(input)->virtual_register()); 1008fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org } 1009a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1010a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1011e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org for (TempIterator it(instr); !it.Done(); it.Advance()) { 1012e297f5973a8a9ff0d9945da3f1e2d8a6230c294djkummerow@chromium.org LOperand* temp = it.Current(); 1013a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org if (instr->ClobbersTemps()) { 1014a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (temp->IsRegister()) continue; 1015a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (temp->IsUnallocated()) { 1016a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LUnallocated* temp_unalloc = LUnallocated::cast(temp); 1017a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (temp_unalloc->HasFixedPolicy()) { 1018a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org continue; 1019a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1020a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1021a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 10225f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org Use(block_start_position, curr_position.InstructionEnd(), temp, NULL); 10235f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org Define(curr_position, temp, NULL); 1024a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1025a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1026a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1027a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1028a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org index = index - 1; 1029a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1030a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1031a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1032a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1033a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::ResolvePhis(HBasicBlock* block) { 1034a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org const ZoneList<HPhi*>* phis = block->phis(); 1035a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < phis->length(); ++i) { 1036a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HPhi* phi = phis->at(i); 10371510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LUnallocated* phi_operand = 10381510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org new(chunk()->zone()) LUnallocated(LUnallocated::NONE); 1039a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org phi_operand->set_virtual_register(phi->id()); 1040a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int j = 0; j < phi->OperandCount(); ++j) { 1041a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HValue* op = phi->OperandAt(j); 1042a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* operand = NULL; 1043a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (op->IsConstant() && op->EmitAtUses()) { 1044a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HConstant* constant = HConstant::cast(op); 1045a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org operand = chunk_->DefineConstantOperand(constant); 1046a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 1047a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!op->EmitAtUses()); 10481510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LUnallocated* unalloc = 10491510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org new(chunk()->zone()) LUnallocated(LUnallocated::ANY); 1050a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org unalloc->set_virtual_register(op->id()); 1051a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org operand = unalloc; 1052a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1053a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HBasicBlock* cur_block = block->predecessors()->at(j); 1054a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // The gap move must be added without any special processing as in 1055a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // the AddConstraintsGapMove. 1056a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org chunk_->AddGapMove(cur_block->last_instruction_index() - 1, 1057a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org operand, 1058a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org phi_operand); 1059dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org 1060dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org // We are going to insert a move before the branch instruction. 1061dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org // Some branch instructions (e.g. loops' back edges) 1062dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org // can potentially cause a GC so they have a pointer map. 1063dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org // By inserting a move we essentially create a copy of a 1064dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org // value which is invisible to PopulatePointerMaps(), because we store 1065dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org // it into a location different from the operand of a live range 1066dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org // covering a branch instruction. 1067dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org // Thus we need to manually record a pointer. 1068c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com LInstruction* branch = 1069c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com InstructionAt(cur_block->last_instruction_index()); 1070c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com if (branch->HasPointerMap()) { 1071d4be0f0c0edfc0a0b46e745055c3dc497c0ffcb5verwaest@chromium.org if (phi->representation().IsTagged() && !phi->type().IsSmi()) { 10721510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org branch->pointer_map()->RecordPointer(phi_operand, chunk()->zone()); 1073c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com } else if (!phi->representation().IsDouble()) { 10741510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org branch->pointer_map()->RecordUntagged(phi_operand, chunk()->zone()); 1075dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org } 1076dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org } 1077a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1078a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1079a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* live_range = LiveRangeFor(phi->id()); 1080a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LLabel* label = chunk_->GetLabel(phi->block()->block_id()); 10811510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org label->GetOrCreateParallelMove(LGap::START, chunk()->zone())-> 10821510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org AddMove(phi_operand, live_range->GetSpillOperand(), chunk()->zone()); 1083a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org live_range->SetSpillStartIndex(phi->block()->first_instruction_index()); 1084a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1085a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1086a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1087a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1088994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.orgbool LAllocator::Allocate(LChunk* chunk) { 1089a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(chunk_ == NULL); 109028583c92ca8f528df625800519088ac88996d504jkummerow@chromium.org chunk_ = static_cast<LPlatformChunk*>(chunk); 109194b0d6fcb08a2f01ba52c6edb712068f482366f1danno@chromium.org assigned_registers_ = 10921510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org new(chunk->zone()) BitVector(Register::NumAllocatableRegisters(), 10931510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk->zone()); 109494b0d6fcb08a2f01ba52c6edb712068f482366f1danno@chromium.org assigned_double_registers_ = 10951510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org new(chunk->zone()) BitVector(DoubleRegister::NumAllocatableRegisters(), 10961510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk->zone()); 1097a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org MeetRegisterConstraints(); 1098994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return false; 1099a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ResolvePhis(); 1100a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org BuildLiveRanges(); 1101a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AllocateGeneralRegisters(); 1102994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return false; 1103a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AllocateDoubleRegisters(); 1104994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return false; 1105a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org PopulatePointerMaps(); 1106a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ConnectRanges(); 1107a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ResolveControlFlow(); 1108994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org return true; 1109a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1110a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1111a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1112a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::MeetRegisterConstraints() { 11131510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LAllocatorPhase phase("L_Register constraints", this); 11145d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org first_artificial_register_ = next_virtual_register_; 111583aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1116a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < blocks->length(); ++i) { 1117a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HBasicBlock* block = blocks->at(i); 1118a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org MeetRegisterConstraints(block); 1119994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return; 1120a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1121a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1122a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1123a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1124a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::ResolvePhis() { 11251510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LAllocatorPhase phase("L_Resolve phis", this); 1126a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1127a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Process the blocks in reverse order. 112883aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1129a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { 1130a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HBasicBlock* block = blocks->at(block_id); 1131a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ResolvePhis(block); 1132a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1133a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1134a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1135a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1136a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::ResolveControlFlow(LiveRange* range, 1137a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HBasicBlock* block, 1138a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HBasicBlock* pred) { 1139a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition pred_end = 114031b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org LifetimePosition::FromInstructionIndex(pred->last_instruction_index()); 1141a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition cur_start = 1142a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition::FromInstructionIndex(block->first_instruction_index()); 1143a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* pred_cover = NULL; 1144a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* cur_cover = NULL; 1145a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* cur_range = range; 1146a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (cur_range != NULL && (cur_cover == NULL || pred_cover == NULL)) { 1147a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (cur_range->CanCover(cur_start)) { 1148a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(cur_cover == NULL); 1149a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org cur_cover = cur_range; 1150a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1151a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (cur_range->CanCover(pred_end)) { 1152a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(pred_cover == NULL); 1153a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org pred_cover = cur_range; 1154a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1155a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org cur_range = cur_range->next(); 1156a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1157a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1158a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (cur_cover->IsSpilled()) return; 1159a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(pred_cover != NULL && cur_cover != NULL); 1160a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (pred_cover != cur_cover) { 11611510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LOperand* pred_op = pred_cover->CreateAssignedOperand(chunk()->zone()); 11621510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LOperand* cur_op = cur_cover->CreateAssignedOperand(chunk()->zone()); 1163a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!pred_op->Equals(cur_op)) { 1164a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LGap* gap = NULL; 1165a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (block->predecessors()->length() == 1) { 116683aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org gap = GapAt(block->first_instruction_index()); 1167a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 1168a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(pred->end()->SecondSuccessor() == NULL); 1169a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org gap = GetLastGap(pred); 11703a5fd78f0ca6c2827bb05f69a373d152a9ce6ff3fschneider@chromium.org 11713a5fd78f0ca6c2827bb05f69a373d152a9ce6ff3fschneider@chromium.org // We are going to insert a move before the branch instruction. 11723a5fd78f0ca6c2827bb05f69a373d152a9ce6ff3fschneider@chromium.org // Some branch instructions (e.g. loops' back edges) 11733a5fd78f0ca6c2827bb05f69a373d152a9ce6ff3fschneider@chromium.org // can potentially cause a GC so they have a pointer map. 1174dcebac0f4c6c0da579b7cc91a0cbba8f3c820c8dricow@chromium.org // By inserting a move we essentially create a copy of a 11753a5fd78f0ca6c2827bb05f69a373d152a9ce6ff3fschneider@chromium.org // value which is invisible to PopulatePointerMaps(), because we store 11763a5fd78f0ca6c2827bb05f69a373d152a9ce6ff3fschneider@chromium.org // it into a location different from the operand of a live range 11773a5fd78f0ca6c2827bb05f69a373d152a9ce6ff3fschneider@chromium.org // covering a branch instruction. 11783a5fd78f0ca6c2827bb05f69a373d152a9ce6ff3fschneider@chromium.org // Thus we need to manually record a pointer. 1179c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com LInstruction* branch = InstructionAt(pred->last_instruction_index()); 1180c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com if (branch->HasPointerMap()) { 1181c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com if (HasTaggedValue(range->id())) { 11821510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org branch->pointer_map()->RecordPointer(cur_op, chunk()->zone()); 1183c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com } else if (!cur_op->IsDoubleStackSlot() && 1184c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com !cur_op->IsDoubleRegister()) { 1185c3b670ff19220959730d7886892bc4beb95d2ebaerik.corry@gmail.com branch->pointer_map()->RemovePointer(cur_op); 11863a5fd78f0ca6c2827bb05f69a373d152a9ce6ff3fschneider@chromium.org } 11873a5fd78f0ca6c2827bb05f69a373d152a9ce6ff3fschneider@chromium.org } 1188a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 11897028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org gap->GetOrCreateParallelMove( 11901510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LGap::START, chunk()->zone())->AddMove(pred_op, cur_op, 11911510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 1192a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1193a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1194a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1195a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1196a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1197a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgLParallelMove* LAllocator::GetConnectingParallelMove(LifetimePosition pos) { 1198a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int index = pos.InstructionIndex(); 119983aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org if (IsGapAt(index)) { 120083aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LGap* gap = GapAt(index); 1201a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return gap->GetOrCreateParallelMove( 12021510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org pos.IsInstructionStart() ? LGap::START : LGap::END, chunk()->zone()); 1203a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1204a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int gap_pos = pos.IsInstructionStart() ? (index - 1) : (index + 1); 120583aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org return GapAt(gap_pos)->GetOrCreateParallelMove( 12061510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org (gap_pos < index) ? LGap::AFTER : LGap::BEFORE, chunk()->zone()); 1207a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1208a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1209a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1210a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgHBasicBlock* LAllocator::GetBlock(LifetimePosition pos) { 121183aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex())); 1212a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return gap->block(); 1213a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1214a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1215a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1216a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::ConnectRanges() { 12171510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LAllocatorPhase phase("L_Connect ranges", this); 1218a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < live_ranges()->length(); ++i) { 1219a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* first_range = live_ranges()->at(i); 1220a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (first_range == NULL || first_range->parent() != NULL) continue; 1221a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1222a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* second_range = first_range->next(); 1223a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (second_range != NULL) { 1224a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition pos = second_range->Start(); 1225a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1226a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!second_range->IsSpilled()) { 1227a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Add gap move if the two live ranges touch and there is no block 1228a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // boundary. 1229a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (first_range->End().Value() == pos.Value()) { 1230a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool should_insert = true; 1231a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (IsBlockBoundary(pos)) { 1232a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org should_insert = CanEagerlyResolveControlFlow(GetBlock(pos)); 1233a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1234a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (should_insert) { 1235a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LParallelMove* move = GetConnectingParallelMove(pos); 12361510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LOperand* prev_operand = first_range->CreateAssignedOperand( 12371510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 12381510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LOperand* cur_operand = second_range->CreateAssignedOperand( 12391510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 12401510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org move->AddMove(prev_operand, cur_operand, 12411510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 1242a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1243a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1244a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1245a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1246a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_range = second_range; 1247a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org second_range = second_range->next(); 1248a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1249a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1250a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1251a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1252a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1253a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool LAllocator::CanEagerlyResolveControlFlow(HBasicBlock* block) const { 1254a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (block->predecessors()->length() != 1) return false; 1255a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return block->predecessors()->first()->block_id() == block->block_id() - 1; 1256a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1257a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1258a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1259a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::ResolveControlFlow() { 12601510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LAllocatorPhase phase("L_Resolve control flow", this); 126183aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1262a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int block_id = 1; block_id < blocks->length(); ++block_id) { 1263a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HBasicBlock* block = blocks->at(block_id); 1264a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (CanEagerlyResolveControlFlow(block)) continue; 1265a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org BitVector* live = live_in_sets_[block->block_id()]; 1266a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org BitVector::Iterator iterator(live); 1267a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (!iterator.Done()) { 1268a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int operand_index = iterator.Current(); 1269a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < block->predecessors()->length(); ++i) { 1270a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HBasicBlock* cur = block->predecessors()->at(i); 1271a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* cur_range = LiveRangeFor(operand_index); 1272a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ResolveControlFlow(cur_range, block, cur); 1273a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1274a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org iterator.Advance(); 1275a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1276a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1277a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1278a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1279a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1280a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::BuildLiveRanges() { 12811510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LAllocatorPhase phase("L_Build live ranges", this); 1282a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org InitializeLivenessAnalysis(); 1283a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Process the blocks in reverse order. 128483aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1285a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { 1286a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HBasicBlock* block = blocks->at(block_id); 1287a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org BitVector* live = ComputeLiveOut(block); 1288a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Initially consider all live_out values live for the entire block. We 1289a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // will shorten these intervals if necessary. 1290a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AddInitialIntervals(block, live); 1291a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1292a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Process the instructions in reverse order, generating and killing 1293a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // live values. 1294a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ProcessInstructions(block, live); 1295a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // All phi output operands are killed by this block. 1296a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org const ZoneList<HPhi*>* phis = block->phis(); 1297a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < phis->length(); ++i) { 1298a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // The live range interval already ends at the first instruction of the 1299a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // block. 1300a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HPhi* phi = phis->at(i); 1301a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org live->Remove(phi->id()); 1302a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1303a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* hint = NULL; 1304a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* phi_operand = NULL; 1305a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LGap* gap = GetLastGap(phi->block()->predecessors()->at(0)); 13061510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, 13071510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org chunk()->zone()); 1308a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int j = 0; j < move->move_operands()->length(); ++j) { 13090511e24c6ebf94594a7e03bdcd58157ac2971d69erik.corry@gmail.com LOperand* to = move->move_operands()->at(j).destination(); 1310fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org if (to->IsUnallocated() && 1311fa458e413c3e5b8d479e49258d060b7bb4567c57danno@chromium.org LUnallocated::cast(to)->virtual_register() == phi->id()) { 13120511e24c6ebf94594a7e03bdcd58157ac2971d69erik.corry@gmail.com hint = move->move_operands()->at(j).source(); 1313a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org phi_operand = to; 1314a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org break; 1315a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1316a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1317a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(hint != NULL); 1318a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1319a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition block_start = LifetimePosition::FromInstructionIndex( 1320a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org block->first_instruction_index()); 1321a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org Define(block_start, phi_operand, hint); 1322a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1323a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1324a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Now live is live_in for this block except not including values live 1325a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // out on backward successor edges. 1326a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org live_in_sets_[block_id] = live; 1327a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1328a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // If this block is a loop header go back and patch up the necessary 1329a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // predecessor blocks. 1330a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (block->IsLoopHeader()) { 1331a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // TODO(kmillikin): Need to be able to get the last block of the loop 1332a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // in the loop information. Add a live range stretching from the first 1333a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // loop instruction to the last for each value live on entry to the 1334a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // header. 1335a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HBasicBlock* back_edge = block->loop_information()->GetLastBackEdge(); 1336a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org BitVector::Iterator iterator(live); 1337a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition start = LifetimePosition::FromInstructionIndex( 1338a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org block->first_instruction_index()); 1339a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition end = LifetimePosition::FromInstructionIndex( 134031b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org back_edge->last_instruction_index()).NextInstruction(); 1341a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (!iterator.Done()) { 1342a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int operand_index = iterator.Current(); 1343a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = LiveRangeFor(operand_index); 13441510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org range->EnsureInterval(start, end, zone()); 1345a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org iterator.Advance(); 1346a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1347a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1348a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = block->block_id() + 1; i <= back_edge->block_id(); ++i) { 1349a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org live_in_sets_[i]->Union(*live); 1350a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1351a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1352a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1353a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#ifdef DEBUG 1354a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (block_id == 0) { 1355a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org BitVector::Iterator iterator(live); 1356a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool found = false; 1357a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (!iterator.Done()) { 1358a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org found = true; 1359a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int operand_index = iterator.Current(); 1360a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org if (chunk_->info()->IsStub()) { 1361a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org CodeStub::Major major_key = chunk_->info()->code_stub()->MajorKey(); 1362a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org PrintF("Function: %s\n", CodeStub::MajorName(major_key, false)); 1363a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org } else { 1364a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org ASSERT(chunk_->info()->IsOptimizing()); 13651fd77d58ca66b2711f09cdea32c0c2d1a01b3ae5danno@chromium.org AllowHandleDereference allow_deref; 1366a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org PrintF("Function: %s\n", 1367a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org *chunk_->info()->function()->debug_name()->ToCString()); 1368a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org } 1369a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org PrintF("Value %d used before first definition!\n", operand_index); 1370a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = LiveRangeFor(operand_index); 1371a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org PrintF("First use is at %d\n", range->first_pos()->pos().Value()); 1372a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org iterator.Advance(); 1373a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1374a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!found); 1375a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1376a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#endif 1377a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1378a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1379a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1380a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1381a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool LAllocator::SafePointsAreInOrder() const { 1382a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); 1383a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int safe_point = 0; 1384a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < pointer_maps->length(); ++i) { 1385a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LPointerMap* map = pointer_maps->at(i); 1386a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (safe_point > map->lithium_position()) return false; 1387a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org safe_point = map->lithium_position(); 1388a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1389a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return true; 1390a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1391a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1392a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1393a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::PopulatePointerMaps() { 13941510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LAllocatorPhase phase("L_Populate pointer maps", this); 1395a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); 1396a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1397a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(SafePointsAreInOrder()); 1398a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1399a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Iterate over all safe point positions and record a pointer 1400a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // for all spilled live ranges at this point. 1401a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int first_safe_point_index = 0; 1402a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int last_range_start = 0; 1403a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { 1404a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = live_ranges()->at(range_idx); 1405a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range == NULL) continue; 1406a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Iterate over the first parts of multi-part live ranges. 1407a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range->parent() != NULL) continue; 1408a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Skip non-pointer values. 1409a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!HasTaggedValue(range->id())) continue; 1410a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Skip empty live ranges. 1411a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range->IsEmpty()) continue; 1412a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1413a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Find the extent of the range and its children. 1414a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int start = range->Start().InstructionIndex(); 1415a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int end = 0; 1416a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (LiveRange* cur = range; cur != NULL; cur = cur->next()) { 1417a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition this_end = cur->End(); 1418a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (this_end.InstructionIndex() > end) end = this_end.InstructionIndex(); 1419a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(cur->Start().InstructionIndex() >= start); 1420a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1421a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1422a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Most of the ranges are in order, but not all. Keep an eye on when 1423a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // they step backwards and reset the first_safe_point_index so we don't 1424a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // miss any safe points. 1425a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (start < last_range_start) { 1426a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_safe_point_index = 0; 1427a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1428a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org last_range_start = start; 1429a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1430a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Step across all the safe points that are before the start of this range, 1431a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // recording how far we step in order to save doing this for the next range. 1432a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (first_safe_point_index < pointer_maps->length()) { 1433a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LPointerMap* map = pointer_maps->at(first_safe_point_index); 1434a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int safe_point = map->lithium_position(); 1435a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (safe_point >= start) break; 1436a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first_safe_point_index++; 1437a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1438a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1439a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Step through the safe points to see whether they are in the range. 1440a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int safe_point_index = first_safe_point_index; 1441a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org safe_point_index < pointer_maps->length(); 1442a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ++safe_point_index) { 1443a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LPointerMap* map = pointer_maps->at(safe_point_index); 1444a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int safe_point = map->lithium_position(); 1445a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1446a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // The safe points are sorted so we can stop searching here. 1447a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (safe_point - 1 > end) break; 1448a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1449a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Advance to the next active range that covers the current 1450a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // safe point position. 1451a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition safe_point_pos = 1452a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition::FromInstructionIndex(safe_point); 1453a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* cur = range; 1454003650ee766f5e92756d470a37973fd371757485yangguo@chromium.org while (cur != NULL && !cur->Covers(safe_point_pos)) { 1455a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org cur = cur->next(); 1456a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1457a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (cur == NULL) continue; 1458a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1459a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Check if the live range is spilled and the safe point is after 1460a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // the spill position. 1461a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range->HasAllocatedSpillOperand() && 1462a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org safe_point >= range->spill_start_index()) { 1463a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Pointer for range %d (spilled at %d) at safe point %d\n", 1464a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org range->id(), range->spill_start_index(), safe_point); 14651510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org map->RecordPointer(range->GetSpillOperand(), chunk()->zone()); 1466a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1467a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1468a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!cur->IsSpilled()) { 1469a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Pointer in register for range %d (start at %d) " 1470a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org "at safe point %d\n", 1471a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org cur->id(), cur->Start().Value(), safe_point); 14721510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LOperand* operand = cur->CreateAssignedOperand(chunk()->zone()); 1473a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!operand->IsStackSlot()); 14741510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org map->RecordPointer(operand, chunk()->zone()); 1475a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1476a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1477a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1478a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1479a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1480a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 14815f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.orgvoid LAllocator::AllocateGeneralRegisters() { 14821510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LAllocatorPhase phase("L_Allocate general registers", this); 1483a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org num_registers_ = Register::NumAllocatableRegisters(); 14845f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org AllocateRegisters(); 14855f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org} 14865f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 14875f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 1488a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::AllocateDoubleRegisters() { 14891510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org LAllocatorPhase phase("L_Allocate double registers", this); 1490a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org num_registers_ = DoubleRegister::NumAllocatableRegisters(); 14915f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org mode_ = DOUBLE_REGISTERS; 1492a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AllocateRegisters(); 1493a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1494a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1495a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1496a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::AllocateRegisters() { 14974d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org ASSERT(unhandled_live_ranges_.is_empty()); 1498a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1499a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < live_ranges_.length(); ++i) { 1500a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (live_ranges_[i] != NULL) { 15015f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (RequiredRegisterKind(live_ranges_[i]->id()) == mode_) { 1502a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AddToUnhandledUnsorted(live_ranges_[i]); 1503a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1504a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1505a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1506a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org SortUnhandled(); 1507a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(UnhandledIsSorted()); 1508a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 15094d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org ASSERT(reusable_slots_.is_empty()); 1510a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(active_live_ranges_.is_empty()); 1511a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(inactive_live_ranges_.is_empty()); 1512a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 15135f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (mode_ == DOUBLE_REGISTERS) { 1514003650ee766f5e92756d470a37973fd371757485yangguo@chromium.org for (int i = 0; i < DoubleRegister::NumAllocatableRegisters(); ++i) { 1515a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* current = fixed_double_live_ranges_.at(i); 1516a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (current != NULL) { 1517a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AddToInactive(current); 1518a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1519a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1520a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 1521a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < fixed_live_ranges_.length(); ++i) { 1522a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* current = fixed_live_ranges_.at(i); 1523a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (current != NULL) { 1524a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AddToInactive(current); 1525a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1526a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1527a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1528a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1529a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (!unhandled_live_ranges_.is_empty()) { 1530a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(UnhandledIsSorted()); 1531a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* current = unhandled_live_ranges_.RemoveLast(); 1532a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(UnhandledIsSorted()); 1533a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition position = current->Start(); 1534e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org#ifdef DEBUG 1535e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org allocation_finger_ = position; 1536e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org#endif 1537a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Processing interval %d start=%d\n", 1538a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org current->id(), 1539a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org position.Value()); 1540a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1541a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (current->HasAllocatedSpillOperand()) { 1542a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Live range %d already has a spill operand\n", current->id()); 1543a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition next_pos = position; 154483aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org if (IsGapAt(next_pos.InstructionIndex())) { 1545a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org next_pos = next_pos.NextInstruction(); 1546a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1547a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* pos = current->NextUsePositionRegisterIsBeneficial(next_pos); 1548a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // If the range already has a spill operand and it doesn't need a 1549a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // register immediately, split it and spill the first part of the range. 1550a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (pos == NULL) { 1551a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org Spill(current); 1552a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org continue; 1553a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else if (pos->pos().Value() > 1554a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org current->Start().NextInstruction().Value()) { 1555a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Do not spill live range eagerly if use position that can benefit from 1556a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // the register is too close to the start of live range. 15575f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org SpillBetween(current, current->Start(), pos->pos()); 1558994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return; 1559a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(UnhandledIsSorted()); 1560a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org continue; 1561a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1562a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1563a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1564a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < active_live_ranges_.length(); ++i) { 1565a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* cur_active = active_live_ranges_.at(i); 1566a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (cur_active->End().Value() <= position.Value()) { 1567a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ActiveToHandled(cur_active); 1568a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org --i; // The live range was removed from the list of active live ranges. 1569a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else if (!cur_active->Covers(position)) { 1570a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ActiveToInactive(cur_active); 1571a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org --i; // The live range was removed from the list of active live ranges. 1572a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1573a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1574a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1575a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1576a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* cur_inactive = inactive_live_ranges_.at(i); 1577a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (cur_inactive->End().Value() <= position.Value()) { 1578a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org InactiveToHandled(cur_inactive); 1579a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org --i; // Live range was removed from the list of inactive live ranges. 1580a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else if (cur_inactive->Covers(position)) { 1581a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org InactiveToActive(cur_inactive); 1582a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org --i; // Live range was removed from the list of inactive live ranges. 1583a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1584a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1585a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1586a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!current->HasRegisterAssigned() && !current->IsSpilled()); 1587a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1588a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool result = TryAllocateFreeReg(current); 1589994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return; 1590994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org 1591994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!result) AllocateBlockedReg(current); 1592994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return; 1593a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1594a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (current->HasRegisterAssigned()) { 1595a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AddToActive(current); 1596a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1597a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1598a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 15994d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org reusable_slots_.Rewind(0); 16004d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org active_live_ranges_.Rewind(0); 16014d3fe4e246b0312eba361689f288ddf8dd516960danno@chromium.org inactive_live_ranges_.Rewind(0); 1602a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1603a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1604a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 16055f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.orgconst char* LAllocator::RegisterName(int allocation_index) { 16065f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (mode_ == GENERAL_REGISTERS) { 16075f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org return Register::AllocationIndexToString(allocation_index); 16085f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } else { 16095f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org return DoubleRegister::AllocationIndexToString(allocation_index); 16105f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } 16115f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org} 16125f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 16135f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 1614a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::TraceAlloc(const char* msg, ...) { 1615a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (FLAG_trace_alloc) { 1616a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org va_list arguments; 1617a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org va_start(arguments, msg); 1618a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org OS::VPrint(msg, arguments); 1619a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org va_end(arguments); 1620a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1621a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1622a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1623a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1624a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool LAllocator::HasTaggedValue(int virtual_register) const { 162583aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org HValue* value = graph_->LookupValue(virtual_register); 1626a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (value == NULL) return false; 1627d4be0f0c0edfc0a0b46e745055c3dc497c0ffcb5verwaest@chromium.org return value->representation().IsTagged() && !value->type().IsSmi(); 1628a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1629a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1630a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 16315f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.orgRegisterKind LAllocator::RequiredRegisterKind(int virtual_register) const { 16325d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org if (virtual_register < first_artificial_register_) { 163383aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org HValue* value = graph_->LookupValue(virtual_register); 16345d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org if (value != NULL && value->representation().IsDouble()) { 16355d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org return DOUBLE_REGISTERS; 16365d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org } 16375d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org } else if (double_artificial_registers_.Contains( 16385d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org virtual_register - first_artificial_register_)) { 16395f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org return DOUBLE_REGISTERS; 16405f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } 16415d00b60c201d860c74821f553fdc34f4e057b411lrn@chromium.org 16425f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org return GENERAL_REGISTERS; 1643a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1644a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1645a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1646a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::AddToActive(LiveRange* range) { 1647a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Add live range %d to active\n", range->id()); 16487028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org active_live_ranges_.Add(range, zone()); 1649a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1650a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1651a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1652a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::AddToInactive(LiveRange* range) { 1653a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Add live range %d to inactive\n", range->id()); 16547028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org inactive_live_ranges_.Add(range, zone()); 1655a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1656a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1657a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1658a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::AddToUnhandledSorted(LiveRange* range) { 1659a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range == NULL || range->IsEmpty()) return; 1660a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!range->HasRegisterAssigned() && !range->IsSpilled()); 1661e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org ASSERT(allocation_finger_.Value() <= range->Start().Value()); 1662a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = unhandled_live_ranges_.length() - 1; i >= 0; --i) { 1663a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* cur_range = unhandled_live_ranges_.at(i); 1664a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range->ShouldBeAllocatedBefore(cur_range)) { 1665a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Add live range %d to unhandled at %d\n", range->id(), i + 1); 16667028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org unhandled_live_ranges_.InsertAt(i + 1, range, zone()); 1667a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(UnhandledIsSorted()); 1668a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return; 1669a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1670a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1671a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Add live range %d to unhandled at start\n", range->id()); 16727028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org unhandled_live_ranges_.InsertAt(0, range, zone()); 1673a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(UnhandledIsSorted()); 1674a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1675a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1676a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1677a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::AddToUnhandledUnsorted(LiveRange* range) { 1678a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range == NULL || range->IsEmpty()) return; 1679a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!range->HasRegisterAssigned() && !range->IsSpilled()); 1680a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Add live range %d to unhandled unsorted at end\n", range->id()); 16817028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org unhandled_live_ranges_.Add(range, zone()); 1682a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1683a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1684a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1685a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgstatic int UnhandledSortHelper(LiveRange* const* a, LiveRange* const* b) { 1686a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!(*a)->ShouldBeAllocatedBefore(*b) || 1687a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org !(*b)->ShouldBeAllocatedBefore(*a)); 1688a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if ((*a)->ShouldBeAllocatedBefore(*b)) return 1; 1689a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if ((*b)->ShouldBeAllocatedBefore(*a)) return -1; 1690a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return (*a)->id() - (*b)->id(); 1691a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1692a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1693a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1694a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// Sort the unhandled live ranges so that the ranges to be processed first are 1695a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// at the end of the array list. This is convenient for the register allocation 1696a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org// algorithm because it is efficient to remove elements from the end. 1697a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::SortUnhandled() { 1698a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Sort unhandled\n"); 1699a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org unhandled_live_ranges_.Sort(&UnhandledSortHelper); 1700a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1701a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1702a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1703a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool LAllocator::UnhandledIsSorted() { 1704a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int len = unhandled_live_ranges_.length(); 1705a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 1; i < len; i++) { 1706a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* a = unhandled_live_ranges_.at(i - 1); 1707a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* b = unhandled_live_ranges_.at(i); 1708a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (a->Start().Value() < b->Start().Value()) return false; 1709a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1710a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return true; 1711a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1712a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1713a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1714a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::FreeSpillSlot(LiveRange* range) { 1715a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Check that we are the last range. 1716a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range->next() != NULL) return; 1717a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1718a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!range->TopLevel()->HasAllocatedSpillOperand()) return; 1719a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1720a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int index = range->TopLevel()->GetSpillOperand()->index(); 1721a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (index >= 0) { 17227028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org reusable_slots_.Add(range, zone()); 1723a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1724a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1725a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1726a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1727a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgLOperand* LAllocator::TryReuseSpillSlot(LiveRange* range) { 1728a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (reusable_slots_.is_empty()) return NULL; 1729a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (reusable_slots_.first()->End().Value() > 1730a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org range->TopLevel()->Start().Value()) { 1731a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return NULL; 1732a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1733a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* result = reusable_slots_.first()->TopLevel()->GetSpillOperand(); 1734a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org reusable_slots_.Remove(0); 1735a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return result; 1736a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1737a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1738a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1739a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::ActiveToHandled(LiveRange* range) { 1740a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(active_live_ranges_.Contains(range)); 1741a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org active_live_ranges_.RemoveElement(range); 1742a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Moving live range %d from active to handled\n", range->id()); 1743a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org FreeSpillSlot(range); 1744a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1745a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1746a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1747a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::ActiveToInactive(LiveRange* range) { 1748a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(active_live_ranges_.Contains(range)); 1749a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org active_live_ranges_.RemoveElement(range); 17507028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org inactive_live_ranges_.Add(range, zone()); 1751a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Moving live range %d from active to inactive\n", range->id()); 1752a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1753a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1754a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1755a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::InactiveToHandled(LiveRange* range) { 1756a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(inactive_live_ranges_.Contains(range)); 1757a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org inactive_live_ranges_.RemoveElement(range); 1758a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); 1759a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org FreeSpillSlot(range); 1760a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1761a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1762a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1763a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::InactiveToActive(LiveRange* range) { 1764a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(inactive_live_ranges_.Contains(range)); 1765a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org inactive_live_ranges_.RemoveElement(range); 17667028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org active_live_ranges_.Add(range, zone()); 1767a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Moving live range %d from inactive to active\n", range->id()); 1768a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1769a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1770a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 17715f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org// TryAllocateFreeReg and AllocateBlockedReg assume this 17725f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org// when allocating local arrays. 1773a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.orgSTATIC_ASSERT(DoubleRegister::kMaxNumAllocatableRegisters >= 1774a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org Register::kMaxNumAllocatableRegisters); 17755f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 17765f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 1777a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool LAllocator::TryAllocateFreeReg(LiveRange* current) { 1778a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org LifetimePosition free_until_pos[DoubleRegister::kMaxNumAllocatableRegisters]; 17795f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 1780e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org for (int i = 0; i < num_registers_; i++) { 17815f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org free_until_pos[i] = LifetimePosition::MaxPosition(); 17825f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } 17835f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 1784a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < active_live_ranges_.length(); ++i) { 1785a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* cur_active = active_live_ranges_.at(i); 17865f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org free_until_pos[cur_active->assigned_register()] = 1787a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition::FromInstructionIndex(0); 1788a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1789a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1790a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1791a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* cur_inactive = inactive_live_ranges_.at(i); 1792a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(cur_inactive->End().Value() > current->Start().Value()); 1793a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition next_intersection = 1794a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org cur_inactive->FirstIntersection(current); 1795a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!next_intersection.IsValid()) continue; 1796a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int cur_reg = cur_inactive->assigned_register(); 17975f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection); 1798a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1799a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 180057ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org LOperand* hint = current->FirstHint(); 180157ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org if (hint != NULL && (hint->IsRegister() || hint->IsDoubleRegister())) { 180257ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org int register_index = hint->index(); 180357ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org TraceAlloc( 180457ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org "Found reg hint %s (free until [%d) for live range %d (end %d[).\n", 180557ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org RegisterName(register_index), 180657ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org free_until_pos[register_index].Value(), 180757ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org current->id(), 180857ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org current->End().Value()); 180957ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org 181057ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org // The desired register is free until the end of the current live range. 181157ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org if (free_until_pos[register_index].Value() >= current->End().Value()) { 181257ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org TraceAlloc("Assigning preferred reg %s to live range %d\n", 181357ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org RegisterName(register_index), 181457ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org current->id()); 18151510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org SetLiveRangeAssignedRegister(current, register_index, mode_); 181657ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org return true; 1817a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1818a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1819a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 18205f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // Find the register which stays free for the longest time. 18215f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org int reg = 0; 1822a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 1; i < RegisterCount(); ++i) { 18235f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (free_until_pos[i].Value() > free_until_pos[reg].Value()) { 18245f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org reg = i; 1825a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1826a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1827a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 18285f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org LifetimePosition pos = free_until_pos[reg]; 18295f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 18305f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (pos.Value() <= current->Start().Value()) { 18315f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // All registers are blocked. 1832a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return false; 1833a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1834a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 18355f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (pos.Value() < current->End().Value()) { 18365f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // Register reg is available at the range start but becomes blocked before 18375f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // the range end. Split current at position where it becomes blocked. 1838994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org LiveRange* tail = SplitRangeAt(current, pos); 1839994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return false; 18405f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org AddToUnhandledSorted(tail); 18415f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } 18425f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 18435f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 18445f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // Register reg is available at the range start and is free until 18455f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // the range end. 18465f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org ASSERT(pos.Value() >= current->End().Value()); 18475f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org TraceAlloc("Assigning free reg %s to live range %d\n", 18485f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org RegisterName(reg), 18495f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org current->id()); 18501510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org SetLiveRangeAssignedRegister(current, reg, mode_); 18515f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 1852a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return true; 1853a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1854a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1855a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1856a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::AllocateBlockedReg(LiveRange* current) { 18575f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org UsePosition* register_use = current->NextRegisterPosition(current->Start()); 18585f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (register_use == NULL) { 18595f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // There is no use in the current live range that requires a register. 18605f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // We can just spill it. 18615f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org Spill(current); 18625f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org return; 18635f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } 18645f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 18655f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 1866a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org LifetimePosition use_pos[DoubleRegister::kMaxNumAllocatableRegisters]; 1867a6bbcc801f63c451f814d6da77a1a48fba3d36c6yangguo@chromium.org LifetimePosition block_pos[DoubleRegister::kMaxNumAllocatableRegisters]; 18685f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 1869e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org for (int i = 0; i < num_registers_; i++) { 18705f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org use_pos[i] = block_pos[i] = LifetimePosition::MaxPosition(); 18715f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } 1872a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1873a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < active_live_ranges_.length(); ++i) { 1874a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = active_live_ranges_[i]; 1875a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int cur_reg = range->assigned_register(); 1876a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range->IsFixed() || !range->CanBeSpilled(current->Start())) { 1877a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org block_pos[cur_reg] = use_pos[cur_reg] = 1878a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition::FromInstructionIndex(0); 1879a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 1880a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* next_use = range->NextUsePositionRegisterIsBeneficial( 1881a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org current->Start()); 1882a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (next_use == NULL) { 1883a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos[cur_reg] = range->End(); 1884a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 1885a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos[cur_reg] = next_use->pos(); 1886a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1887a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1888a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1889a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1890a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1891a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = inactive_live_ranges_.at(i); 1892a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(range->End().Value() > current->Start().Value()); 1893a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition next_intersection = range->FirstIntersection(current); 1894a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!next_intersection.IsValid()) continue; 1895a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int cur_reg = range->assigned_register(); 1896a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range->IsFixed()) { 1897a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection); 1898a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]); 1899a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 1900a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection); 1901a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1902a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1903a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 19045f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org int reg = 0; 1905a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 1; i < RegisterCount(); ++i) { 19065f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (use_pos[i].Value() > use_pos[reg].Value()) { 19075f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org reg = i; 1908a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1909a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 1910a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 19115f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org LifetimePosition pos = use_pos[reg]; 1912a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 19135f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (pos.Value() < register_use->pos().Value()) { 19145f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // All registers are blocked before the first use that requires a register. 19155f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // Spill starting part of live range up to that use. 19165f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org SpillBetween(current, current->Start(), register_use->pos()); 19175f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org return; 1918a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 19195f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 19205f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (block_pos[reg].Value() < current->End().Value()) { 19215f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // Register becomes blocked before the current range end. Split before that 19225f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // position. 19235f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org LiveRange* tail = SplitBetween(current, 19245f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org current->Start(), 19255f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org block_pos[reg].InstructionStart()); 19262bda543d75374afd8d7e98f56ca99a57ae1b7bd1svenpanne@chromium.org if (!AllocationOk()) return; 19275f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org AddToUnhandledSorted(tail); 19285f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org } 19295f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 19305f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // Register reg is not blocked for the whole range. 19315f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org ASSERT(block_pos[reg].Value() >= current->End().Value()); 19325f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org TraceAlloc("Assigning blocked reg %s to live range %d\n", 19335f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org RegisterName(reg), 19345f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org current->id()); 19351510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org SetLiveRangeAssignedRegister(current, reg, mode_); 19365f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 19375f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // This register was not free. Thus we need to find and spill 19385f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // parts of active and inactive live regions that use the same register 19395f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // at the same lifetime positions as current. 19405f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org SplitAndSpillIntersecting(current); 1941a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 1942a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1943a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 1944876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.orgLifetimePosition LAllocator::FindOptimalSpillingPos(LiveRange* range, 1945876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org LifetimePosition pos) { 1946876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org HBasicBlock* block = GetBlock(pos.InstructionStart()); 1947876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org HBasicBlock* loop_header = 1948876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org block->IsLoopHeader() ? block : block->parent_loop_header(); 1949876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org 1950876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org if (loop_header == NULL) return pos; 1951876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org 1952876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org UsePosition* prev_use = 1953876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org range->PreviousUsePositionRegisterIsBeneficial(pos); 1954876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org 1955876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org while (loop_header != NULL) { 1956876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org // We are going to spill live range inside the loop. 1957876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org // If possible try to move spilling position backwards to loop header. 1958876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org // This will reduce number of memory moves on the back edge. 1959876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org LifetimePosition loop_start = LifetimePosition::FromInstructionIndex( 1960876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org loop_header->first_instruction_index()); 1961876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org 1962876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org if (range->Covers(loop_start)) { 1963876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org if (prev_use == NULL || prev_use->pos().Value() < loop_start.Value()) { 1964876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org // No register beneficial use inside the loop before the pos. 1965876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org pos = loop_start; 1966876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org } 1967876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org } 1968876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org 1969876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org // Try hoisting out to an outer loop. 1970876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org loop_header = loop_header->parent_loop_header(); 1971876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org } 1972876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org 1973876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org return pos; 1974876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org} 1975876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org 1976876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org 1977a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::SplitAndSpillIntersecting(LiveRange* current) { 1978a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(current->HasRegisterAssigned()); 1979a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int reg = current->assigned_register(); 19805f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org LifetimePosition split_pos = current->Start(); 1981a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < active_live_ranges_.length(); ++i) { 1982a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = active_live_ranges_[i]; 1983a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range->assigned_register() == reg) { 1984a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* next_pos = range->NextRegisterPosition(current->Start()); 1985876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos); 1986a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (next_pos == NULL) { 1987876cca833d7212e476250d102cad185cdcfa9dfesvenpanne@chromium.org SpillAfter(range, spill_pos); 1988a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 1989e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org // When spilling between spill_pos and next_pos ensure that the range 1990e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org // remains spilled at least until the start of the current live range. 1991e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org // This guarantees that we will not introduce new unhandled ranges that 1992e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org // start before the current range as this violates allocation invariant 1993e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org // and will lead to an inconsistent state of active and inactive 1994e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org // live-ranges: ranges are allocated in order of their start positions, 1995e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org // ranges are retired from active/inactive when the start of the 1996e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org // current live-range is larger than their end. 1997e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos()); 1998a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 19992bda543d75374afd8d7e98f56ca99a57ae1b7bd1svenpanne@chromium.org if (!AllocationOk()) return; 2000a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ActiveToHandled(range); 2001a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org --i; 2002a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 2003a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 2004a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2005a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 2006a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* range = inactive_live_ranges_[i]; 2007a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(range->End().Value() > current->Start().Value()); 2008a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (range->assigned_register() == reg && !range->IsFixed()) { 2009a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition next_intersection = range->FirstIntersection(current); 2010a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (next_intersection.IsValid()) { 2011a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org UsePosition* next_pos = range->NextRegisterPosition(current->Start()); 2012a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (next_pos == NULL) { 20135f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org SpillAfter(range, split_pos); 2014a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 2015a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org next_intersection = Min(next_intersection, next_pos->pos()); 20165f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org SpillBetween(range, split_pos, next_intersection); 2017a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 20182bda543d75374afd8d7e98f56ca99a57ae1b7bd1svenpanne@chromium.org if (!AllocationOk()) return; 2019a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org InactiveToHandled(range); 2020a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org --i; 2021a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 2022a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 2023a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 2024a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 2025a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2026a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 20275f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.orgbool LAllocator::IsBlockBoundary(LifetimePosition pos) { 20285f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org return pos.IsInstructionStart() && 202983aa54905e559090bea7771b83f188762cfcf082ricow@chromium.org InstructionAt(pos.InstructionIndex())->IsLabel(); 20305f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org} 20315f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 20325f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 2033994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.orgLiveRange* LAllocator::SplitRangeAt(LiveRange* range, LifetimePosition pos) { 2034a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!range->IsFixed()); 20355f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value()); 20365f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 20375f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (pos.Value() <= range->Start().Value()) return range; 20385f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 203931b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org // We can't properly connect liveranges if split occured at the end 204031b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org // of control instruction. 204131b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org ASSERT(pos.IsInstructionStart() || 204231b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org !chunk_->instructions()->at(pos.InstructionIndex())->IsControl()); 204331b1277ec3b8cd17acb01c66d85a456159072157kmillikin@chromium.org 20442bda543d75374afd8d7e98f56ca99a57ae1b7bd1svenpanne@chromium.org int vreg = GetVirtualRegister(); 2045994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return NULL; 20462bda543d75374afd8d7e98f56ca99a57ae1b7bd1svenpanne@chromium.org LiveRange* result = LiveRangeFor(vreg); 20471510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org range->SplitAt(pos, result, zone()); 20485f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org return result; 20495f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org} 20505f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 20515f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org 20525f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.orgLiveRange* LAllocator::SplitBetween(LiveRange* range, 20535f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org LifetimePosition start, 20545f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org LifetimePosition end) { 20555f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org ASSERT(!range->IsFixed()); 20565f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org TraceAlloc("Splitting live range %d in position between [%d, %d]\n", 2057a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org range->id(), 2058a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org start.Value(), 2059a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org end.Value()); 2060a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 20615f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org LifetimePosition split_pos = FindOptimalSplitPos(start, end); 2062a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(split_pos.Value() >= start.Value()); 2063994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org return SplitRangeAt(range, split_pos); 2064a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 2065a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2066a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2067a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgLifetimePosition LAllocator::FindOptimalSplitPos(LifetimePosition start, 2068a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LifetimePosition end) { 2069a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int start_instr = start.InstructionIndex(); 2070a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int end_instr = end.InstructionIndex(); 2071a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(start_instr <= end_instr); 2072a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2073a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // We have no choice 2074a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (start_instr == end_instr) return end; 2075a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 20768e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org HBasicBlock* start_block = GetBlock(start); 20778e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org HBasicBlock* end_block = GetBlock(end); 2078a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2079a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (end_block == start_block) { 20808e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org // The interval is split in the same basic block. Split at the latest 20818e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org // possible position. 2082a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return end; 2083a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 2084a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2085a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org HBasicBlock* block = end_block; 20865f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // Find header of outermost loop. 2087a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org while (block->parent_loop_header() != NULL && 2088a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org block->parent_loop_header()->block_id() > start_block->block_id()) { 2089a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org block = block->parent_loop_header(); 2090a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 2091a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 20928e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org // We did not find any suitable outer loop. Split at the latest possible 20938e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org // position unless end_block is a loop header itself. 20948e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org if (block == end_block && !end_block->IsLoopHeader()) return end; 2095a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2096a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return LifetimePosition::FromInstructionIndex( 2097a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org block->first_instruction_index()); 2098a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 2099a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2100a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 21015f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.orgvoid LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) { 2102994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org LiveRange* second_part = SplitRangeAt(range, pos); 2103994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return; 21045f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org Spill(second_part); 2105a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 2106a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2107a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 21085f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.orgvoid LAllocator::SpillBetween(LiveRange* range, 21095f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org LifetimePosition start, 21105f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org LifetimePosition end) { 2111e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org SpillBetweenUntil(range, start, start, end); 2112e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org} 2113e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org 2114e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org 2115e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.orgvoid LAllocator::SpillBetweenUntil(LiveRange* range, 2116e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org LifetimePosition start, 2117e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org LifetimePosition until, 2118e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org LifetimePosition end) { 21196e196bfaf0e555d0c835390bb6ebc0a74484491dulan@chromium.org CHECK(start.Value() < end.Value()); 2120994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org LiveRange* second_part = SplitRangeAt(range, start); 2121994edf6a113fb3651536b60073df05a72a95f77erossberg@chromium.org if (!AllocationOk()) return; 2122a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 21235f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (second_part->Start().Value() < end.Value()) { 21245f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // The split result intersects with [start, end[. 21255f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // Split it at position between ]start+1, end[, spill the middle part 21265f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // and put the rest to unhandled. 21275f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org LiveRange* third_part = SplitBetween( 21285f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org second_part, 2129e27d617298263725e8a48c2aa14029759b952623mstarzinger@chromium.org Max(second_part->Start().InstructionEnd(), until), 21305f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org end.PrevInstruction().InstructionEnd()); 21312bda543d75374afd8d7e98f56ca99a57ae1b7bd1svenpanne@chromium.org if (!AllocationOk()) return; 2132a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 21335f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org ASSERT(third_part != second_part); 21348541d77d2d2a96c3e430974b3027f29b2a8e4a68lrn@chromium.org 21355f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org Spill(second_part); 2136a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org AddToUnhandledSorted(third_part); 2137a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } else { 21385f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // The split result does not intersect with [start, end[. 21395f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org // Nothing to spill. Just put it to unhandled as whole. 21405f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org AddToUnhandledSorted(second_part); 2141a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 2142a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 2143a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2144a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2145a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::Spill(LiveRange* range) { 2146a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org ASSERT(!range->IsSpilled()); 2147a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org TraceAlloc("Spilling live range %d\n", range->id()); 2148a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* first = range->TopLevel(); 2149a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2150a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (!first->HasAllocatedSpillOperand()) { 2151a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LOperand* op = TryReuseSpillSlot(range); 21525f0c45f2cacb31d36a8f80c31f17bda7751a3644ager@chromium.org if (op == NULL) op = chunk_->GetNextSpillSlot(mode_ == DOUBLE_REGISTERS); 2153a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org first->SetSpillOperand(op); 2154a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 21551510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org range->MakeSpilled(chunk()->zone()); 2156a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 2157a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2158a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2159a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgint LAllocator::RegisterCount() const { 2160a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return num_registers_; 2161a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 2162a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2163a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2164a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#ifdef DEBUG 2165a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2166a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2167a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgvoid LAllocator::Verify() const { 2168a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < live_ranges()->length(); ++i) { 2169a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org LiveRange* current = live_ranges()->at(i); 2170a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (current != NULL) current->Verify(); 2171a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 2172a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 2173a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2174a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2175a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org#endif 2176a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 2177a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 21781510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.orgLAllocatorPhase::LAllocatorPhase(const char* name, LAllocator* allocator) 21791510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org : CompilationPhase(name, allocator->graph()->info()), 21801510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org allocator_(allocator) { 21811510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org if (FLAG_hydrogen_stats) { 21821510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org allocator_zone_start_allocation_size_ = 21831510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org allocator->zone()->allocation_size(); 21841510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org } 21851510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org} 21861510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org 21871510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org 21881510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.orgLAllocatorPhase::~LAllocatorPhase() { 21891510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org if (FLAG_hydrogen_stats) { 21901510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org unsigned size = allocator_->zone()->allocation_size() - 21911510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org allocator_zone_start_allocation_size_; 21921510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org isolate()->GetHStatistics()->SaveTiming(name(), 0, size); 21931510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org } 21941510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org 21951510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org if (ShouldProduceTraceOutput()) { 21961510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org isolate()->GetHTracer()->TraceLithium(name(), allocator_->chunk()); 21971510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org isolate()->GetHTracer()->TraceLiveRanges(name(), allocator_); 21981510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org } 21991510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org 22001510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org#ifdef DEBUG 22011510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org if (allocator_ != NULL) allocator_->Verify(); 22021510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org#endif 22031510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org} 22041510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org 22051510d58cbcf57c82a10e7d390bfe21a7ae68ba43mstarzinger@chromium.org 2206a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} } // namespace v8::internal 2207