13ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// Copyright 2012 the V8 project authors. All rights reserved. 2b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Redistribution and use in source and binary forms, with or without 3b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// modification, are permitted provided that the following conditions are 4b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// met: 5b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// 6b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// * Redistributions of source code must retain the above copyright 7b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// notice, this list of conditions and the following disclaimer. 8b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// * Redistributions in binary form must reproduce the above 9b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// copyright notice, this list of conditions and the following 10b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// disclaimer in the documentation and/or other materials provided 11b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// with the distribution. 12b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// * Neither the name of Google Inc. nor the names of its 13b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// contributors may be used to endorse or promote products derived 14b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// from this software without specific prior written permission. 15b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// 16b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2844f0eee88ff00398ff7f715fab053374d808c90dSteve Block#include "v8.h" 291e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block#include "lithium-allocator-inl.h" 30b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 31b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#include "hydrogen.h" 32b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#include "string-stream.h" 33b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 34b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#if V8_TARGET_ARCH_IA32 35b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#include "ia32/lithium-ia32.h" 36b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#elif V8_TARGET_ARCH_X64 37b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#include "x64/lithium-x64.h" 38b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#elif V8_TARGET_ARCH_ARM 39b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#include "arm/lithium-arm.h" 4044f0eee88ff00398ff7f715fab053374d808c90dSteve Block#elif V8_TARGET_ARCH_MIPS 4144f0eee88ff00398ff7f715fab053374d808c90dSteve Block#include "mips/lithium-mips.h" 42b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#else 43b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#error "Unknown architecture." 44b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 45b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 46b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochnamespace v8 { 47b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochnamespace internal { 48b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 49b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) { 50b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return a.Value() < b.Value() ? a : b; 51b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 52b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 53b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 54b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) { 55b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return a.Value() > b.Value() ? a : b; 56b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 57b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 58b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 591e0659c275bb392c045087af4f6b0d7565cb3d77Steve BlockUsePosition::UsePosition(LifetimePosition pos, LOperand* operand) 601e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block : operand_(operand), 611e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block hint_(NULL), 621e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block pos_(pos), 631e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block next_(NULL), 641e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block requires_reg_(false), 651e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block register_beneficial_(true) { 661e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (operand_ != NULL && operand_->IsUnallocated()) { 671e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LUnallocated* unalloc = LUnallocated::cast(operand_); 681e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block requires_reg_ = unalloc->HasRegisterPolicy(); 691e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block register_beneficial_ = !unalloc->HasAnyPolicy(); 70b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 711e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block ASSERT(pos_.IsValid()); 72b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 73b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 741e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 751e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockbool UsePosition::HasHint() const { 761e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return hint_ != NULL && !hint_->IsUnallocated(); 77b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 78b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 79b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 80b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool UsePosition::RequiresRegister() const { 81b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return requires_reg_; 82b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 83b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 84b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 85b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool UsePosition::RegisterIsBeneficial() const { 86b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return register_beneficial_; 87b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 88b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 89b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 903ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid UseInterval::SplitAt(LifetimePosition pos, Zone* zone) { 91b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(Contains(pos) && pos.Value() != start().Value()); 923ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* after = new(zone) UseInterval(pos, end_); 93b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch after->next_ = next_; 94b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_ = after; 95b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end_ = pos; 96b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 97b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 98b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 99b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 100b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 101b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 102b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::Verify() const { 103b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* cur = first_pos_; 104b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (cur != NULL) { 105b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(Start().Value() <= cur->pos().Value() && 106b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur->pos().Value() <= End().Value()); 107b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur = cur->next(); 108b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 109b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 110b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 111b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 112b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::HasOverlap(UseInterval* target) const { 113b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* current_interval = first_interval_; 114b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current_interval != NULL) { 115b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Intervals overlap if the start of one is contained in the other. 116b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval->Contains(target->start()) || 117b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch target->Contains(current_interval->start())) { 118b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 119b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 120b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval = current_interval->next(); 121b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 122b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 123b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 124b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 125b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 126b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 127b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 128b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1293ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLiveRange::LiveRange(int id, Zone* zone) 1301e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block : id_(id), 1311e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spilled_(false), 1323ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch is_double_(false), 1331e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_(kInvalidAssignment), 1341e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block last_interval_(NULL), 1351e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block first_interval_(NULL), 1361e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block first_pos_(NULL), 1371e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block parent_(NULL), 1381e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block next_(NULL), 1391e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block current_interval_(NULL), 1401e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block last_processed_use_(NULL), 1413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch spill_operand_(new(zone) LOperand()), 1423ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch spill_start_index_(kMaxInt) { } 1431e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1441e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1453ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::set_assigned_register(int reg, 1463ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch RegisterKind register_kind, 1473ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 1481e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block ASSERT(!HasRegisterAssigned() && !IsSpilled()); 1491e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_ = reg; 1503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch is_double_ = (register_kind == DOUBLE_REGISTERS); 1513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ConvertOperands(zone); 1521e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1531e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1541e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1553ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::MakeSpilled(Zone* zone) { 1561e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block ASSERT(!IsSpilled()); 1571e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block ASSERT(TopLevel()->HasAllocatedSpillOperand()); 1581e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spilled_ = true; 1591e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_ = kInvalidAssignment; 1603ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ConvertOperands(zone); 1611e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1621e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1631e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1641e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockbool LiveRange::HasAllocatedSpillOperand() const { 1653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ASSERT(spill_operand_ != NULL); 1663ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return !spill_operand_->IsIgnored(); 1671e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1681e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1691e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1701e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockvoid LiveRange::SetSpillOperand(LOperand* operand) { 1711e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block ASSERT(!operand->IsUnallocated()); 1721e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block ASSERT(spill_operand_ != NULL); 1733ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ASSERT(spill_operand_->IsIgnored()); 1741e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spill_operand_->ConvertTo(operand->kind(), operand->index()); 1751e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1761e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1771e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 178b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextUsePosition(LifetimePosition start) { 179b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = last_processed_use_; 180b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos == NULL) use_pos = first_pos(); 181b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_pos != NULL && use_pos->pos().Value() < start.Value()) { 182b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = use_pos->next(); 183b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 184b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_processed_use_ = use_pos; 185b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return use_pos; 186b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 187b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 188b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 189b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextUsePositionRegisterIsBeneficial( 190b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start) { 191b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = NextUsePosition(start); 192b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (pos != NULL && !pos->RegisterIsBeneficial()) { 193b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos = pos->next(); 194b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 195b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos; 196b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 197b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 198b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 199b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) { 200b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = NextUsePosition(start); 201b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (pos != NULL && !pos->RequiresRegister()) { 202b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos = pos->next(); 203b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 204b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos; 205b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 206b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 207b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 208b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::CanBeSpilled(LifetimePosition pos) { 209b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // TODO(kmillikin): Comment. Now. 210b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() <= Start().Value() && HasRegisterAssigned()) return false; 211b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 212b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We cannot spill a live range that has a use requiring a register 213b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // at the current or the immediate next position. 214b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = NextRegisterPosition(pos); 215b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos == NULL) return true; 2163ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return 2173ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch use_pos->pos().Value() > pos.NextInstruction().InstructionEnd().Value(); 218b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 219b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 220b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 221b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::FirstPosWithHint() const { 222b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = first_pos_; 223b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (pos != NULL && !pos->HasHint()) pos = pos->next(); 224b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos; 225b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 226b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 227b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2283ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLOperand* LiveRange::CreateAssignedOperand(Zone* zone) { 229b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* op = NULL; 230b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (HasRegisterAssigned()) { 231b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!IsSpilled()); 232b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (IsDouble()) { 233b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch op = LDoubleRegister::Create(assigned_register()); 234b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 235b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch op = LRegister::Create(assigned_register()); 236b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 237b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (IsSpilled()) { 238b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!HasRegisterAssigned()); 239b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch op = TopLevel()->GetSpillOperand(); 240b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!op->IsUnallocated()); 241b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 2423ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated* unalloc = new(zone) LUnallocated(LUnallocated::NONE); 243b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unalloc->set_virtual_register(id_); 244b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch op = unalloc; 245b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 246b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return op; 247b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 248b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 249b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 250b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUseInterval* LiveRange::FirstSearchIntervalForPosition( 251b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position) const { 252b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval_ == NULL) return first_interval_; 253b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval_->start().Value() > position.Value()) { 254b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ = NULL; 255b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return first_interval_; 256b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 257b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return current_interval_; 258b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 259b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 260b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 261b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::AdvanceLastProcessedMarker( 262b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* to_start_of, LifetimePosition but_not_past) const { 263b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of == NULL) return; 264b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of->start().Value() > but_not_past.Value()) return; 265b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = 266b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ == NULL ? LifetimePosition::Invalid() 267b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch : current_interval_->start(); 268b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of->start().Value() > start.Value()) { 269b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ = to_start_of; 270b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 271b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 272b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 273b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2743ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::SplitAt(LifetimePosition position, 2753ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* result, 2763ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 277b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(Start().Value() < position.Value()); 278b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(result->IsEmpty()); 279b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the last interval that ends before the position. If the 280b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position is contained in one of the intervals in the chain, we 281b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // split that interval and use the first part. 282b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* current = FirstSearchIntervalForPosition(position); 283b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 284b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If the split position coincides with the beginning of a use interval 285b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // we need to split use positons in a special way. 286b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool split_at_start = false; 287b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2883fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch if (current->start().Value() == position.Value()) { 2893fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // When splitting at start we need to locate the previous use interval. 2903fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch current = first_interval_; 2913fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch } 2923fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 293b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current != NULL) { 294b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current->Contains(position)) { 2953ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch current->SplitAt(position, zone); 296b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch break; 297b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 298b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* next = current->next(); 299b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next->start().Value() >= position.Value()) { 300b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch split_at_start = (next->start().Value() == position.Value()); 301b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch break; 302b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 303b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current = next; 304b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 305b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 306b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Partition original use intervals to the two live ranges. 307b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* before = current; 308b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* after = before->next(); 309b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->last_interval_ = (last_interval_ == before) 310b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ? after // Only interval in the range after split. 311b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch : last_interval_; // Last interval of the original range. 312b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->first_interval_ = after; 313b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = before; 314b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 315b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the last use position before the split and the first use 316b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position after it. 317b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_after = first_pos_; 318b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_before = NULL; 319b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (split_at_start) { 320b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split position coincides with the beginning of a use interval (the 321b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // end of a lifetime hole). Use at this position should be attributed to 322b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the split child because split child owns use interval covering it. 323b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_after != NULL && use_after->pos().Value() < position.Value()) { 324b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before = use_after; 325b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_after = use_after->next(); 326b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 327b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 328b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_after != NULL && use_after->pos().Value() <= position.Value()) { 329b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before = use_after; 330b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_after = use_after->next(); 331b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 332b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 333b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 334b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Partition original use positions to the two live ranges. 335b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_before != NULL) { 336b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before->next_ = NULL; 337b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 338b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_pos_ = NULL; 339b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 340b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->first_pos_ = use_after; 341b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3423fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Discard cached iteration state. It might be pointing 3433fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // to the use that no longer belongs to this live range. 3443fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch last_processed_use_ = NULL; 3453fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch current_interval_ = NULL; 3463fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 347b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Link the new live range in the chain before any of the other 348b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // ranges linked from the range before the split. 349b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->parent_ = (parent_ == NULL) ? this : parent_; 350b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->next_ = next_; 351b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_ = result; 352b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 353b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 354b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Verify(); 355b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->Verify(); 356b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 357b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 358b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 359b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 360b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// This implements an ordering on live ranges so that they are ordered by their 361b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// start positions. This is needed for the correctness of the register 362b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// allocation algorithm. If two live ranges start at the same offset then there 363b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// is a tie breaker based on where the value is first used. This part of the 364b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// ordering is merely a heuristic. 365b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const { 366b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = Start(); 367b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition other_start = other->Start(); 368b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start.Value() == other_start.Value()) { 369b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = FirstPosWithHint(); 370b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos == NULL) return false; 371b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* other_pos = other->first_pos(); 372b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (other_pos == NULL) return true; 373b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos->pos().Value() < other_pos->pos().Value(); 374b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 375b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return start.Value() < other_start.Value(); 376b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 377b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 378b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 379b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::ShortenTo(LifetimePosition start) { 380b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Shorten live range %d to [%d\n", id_, start.Value()); 381b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(first_interval_ != NULL); 382b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(first_interval_->start().Value() <= start.Value()); 383b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(start.Value() < first_interval_->end().Value()); 384b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->set_start(start); 385b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 386b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 387b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3883ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::EnsureInterval(LifetimePosition start, 3893ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LifetimePosition end, 3903ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 391b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Ensure live range %d in interval [%d %d[\n", 392b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 393b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 394b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 395b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition new_end = end; 396b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (first_interval_ != NULL && 397b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->start().Value() <= end.Value()) { 398b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_interval_->end().Value() > end.Value()) { 399b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch new_end = first_interval_->end(); 400b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 401b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = first_interval_->next(); 402b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 403b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 4043ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* new_interval = new(zone) UseInterval(start, new_end); 405b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch new_interval->next_ = first_interval_; 406b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = new_interval; 407b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (new_interval->next() == NULL) { 408b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = new_interval; 409b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 410b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 411b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 412b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 4133ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::AddUseInterval(LifetimePosition start, 4143ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LifetimePosition end, 4153ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 416b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Add to live range %d interval [%d %d[\n", 417b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 418b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 419b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 420b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_interval_ == NULL) { 4213ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* interval = new(zone) UseInterval(start, end); 422b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = interval; 423b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = interval; 424b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 425b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (end.Value() == first_interval_->start().Value()) { 426b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->set_start(start); 427b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (end.Value() < first_interval_->start().Value()) { 4283ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* interval = new(zone) UseInterval(start, end); 429b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval->set_next(first_interval_); 430b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = interval; 431b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 432b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Order of instruction's processing (see ProcessInstructions) guarantees 433b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // that each new use interval either precedes or intersects with 434b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // last added interval. 435b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(start.Value() < first_interval_->end().Value()); 436b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->start_ = Min(start, first_interval_->start_); 437b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->end_ = Max(end, first_interval_->end_); 438b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 439b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 440b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 441b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 442b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 443b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::AddUsePosition(LifetimePosition pos, 4443ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* operand, 4453ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 446b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Add to live range %d use position %d\n", 447b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 448b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos.Value()); 4493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UsePosition* use_pos = new(zone) UsePosition(pos, operand); 450b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* prev = NULL; 451b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* current = first_pos_; 452b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current != NULL && current->pos().Value() < pos.Value()) { 453b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch prev = current; 454b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current = current->next(); 455b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 456b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 457b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (prev == NULL) { 458b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->set_next(first_pos_); 459b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_pos_ = use_pos; 460b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 461b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->next_ = prev->next_; 462b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch prev->next_ = use_pos; 463b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 464b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 465b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return use_pos; 466b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 467b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 468b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 4693ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::ConvertOperands(Zone* zone) { 4703ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* op = CreateAssignedOperand(zone); 471b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = first_pos(); 472b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_pos != NULL) { 473b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(Start().Value() <= use_pos->pos().Value() && 474b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->pos().Value() <= End().Value()); 475b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 476b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos->HasOperand()) { 477b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(op->IsRegister() || op->IsDoubleRegister() || 478b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch !use_pos->RequiresRegister()); 479b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->operand()->ConvertTo(op->kind(), op->index()); 480b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 481b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = use_pos->next(); 482b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 483b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 484b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 485b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 486b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::CanCover(LifetimePosition position) const { 487b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (IsEmpty()) return false; 488b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return Start().Value() <= position.Value() && 489b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch position.Value() < End().Value(); 490b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 491b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 492b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 493b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::Covers(LifetimePosition position) { 494b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!CanCover(position)) return false; 495b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* start_search = FirstSearchIntervalForPosition(position); 496b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (UseInterval* interval = start_search; 497b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval != NULL; 498b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval = interval->next()) { 499b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(interval->next() == NULL || 500b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval->next()->start().Value() >= interval->start().Value()); 501b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AdvanceLastProcessedMarker(interval, position); 502b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (interval->Contains(position)) return true; 503b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (interval->start().Value() > position.Value()) return false; 504b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 505b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 506b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 507b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 508b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 509b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLifetimePosition LiveRange::FirstIntersection(LiveRange* other) { 510b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* b = other->first_interval(); 511b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (b == NULL) return LifetimePosition::Invalid(); 512b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition advance_last_processed_up_to = b->start(); 513b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* a = FirstSearchIntervalForPosition(b->start()); 514b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (a != NULL && b != NULL) { 515b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->start().Value() > other->End().Value()) break; 516b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (b->start().Value() > End().Value()) break; 517b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition cur_intersection = a->Intersect(b); 518b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_intersection.IsValid()) { 519b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return cur_intersection; 520b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 521b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->start().Value() < b->start().Value()) { 522b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch a = a->next(); 523b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a == NULL || a->start().Value() > other->End().Value()) break; 524b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AdvanceLastProcessedMarker(a, advance_last_processed_up_to); 525b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 526b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch b = b->next(); 527b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 528b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 529b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition::Invalid(); 530b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 531b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 532b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 53344f0eee88ff00398ff7f715fab053374d808c90dSteve BlockLAllocator::LAllocator(int num_values, HGraph* graph) 5343ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch : zone_(graph->zone()), 5353ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch chunk_(NULL), 53644f0eee88ff00398ff7f715fab053374d808c90dSteve Block live_in_sets_(graph->blocks()->length()), 53744f0eee88ff00398ff7f715fab053374d808c90dSteve Block live_ranges_(num_values * 2), 53844f0eee88ff00398ff7f715fab053374d808c90dSteve Block fixed_live_ranges_(NULL), 53944f0eee88ff00398ff7f715fab053374d808c90dSteve Block fixed_double_live_ranges_(NULL), 54044f0eee88ff00398ff7f715fab053374d808c90dSteve Block unhandled_live_ranges_(num_values * 2), 54144f0eee88ff00398ff7f715fab053374d808c90dSteve Block active_live_ranges_(8), 54244f0eee88ff00398ff7f715fab053374d808c90dSteve Block inactive_live_ranges_(8), 54344f0eee88ff00398ff7f715fab053374d808c90dSteve Block reusable_slots_(8), 54444f0eee88ff00398ff7f715fab053374d808c90dSteve Block next_virtual_register_(num_values), 54544f0eee88ff00398ff7f715fab053374d808c90dSteve Block first_artificial_register_(num_values), 5463ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch mode_(GENERAL_REGISTERS), 54744f0eee88ff00398ff7f715fab053374d808c90dSteve Block num_registers_(-1), 54844f0eee88ff00398ff7f715fab053374d808c90dSteve Block graph_(graph), 5493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch has_osr_entry_(false), 5503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch allocation_ok_(true) { } 55144f0eee88ff00398ff7f715fab053374d808c90dSteve Block 55244f0eee88ff00398ff7f715fab053374d808c90dSteve Block 553b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::InitializeLivenessAnalysis() { 554b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Initialize the live_in sets for each block to NULL. 5551e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block int block_count = graph_->blocks()->length(); 556b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_in_sets_.Initialize(block_count); 557b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_in_sets_.AddBlock(NULL, block_count); 558b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 559b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 560b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 561b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochBitVector* LAllocator::ComputeLiveOut(HBasicBlock* block) { 562b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Compute live out for the given block, except not including backward 563b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // successor edges. 5643ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch BitVector* live_out = new(zone_) BitVector(next_virtual_register_, zone_); 565b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 566b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process all successor blocks. 5673fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) { 568b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Add values live on entry to the successor. Note the successor's 569b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // live_in will not be computed yet for backwards edges. 5703fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch HBasicBlock* successor = it.Current(); 571b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live_in = live_in_sets_[successor->block_id()]; 572b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (live_in != NULL) live_out->Union(*live_in); 573b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 574b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All phi input operands corresponding to this successor edge are live 575b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // out from this block. 576b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = successor->PredecessorIndexOf(block); 577b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<HPhi*>* phis = successor->phis(); 578b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < phis->length(); ++i) { 579b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = phis->at(i); 580b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!phi->OperandAt(index)->IsConstant()) { 581b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_out->Add(phi->OperandAt(index)->id()); 582b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 583b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 584b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 585b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 586b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return live_out; 587b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 588b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 589b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 590b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddInitialIntervals(HBasicBlock* block, 591b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live_out) { 592b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Add an interval that includes the entire block to the live range for 593b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // each live_out value. 594b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = LifetimePosition::FromInstructionIndex( 595b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 596b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end = LifetimePosition::FromInstructionIndex( 597b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->last_instruction_index()).NextInstruction(); 598b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live_out); 599b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 600b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 601b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand_index); 6023ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch range->AddUseInterval(start, end, zone_); 603b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 604b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 605b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 606b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 607b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 608b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochint LAllocator::FixedDoubleLiveRangeID(int index) { 609b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return -index - 1 - Register::kNumAllocatableRegisters; 610b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 611b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 612b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 613b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLOperand* LAllocator::AllocateFixed(LUnallocated* operand, 614b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int pos, 615b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool is_tagged) { 616b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Allocating fixed reg for op %d\n", operand->virtual_register()); 617b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(operand->HasFixedPolicy()); 618b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (operand->policy() == LUnallocated::FIXED_SLOT) { 619b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand->ConvertTo(LOperand::STACK_SLOT, operand->fixed_index()); 620b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (operand->policy() == LUnallocated::FIXED_REGISTER) { 621b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int reg_index = operand->fixed_index(); 622b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand->ConvertTo(LOperand::REGISTER, reg_index); 623b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (operand->policy() == LUnallocated::FIXED_DOUBLE_REGISTER) { 624b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int reg_index = operand->fixed_index(); 625b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand->ConvertTo(LOperand::DOUBLE_REGISTER, reg_index); 626b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 627b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UNREACHABLE(); 628b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 629b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (is_tagged) { 630b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Fixed reg is tagged at %d\n", pos); 6311e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = InstructionAt(pos); 632b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (instr->HasPointerMap()) { 633b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch instr->pointer_map()->RecordPointer(operand); 634b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 635b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 636b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return operand; 637b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 638b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 639b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 640b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::FixedLiveRangeFor(int index) { 64144f0eee88ff00398ff7f715fab053374d808c90dSteve Block ASSERT(index < Register::kNumAllocatableRegisters); 642b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* result = fixed_live_ranges_[index]; 643b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (result == NULL) { 6443ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch result = new(zone_) LiveRange(FixedLiveRangeID(index), zone_); 645b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(result->IsFixed()); 6463ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch result->set_assigned_register(index, GENERAL_REGISTERS, zone_); 647b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch fixed_live_ranges_[index] = result; 648b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 649b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 650b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 651b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 652b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 653b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::FixedDoubleLiveRangeFor(int index) { 65444f0eee88ff00398ff7f715fab053374d808c90dSteve Block ASSERT(index < DoubleRegister::kNumAllocatableRegisters); 655b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* result = fixed_double_live_ranges_[index]; 656b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (result == NULL) { 6573ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch result = new(zone_) LiveRange(FixedDoubleLiveRangeID(index), zone_); 658b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(result->IsFixed()); 6593ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch result->set_assigned_register(index, DOUBLE_REGISTERS, zone_); 660b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch fixed_double_live_ranges_[index] = result; 661b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 662b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 663b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 664b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 66544f0eee88ff00398ff7f715fab053374d808c90dSteve Block 666b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::LiveRangeFor(int index) { 667b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (index >= live_ranges_.length()) { 668b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_ranges_.AddBlock(NULL, index - live_ranges_.length() + 1); 669b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 670b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* result = live_ranges_[index]; 671b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (result == NULL) { 6723ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch result = new(zone_) LiveRange(index, zone_); 673b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_ranges_[index] = result; 674b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 675b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 676b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 677b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 678b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 6791e0659c275bb392c045087af4f6b0d7565cb3d77Steve BlockLGap* LAllocator::GetLastGap(HBasicBlock* block) { 680b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int last_instruction = block->last_instruction_index(); 681b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = chunk_->NearestGapPos(last_instruction); 6821e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return GapAt(index); 683b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 684b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 685b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 686b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochHPhi* LAllocator::LookupPhi(LOperand* operand) const { 687b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!operand->IsUnallocated()) return NULL; 6883ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int index = LUnallocated::cast(operand)->virtual_register(); 6891e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block HValue* instr = graph_->LookupValue(index); 690b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (instr != NULL && instr->IsPhi()) { 691b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return HPhi::cast(instr); 692b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 693b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 694b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 695b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 696b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 697b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::LiveRangeFor(LOperand* operand) { 698b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (operand->IsUnallocated()) { 699b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LiveRangeFor(LUnallocated::cast(operand)->virtual_register()); 700b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (operand->IsRegister()) { 701b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return FixedLiveRangeFor(operand->index()); 702b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (operand->IsDoubleRegister()) { 703b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return FixedDoubleLiveRangeFor(operand->index()); 704b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 705b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 706b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 707b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 708b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 709b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 710b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Define(LifetimePosition position, 711b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand, 712b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint) { 713b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand); 714b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL) return; 715b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 716b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsEmpty() || range->Start().Value() > position.Value()) { 717b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Can happen if there is a definition without use. 7183ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch range->AddUseInterval(position, position.NextInstruction(), zone_); 7193ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch range->AddUsePosition(position.NextInstruction(), NULL, zone_); 720b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 721b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->ShortenTo(position); 722b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 723b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 724b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (operand->IsUnallocated()) { 725b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* unalloc_operand = LUnallocated::cast(operand); 7263ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch range->AddUsePosition(position, unalloc_operand, zone_)->set_hint(hint); 727b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 728b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 729b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 730b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 731b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Use(LifetimePosition block_start, 732b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position, 733b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand, 734b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint) { 735b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand); 736b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL) return; 737b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (operand->IsUnallocated()) { 738b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* unalloc_operand = LUnallocated::cast(operand); 7393ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch range->AddUsePosition(position, unalloc_operand, zone_)->set_hint(hint); 740b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 7413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch range->AddUseInterval(block_start, position, zone_); 742b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 743b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 744b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 745b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddConstraintsGapMove(int index, 746b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* from, 747b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* to) { 7481e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(index); 749b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START); 750b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (from->IsUnallocated()) { 751b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LMoveOperands>* move_operands = move->move_operands(); 752b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < move_operands->length(); ++i) { 753b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LMoveOperands cur = move_operands->at(i); 754b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* cur_to = cur.destination(); 755b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_to->IsUnallocated()) { 7563ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (LUnallocated::cast(cur_to)->virtual_register() == 7573ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated::cast(from)->virtual_register()) { 758b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch move->AddMove(cur.source(), to); 759b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 760b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 761b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 762b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 763b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 764b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch move->AddMove(from, to); 765b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 766b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 767b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 768b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::MeetRegisterConstraints(HBasicBlock* block) { 769b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int start = block->first_instruction_index(); 770b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int end = block->last_instruction_index(); 771b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = start; i <= end; ++i) { 7721e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(i)) { 7731e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = NULL; 7741e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* prev_instr = NULL; 7751e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (i < end) instr = InstructionAt(i + 1); 7761e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (i > start) prev_instr = InstructionAt(i - 1); 7771e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block MeetConstraintsBetween(prev_instr, instr, i); 7783ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 779b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 780b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 781b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 782b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 783b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 7841e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockvoid LAllocator::MeetConstraintsBetween(LInstruction* first, 7851e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* second, 786b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int gap_index) { 787b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle fixed temporaries. 788b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first != NULL) { 7893fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (TempIterator it(first); !it.Done(); it.Advance()) { 7903fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LUnallocated* temp = LUnallocated::cast(it.Current()); 791b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp->HasFixedPolicy()) { 792b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateFixed(temp, gap_index - 1, false); 793b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 794b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 795b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 796b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 797b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle fixed output operand. 798b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first != NULL && first->Output() != NULL) { 799b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* first_output = LUnallocated::cast(first->Output()); 8003ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* range = LiveRangeFor(first_output->virtual_register()); 801b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool assigned = false; 802b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_output->HasFixedPolicy()) { 803b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* output_copy = first_output->CopyUnconstrained(); 8043ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool is_tagged = HasTaggedValue(first_output->virtual_register()); 805b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateFixed(first_output, gap_index, is_tagged); 806b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 807b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This value is produced on the stack, we never need to spill it. 808b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_output->IsStackSlot()) { 809b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->SetSpillOperand(first_output); 810b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->SetSpillStartIndex(gap_index - 1); 811b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch assigned = true; 812b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 813b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch chunk_->AddGapMove(gap_index, first_output, output_copy); 814b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 815b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 816b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!assigned) { 817b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->SetSpillStartIndex(gap_index); 818b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 819b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This move to spill operand is not a real use. Liveness analysis 820b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // and splitting of live ranges do not account for it. 821b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Thus it should be inserted to a lifetime position corresponding to 822b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the instruction end. 8231e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(gap_index); 824b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::BEFORE); 825b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch move->AddMove(first_output, range->GetSpillOperand()); 826b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 827b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 828b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 829b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle fixed input operands of second instruction. 830b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second != NULL) { 8313fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (UseIterator it(second); !it.Done(); it.Advance()) { 8323fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LUnallocated* cur_input = LUnallocated::cast(it.Current()); 833b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_input->HasFixedPolicy()) { 834b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* input_copy = cur_input->CopyUnconstrained(); 8353ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool is_tagged = HasTaggedValue(cur_input->virtual_register()); 836b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateFixed(cur_input, gap_index + 1, is_tagged); 837b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddConstraintsGapMove(gap_index, input_copy, cur_input); 838b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (cur_input->policy() == LUnallocated::WRITABLE_REGISTER) { 839b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch // The live range of writable input registers always goes until the end 840b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch // of the instruction. 841b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch ASSERT(!cur_input->IsUsedAtStart()); 842b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch 843b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* input_copy = cur_input->CopyUnconstrained(); 8443ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch cur_input->set_virtual_register(GetVirtualRegister()); 8453ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 8469fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 8479fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (RequiredRegisterKind(input_copy->virtual_register()) == 8489fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block DOUBLE_REGISTERS) { 8499fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block double_artificial_registers_.Add( 8503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch cur_input->virtual_register() - first_artificial_register_, 8513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch zone_); 8529fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 8539fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 854b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddConstraintsGapMove(gap_index, input_copy, cur_input); 855b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 856b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 857b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 858b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 859b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle "output same as input" for second instruction. 860b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second != NULL && second->Output() != NULL) { 861b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* second_output = LUnallocated::cast(second->Output()); 862b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second_output->HasSameAsInputPolicy()) { 8631e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LUnallocated* cur_input = LUnallocated::cast(second->FirstInput()); 8643ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int output_vreg = second_output->virtual_register(); 8653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int input_vreg = cur_input->virtual_register(); 866b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 867b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* input_copy = cur_input->CopyUnconstrained(); 868b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_input->set_virtual_register(second_output->virtual_register()); 869b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddConstraintsGapMove(gap_index, input_copy, cur_input); 870b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 871b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (HasTaggedValue(input_vreg) && !HasTaggedValue(output_vreg)) { 872b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = gap_index + 1; 8731e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = InstructionAt(index); 874b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (instr->HasPointerMap()) { 875b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch instr->pointer_map()->RecordPointer(input_copy); 876b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 877b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (!HasTaggedValue(input_vreg) && HasTaggedValue(output_vreg)) { 878b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The input is assumed to immediately have a tagged representation, 879b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // before the pointer map can be used. I.e. the pointer map at the 880b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // instruction will include the output operand (whose value at the 881b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // beginning of the instruction is equal to the input operand). If 882b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // this is not desired, then the pointer map at this instruction needs 883b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // to be adjusted manually. 884b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 885b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 886b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 887b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 888b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 889b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 890b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) { 891b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int block_start = block->first_instruction_index(); 892b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = block->last_instruction_index(); 893b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 894b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition block_start_position = 895b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(block_start); 896b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 897b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (index >= block_start) { 898b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition curr_position = 899b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(index); 900b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9011e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(index)) { 902b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We have a gap at this position. 9031e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(index); 904b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START); 905b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LMoveOperands>* move_operands = move->move_operands(); 906b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < move_operands->length(); ++i) { 907b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LMoveOperands* cur = &move_operands->at(i); 908b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur->IsIgnored()) continue; 909b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* from = cur->source(); 910b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* to = cur->destination(); 911b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = LookupPhi(to); 912b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint = to; 913b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (phi != NULL) { 914b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This is a phi resolving move. 915b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!phi->block()->IsLoopHeader()) { 916b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch hint = LiveRangeFor(phi->id())->FirstHint(); 917b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 918b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 919b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to->IsUnallocated()) { 9203ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (live->Contains(LUnallocated::cast(to)->virtual_register())) { 921b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, to, from); 9223ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Remove(LUnallocated::cast(to)->virtual_register()); 923b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 924b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur->Eliminate(); 925b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 926b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 927b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 928b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, to, from); 929b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 930b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 931b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Use(block_start_position, curr_position, from, hint); 932b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (from->IsUnallocated()) { 9333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Add(LUnallocated::cast(from)->virtual_register()); 934b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 935b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 936b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 9371e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block ASSERT(!IsGapAt(index)); 9381e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = InstructionAt(index); 939b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9401e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (instr != NULL) { 9411e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LOperand* output = instr->Output(); 942b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (output != NULL) { 9433ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (output->IsUnallocated()) { 9443ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Remove(LUnallocated::cast(output)->virtual_register()); 9453ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 946b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, output, NULL); 947b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 948b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9491e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (instr->IsMarkedAsCall()) { 950b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < Register::kNumAllocatableRegisters; ++i) { 951b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (output == NULL || !output->IsRegister() || 952b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch output->index() != i) { 953b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = FixedLiveRangeFor(i); 954b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->AddUseInterval(curr_position, 9553ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch curr_position.InstructionEnd(), 9563ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch zone_); 957b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 958b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 959086aeeaae12517475c22695a200be45495516549Ben Murdoch } 960086aeeaae12517475c22695a200be45495516549Ben Murdoch 9611e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (instr->IsMarkedAsCall() || instr->IsMarkedAsSaveDoubles()) { 962b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < DoubleRegister::kNumAllocatableRegisters; ++i) { 963b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (output == NULL || !output->IsDoubleRegister() || 964b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch output->index() != i) { 965b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = FixedDoubleLiveRangeFor(i); 966b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->AddUseInterval(curr_position, 9673ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch curr_position.InstructionEnd(), 9683ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch zone_); 969b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 970b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 971b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 972b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9733fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (UseIterator it(instr); !it.Done(); it.Advance()) { 9743fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LOperand* input = it.Current(); 975b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 976b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition use_pos; 977b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (input->IsUnallocated() && 978b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated::cast(input)->IsUsedAtStart()) { 979b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = curr_position; 980b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 981b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = curr_position.InstructionEnd(); 982b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 983b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 984b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Use(block_start_position, use_pos, input, NULL); 9853ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (input->IsUnallocated()) { 9863ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Add(LUnallocated::cast(input)->virtual_register()); 9873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 988b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 989b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9903fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (TempIterator it(instr); !it.Done(); it.Advance()) { 9913fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LOperand* temp = it.Current(); 9921e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (instr->IsMarkedAsCall()) { 993b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp->IsRegister()) continue; 994b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp->IsUnallocated()) { 995b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* temp_unalloc = LUnallocated::cast(temp); 996b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp_unalloc->HasFixedPolicy()) { 997b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 998b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 999b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1000b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1001b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Use(block_start_position, curr_position.InstructionEnd(), temp, NULL); 1002b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, temp, NULL); 1003b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1004b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1005b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1006b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1007b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch index = index - 1; 1008b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1009b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1010b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1011b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1012b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolvePhis(HBasicBlock* block) { 1013b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<HPhi*>* phis = block->phis(); 1014b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < phis->length(); ++i) { 1015b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = phis->at(i); 10163ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated* phi_operand = new(zone_) LUnallocated(LUnallocated::NONE); 1017b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch phi_operand->set_virtual_register(phi->id()); 1018b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int j = 0; j < phi->OperandCount(); ++j) { 1019b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HValue* op = phi->OperandAt(j); 1020b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand = NULL; 1021b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (op->IsConstant() && op->EmitAtUses()) { 1022b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HConstant* constant = HConstant::cast(op); 1023b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand = chunk_->DefineConstantOperand(constant); 1024b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1025b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!op->EmitAtUses()); 10263ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated* unalloc = new(zone_) LUnallocated(LUnallocated::ANY); 1027b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unalloc->set_virtual_register(op->id()); 1028b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand = unalloc; 1029b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1030b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* cur_block = block->predecessors()->at(j); 1031b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The gap move must be added without any special processing as in 1032b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the AddConstraintsGapMove. 1033b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch chunk_->AddGapMove(cur_block->last_instruction_index() - 1, 1034b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand, 1035b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch phi_operand); 1036257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 1037257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // We are going to insert a move before the branch instruction. 1038257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // Some branch instructions (e.g. loops' back edges) 1039257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // can potentially cause a GC so they have a pointer map. 1040257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // By inserting a move we essentially create a copy of a 1041257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // value which is invisible to PopulatePointerMaps(), because we store 1042257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // it into a location different from the operand of a live range 1043257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // covering a branch instruction. 1044257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // Thus we need to manually record a pointer. 10453ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LInstruction* branch = 10463ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch InstructionAt(cur_block->last_instruction_index()); 10473ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (branch->HasPointerMap()) { 10483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (phi->representation().IsTagged()) { 1049257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch branch->pointer_map()->RecordPointer(phi_operand); 10503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } else if (!phi->representation().IsDouble()) { 10513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch branch->pointer_map()->RecordUntagged(phi_operand); 1052257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch } 1053257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch } 1054b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1055b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1056b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* live_range = LiveRangeFor(phi->id()); 1057b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LLabel* label = chunk_->GetLabel(phi->block()->block_id()); 1058b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch label->GetOrCreateParallelMove(LGap::START)-> 1059b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddMove(phi_operand, live_range->GetSpillOperand()); 1060b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_range->SetSpillStartIndex(phi->block()->first_instruction_index()); 1061b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1062b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1063b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1064b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 10653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochbool LAllocator::Allocate(LChunk* chunk) { 1066b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(chunk_ == NULL); 1067b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch chunk_ = chunk; 1068b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch MeetRegisterConstraints(); 10693ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1070b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolvePhis(); 1071b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BuildLiveRanges(); 1072b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateGeneralRegisters(); 10733ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1074b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateDoubleRegisters(); 10753ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1076b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PopulatePointerMaps(); 1077b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (has_osr_entry_) ProcessOsrEntry(); 1078b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ConnectRanges(); 1079b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolveControlFlow(); 10803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return true; 1081b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1082b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1083b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1084b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::MeetRegisterConstraints() { 10853ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch HPhase phase("L_Register constraints", chunk_); 10869fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block first_artificial_register_ = next_virtual_register_; 10871e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1088b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < blocks->length(); ++i) { 1089b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(i); 1090b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch MeetRegisterConstraints(block); 10913ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 1092b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1093b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1094b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1095b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1096b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolvePhis() { 10973ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch HPhase phase("L_Resolve phis", chunk_); 1098b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1099b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process the blocks in reverse order. 11001e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1101b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { 1102b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(block_id); 1103b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolvePhis(block); 1104b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1105b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1106b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1107b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1108b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolveControlFlow(LiveRange* range, 1109b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block, 1110b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* pred) { 1111b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pred_end = 11121e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LifetimePosition::FromInstructionIndex(pred->last_instruction_index()); 1113b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition cur_start = 1114b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(block->first_instruction_index()); 1115b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* pred_cover = NULL; 1116b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_cover = NULL; 1117b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_range = range; 1118b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (cur_range != NULL && (cur_cover == NULL || pred_cover == NULL)) { 1119b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_range->CanCover(cur_start)) { 1120b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(cur_cover == NULL); 1121b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_cover = cur_range; 1122b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1123b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_range->CanCover(pred_end)) { 1124b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(pred_cover == NULL); 1125b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pred_cover = cur_range; 1126b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1127b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_range = cur_range->next(); 1128b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1129b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1130b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_cover->IsSpilled()) return; 1131b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(pred_cover != NULL && cur_cover != NULL); 1132b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pred_cover != cur_cover) { 11333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* pred_op = pred_cover->CreateAssignedOperand(zone_); 11343ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* cur_op = cur_cover->CreateAssignedOperand(zone_); 1135b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!pred_op->Equals(cur_op)) { 1136b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LGap* gap = NULL; 1137b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block->predecessors()->length() == 1) { 11381e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block gap = GapAt(block->first_instruction_index()); 1139b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1140b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(pred->end()->SecondSuccessor() == NULL); 1141b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch gap = GetLastGap(pred); 1142e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch 1143e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // We are going to insert a move before the branch instruction. 1144e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // Some branch instructions (e.g. loops' back edges) 1145e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // can potentially cause a GC so they have a pointer map. 1146257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // By inserting a move we essentially create a copy of a 1147e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // value which is invisible to PopulatePointerMaps(), because we store 1148e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // it into a location different from the operand of a live range 1149e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // covering a branch instruction. 1150e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // Thus we need to manually record a pointer. 11513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LInstruction* branch = InstructionAt(pred->last_instruction_index()); 11523ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (branch->HasPointerMap()) { 11533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (HasTaggedValue(range->id())) { 1154e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch branch->pointer_map()->RecordPointer(cur_op); 11553ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } else if (!cur_op->IsDoubleStackSlot() && 11563ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch !cur_op->IsDoubleRegister()) { 11573ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch branch->pointer_map()->RemovePointer(cur_op); 1158e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch } 1159e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch } 1160b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1161b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch gap->GetOrCreateParallelMove(LGap::START)->AddMove(pred_op, cur_op); 1162b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1163b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1164b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1165b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1166b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1167b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLParallelMove* LAllocator::GetConnectingParallelMove(LifetimePosition pos) { 1168b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = pos.InstructionIndex(); 11691e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(index)) { 11701e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(index); 1171b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return gap->GetOrCreateParallelMove( 1172b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos.IsInstructionStart() ? LGap::START : LGap::END); 1173b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1174b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int gap_pos = pos.IsInstructionStart() ? (index - 1) : (index + 1); 11751e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return GapAt(gap_pos)->GetOrCreateParallelMove( 1176b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch (gap_pos < index) ? LGap::AFTER : LGap::BEFORE); 1177b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1178b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1179b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1180b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochHBasicBlock* LAllocator::GetBlock(LifetimePosition pos) { 11811e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex())); 1182b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return gap->block(); 1183b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1184b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1185b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1186b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ConnectRanges() { 11873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch HPhase phase("L_Connect ranges", this); 1188b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges()->length(); ++i) { 1189b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* first_range = live_ranges()->at(i); 1190b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_range == NULL || first_range->parent() != NULL) continue; 1191b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1192b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* second_range = first_range->next(); 1193b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (second_range != NULL) { 1194b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos = second_range->Start(); 1195b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1196b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!second_range->IsSpilled()) { 1197b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Add gap move if the two live ranges touch and there is no block 1198b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // boundary. 1199b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_range->End().Value() == pos.Value()) { 1200b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool should_insert = true; 1201b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (IsBlockBoundary(pos)) { 1202b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch should_insert = CanEagerlyResolveControlFlow(GetBlock(pos)); 1203b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1204b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (should_insert) { 1205b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LParallelMove* move = GetConnectingParallelMove(pos); 12063ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* prev_operand = first_range->CreateAssignedOperand(zone_); 12073ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* cur_operand = second_range->CreateAssignedOperand(zone_); 1208b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch move->AddMove(prev_operand, cur_operand); 1209b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1210b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1211b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1212b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1213b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_range = second_range; 1214b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch second_range = second_range->next(); 1215b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1216b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1217b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1218b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1219b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1220b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::CanEagerlyResolveControlFlow(HBasicBlock* block) const { 1221b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block->predecessors()->length() != 1) return false; 1222b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return block->predecessors()->first()->block_id() == block->block_id() - 1; 1223b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1224b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1225b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1226b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolveControlFlow() { 12273ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch HPhase phase("L_Resolve control flow", this); 12281e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1229b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int block_id = 1; block_id < blocks->length(); ++block_id) { 1230b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(block_id); 1231b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (CanEagerlyResolveControlFlow(block)) continue; 1232b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live = live_in_sets_[block->block_id()]; 1233b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live); 1234b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 1235b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 1236b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < block->predecessors()->length(); ++i) { 1237b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* cur = block->predecessors()->at(i); 1238b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_range = LiveRangeFor(operand_index); 1239b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolveControlFlow(cur_range, block, cur); 1240b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1241b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 1242b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1243b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1244b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1245b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1246b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1247b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::BuildLiveRanges() { 12483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch HPhase phase("L_Build live ranges", this); 1249b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InitializeLivenessAnalysis(); 1250b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process the blocks in reverse order. 12511e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1252b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { 1253b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(block_id); 1254b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live = ComputeLiveOut(block); 1255b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Initially consider all live_out values live for the entire block. We 1256b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // will shorten these intervals if necessary. 1257b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddInitialIntervals(block, live); 1258b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1259b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process the instructions in reverse order, generating and killing 1260b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // live values. 1261b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ProcessInstructions(block, live); 1262b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All phi output operands are killed by this block. 1263b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<HPhi*>* phis = block->phis(); 1264b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < phis->length(); ++i) { 1265b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The live range interval already ends at the first instruction of the 1266b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // block. 1267b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = phis->at(i); 1268b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live->Remove(phi->id()); 1269b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1270b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint = NULL; 1271b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* phi_operand = NULL; 1272b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LGap* gap = GetLastGap(phi->block()->predecessors()->at(0)); 1273b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START); 1274b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int j = 0; j < move->move_operands()->length(); ++j) { 1275b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* to = move->move_operands()->at(j).destination(); 12763ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (to->IsUnallocated() && 12773ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated::cast(to)->virtual_register() == phi->id()) { 1278b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch hint = move->move_operands()->at(j).source(); 1279b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch phi_operand = to; 1280b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch break; 1281b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1282b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1283b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(hint != NULL); 1284b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1285b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition block_start = LifetimePosition::FromInstructionIndex( 1286b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 1287b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(block_start, phi_operand, hint); 1288b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1289b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1290b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Now live is live_in for this block except not including values live 1291b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // out on backward successor edges. 1292b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_in_sets_[block_id] = live; 1293b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1294b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If this block is a loop header go back and patch up the necessary 1295b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // predecessor blocks. 1296b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block->IsLoopHeader()) { 1297b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // TODO(kmillikin): Need to be able to get the last block of the loop 1298b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // in the loop information. Add a live range stretching from the first 1299b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // loop instruction to the last for each value live on entry to the 1300b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // header. 1301b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* back_edge = block->loop_information()->GetLastBackEdge(); 1302b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live); 1303b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = LifetimePosition::FromInstructionIndex( 1304b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 1305b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end = LifetimePosition::FromInstructionIndex( 13061e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block back_edge->last_instruction_index()).NextInstruction(); 1307b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 1308b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 1309b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand_index); 13103ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch range->EnsureInterval(start, end, zone_); 1311b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 1312b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1313b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1314b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = block->block_id() + 1; i <= back_edge->block_id(); ++i) { 1315b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_in_sets_[i]->Union(*live); 1316b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1317b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1318b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1319b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 1320b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block_id == 0) { 1321b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live); 1322b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool found = false; 1323b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 1324b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch found = true; 1325b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 1326b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PrintF("Function: %s\n", 1327e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch *chunk_->info()->function()->debug_name()->ToCString()); 1328b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PrintF("Value %d used before first definition!\n", operand_index); 1329b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand_index); 1330b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PrintF("First use is at %d\n", range->first_pos()->pos().Value()); 1331b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 1332b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1333b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!found); 1334b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1335b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 1336b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1337b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1338b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1339b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1340b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::SafePointsAreInOrder() const { 1341b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); 1342b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = 0; 1343b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < pointer_maps->length(); ++i) { 1344b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(i); 1345b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point > map->lithium_position()) return false; 1346b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point = map->lithium_position(); 1347b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1348b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1349b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1350b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1351b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1352b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::PopulatePointerMaps() { 13533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch HPhase phase("L_Populate pointer maps", this); 1354b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); 1355b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1356b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(SafePointsAreInOrder()); 1357b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1358b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Iterate over all safe point positions and record a pointer 1359b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // for all spilled live ranges at this point. 1360b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int first_safe_point_index = 0; 1361b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int last_range_start = 0; 1362b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { 1363b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = live_ranges()->at(range_idx); 1364b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL) continue; 1365b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Iterate over the first parts of multi-part live ranges. 1366b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->parent() != NULL) continue; 1367b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Skip non-pointer values. 1368b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!HasTaggedValue(range->id())) continue; 1369b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Skip empty live ranges. 1370b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsEmpty()) continue; 1371b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1372b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the extent of the range and its children. 1373b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int start = range->Start().InstructionIndex(); 1374b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int end = 0; 1375b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (LiveRange* cur = range; cur != NULL; cur = cur->next()) { 1376b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition this_end = cur->End(); 1377b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (this_end.InstructionIndex() > end) end = this_end.InstructionIndex(); 1378b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(cur->Start().InstructionIndex() >= start); 1379b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1380b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1381b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Most of the ranges are in order, but not all. Keep an eye on when 1382b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // they step backwards and reset the first_safe_point_index so we don't 1383b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // miss any safe points. 1384b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start < last_range_start) { 1385b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_safe_point_index = 0; 1386b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1387b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_range_start = start; 1388b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1389b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Step across all the safe points that are before the start of this range, 1390b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // recording how far we step in order to save doing this for the next range. 1391b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (first_safe_point_index < pointer_maps->length()) { 1392b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(first_safe_point_index); 1393b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = map->lithium_position(); 1394b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point >= start) break; 1395b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_safe_point_index++; 1396b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1397b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1398b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Step through the safe points to see whether they are in the range. 1399b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int safe_point_index = first_safe_point_index; 1400b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point_index < pointer_maps->length(); 1401b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ++safe_point_index) { 1402b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(safe_point_index); 1403b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = map->lithium_position(); 1404b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1405b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The safe points are sorted so we can stop searching here. 1406b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point - 1 > end) break; 1407b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1408b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Advance to the next active range that covers the current 1409b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // safe point position. 1410b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition safe_point_pos = 1411b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(safe_point); 1412b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur = range; 1413b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (cur != NULL && !cur->Covers(safe_point_pos.PrevInstruction())) { 1414b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur = cur->next(); 1415b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1416b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur == NULL) continue; 1417b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1418b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Check if the live range is spilled and the safe point is after 1419b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the spill position. 1420b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->HasAllocatedSpillOperand() && 1421b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point >= range->spill_start_index()) { 1422b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Pointer for range %d (spilled at %d) at safe point %d\n", 1423b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->id(), range->spill_start_index(), safe_point); 1424b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch map->RecordPointer(range->GetSpillOperand()); 1425b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1426b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1427b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!cur->IsSpilled()) { 1428b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Pointer in register for range %d (start at %d) " 1429b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch "at safe point %d\n", 1430b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur->id(), cur->Start().Value(), safe_point); 14313ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* operand = cur->CreateAssignedOperand(zone_); 1432b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!operand->IsStackSlot()); 1433b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch map->RecordPointer(operand); 1434b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1435b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1436b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1437b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1438b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1439b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1440b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ProcessOsrEntry() { 1441b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LInstruction*>* instrs = chunk_->instructions(); 1442b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1443b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Linear search for the OSR entry instruction in the chunk. 1444b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = -1; 1445b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (++index < instrs->length() && 1446b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch !instrs->at(index)->IsOsrEntry()) { 1447b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1448b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(index < instrs->length()); 1449b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOsrEntry* instruction = LOsrEntry::cast(instrs->at(index)); 1450b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1451b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position = LifetimePosition::FromInstructionIndex(index); 1452b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges()->length(); ++i) { 1453b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = live_ranges()->at(i); 1454b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range != NULL) { 1455b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->Covers(position) && 1456b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->HasRegisterAssigned() && 1457b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->TopLevel()->HasAllocatedSpillOperand()) { 1458b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int reg_index = range->assigned_register(); 1459b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* spill_operand = range->TopLevel()->GetSpillOperand(); 1460b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsDouble()) { 1461b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch instruction->MarkSpilledDoubleRegister(reg_index, spill_operand); 1462b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1463b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch instruction->MarkSpilledRegister(reg_index, spill_operand); 1464b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1465b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1466b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1467b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1468b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1469b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1470b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1471b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateGeneralRegisters() { 14723ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch HPhase phase("L_Allocate general registers", this); 1473b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch num_registers_ = Register::kNumAllocatableRegisters; 1474b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateRegisters(); 1475b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1476b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1477b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1478b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateDoubleRegisters() { 14793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch HPhase phase("L_Allocate double registers", this); 1480b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch num_registers_ = DoubleRegister::kNumAllocatableRegisters; 1481b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch mode_ = DOUBLE_REGISTERS; 1482b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateRegisters(); 1483b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1484b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1485b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1486b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateRegisters() { 148744f0eee88ff00398ff7f715fab053374d808c90dSteve Block ASSERT(unhandled_live_ranges_.is_empty()); 1488b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1489b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges_.length(); ++i) { 1490b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (live_ranges_[i] != NULL) { 1491b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (RequiredRegisterKind(live_ranges_[i]->id()) == mode_) { 1492b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledUnsorted(live_ranges_[i]); 1493b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1494b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1495b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1496b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SortUnhandled(); 1497b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(UnhandledIsSorted()); 1498b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 149944f0eee88ff00398ff7f715fab053374d808c90dSteve Block ASSERT(reusable_slots_.is_empty()); 1500b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(active_live_ranges_.is_empty()); 1501b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(inactive_live_ranges_.is_empty()); 1502b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1503b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (mode_ == DOUBLE_REGISTERS) { 1504b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < fixed_double_live_ranges_.length(); ++i) { 1505b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = fixed_double_live_ranges_.at(i); 1506b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) { 1507b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToInactive(current); 1508b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1509b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1510b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1511b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < fixed_live_ranges_.length(); ++i) { 1512b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = fixed_live_ranges_.at(i); 1513b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) { 1514b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToInactive(current); 1515b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1516b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1517b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1518b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1519b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!unhandled_live_ranges_.is_empty()) { 1520b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(UnhandledIsSorted()); 1521b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = unhandled_live_ranges_.RemoveLast(); 1522b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(UnhandledIsSorted()); 1523b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position = current->Start(); 1524b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Processing interval %d start=%d\n", 1525b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id(), 1526b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch position.Value()); 1527b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1528b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current->HasAllocatedSpillOperand()) { 1529b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Live range %d already has a spill operand\n", current->id()); 1530b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_pos = position; 15311e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(next_pos.InstructionIndex())) { 1532b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_pos = next_pos.NextInstruction(); 1533b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1534b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = current->NextUsePositionRegisterIsBeneficial(next_pos); 1535b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If the range already has a spill operand and it doesn't need a 1536b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // register immediately, split it and spill the first part of the range. 1537b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos == NULL) { 1538b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(current); 1539b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 1540b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (pos->pos().Value() > 1541b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->Start().NextInstruction().Value()) { 1542b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Do not spill live range eagerly if use position that can benefit from 1543b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the register is too close to the start of live range. 1544b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(current, current->Start(), pos->pos()); 15453ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 1546b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(UnhandledIsSorted()); 1547b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 1548b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1549b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1550b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1551b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1552b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_active = active_live_ranges_.at(i); 1553b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_active->End().Value() <= position.Value()) { 1554b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ActiveToHandled(cur_active); 1555b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // The live range was removed from the list of active live ranges. 1556b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (!cur_active->Covers(position)) { 1557b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ActiveToInactive(cur_active); 1558b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // The live range was removed from the list of active live ranges. 1559b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1560b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1561b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1562b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1563b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_inactive = inactive_live_ranges_.at(i); 1564b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_inactive->End().Value() <= position.Value()) { 1565b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InactiveToHandled(cur_inactive); 1566b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // Live range was removed from the list of inactive live ranges. 1567b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (cur_inactive->Covers(position)) { 1568b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InactiveToActive(cur_inactive); 1569b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // Live range was removed from the list of inactive live ranges. 1570b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1571b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1572b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1573b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!current->HasRegisterAssigned() && !current->IsSpilled()); 1574b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1575b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool result = TryAllocateFreeReg(current); 15763ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 15773ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 15783ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!result) AllocateBlockedReg(current); 15793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 1580b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1581b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current->HasRegisterAssigned()) { 1582b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToActive(current); 1583b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1584b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1585b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 158644f0eee88ff00398ff7f715fab053374d808c90dSteve Block reusable_slots_.Rewind(0); 158744f0eee88ff00398ff7f715fab053374d808c90dSteve Block active_live_ranges_.Rewind(0); 158844f0eee88ff00398ff7f715fab053374d808c90dSteve Block inactive_live_ranges_.Rewind(0); 1589b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1590b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1591b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1592b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochconst char* LAllocator::RegisterName(int allocation_index) { 1593b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (mode_ == GENERAL_REGISTERS) { 1594b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return Register::AllocationIndexToString(allocation_index); 1595b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1596b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return DoubleRegister::AllocationIndexToString(allocation_index); 1597b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1598b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1599b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1600b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1601b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::TraceAlloc(const char* msg, ...) { 1602b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (FLAG_trace_alloc) { 1603b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch va_list arguments; 1604b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch va_start(arguments, msg); 1605b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch OS::VPrint(msg, arguments); 1606b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch va_end(arguments); 1607b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1608b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1609b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1610b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1611b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::HasTaggedValue(int virtual_register) const { 16121e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block HValue* value = graph_->LookupValue(virtual_register); 1613b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (value == NULL) return false; 1614b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return value->representation().IsTagged(); 1615b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1616b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1617b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1618b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochRegisterKind LAllocator::RequiredRegisterKind(int virtual_register) const { 16199fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (virtual_register < first_artificial_register_) { 16201e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block HValue* value = graph_->LookupValue(virtual_register); 16219fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (value != NULL && value->representation().IsDouble()) { 16229fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block return DOUBLE_REGISTERS; 16239fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 16249fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } else if (double_artificial_registers_.Contains( 16259fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block virtual_register - first_artificial_register_)) { 1626b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return DOUBLE_REGISTERS; 1627b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 16289fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 1629b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return GENERAL_REGISTERS; 1630b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1631b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1632b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1633b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToActive(LiveRange* range) { 1634b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to active\n", range->id()); 1635b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch active_live_ranges_.Add(range); 1636b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1637b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1638b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1639b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToInactive(LiveRange* range) { 1640b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to inactive\n", range->id()); 1641b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inactive_live_ranges_.Add(range); 1642b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1643b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1644b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1645b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToUnhandledSorted(LiveRange* range) { 1646b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL || range->IsEmpty()) return; 1647b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!range->HasRegisterAssigned() && !range->IsSpilled()); 1648b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = unhandled_live_ranges_.length() - 1; i >= 0; --i) { 1649b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_range = unhandled_live_ranges_.at(i); 1650b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->ShouldBeAllocatedBefore(cur_range)) { 1651b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled at %d\n", range->id(), i + 1); 1652b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unhandled_live_ranges_.InsertAt(i + 1, range); 1653b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(UnhandledIsSorted()); 1654b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1655b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1656b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1657b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled at start\n", range->id()); 1658b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unhandled_live_ranges_.InsertAt(0, range); 1659b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(UnhandledIsSorted()); 1660b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1661b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1662b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1663b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToUnhandledUnsorted(LiveRange* range) { 1664b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL || range->IsEmpty()) return; 1665b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!range->HasRegisterAssigned() && !range->IsSpilled()); 1666b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled unsorted at end\n", range->id()); 1667b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unhandled_live_ranges_.Add(range); 1668b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1669b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1670b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1671b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic int UnhandledSortHelper(LiveRange* const* a, LiveRange* const* b) { 1672b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!(*a)->ShouldBeAllocatedBefore(*b) || 1673b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch !(*b)->ShouldBeAllocatedBefore(*a)); 1674b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if ((*a)->ShouldBeAllocatedBefore(*b)) return 1; 1675b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if ((*b)->ShouldBeAllocatedBefore(*a)) return -1; 1676b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return (*a)->id() - (*b)->id(); 1677b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1678b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1679b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1680b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Sort the unhandled live ranges so that the ranges to be processed first are 1681b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// at the end of the array list. This is convenient for the register allocation 1682b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// algorithm because it is efficient to remove elements from the end. 1683b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SortUnhandled() { 1684b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Sort unhandled\n"); 1685b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unhandled_live_ranges_.Sort(&UnhandledSortHelper); 1686b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1687b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1688b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1689b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::UnhandledIsSorted() { 1690b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int len = unhandled_live_ranges_.length(); 1691b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < len; i++) { 1692b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* a = unhandled_live_ranges_.at(i - 1); 1693b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* b = unhandled_live_ranges_.at(i); 1694b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->Start().Value() < b->Start().Value()) return false; 1695b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1696b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1697b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1698b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1699b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1700b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::FreeSpillSlot(LiveRange* range) { 1701b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Check that we are the last range. 1702b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->next() != NULL) return; 1703b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1704b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!range->TopLevel()->HasAllocatedSpillOperand()) return; 1705b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1706b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = range->TopLevel()->GetSpillOperand()->index(); 1707b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (index >= 0) { 1708b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch reusable_slots_.Add(range); 1709b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1710b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1711b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1712b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1713b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLOperand* LAllocator::TryReuseSpillSlot(LiveRange* range) { 1714b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (reusable_slots_.is_empty()) return NULL; 1715b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (reusable_slots_.first()->End().Value() > 1716b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->TopLevel()->Start().Value()) { 1717b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 1718b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1719b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* result = reusable_slots_.first()->TopLevel()->GetSpillOperand(); 1720b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch reusable_slots_.Remove(0); 1721b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 1722b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1723b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1724b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1725b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ActiveToHandled(LiveRange* range) { 1726b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(active_live_ranges_.Contains(range)); 1727b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch active_live_ranges_.RemoveElement(range); 1728b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from active to handled\n", range->id()); 1729b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch FreeSpillSlot(range); 1730b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1731b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1732b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1733b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ActiveToInactive(LiveRange* range) { 1734b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(active_live_ranges_.Contains(range)); 1735b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch active_live_ranges_.RemoveElement(range); 1736b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inactive_live_ranges_.Add(range); 1737b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from active to inactive\n", range->id()); 1738b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1739b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1740b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1741b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::InactiveToHandled(LiveRange* range) { 1742b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(inactive_live_ranges_.Contains(range)); 1743b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inactive_live_ranges_.RemoveElement(range); 1744b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); 1745b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch FreeSpillSlot(range); 1746b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1747b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1748b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1749b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::InactiveToActive(LiveRange* range) { 1750b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(inactive_live_ranges_.Contains(range)); 1751b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inactive_live_ranges_.RemoveElement(range); 1752b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch active_live_ranges_.Add(range); 1753b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from inactive to active\n", range->id()); 1754b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1755b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1756b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1757b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// TryAllocateFreeReg and AllocateBlockedReg assume this 1758b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// when allocating local arrays. 1759b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochSTATIC_ASSERT(DoubleRegister::kNumAllocatableRegisters >= 1760b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Register::kNumAllocatableRegisters); 1761b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1762b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1763b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::TryAllocateFreeReg(LiveRange* current) { 1764b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition free_until_pos[DoubleRegister::kNumAllocatableRegisters]; 1765b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1766b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < DoubleRegister::kNumAllocatableRegisters; i++) { 1767b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[i] = LifetimePosition::MaxPosition(); 1768b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1769b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1770b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1771b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_active = active_live_ranges_.at(i); 1772b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[cur_active->assigned_register()] = 1773b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(0); 1774b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1775b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1776b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1777b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_inactive = inactive_live_ranges_.at(i); 1778b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(cur_inactive->End().Value() > current->Start().Value()); 1779b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = 1780b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_inactive->FirstIntersection(current); 1781b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!next_intersection.IsValid()) continue; 1782b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = cur_inactive->assigned_register(); 1783b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection); 1784b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1785b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1786b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* hinted_use = current->FirstPosWithHint(); 1787b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (hinted_use != NULL) { 1788b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint = hinted_use->hint(); 1789b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (hint->IsRegister() || hint->IsDoubleRegister()) { 1790b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int register_index = hint->index(); 1791b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc( 1792b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch "Found reg hint %s (free until [%d) for live range %d (end %d[).\n", 1793b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterName(register_index), 1794b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[register_index].Value(), 1795b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id(), 1796b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->End().Value()); 1797b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1798b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The desired register is free until the end of the current live range. 1799b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (free_until_pos[register_index].Value() >= current->End().Value()) { 1800b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Assigning preferred reg %s to live range %d\n", 1801b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterName(register_index), 1802b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id()); 18033ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch current->set_assigned_register(register_index, mode_, zone_); 1804b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1805b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1806b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1807b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1808b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1809b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the register which stays free for the longest time. 1810b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int reg = 0; 1811b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < RegisterCount(); ++i) { 1812b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (free_until_pos[i].Value() > free_until_pos[reg].Value()) { 1813b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch reg = i; 1814b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1815b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1816b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1817b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos = free_until_pos[reg]; 1818b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1819b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() <= current->Start().Value()) { 1820b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All registers are blocked. 1821b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 1822b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1823b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1824b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() < current->End().Value()) { 1825b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is available at the range start but becomes blocked before 1826b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the range end. Split current at position where it becomes blocked. 18273ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* tail = SplitRangeAt(current, pos); 18283ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1829b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(tail); 1830b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1831b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1832b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1833b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is available at the range start and is free until 1834b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the range end. 1835b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(pos.Value() >= current->End().Value()); 1836b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Assigning free reg %s to live range %d\n", 1837b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterName(reg), 1838b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id()); 18393ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch current->set_assigned_register(reg, mode_, zone_); 1840b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1841b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1842b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1843b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1844b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1845b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateBlockedReg(LiveRange* current) { 1846b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* register_use = current->NextRegisterPosition(current->Start()); 1847b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (register_use == NULL) { 1848b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // There is no use in the current live range that requires a register. 1849b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We can just spill it. 1850b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(current); 1851b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1852b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1853b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1854b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1855b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition use_pos[DoubleRegister::kNumAllocatableRegisters]; 1856b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition block_pos[DoubleRegister::kNumAllocatableRegisters]; 1857b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1858b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < DoubleRegister::kNumAllocatableRegisters; i++) { 1859b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[i] = block_pos[i] = LifetimePosition::MaxPosition(); 1860b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1861b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1862b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1863b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = active_live_ranges_[i]; 1864b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = range->assigned_register(); 1865b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsFixed() || !range->CanBeSpilled(current->Start())) { 1866b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[cur_reg] = use_pos[cur_reg] = 1867b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(0); 1868b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1869b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_use = range->NextUsePositionRegisterIsBeneficial( 1870b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->Start()); 1871b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_use == NULL) { 1872b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = range->End(); 1873b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1874b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = next_use->pos(); 1875b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1876b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1877b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1878b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1879b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1880b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = inactive_live_ranges_.at(i); 1881b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(range->End().Value() > current->Start().Value()); 1882b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = range->FirstIntersection(current); 1883b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!next_intersection.IsValid()) continue; 1884b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = range->assigned_register(); 1885b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsFixed()) { 1886b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection); 1887b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]); 1888b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1889b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection); 1890b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1891b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1892b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1893b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int reg = 0; 1894b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < RegisterCount(); ++i) { 1895b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos[i].Value() > use_pos[reg].Value()) { 1896b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch reg = i; 1897b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1898b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1899b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1900b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos = use_pos[reg]; 1901b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1902b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() < register_use->pos().Value()) { 1903b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All registers are blocked before the first use that requires a register. 1904b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Spill starting part of live range up to that use. 1905b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // 1906b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Corner case: the first use position is equal to the start of the range. 1907b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // In this case we have nothing to spill and SpillBetween will just return 1908b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // this range to the list of unhandled ones. This will lead to the infinite 1909b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // loop. 1910b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(current->Start().Value() < register_use->pos().Value()); 1911b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(current, current->Start(), register_use->pos()); 1912b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1913b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1914b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1915b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block_pos[reg].Value() < current->End().Value()) { 1916b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register becomes blocked before the current range end. Split before that 1917b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position. 1918b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* tail = SplitBetween(current, 1919b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->Start(), 1920b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[reg].InstructionStart()); 1921b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(tail); 1922b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1923b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1924b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is not blocked for the whole range. 1925b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(block_pos[reg].Value() >= current->End().Value()); 1926b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Assigning blocked reg %s to live range %d\n", 1927b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterName(reg), 1928b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id()); 19293ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch current->set_assigned_register(reg, mode_, zone_); 1930b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1931b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This register was not free. Thus we need to find and spill 1932b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // parts of active and inactive live regions that use the same register 1933b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // at the same lifetime positions as current. 1934b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SplitAndSpillIntersecting(current); 1935b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1936b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1937b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1938b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SplitAndSpillIntersecting(LiveRange* current) { 1939b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(current->HasRegisterAssigned()); 1940b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int reg = current->assigned_register(); 1941b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition split_pos = current->Start(); 1942b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1943b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = active_live_ranges_[i]; 1944b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->assigned_register() == reg) { 1945b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_pos = range->NextRegisterPosition(current->Start()); 1946b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_pos == NULL) { 1947b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillAfter(range, split_pos); 1948b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1949b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(range, split_pos, next_pos->pos()); 1950b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1951b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ActiveToHandled(range); 1952b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; 1953b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1954b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1955b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1956b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1957b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = inactive_live_ranges_[i]; 1958b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(range->End().Value() > current->Start().Value()); 1959b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->assigned_register() == reg && !range->IsFixed()) { 1960b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = range->FirstIntersection(current); 1961b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_intersection.IsValid()) { 1962b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_pos = range->NextRegisterPosition(current->Start()); 1963b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_pos == NULL) { 1964b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillAfter(range, split_pos); 1965b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1966b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_intersection = Min(next_intersection, next_pos->pos()); 1967b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(range, split_pos, next_intersection); 1968b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1969b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InactiveToHandled(range); 1970b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; 1971b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1972b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1973b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1974b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1975b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1976b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1977b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::IsBlockBoundary(LifetimePosition pos) { 1978b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos.IsInstructionStart() && 19791e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block InstructionAt(pos.InstructionIndex())->IsLabel(); 1980b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1981b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1982b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 19833ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLiveRange* LAllocator::SplitRangeAt(LiveRange* range, LifetimePosition pos) { 1984b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!range->IsFixed()); 1985b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value()); 1986b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1987b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() <= range->Start().Value()) return range; 1988b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 19891e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block // We can't properly connect liveranges if split occured at the end 19901e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block // of control instruction. 19911e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block ASSERT(pos.IsInstructionStart() || 19921e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block !chunk_->instructions()->at(pos.InstructionIndex())->IsControl()); 19931e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 19943ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* result = LiveRangeFor(GetVirtualRegister()); 19953ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return NULL; 19963ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch range->SplitAt(pos, result, zone_); 1997b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 1998b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1999b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2000b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2001b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::SplitBetween(LiveRange* range, 2002b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 2003b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2004b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!range->IsFixed()); 2005b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Splitting live range %d in position between [%d, %d]\n", 2006b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->id(), 2007b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 2008b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 2009b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2010b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition split_pos = FindOptimalSplitPos(start, end); 2011b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(split_pos.Value() >= start.Value()); 20123ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return SplitRangeAt(range, split_pos); 2013b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2014b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2015b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2016b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLifetimePosition LAllocator::FindOptimalSplitPos(LifetimePosition start, 2017b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2018b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int start_instr = start.InstructionIndex(); 2019b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int end_instr = end.InstructionIndex(); 2020b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(start_instr <= end_instr); 2021b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2022b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We have no choice 2023b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start_instr == end_instr) return end; 2024b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2025257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch HBasicBlock* start_block = GetBlock(start); 2026257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch HBasicBlock* end_block = GetBlock(end); 2027b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2028b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (end_block == start_block) { 2029257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // The interval is split in the same basic block. Split at the latest 2030257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // possible position. 2031b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return end; 2032b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2033b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2034b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = end_block; 2035b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find header of outermost loop. 2036b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (block->parent_loop_header() != NULL && 2037b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->parent_loop_header()->block_id() > start_block->block_id()) { 2038b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block = block->parent_loop_header(); 2039b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2040b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2041257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // We did not find any suitable outer loop. Split at the latest possible 2042257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // position unless end_block is a loop header itself. 2043257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch if (block == end_block && !end_block->IsLoopHeader()) return end; 2044b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2045b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition::FromInstructionIndex( 2046b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 2047b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2048b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2049b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2050b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) { 20513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* second_part = SplitRangeAt(range, pos); 20523ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 2053b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(second_part); 2054b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2055b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2056b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2057b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SpillBetween(LiveRange* range, 2058b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 2059b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2060b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(start.Value() < end.Value()); 20613ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* second_part = SplitRangeAt(range, start); 20623ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 2063b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2064b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second_part->Start().Value() < end.Value()) { 2065b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split result intersects with [start, end[. 2066b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split it at position between ]start+1, end[, spill the middle part 2067b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // and put the rest to unhandled. 2068b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* third_part = SplitBetween( 2069b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch second_part, 2070b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch second_part->Start().InstructionEnd(), 2071b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.PrevInstruction().InstructionEnd()); 2072b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2073b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(third_part != second_part); 2074b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2075b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(second_part); 2076b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(third_part); 2077b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 2078b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split result does not intersect with [start, end[. 2079b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Nothing to spill. Just put it to unhandled as whole. 2080b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(second_part); 2081b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2082b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2083b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2084b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2085b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Spill(LiveRange* range) { 2086b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(!range->IsSpilled()); 2087b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Spilling live range %d\n", range->id()); 2088b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* first = range->TopLevel(); 2089b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2090b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!first->HasAllocatedSpillOperand()) { 2091b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* op = TryReuseSpillSlot(range); 2092b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (op == NULL) op = chunk_->GetNextSpillSlot(mode_ == DOUBLE_REGISTERS); 2093b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first->SetSpillOperand(op); 2094b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 20953ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch range->MakeSpilled(zone_); 2096b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2097b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2098b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2099b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochint LAllocator::RegisterCount() const { 2100b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return num_registers_; 2101b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2102b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2103b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2104b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 2105b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2106b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2107b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Verify() const { 2108b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges()->length(); ++i) { 2109b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = live_ranges()->at(i); 2110b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) current->Verify(); 2111b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2112b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2113b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2114b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2115b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 2116b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2117b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2118b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} } // namespace v8::internal 2119