13ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// Copyright 2012 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/crankshaft/lithium-allocator.h" 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 7014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/crankshaft/hydrogen.h" 8014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/crankshaft/lithium-allocator-inl.h" 962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch#include "src/crankshaft/lithium-inl.h" 1062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch#include "src/objects-inl.h" 11014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/register-configuration.h" 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/string-stream.h" 13b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 14b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochnamespace v8 { 15b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochnamespace internal { 16b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1713e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdochconst auto GetRegConfig = RegisterConfiguration::Crankshaft; 1813e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 19b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) { 20b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return a.Value() < b.Value() ? a : b; 21b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 22b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 23b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 24b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) { 25b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return a.Value() > b.Value() ? a : b; 26b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 27b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 28b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochUsePosition::UsePosition(LifetimePosition pos, 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* operand, 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* hint) 321e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block : operand_(operand), 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch hint_(hint), 341e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block pos_(pos), 351e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block next_(NULL), 361e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block requires_reg_(false), 371e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block register_beneficial_(true) { 381e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (operand_ != NULL && operand_->IsUnallocated()) { 391e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LUnallocated* unalloc = LUnallocated::cast(operand_); 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch requires_reg_ = unalloc->HasRegisterPolicy() || 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unalloc->HasDoubleRegisterPolicy(); 421e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block register_beneficial_ = !unalloc->HasAnyPolicy(); 43b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pos_.IsValid()); 45b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 46b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 471e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 481e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockbool UsePosition::HasHint() const { 491e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return hint_ != NULL && !hint_->IsUnallocated(); 50b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 51b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 52b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 53b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool UsePosition::RequiresRegister() const { 54b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return requires_reg_; 55b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 56b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 57b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 58b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool UsePosition::RegisterIsBeneficial() const { 59b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return register_beneficial_; 60b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 61b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 62b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 633ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid UseInterval::SplitAt(LifetimePosition pos, Zone* zone) { 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Contains(pos) && pos.Value() != start().Value()); 653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* after = new(zone) UseInterval(pos, end_); 66b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch after->next_ = next_; 67b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_ = after; 68b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end_ = pos; 69b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 70b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 71b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 72b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 73b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 74b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 75b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::Verify() const { 76b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* cur = first_pos_; 77b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (cur != NULL) { 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Start().Value() <= cur->pos().Value() && 79b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur->pos().Value() <= End().Value()); 80b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur = cur->next(); 81b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 82b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 83b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 84b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 85b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::HasOverlap(UseInterval* target) const { 86b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* current_interval = first_interval_; 87b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current_interval != NULL) { 88b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Intervals overlap if the start of one is contained in the other. 89b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval->Contains(target->start()) || 90b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch target->Contains(current_interval->start())) { 91b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 92b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 93b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval = current_interval->next(); 94b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 95b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 96b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 97b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 98b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 99b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 100b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 101b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1023ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLiveRange::LiveRange(int id, Zone* zone) 1031e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block : id_(id), 1041e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spilled_(false), 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch kind_(UNALLOCATED_REGISTERS), 1061e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_(kInvalidAssignment), 1071e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block last_interval_(NULL), 1081e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block first_interval_(NULL), 1091e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block first_pos_(NULL), 1101e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block parent_(NULL), 1111e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block next_(NULL), 1121e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block current_interval_(NULL), 1131e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block last_processed_use_(NULL), 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current_hint_operand_(NULL), 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch spill_operand_(new (zone) LOperand()), 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch spill_start_index_(kMaxInt) {} 1171e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1181e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid LiveRange::set_assigned_register(int reg, Zone* zone) { 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!HasRegisterAssigned() && !IsSpilled()); 1211e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_ = reg; 1223ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ConvertOperands(zone); 1231e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1241e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1251e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1263ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::MakeSpilled(Zone* zone) { 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsSpilled()); 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(TopLevel()->HasAllocatedSpillOperand()); 1291e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spilled_ = true; 1301e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_ = kInvalidAssignment; 1313ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ConvertOperands(zone); 1321e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1331e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1341e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1351e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockbool LiveRange::HasAllocatedSpillOperand() const { 136b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(spill_operand_ != NULL); 1373ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return !spill_operand_->IsIgnored(); 1381e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1391e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1401e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1411e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockvoid LiveRange::SetSpillOperand(LOperand* operand) { 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!operand->IsUnallocated()); 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(spill_operand_ != NULL); 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(spill_operand_->IsIgnored()); 1451e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spill_operand_->ConvertTo(operand->kind(), operand->index()); 1461e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1471e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1481e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 149b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextUsePosition(LifetimePosition start) { 150b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = last_processed_use_; 151b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos == NULL) use_pos = first_pos(); 152b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_pos != NULL && use_pos->pos().Value() < start.Value()) { 153b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = use_pos->next(); 154b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 155b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_processed_use_ = use_pos; 156b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return use_pos; 157b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 158b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 159b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 160b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextUsePositionRegisterIsBeneficial( 161b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start) { 162b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = NextUsePosition(start); 163b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (pos != NULL && !pos->RegisterIsBeneficial()) { 164b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos = pos->next(); 165b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 166b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos; 167b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 168b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 169b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochUsePosition* LiveRange::PreviousUsePositionRegisterIsBeneficial( 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition start) { 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* pos = first_pos(); 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* prev = NULL; 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (pos != NULL && pos->pos().Value() < start.Value()) { 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (pos->RegisterIsBeneficial()) prev = pos; 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch pos = pos->next(); 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return prev; 179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 182b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) { 183b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = NextUsePosition(start); 184b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (pos != NULL && !pos->RequiresRegister()) { 185b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos = pos->next(); 186b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 187b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos; 188b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 189b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 190b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 191b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::CanBeSpilled(LifetimePosition pos) { 192b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We cannot spill a live range that has a use requiring a register 193b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // at the current or the immediate next position. 194b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = NextRegisterPosition(pos); 195b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos == NULL) return true; 1963ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return 1973ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch use_pos->pos().Value() > pos.NextInstruction().InstructionEnd().Value(); 198b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 199b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 200b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2013ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLOperand* LiveRange::CreateAssignedOperand(Zone* zone) { 202b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* op = NULL; 203b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (HasRegisterAssigned()) { 204b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsSpilled()); 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch switch (Kind()) { 206b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case GENERAL_REGISTERS: 207b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch op = LRegister::Create(assigned_register(), zone); 208b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 209b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case DOUBLE_REGISTERS: 210b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch op = LDoubleRegister::Create(assigned_register(), zone); 211b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 212b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch default: 213b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UNREACHABLE(); 214b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 215b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (IsSpilled()) { 216b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!HasRegisterAssigned()); 217b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch op = TopLevel()->GetSpillOperand(); 218b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!op->IsUnallocated()); 219b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 2203ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated* unalloc = new(zone) LUnallocated(LUnallocated::NONE); 221b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unalloc->set_virtual_register(id_); 222b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch op = unalloc; 223b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 224b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return op; 225b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 226b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 227b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 228b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUseInterval* LiveRange::FirstSearchIntervalForPosition( 229b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position) const { 230b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval_ == NULL) return first_interval_; 231b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval_->start().Value() > position.Value()) { 232b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ = NULL; 233b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return first_interval_; 234b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 235b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return current_interval_; 236b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 237b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 238b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 239b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::AdvanceLastProcessedMarker( 240b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* to_start_of, LifetimePosition but_not_past) const { 241b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of == NULL) return; 242b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of->start().Value() > but_not_past.Value()) return; 243b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = 244b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ == NULL ? LifetimePosition::Invalid() 245b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch : current_interval_->start(); 246b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of->start().Value() > start.Value()) { 247b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ = to_start_of; 248b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 249b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 250b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 251b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2523ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::SplitAt(LifetimePosition position, 2533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* result, 2543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 255b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Start().Value() < position.Value()); 256b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(result->IsEmpty()); 257b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the last interval that ends before the position. If the 258b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position is contained in one of the intervals in the chain, we 259b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // split that interval and use the first part. 260b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* current = FirstSearchIntervalForPosition(position); 261b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 262b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If the split position coincides with the beginning of a use interval 263b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // we need to split use positons in a special way. 264b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool split_at_start = false; 265b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2663fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch if (current->start().Value() == position.Value()) { 2673fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // When splitting at start we need to locate the previous use interval. 2683fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch current = first_interval_; 2693fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch } 2703fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 271b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current != NULL) { 272b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current->Contains(position)) { 2733ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch current->SplitAt(position, zone); 274b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch break; 275b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 276b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* next = current->next(); 277b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next->start().Value() >= position.Value()) { 278b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch split_at_start = (next->start().Value() == position.Value()); 279b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch break; 280b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 281b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current = next; 282b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 283b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 284b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Partition original use intervals to the two live ranges. 285b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* before = current; 286b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* after = before->next(); 287b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->last_interval_ = (last_interval_ == before) 288b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ? after // Only interval in the range after split. 289b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch : last_interval_; // Last interval of the original range. 290b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->first_interval_ = after; 291b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = before; 292b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 293b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the last use position before the split and the first use 294b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position after it. 295b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_after = first_pos_; 296b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_before = NULL; 297b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (split_at_start) { 298b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split position coincides with the beginning of a use interval (the 299b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // end of a lifetime hole). Use at this position should be attributed to 300b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the split child because split child owns use interval covering it. 301b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_after != NULL && use_after->pos().Value() < position.Value()) { 302b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before = use_after; 303b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_after = use_after->next(); 304b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 305b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 306b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_after != NULL && use_after->pos().Value() <= position.Value()) { 307b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before = use_after; 308b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_after = use_after->next(); 309b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 310b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 311b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 312b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Partition original use positions to the two live ranges. 313b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_before != NULL) { 314b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before->next_ = NULL; 315b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 316b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_pos_ = NULL; 317b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 318b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->first_pos_ = use_after; 319b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3203fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Discard cached iteration state. It might be pointing 3213fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // to the use that no longer belongs to this live range. 3223fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch last_processed_use_ = NULL; 3233fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch current_interval_ = NULL; 3243fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 325b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Link the new live range in the chain before any of the other 326b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // ranges linked from the range before the split. 327b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->parent_ = (parent_ == NULL) ? this : parent_; 328b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result->kind_ = result->parent_->kind_; 329b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->next_ = next_; 330b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_ = result; 331b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 332b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 333b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Verify(); 334b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->Verify(); 335b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 336b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 337b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 338b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 339b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// This implements an ordering on live ranges so that they are ordered by their 340b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// start positions. This is needed for the correctness of the register 341b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// allocation algorithm. If two live ranges start at the same offset then there 342b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// is a tie breaker based on where the value is first used. This part of the 343b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// ordering is merely a heuristic. 344b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const { 345b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = Start(); 346b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition other_start = other->Start(); 347b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start.Value() == other_start.Value()) { 348b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* pos = first_pos(); 349b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos == NULL) return false; 350b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* other_pos = other->first_pos(); 351b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (other_pos == NULL) return true; 352b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos->pos().Value() < other_pos->pos().Value(); 353b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 354b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return start.Value() < other_start.Value(); 355b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 356b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 357b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 358b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::ShortenTo(LifetimePosition start) { 359b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Shorten live range %d to [%d\n", id_, start.Value()); 360b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(first_interval_ != NULL); 361b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(first_interval_->start().Value() <= start.Value()); 362b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(start.Value() < first_interval_->end().Value()); 363b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->set_start(start); 364b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 365b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 366b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3673ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::EnsureInterval(LifetimePosition start, 3683ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LifetimePosition end, 3693ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 370b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Ensure live range %d in interval [%d %d[\n", 371b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 372b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 373b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 374b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition new_end = end; 375b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (first_interval_ != NULL && 376b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->start().Value() <= end.Value()) { 377b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_interval_->end().Value() > end.Value()) { 378b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch new_end = first_interval_->end(); 379b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 380b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = first_interval_->next(); 381b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 382b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3833ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* new_interval = new(zone) UseInterval(start, new_end); 384b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch new_interval->next_ = first_interval_; 385b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = new_interval; 386b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (new_interval->next() == NULL) { 387b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = new_interval; 388b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 389b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 390b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 391b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3923ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::AddUseInterval(LifetimePosition start, 3933ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LifetimePosition end, 3943ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 395b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Add to live range %d interval [%d %d[\n", 396b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 397b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 398b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 399b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_interval_ == NULL) { 4003ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* interval = new(zone) UseInterval(start, end); 401b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = interval; 402b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = interval; 403b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 404b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (end.Value() == first_interval_->start().Value()) { 405b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->set_start(start); 406b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (end.Value() < first_interval_->start().Value()) { 4073ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* interval = new(zone) UseInterval(start, end); 408b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval->set_next(first_interval_); 409b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = interval; 410b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 411b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Order of instruction's processing (see ProcessInstructions) guarantees 412b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // that each new use interval either precedes or intersects with 413b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // last added interval. 414b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(start.Value() < first_interval_->end().Value()); 415b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->start_ = Min(start, first_interval_->start_); 416b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->end_ = Max(end, first_interval_->end_); 417b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 418b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 419b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 420b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 421b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 422b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid LiveRange::AddUsePosition(LifetimePosition pos, 423b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* operand, 424b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* hint, 425b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone) { 426b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Add to live range %d use position %d\n", 427b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 428b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos.Value()); 429b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* use_pos = new(zone) UsePosition(pos, operand, hint); 430b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* prev_hint = NULL; 431b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* prev = NULL; 432b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* current = first_pos_; 433b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current != NULL && current->pos().Value() < pos.Value()) { 434b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch prev_hint = current->HasHint() ? current : prev_hint; 435b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch prev = current; 436b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current = current->next(); 437b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 438b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 439b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (prev == NULL) { 440b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->set_next(first_pos_); 441b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_pos_ = use_pos; 442b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 443b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->next_ = prev->next_; 444b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch prev->next_ = use_pos; 445b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 446b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 447b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (prev_hint == NULL && use_pos->HasHint()) { 448b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current_hint_operand_ = hint; 449b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 450b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 451b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 452b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 4533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::ConvertOperands(Zone* zone) { 4543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* op = CreateAssignedOperand(zone); 455b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = first_pos(); 456b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_pos != NULL) { 457b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Start().Value() <= use_pos->pos().Value() && 458b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->pos().Value() <= End().Value()); 459b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 460b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos->HasOperand()) { 461b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(op->IsRegister() || op->IsDoubleRegister() || 462b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch !use_pos->RequiresRegister()); 463b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->operand()->ConvertTo(op->kind(), op->index()); 464b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 465b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = use_pos->next(); 466b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 467b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 468b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 469b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 470b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::CanCover(LifetimePosition position) const { 471b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (IsEmpty()) return false; 472b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return Start().Value() <= position.Value() && 473b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch position.Value() < End().Value(); 474b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 475b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 476b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 477b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::Covers(LifetimePosition position) { 478b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!CanCover(position)) return false; 479b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* start_search = FirstSearchIntervalForPosition(position); 480b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (UseInterval* interval = start_search; 481b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval != NULL; 482b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval = interval->next()) { 483b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(interval->next() == NULL || 484b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval->next()->start().Value() >= interval->start().Value()); 485b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AdvanceLastProcessedMarker(interval, position); 486b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (interval->Contains(position)) return true; 487b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (interval->start().Value() > position.Value()) return false; 488b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 489b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 490b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 491b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 492b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 493b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLifetimePosition LiveRange::FirstIntersection(LiveRange* other) { 494b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* b = other->first_interval(); 495b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (b == NULL) return LifetimePosition::Invalid(); 496b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition advance_last_processed_up_to = b->start(); 497b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* a = FirstSearchIntervalForPosition(b->start()); 498b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (a != NULL && b != NULL) { 499b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->start().Value() > other->End().Value()) break; 500b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (b->start().Value() > End().Value()) break; 501b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition cur_intersection = a->Intersect(b); 502b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_intersection.IsValid()) { 503b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return cur_intersection; 504b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 505b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->start().Value() < b->start().Value()) { 506b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch a = a->next(); 507b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a == NULL || a->start().Value() > other->End().Value()) break; 508b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AdvanceLastProcessedMarker(a, advance_last_processed_up_to); 509b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 510b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch b = b->next(); 511b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 512b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 513b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition::Invalid(); 514b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 515b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 51644f0eee88ff00398ff7f715fab053374d808c90dSteve BlockLAllocator::LAllocator(int num_values, HGraph* graph) 517c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch : zone_(graph->isolate()->allocator(), ZONE_NAME), 5183b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch chunk_(NULL), 519b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_in_sets_(graph->blocks()->length(), zone()), 520b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_ranges_(num_values * 2, zone()), 52144f0eee88ff00398ff7f715fab053374d808c90dSteve Block fixed_live_ranges_(NULL), 52244f0eee88ff00398ff7f715fab053374d808c90dSteve Block fixed_double_live_ranges_(NULL), 523b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unhandled_live_ranges_(num_values * 2, zone()), 524b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch active_live_ranges_(8, zone()), 525b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inactive_live_ranges_(8, zone()), 526b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch reusable_slots_(8, zone()), 52744f0eee88ff00398ff7f715fab053374d808c90dSteve Block next_virtual_register_(num_values), 52844f0eee88ff00398ff7f715fab053374d808c90dSteve Block first_artificial_register_(num_values), 529b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch mode_(UNALLOCATED_REGISTERS), 53044f0eee88ff00398ff7f715fab053374d808c90dSteve Block num_registers_(-1), 53144f0eee88ff00398ff7f715fab053374d808c90dSteve Block graph_(graph), 5323ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch has_osr_entry_(false), 533b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocation_ok_(true) {} 53444f0eee88ff00398ff7f715fab053374d808c90dSteve Block 535b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::InitializeLivenessAnalysis() { 536b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Initialize the live_in sets for each block to NULL. 5371e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block int block_count = graph_->blocks()->length(); 538b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_in_sets_.Initialize(block_count, zone()); 539b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_in_sets_.AddBlock(NULL, block_count, zone()); 540b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 541b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 542b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 543b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochBitVector* LAllocator::ComputeLiveOut(HBasicBlock* block) { 544b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Compute live out for the given block, except not including backward 545b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // successor edges. 546b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BitVector* live_out = new(zone()) BitVector(next_virtual_register_, zone()); 547b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 548b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process all successor blocks. 5493fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) { 550b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Add values live on entry to the successor. Note the successor's 551b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // live_in will not be computed yet for backwards edges. 5523fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch HBasicBlock* successor = it.Current(); 553b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live_in = live_in_sets_[successor->block_id()]; 554b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (live_in != NULL) live_out->Union(*live_in); 555b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 556b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All phi input operands corresponding to this successor edge are live 557b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // out from this block. 558b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = successor->PredecessorIndexOf(block); 559b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<HPhi*>* phis = successor->phis(); 560b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < phis->length(); ++i) { 561b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = phis->at(i); 562b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!phi->OperandAt(index)->IsConstant()) { 563b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_out->Add(phi->OperandAt(index)->id()); 564b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 565b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 566b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 567b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 568b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return live_out; 569b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 570b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 571b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 572b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddInitialIntervals(HBasicBlock* block, 573b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live_out) { 574b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Add an interval that includes the entire block to the live range for 575b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // each live_out value. 576b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = LifetimePosition::FromInstructionIndex( 577b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 578b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end = LifetimePosition::FromInstructionIndex( 579b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->last_instruction_index()).NextInstruction(); 580b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live_out); 581b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 582b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 583b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand_index); 584b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUseInterval(start, end, zone()); 585b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 586b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 587b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 588b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 589b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 590b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochint LAllocator::FixedDoubleLiveRangeID(int index) { 591014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return -index - 1 - Register::kNumRegisters; 592b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 593b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 594b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 595b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLOperand* LAllocator::AllocateFixed(LUnallocated* operand, 596b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int pos, 597b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool is_tagged) { 598b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Allocating fixed reg for op %d\n", operand->virtual_register()); 599b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(operand->HasFixedPolicy()); 600b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (operand->HasFixedSlotPolicy()) { 601b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch operand->ConvertTo(LOperand::STACK_SLOT, operand->fixed_slot_index()); 602b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (operand->HasFixedRegisterPolicy()) { 603b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int reg_index = operand->fixed_register_index(); 604b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand->ConvertTo(LOperand::REGISTER, reg_index); 605b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (operand->HasFixedDoubleRegisterPolicy()) { 606b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int reg_index = operand->fixed_register_index(); 607b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand->ConvertTo(LOperand::DOUBLE_REGISTER, reg_index); 608b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 609b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UNREACHABLE(); 610b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 611b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (is_tagged) { 612b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Fixed reg is tagged at %d\n", pos); 6131e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = InstructionAt(pos); 614b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (instr->HasPointerMap()) { 615b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->pointer_map()->RecordPointer(operand, chunk()->zone()); 616b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 617b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 618b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return operand; 619b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 620b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 621b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 622b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::FixedLiveRangeFor(int index) { 623014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(index < Register::kNumRegisters); 624b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* result = fixed_live_ranges_[index]; 625b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (result == NULL) { 626b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = new(zone()) LiveRange(FixedLiveRangeID(index), chunk()->zone()); 627b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(result->IsFixed()); 628b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result->kind_ = GENERAL_REGISTERS; 629b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(result, index); 630b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch fixed_live_ranges_[index] = result; 631b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 632b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 633b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 634b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 635b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 636b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::FixedDoubleLiveRangeFor(int index) { 637014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(index < DoubleRegister::kMaxNumRegisters); 638b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* result = fixed_double_live_ranges_[index]; 639b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (result == NULL) { 640b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = new(zone()) LiveRange(FixedDoubleLiveRangeID(index), 641b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 642b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(result->IsFixed()); 643b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result->kind_ = DOUBLE_REGISTERS; 644b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(result, index); 645b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch fixed_double_live_ranges_[index] = result; 646b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 647b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 648b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 649b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 65044f0eee88ff00398ff7f715fab053374d808c90dSteve Block 651b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::LiveRangeFor(int index) { 652b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (index >= live_ranges_.length()) { 653b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_ranges_.AddBlock(NULL, index - live_ranges_.length() + 1, zone()); 654b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 655b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* result = live_ranges_[index]; 656b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (result == NULL) { 657b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = new(zone()) LiveRange(index, chunk()->zone()); 658b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_ranges_[index] = result; 659b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 660b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 661b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 662b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 663b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 6641e0659c275bb392c045087af4f6b0d7565cb3d77Steve BlockLGap* LAllocator::GetLastGap(HBasicBlock* block) { 665b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int last_instruction = block->last_instruction_index(); 666b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = chunk_->NearestGapPos(last_instruction); 6671e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return GapAt(index); 668b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 669b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 670b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 671b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochHPhi* LAllocator::LookupPhi(LOperand* operand) const { 672b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!operand->IsUnallocated()) return NULL; 6733ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int index = LUnallocated::cast(operand)->virtual_register(); 6741e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block HValue* instr = graph_->LookupValue(index); 675b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (instr != NULL && instr->IsPhi()) { 676b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return HPhi::cast(instr); 677b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 678b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 679b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 680b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 681b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 682b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::LiveRangeFor(LOperand* operand) { 683b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (operand->IsUnallocated()) { 684b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LiveRangeFor(LUnallocated::cast(operand)->virtual_register()); 685b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (operand->IsRegister()) { 686b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return FixedLiveRangeFor(operand->index()); 687b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (operand->IsDoubleRegister()) { 688b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return FixedDoubleLiveRangeFor(operand->index()); 689b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 690b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 691b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 692b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 693b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 694b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 695b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Define(LifetimePosition position, 696b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand, 697b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint) { 698b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand); 699b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL) return; 700b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 701b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsEmpty() || range->Start().Value() > position.Value()) { 702b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Can happen if there is a definition without use. 703b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUseInterval(position, position.NextInstruction(), zone()); 704b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUsePosition(position.NextInstruction(), NULL, NULL, zone()); 705b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 706b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->ShortenTo(position); 707b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 708b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 709b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (operand->IsUnallocated()) { 710b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* unalloc_operand = LUnallocated::cast(operand); 711b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUsePosition(position, unalloc_operand, hint, zone()); 712b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 713b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 714b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 715b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 716b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Use(LifetimePosition block_start, 717b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position, 718b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand, 719b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint) { 720b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand); 721b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL) return; 722b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (operand->IsUnallocated()) { 723b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* unalloc_operand = LUnallocated::cast(operand); 724b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUsePosition(position, unalloc_operand, hint, zone()); 725b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 726b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUseInterval(block_start, position, zone()); 727b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 728b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 729b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 730b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddConstraintsGapMove(int index, 731b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* from, 732b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* to) { 7331e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(index); 734b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, 735b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 736b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (from->IsUnallocated()) { 737b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LMoveOperands>* move_operands = move->move_operands(); 738b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < move_operands->length(); ++i) { 739b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LMoveOperands cur = move_operands->at(i); 740b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* cur_to = cur.destination(); 741b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_to->IsUnallocated()) { 7423ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (LUnallocated::cast(cur_to)->virtual_register() == 7433ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated::cast(from)->virtual_register()) { 744b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch move->AddMove(cur.source(), to, chunk()->zone()); 745b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 746b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 747b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 748b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 749b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 750b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch move->AddMove(from, to, chunk()->zone()); 751b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 752b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 753b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 754b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::MeetRegisterConstraints(HBasicBlock* block) { 755b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int start = block->first_instruction_index(); 756b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int end = block->last_instruction_index(); 757b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (start == -1) return; 758b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = start; i <= end; ++i) { 7591e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(i)) { 7601e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = NULL; 7611e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* prev_instr = NULL; 7621e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (i < end) instr = InstructionAt(i + 1); 7631e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (i > start) prev_instr = InstructionAt(i - 1); 7641e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block MeetConstraintsBetween(prev_instr, instr, i); 7653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 766b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 767b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 768b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 769b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 770b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 7711e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockvoid LAllocator::MeetConstraintsBetween(LInstruction* first, 7721e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* second, 773b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int gap_index) { 774b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle fixed temporaries. 775b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first != NULL) { 7763fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (TempIterator it(first); !it.Done(); it.Advance()) { 7773fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LUnallocated* temp = LUnallocated::cast(it.Current()); 778b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp->HasFixedPolicy()) { 779b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateFixed(temp, gap_index - 1, false); 780b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 781b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 782b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 783b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 784b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle fixed output operand. 785b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first != NULL && first->Output() != NULL) { 786b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* first_output = LUnallocated::cast(first->Output()); 7873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* range = LiveRangeFor(first_output->virtual_register()); 788b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool assigned = false; 789b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_output->HasFixedPolicy()) { 790b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* output_copy = first_output->CopyUnconstrained( 791b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 7923ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool is_tagged = HasTaggedValue(first_output->virtual_register()); 793b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateFixed(first_output, gap_index, is_tagged); 794b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 795b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This value is produced on the stack, we never need to spill it. 796b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_output->IsStackSlot()) { 797b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->SetSpillOperand(first_output); 798b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->SetSpillStartIndex(gap_index - 1); 799b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch assigned = true; 800b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 801b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch chunk_->AddGapMove(gap_index, first_output, output_copy); 802b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 803b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 804b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!assigned) { 805b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->SetSpillStartIndex(gap_index); 806b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 807b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This move to spill operand is not a real use. Liveness analysis 808b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // and splitting of live ranges do not account for it. 809b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Thus it should be inserted to a lifetime position corresponding to 810b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the instruction end. 8111e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(gap_index); 812b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::BEFORE, 813b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 814b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch move->AddMove(first_output, range->GetSpillOperand(), 815b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 816b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 817b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 818b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 819b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle fixed input operands of second instruction. 820b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second != NULL) { 8213fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (UseIterator it(second); !it.Done(); it.Advance()) { 8223fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LUnallocated* cur_input = LUnallocated::cast(it.Current()); 823b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_input->HasFixedPolicy()) { 824b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* input_copy = cur_input->CopyUnconstrained( 825b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 8263ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool is_tagged = HasTaggedValue(cur_input->virtual_register()); 827b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateFixed(cur_input, gap_index + 1, is_tagged); 828b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddConstraintsGapMove(gap_index, input_copy, cur_input); 829b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (cur_input->HasWritableRegisterPolicy()) { 830b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch // The live range of writable input registers always goes until the end 831b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch // of the instruction. 832b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!cur_input->IsUsedAtStart()); 833b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch 834b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* input_copy = cur_input->CopyUnconstrained( 835b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 836b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int vreg = GetVirtualRegister(); 8373ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 838b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch cur_input->set_virtual_register(vreg); 8399fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 8409fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (RequiredRegisterKind(input_copy->virtual_register()) == 8419fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block DOUBLE_REGISTERS) { 8429fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block double_artificial_registers_.Add( 8433ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch cur_input->virtual_register() - first_artificial_register_, 844b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch zone()); 8459fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 8469fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 847b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddConstraintsGapMove(gap_index, input_copy, cur_input); 848b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 849b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 850b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 851b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 852b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle "output same as input" for second instruction. 853b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second != NULL && second->Output() != NULL) { 854b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* second_output = LUnallocated::cast(second->Output()); 855b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second_output->HasSameAsInputPolicy()) { 8561e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LUnallocated* cur_input = LUnallocated::cast(second->FirstInput()); 8573ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int output_vreg = second_output->virtual_register(); 8583ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int input_vreg = cur_input->virtual_register(); 859b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 860b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* input_copy = cur_input->CopyUnconstrained( 861b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 862b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_input->set_virtual_register(second_output->virtual_register()); 863b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddConstraintsGapMove(gap_index, input_copy, cur_input); 864b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 865b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (HasTaggedValue(input_vreg) && !HasTaggedValue(output_vreg)) { 866b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = gap_index + 1; 8671e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = InstructionAt(index); 868b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (instr->HasPointerMap()) { 869b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->pointer_map()->RecordPointer(input_copy, chunk()->zone()); 870b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 871b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (!HasTaggedValue(input_vreg) && HasTaggedValue(output_vreg)) { 872b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The input is assumed to immediately have a tagged representation, 873b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // before the pointer map can be used. I.e. the pointer map at the 874b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // instruction will include the output operand (whose value at the 875b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // beginning of the instruction is equal to the input operand). If 876b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // this is not desired, then the pointer map at this instruction needs 877b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // to be adjusted manually. 878b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 879b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 880b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 881b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 882b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 883b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 884b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) { 885b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int block_start = block->first_instruction_index(); 886b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = block->last_instruction_index(); 887b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 888b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition block_start_position = 889b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(block_start); 890b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 891b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (index >= block_start) { 892b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition curr_position = 893b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(index); 894b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 8951e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(index)) { 896b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We have a gap at this position. 8971e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(index); 898b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, 899b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 900b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LMoveOperands>* move_operands = move->move_operands(); 901b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < move_operands->length(); ++i) { 902b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LMoveOperands* cur = &move_operands->at(i); 903b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur->IsIgnored()) continue; 904b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* from = cur->source(); 905b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* to = cur->destination(); 906b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = LookupPhi(to); 907b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint = to; 908b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (phi != NULL) { 909b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This is a phi resolving move. 910b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!phi->block()->IsLoopHeader()) { 911b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch hint = LiveRangeFor(phi->id())->current_hint_operand(); 912b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 913b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 914b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to->IsUnallocated()) { 9153ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (live->Contains(LUnallocated::cast(to)->virtual_register())) { 916b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, to, from); 9173ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Remove(LUnallocated::cast(to)->virtual_register()); 918b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 919b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur->Eliminate(); 920b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 921b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 922b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 923b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, to, from); 924b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 925b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 926b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Use(block_start_position, curr_position, from, hint); 927b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (from->IsUnallocated()) { 9283ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Add(LUnallocated::cast(from)->virtual_register()); 929b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 930b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 931b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 932b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsGapAt(index)); 9331e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = InstructionAt(index); 934b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9351e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (instr != NULL) { 9361e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LOperand* output = instr->Output(); 937b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (output != NULL) { 9383ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (output->IsUnallocated()) { 9393ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Remove(LUnallocated::cast(output)->virtual_register()); 9403ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 941b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, output, NULL); 942b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 943b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 944b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->ClobbersRegisters()) { 945014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < Register::kNumRegisters; ++i) { 94613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch if (GetRegConfig()->IsAllocatableGeneralCode(i)) { 947014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (output == NULL || !output->IsRegister() || 948014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch output->index() != i) { 949014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LiveRange* range = FixedLiveRangeFor(i); 950014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch range->AddUseInterval(curr_position, 951014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch curr_position.InstructionEnd(), zone()); 952014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 953b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 954b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 955086aeeaae12517475c22695a200be45495516549Ben Murdoch } 956086aeeaae12517475c22695a200be45495516549Ben Murdoch 957b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->ClobbersDoubleRegisters(isolate())) { 958014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < DoubleRegister::kMaxNumRegisters; ++i) { 95913e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch if (GetRegConfig()->IsAllocatableDoubleCode(i)) { 960014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (output == NULL || !output->IsDoubleRegister() || 961014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch output->index() != i) { 962014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LiveRange* range = FixedDoubleLiveRangeFor(i); 963014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch range->AddUseInterval(curr_position, 964014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch curr_position.InstructionEnd(), zone()); 965014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 966b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 967b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 968b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 969b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9703fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (UseIterator it(instr); !it.Done(); it.Advance()) { 9713fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LOperand* input = it.Current(); 972b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 973b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition use_pos; 974b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (input->IsUnallocated() && 975b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated::cast(input)->IsUsedAtStart()) { 976b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = curr_position; 977b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 978b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = curr_position.InstructionEnd(); 979b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 980b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 981b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Use(block_start_position, use_pos, input, NULL); 9823ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (input->IsUnallocated()) { 9833ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Add(LUnallocated::cast(input)->virtual_register()); 9843ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 985b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 986b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9873fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (TempIterator it(instr); !it.Done(); it.Advance()) { 9883fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LOperand* temp = it.Current(); 989b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->ClobbersTemps()) { 990b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp->IsRegister()) continue; 991b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp->IsUnallocated()) { 992b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* temp_unalloc = LUnallocated::cast(temp); 993b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp_unalloc->HasFixedPolicy()) { 994b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 995b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 996b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 997b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 998b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Use(block_start_position, curr_position.InstructionEnd(), temp, NULL); 999b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, temp, NULL); 1000b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1001b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (temp->IsUnallocated()) { 1002b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* temp_unalloc = LUnallocated::cast(temp); 1003b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (temp_unalloc->HasDoubleRegisterPolicy()) { 1004b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch double_artificial_registers_.Add( 1005b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch temp_unalloc->virtual_register() - first_artificial_register_, 1006b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch zone()); 1007b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1008b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1009b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1010b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1011b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1012b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1013b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch index = index - 1; 1014b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1015b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1016b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1017b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1018b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolvePhis(HBasicBlock* block) { 1019b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<HPhi*>* phis = block->phis(); 1020b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < phis->length(); ++i) { 1021b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = phis->at(i); 1022b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* phi_operand = 1023b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new (chunk()->zone()) LUnallocated(LUnallocated::NONE); 1024b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch phi_operand->set_virtual_register(phi->id()); 1025b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int j = 0; j < phi->OperandCount(); ++j) { 1026b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HValue* op = phi->OperandAt(j); 1027b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand = NULL; 1028b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (op->IsConstant() && op->EmitAtUses()) { 1029b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HConstant* constant = HConstant::cast(op); 1030b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand = chunk_->DefineConstantOperand(constant); 1031b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1032b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!op->EmitAtUses()); 1033b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* unalloc = 1034b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new(chunk()->zone()) LUnallocated(LUnallocated::ANY); 1035b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unalloc->set_virtual_register(op->id()); 1036b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand = unalloc; 1037b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1038b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* cur_block = block->predecessors()->at(j); 1039b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The gap move must be added without any special processing as in 1040b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the AddConstraintsGapMove. 1041b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch chunk_->AddGapMove(cur_block->last_instruction_index() - 1, 1042b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand, 1043b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch phi_operand); 1044257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 1045257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // We are going to insert a move before the branch instruction. 1046257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // Some branch instructions (e.g. loops' back edges) 1047257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // can potentially cause a GC so they have a pointer map. 1048257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // By inserting a move we essentially create a copy of a 1049257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // value which is invisible to PopulatePointerMaps(), because we store 1050257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // it into a location different from the operand of a live range 1051257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // covering a branch instruction. 1052257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // Thus we need to manually record a pointer. 10533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LInstruction* branch = 10543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch InstructionAt(cur_block->last_instruction_index()); 10553ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (branch->HasPointerMap()) { 1056b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (phi->representation().IsTagged() && !phi->type().IsSmi()) { 1057b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch branch->pointer_map()->RecordPointer(phi_operand, chunk()->zone()); 10583ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } else if (!phi->representation().IsDouble()) { 1059b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch branch->pointer_map()->RecordUntagged(phi_operand, chunk()->zone()); 1060257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch } 1061257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch } 1062b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1063b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1064b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* live_range = LiveRangeFor(phi->id()); 1065b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LLabel* label = chunk_->GetLabel(phi->block()->block_id()); 1066b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch label->GetOrCreateParallelMove(LGap::START, chunk()->zone())-> 1067b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AddMove(phi_operand, live_range->GetSpillOperand(), chunk()->zone()); 1068b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_range->SetSpillStartIndex(phi->block()->first_instruction_index()); 1069b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1070b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1071b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1072b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 10733ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochbool LAllocator::Allocate(LChunk* chunk) { 1074b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(chunk_ == NULL); 1075b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk_ = static_cast<LPlatformChunk*>(chunk); 1076b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch assigned_registers_ = 1077014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch new (chunk->zone()) BitVector(Register::kNumRegisters, chunk->zone()); 1078014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch assigned_double_registers_ = new (chunk->zone()) 1079014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BitVector(DoubleRegister::kMaxNumRegisters, chunk->zone()); 1080b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch MeetRegisterConstraints(); 10813ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1082b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolvePhis(); 1083b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BuildLiveRanges(); 1084b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateGeneralRegisters(); 10853ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1086b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateDoubleRegisters(); 10873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1088b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PopulatePointerMaps(); 1089b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ConnectRanges(); 1090b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolveControlFlow(); 10913ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return true; 1092b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1093b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1094b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1095b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::MeetRegisterConstraints() { 1096b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Register constraints", this); 10971e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1098b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < blocks->length(); ++i) { 1099b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(i); 1100b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch MeetRegisterConstraints(block); 11013ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 1102b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1103b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1104b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1105b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1106b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolvePhis() { 1107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Resolve phis", this); 1108b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1109b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process the blocks in reverse order. 11101e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1111b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { 1112b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(block_id); 1113b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolvePhis(block); 1114b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1115b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1116b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1117b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1118b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolveControlFlow(LiveRange* range, 1119b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block, 1120b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* pred) { 1121b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pred_end = 11221e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LifetimePosition::FromInstructionIndex(pred->last_instruction_index()); 1123b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition cur_start = 1124b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(block->first_instruction_index()); 1125b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* pred_cover = NULL; 1126b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_cover = NULL; 1127b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_range = range; 1128b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (cur_range != NULL && (cur_cover == NULL || pred_cover == NULL)) { 1129b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_range->CanCover(cur_start)) { 1130b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(cur_cover == NULL); 1131b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_cover = cur_range; 1132b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1133b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_range->CanCover(pred_end)) { 1134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pred_cover == NULL); 1135b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pred_cover = cur_range; 1136b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1137b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_range = cur_range->next(); 1138b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1139b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1140b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_cover->IsSpilled()) return; 1141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pred_cover != NULL && cur_cover != NULL); 1142b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pred_cover != cur_cover) { 1143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* pred_op = pred_cover->CreateAssignedOperand(chunk()->zone()); 1144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* cur_op = cur_cover->CreateAssignedOperand(chunk()->zone()); 1145b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!pred_op->Equals(cur_op)) { 1146b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LGap* gap = NULL; 1147b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block->predecessors()->length() == 1) { 11481e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block gap = GapAt(block->first_instruction_index()); 1149b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1150b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pred->end()->SecondSuccessor() == NULL); 1151b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch gap = GetLastGap(pred); 1152e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch 1153e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // We are going to insert a move before the branch instruction. 1154e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // Some branch instructions (e.g. loops' back edges) 1155e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // can potentially cause a GC so they have a pointer map. 1156257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // By inserting a move we essentially create a copy of a 1157e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // value which is invisible to PopulatePointerMaps(), because we store 1158e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // it into a location different from the operand of a live range 1159e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // covering a branch instruction. 1160e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // Thus we need to manually record a pointer. 11613ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LInstruction* branch = InstructionAt(pred->last_instruction_index()); 11623ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (branch->HasPointerMap()) { 11633ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (HasTaggedValue(range->id())) { 1164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch branch->pointer_map()->RecordPointer(cur_op, chunk()->zone()); 11653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } else if (!cur_op->IsDoubleStackSlot() && 11663ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch !cur_op->IsDoubleRegister()) { 11673ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch branch->pointer_map()->RemovePointer(cur_op); 1168e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch } 1169e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch } 1170b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch gap->GetOrCreateParallelMove( 1172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LGap::START, chunk()->zone())->AddMove(pred_op, cur_op, 1173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 1174b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1175b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1176b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1177b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1178b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1179b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLParallelMove* LAllocator::GetConnectingParallelMove(LifetimePosition pos) { 1180b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = pos.InstructionIndex(); 11811e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(index)) { 11821e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(index); 1183b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return gap->GetOrCreateParallelMove( 1184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch pos.IsInstructionStart() ? LGap::START : LGap::END, chunk()->zone()); 1185b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1186b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int gap_pos = pos.IsInstructionStart() ? (index - 1) : (index + 1); 11871e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return GapAt(gap_pos)->GetOrCreateParallelMove( 1188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch (gap_pos < index) ? LGap::AFTER : LGap::BEFORE, chunk()->zone()); 1189b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1190b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1191b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1192b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochHBasicBlock* LAllocator::GetBlock(LifetimePosition pos) { 11931e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex())); 1194b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return gap->block(); 1195b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1196b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1197b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1198b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ConnectRanges() { 1199b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Connect ranges", this); 1200b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges()->length(); ++i) { 1201b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* first_range = live_ranges()->at(i); 1202b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_range == NULL || first_range->parent() != NULL) continue; 1203b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1204b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* second_range = first_range->next(); 1205b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (second_range != NULL) { 1206b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos = second_range->Start(); 1207b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1208b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!second_range->IsSpilled()) { 1209b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Add gap move if the two live ranges touch and there is no block 1210b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // boundary. 1211b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_range->End().Value() == pos.Value()) { 1212b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool should_insert = true; 1213b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (IsBlockBoundary(pos)) { 1214b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch should_insert = CanEagerlyResolveControlFlow(GetBlock(pos)); 1215b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1216b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (should_insert) { 1217b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LParallelMove* move = GetConnectingParallelMove(pos); 1218b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* prev_operand = first_range->CreateAssignedOperand( 1219b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 1220b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* cur_operand = second_range->CreateAssignedOperand( 1221b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 1222b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch move->AddMove(prev_operand, cur_operand, 1223b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 1224b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1225b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1226b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1227b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1228b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_range = second_range; 1229b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch second_range = second_range->next(); 1230b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1231b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1232b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1233b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1234b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1235b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::CanEagerlyResolveControlFlow(HBasicBlock* block) const { 1236b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block->predecessors()->length() != 1) return false; 1237b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return block->predecessors()->first()->block_id() == block->block_id() - 1; 1238b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1239b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1240b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1241b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolveControlFlow() { 1242b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Resolve control flow", this); 12431e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1244b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int block_id = 1; block_id < blocks->length(); ++block_id) { 1245b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(block_id); 1246b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (CanEagerlyResolveControlFlow(block)) continue; 1247b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live = live_in_sets_[block->block_id()]; 1248b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live); 1249b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 1250b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 1251b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < block->predecessors()->length(); ++i) { 1252b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* cur = block->predecessors()->at(i); 1253b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_range = LiveRangeFor(operand_index); 1254b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolveControlFlow(cur_range, block, cur); 1255b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1256b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 1257b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1258b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1259b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1260b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1261b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1262b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::BuildLiveRanges() { 1263b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Build live ranges", this); 1264b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InitializeLivenessAnalysis(); 1265b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process the blocks in reverse order. 12661e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1267b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { 1268b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(block_id); 1269b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live = ComputeLiveOut(block); 1270b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Initially consider all live_out values live for the entire block. We 1271b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // will shorten these intervals if necessary. 1272b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddInitialIntervals(block, live); 1273b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1274b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process the instructions in reverse order, generating and killing 1275b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // live values. 1276b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ProcessInstructions(block, live); 1277b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All phi output operands are killed by this block. 1278b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<HPhi*>* phis = block->phis(); 1279b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < phis->length(); ++i) { 1280b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The live range interval already ends at the first instruction of the 1281b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // block. 1282b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = phis->at(i); 1283b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live->Remove(phi->id()); 1284b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1285b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint = NULL; 1286b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* phi_operand = NULL; 1287b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LGap* gap = GetLastGap(phi->block()->predecessors()->at(0)); 1288b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, 1289b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 1290b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int j = 0; j < move->move_operands()->length(); ++j) { 1291b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* to = move->move_operands()->at(j).destination(); 12923ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (to->IsUnallocated() && 12933ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated::cast(to)->virtual_register() == phi->id()) { 1294b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch hint = move->move_operands()->at(j).source(); 1295b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch phi_operand = to; 1296b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch break; 1297b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1298b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1299b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(hint != NULL); 1300b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1301b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition block_start = LifetimePosition::FromInstructionIndex( 1302b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 1303b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(block_start, phi_operand, hint); 1304b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1305b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1306b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Now live is live_in for this block except not including values live 1307b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // out on backward successor edges. 1308b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_in_sets_[block_id] = live; 1309b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1310b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If this block is a loop header go back and patch up the necessary 1311b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // predecessor blocks. 1312b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block->IsLoopHeader()) { 1313b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // TODO(kmillikin): Need to be able to get the last block of the loop 1314b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // in the loop information. Add a live range stretching from the first 1315b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // loop instruction to the last for each value live on entry to the 1316b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // header. 1317b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* back_edge = block->loop_information()->GetLastBackEdge(); 1318b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live); 1319b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = LifetimePosition::FromInstructionIndex( 1320b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 1321b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end = LifetimePosition::FromInstructionIndex( 13221e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block back_edge->last_instruction_index()).NextInstruction(); 1323b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 1324b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 1325b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand_index); 1326b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->EnsureInterval(start, end, zone()); 1327b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 1328b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1329b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1330b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = block->block_id() + 1; i <= back_edge->block_id(); ++i) { 1331b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_in_sets_[i]->Union(*live); 1332b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1333b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1334b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1335b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 1336b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block_id == 0) { 1337b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live); 1338b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool found = false; 1339b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 1340b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch found = true; 1341b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 1342014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch { 1343b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AllowHandleDereference allow_deref; 1344014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PrintF("Function: %s\n", chunk_->info()->GetDebugName().get()); 1345b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1346b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PrintF("Value %d used before first definition!\n", operand_index); 1347b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand_index); 1348b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PrintF("First use is at %d\n", range->first_pos()->pos().Value()); 1349b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 1350b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1351b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!found); 1352b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1353b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 1354b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1355b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1356b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < live_ranges_.length(); ++i) { 1357b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (live_ranges_[i] != NULL) { 1358b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_ranges_[i]->kind_ = RequiredRegisterKind(live_ranges_[i]->id()); 1359b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1360b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1361b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1362b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1363b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1364b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::SafePointsAreInOrder() const { 1365b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); 1366b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = 0; 1367b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < pointer_maps->length(); ++i) { 1368b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(i); 1369b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point > map->lithium_position()) return false; 1370b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point = map->lithium_position(); 1371b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1372b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1373b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1374b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1375b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1376b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::PopulatePointerMaps() { 1377b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Populate pointer maps", this); 1378b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); 1379b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1380b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(SafePointsAreInOrder()); 1381b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1382b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Iterate over all safe point positions and record a pointer 1383b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // for all spilled live ranges at this point. 1384b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int first_safe_point_index = 0; 1385b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int last_range_start = 0; 1386b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { 1387b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = live_ranges()->at(range_idx); 1388b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL) continue; 1389b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Iterate over the first parts of multi-part live ranges. 1390b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->parent() != NULL) continue; 1391b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Skip non-pointer values. 1392b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!HasTaggedValue(range->id())) continue; 1393b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Skip empty live ranges. 1394b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsEmpty()) continue; 1395b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1396b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the extent of the range and its children. 1397b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int start = range->Start().InstructionIndex(); 1398b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int end = 0; 1399b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (LiveRange* cur = range; cur != NULL; cur = cur->next()) { 1400b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition this_end = cur->End(); 1401b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (this_end.InstructionIndex() > end) end = this_end.InstructionIndex(); 1402b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(cur->Start().InstructionIndex() >= start); 1403b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1404b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1405b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Most of the ranges are in order, but not all. Keep an eye on when 1406b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // they step backwards and reset the first_safe_point_index so we don't 1407b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // miss any safe points. 1408b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start < last_range_start) { 1409b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_safe_point_index = 0; 1410b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1411b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_range_start = start; 1412b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1413b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Step across all the safe points that are before the start of this range, 1414b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // recording how far we step in order to save doing this for the next range. 1415b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (first_safe_point_index < pointer_maps->length()) { 1416b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(first_safe_point_index); 1417b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = map->lithium_position(); 1418b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point >= start) break; 1419b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_safe_point_index++; 1420b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1421b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1422b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Step through the safe points to see whether they are in the range. 1423b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int safe_point_index = first_safe_point_index; 1424b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point_index < pointer_maps->length(); 1425b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ++safe_point_index) { 1426b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(safe_point_index); 1427b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = map->lithium_position(); 1428b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1429b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The safe points are sorted so we can stop searching here. 1430b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point - 1 > end) break; 1431b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1432b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Advance to the next active range that covers the current 1433b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // safe point position. 1434b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition safe_point_pos = 1435b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(safe_point); 1436b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur = range; 1437b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (cur != NULL && !cur->Covers(safe_point_pos)) { 1438b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur = cur->next(); 1439b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1440b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur == NULL) continue; 1441b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1442b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Check if the live range is spilled and the safe point is after 1443b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the spill position. 1444b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->HasAllocatedSpillOperand() && 1445b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point >= range->spill_start_index()) { 1446b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Pointer for range %d (spilled at %d) at safe point %d\n", 1447b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->id(), range->spill_start_index(), safe_point); 1448b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch map->RecordPointer(range->GetSpillOperand(), chunk()->zone()); 1449b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1450b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1451b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!cur->IsSpilled()) { 1452b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Pointer in register for range %d (start at %d) " 1453b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch "at safe point %d\n", 1454b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur->id(), cur->Start().Value(), safe_point); 1455b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* operand = cur->CreateAssignedOperand(chunk()->zone()); 1456b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!operand->IsStackSlot()); 1457b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch map->RecordPointer(operand, chunk()->zone()); 1458b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1459b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1460b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1461b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1462b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1463b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1464b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateGeneralRegisters() { 1465b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Allocate general registers", this); 146613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch num_registers_ = GetRegConfig()->num_allocatable_general_registers(); 146713e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch allocatable_register_codes_ = GetRegConfig()->allocatable_general_codes(); 1468b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch mode_ = GENERAL_REGISTERS; 1469b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateRegisters(); 1470b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1471b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1472b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1473b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateDoubleRegisters() { 1474b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Allocate double registers", this); 147513e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch num_registers_ = GetRegConfig()->num_allocatable_double_registers(); 147613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch allocatable_register_codes_ = GetRegConfig()->allocatable_double_codes(); 1477b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch mode_ = DOUBLE_REGISTERS; 1478b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateRegisters(); 1479b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1480b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1481b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1482b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateRegisters() { 1483b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(unhandled_live_ranges_.is_empty()); 1484b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1485b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges_.length(); ++i) { 1486b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (live_ranges_[i] != NULL) { 1487b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (live_ranges_[i]->Kind() == mode_) { 1488b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledUnsorted(live_ranges_[i]); 1489b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1490b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1491b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1492b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SortUnhandled(); 1493b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1494b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1495b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(reusable_slots_.is_empty()); 1496b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(active_live_ranges_.is_empty()); 1497b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(inactive_live_ranges_.is_empty()); 1498b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1499b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (mode_ == DOUBLE_REGISTERS) { 1500014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < fixed_double_live_ranges_.length(); ++i) { 1501b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = fixed_double_live_ranges_.at(i); 1502b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) { 1503b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToInactive(current); 1504b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1505b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1506b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1507b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(mode_ == GENERAL_REGISTERS); 1508b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < fixed_live_ranges_.length(); ++i) { 1509b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = fixed_live_ranges_.at(i); 1510b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) { 1511b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToInactive(current); 1512b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1513b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1514b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1515b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1516b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!unhandled_live_ranges_.is_empty()) { 1517b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1518b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = unhandled_live_ranges_.RemoveLast(); 1519b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1520b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position = current->Start(); 1521b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifdef DEBUG 1522b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocation_finger_ = position; 1523b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 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; 1546b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(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 1573b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!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) { 159413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch return GetRegConfig()->GetGeneralRegisterName(allocation_index); 1595b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 159613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch return GetRegConfig()->GetDoubleRegisterName(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); 1605b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch base::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; 1614b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return value->representation().IsTagged() && !value->type().IsSmi(); 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()); 1635b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch active_live_ranges_.Add(range, zone()); 1636b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1637b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1638b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1639b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToInactive(LiveRange* range) { 1640b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to inactive\n", range->id()); 1641b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inactive_live_ranges_.Add(range, zone()); 1642b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1643b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1644b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1645b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToUnhandledSorted(LiveRange* range) { 1646b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL || range->IsEmpty()) return; 1647b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); 1648b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(allocation_finger_.Value() <= range->Start().Value()); 1649b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = unhandled_live_ranges_.length() - 1; i >= 0; --i) { 1650b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_range = unhandled_live_ranges_.at(i); 1651b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->ShouldBeAllocatedBefore(cur_range)) { 1652b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled at %d\n", range->id(), i + 1); 1653b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unhandled_live_ranges_.InsertAt(i + 1, range, zone()); 1654b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1655b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1656b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1657b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1658b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled at start\n", range->id()); 1659b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unhandled_live_ranges_.InsertAt(0, range, zone()); 1660b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1661b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1662b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1663b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1664b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToUnhandledUnsorted(LiveRange* range) { 1665b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL || range->IsEmpty()) return; 1666b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); 1667b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled unsorted at end\n", range->id()); 1668b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unhandled_live_ranges_.Add(range, zone()); 1669b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1670b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1671b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1672b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic int UnhandledSortHelper(LiveRange* const* a, LiveRange* const* b) { 1673b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!(*a)->ShouldBeAllocatedBefore(*b) || 1674b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch !(*b)->ShouldBeAllocatedBefore(*a)); 1675b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if ((*a)->ShouldBeAllocatedBefore(*b)) return 1; 1676b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if ((*b)->ShouldBeAllocatedBefore(*a)) return -1; 1677b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return (*a)->id() - (*b)->id(); 1678b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1679b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1680b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1681b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Sort the unhandled live ranges so that the ranges to be processed first are 1682b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// at the end of the array list. This is convenient for the register allocation 1683b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// algorithm because it is efficient to remove elements from the end. 1684b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SortUnhandled() { 1685b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Sort unhandled\n"); 1686b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unhandled_live_ranges_.Sort(&UnhandledSortHelper); 1687b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1688b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1689b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1690b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::UnhandledIsSorted() { 1691b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int len = unhandled_live_ranges_.length(); 1692b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < len; i++) { 1693b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* a = unhandled_live_ranges_.at(i - 1); 1694b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* b = unhandled_live_ranges_.at(i); 1695b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->Start().Value() < b->Start().Value()) return false; 1696b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1697b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1698b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1699b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1700b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1701b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::FreeSpillSlot(LiveRange* range) { 1702b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Check that we are the last range. 1703b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->next() != NULL) return; 1704b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1705b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!range->TopLevel()->HasAllocatedSpillOperand()) return; 1706b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1707b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = range->TopLevel()->GetSpillOperand()->index(); 1708b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (index >= 0) { 1709b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch reusable_slots_.Add(range, zone()); 1710b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1711b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1712b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1713b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1714b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLOperand* LAllocator::TryReuseSpillSlot(LiveRange* range) { 1715b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (reusable_slots_.is_empty()) return NULL; 1716b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (reusable_slots_.first()->End().Value() > 1717b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->TopLevel()->Start().Value()) { 1718b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 1719b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1720b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* result = reusable_slots_.first()->TopLevel()->GetSpillOperand(); 1721b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch reusable_slots_.Remove(0); 1722b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 1723b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1724b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1725b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1726b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ActiveToHandled(LiveRange* range) { 1727b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(active_live_ranges_.Contains(range)); 1728b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch active_live_ranges_.RemoveElement(range); 1729b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from active to handled\n", range->id()); 1730b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch FreeSpillSlot(range); 1731b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1732b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1733b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1734b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ActiveToInactive(LiveRange* range) { 1735b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(active_live_ranges_.Contains(range)); 1736b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch active_live_ranges_.RemoveElement(range); 1737b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inactive_live_ranges_.Add(range, zone()); 1738b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from active to inactive\n", range->id()); 1739b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1740b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1741b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1742b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::InactiveToHandled(LiveRange* range) { 1743b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(inactive_live_ranges_.Contains(range)); 1744b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inactive_live_ranges_.RemoveElement(range); 1745b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); 1746b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch FreeSpillSlot(range); 1747b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1748b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1749b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1750b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::InactiveToActive(LiveRange* range) { 1751b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(inactive_live_ranges_.Contains(range)); 1752b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inactive_live_ranges_.RemoveElement(range); 1753b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch active_live_ranges_.Add(range, zone()); 1754b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from inactive to active\n", range->id()); 1755b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1756b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1757b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1758b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::TryAllocateFreeReg(LiveRange* current) { 1759014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(DoubleRegister::kMaxNumRegisters >= Register::kNumRegisters); 1760014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1761014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition free_until_pos[DoubleRegister::kMaxNumRegisters]; 1762b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1763014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < DoubleRegister::kMaxNumRegisters; i++) { 1764b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[i] = LifetimePosition::MaxPosition(); 1765b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1766b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1767b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1768b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_active = active_live_ranges_.at(i); 1769b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[cur_active->assigned_register()] = 1770b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(0); 1771b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1772b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1773b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1774b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_inactive = inactive_live_ranges_.at(i); 1775b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(cur_inactive->End().Value() > current->Start().Value()); 1776b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = 1777b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_inactive->FirstIntersection(current); 1778b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!next_intersection.IsValid()) continue; 1779b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = cur_inactive->assigned_register(); 1780b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection); 1781b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1782b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1783b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* hint = current->FirstHint(); 1784b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (hint != NULL && (hint->IsRegister() || hint->IsDoubleRegister())) { 1785b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int register_index = hint->index(); 1786b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TraceAlloc( 1787b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch "Found reg hint %s (free until [%d) for live range %d (end %d[).\n", 1788b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterName(register_index), 1789b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch free_until_pos[register_index].Value(), 1790b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->id(), 1791b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->End().Value()); 1792b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1793b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // The desired register is free until the end of the current live range. 1794b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (free_until_pos[register_index].Value() >= current->End().Value()) { 1795b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TraceAlloc("Assigning preferred reg %s to live range %d\n", 1796b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterName(register_index), 1797b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->id()); 1798b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(current, register_index); 1799b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return true; 1800b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1801b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1802b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1803b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the register which stays free for the longest time. 1804014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int reg = allocatable_register_codes_[0]; 1805b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < RegisterCount(); ++i) { 1806014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int code = allocatable_register_codes_[i]; 1807014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (free_until_pos[code].Value() > free_until_pos[reg].Value()) { 1808014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch reg = code; 1809b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1810b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1811b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1812b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos = free_until_pos[reg]; 1813b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1814b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() <= current->Start().Value()) { 1815b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All registers are blocked. 1816b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 1817b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1818b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1819b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() < current->End().Value()) { 1820b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is available at the range start but becomes blocked before 1821b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the range end. Split current at position where it becomes blocked. 18223ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* tail = SplitRangeAt(current, pos); 18233ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1824b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(tail); 1825b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1826b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1827b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1828b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is available at the range start and is free until 1829b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the range end. 1830b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pos.Value() >= current->End().Value()); 1831b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Assigning free reg %s to live range %d\n", 1832b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterName(reg), 1833b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id()); 1834b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(current, reg); 1835b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1836b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1837b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1838b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1839b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1840b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateBlockedReg(LiveRange* current) { 1841b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* register_use = current->NextRegisterPosition(current->Start()); 1842b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (register_use == NULL) { 1843b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // There is no use in the current live range that requires a register. 1844b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We can just spill it. 1845b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(current); 1846b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1847b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1848b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1849b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1850014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition use_pos[DoubleRegister::kMaxNumRegisters]; 1851014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition block_pos[DoubleRegister::kMaxNumRegisters]; 1852b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1853014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < DoubleRegister::kMaxNumRegisters; i++) { 1854b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[i] = block_pos[i] = LifetimePosition::MaxPosition(); 1855b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1856b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1857b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1858b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = active_live_ranges_[i]; 1859b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = range->assigned_register(); 1860b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsFixed() || !range->CanBeSpilled(current->Start())) { 1861b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[cur_reg] = use_pos[cur_reg] = 1862b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(0); 1863b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1864b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_use = range->NextUsePositionRegisterIsBeneficial( 1865b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->Start()); 1866b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_use == NULL) { 1867b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = range->End(); 1868b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1869b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = next_use->pos(); 1870b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1871b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1872b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1873b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1874b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1875b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = inactive_live_ranges_.at(i); 1876b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(range->End().Value() > current->Start().Value()); 1877b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = range->FirstIntersection(current); 1878b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!next_intersection.IsValid()) continue; 1879b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = range->assigned_register(); 1880b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsFixed()) { 1881b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection); 1882b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]); 1883b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1884b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection); 1885b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1886b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1887b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1888014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int reg = allocatable_register_codes_[0]; 1889b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < RegisterCount(); ++i) { 1890014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int code = allocatable_register_codes_[i]; 1891014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (use_pos[code].Value() > use_pos[reg].Value()) { 1892014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch reg = code; 1893b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1894b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1895b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1896b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos = use_pos[reg]; 1897b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1898b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() < register_use->pos().Value()) { 1899b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All registers are blocked before the first use that requires a register. 1900b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Spill starting part of live range up to that use. 1901b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(current, current->Start(), register_use->pos()); 1902b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1903b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1904b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1905b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block_pos[reg].Value() < current->End().Value()) { 1906b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register becomes blocked before the current range end. Split before that 1907b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position. 1908b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* tail = SplitBetween(current, 1909b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->Start(), 1910b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[reg].InstructionStart()); 1911b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 1912b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(tail); 1913b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1914b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1915b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is not blocked for the whole range. 1916b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(block_pos[reg].Value() >= current->End().Value()); 1917b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Assigning blocked reg %s to live range %d\n", 1918b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterName(reg), 1919b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id()); 1920b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(current, reg); 1921b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1922b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This register was not free. Thus we need to find and spill 1923b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // parts of active and inactive live regions that use the same register 1924b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // at the same lifetime positions as current. 1925b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SplitAndSpillIntersecting(current); 1926b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1927b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1928b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1929b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochLifetimePosition LAllocator::FindOptimalSpillingPos(LiveRange* range, 1930b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition pos) { 1931b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block = GetBlock(pos.InstructionStart()); 1932b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* loop_header = 1933b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block->IsLoopHeader() ? block : block->parent_loop_header(); 1934b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1935b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (loop_header == NULL) return pos; 1936b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1937b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* prev_use = 1938b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->PreviousUsePositionRegisterIsBeneficial(pos); 1939b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1940b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (loop_header != NULL) { 1941b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // We are going to spill live range inside the loop. 1942b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If possible try to move spilling position backwards to loop header. 1943b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This will reduce number of memory moves on the back edge. 1944b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition loop_start = LifetimePosition::FromInstructionIndex( 1945b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch loop_header->first_instruction_index()); 1946b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1947b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (range->Covers(loop_start)) { 1948b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (prev_use == NULL || prev_use->pos().Value() < loop_start.Value()) { 1949b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // No register beneficial use inside the loop before the pos. 1950b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch pos = loop_start; 1951b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1952b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1953b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1954b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Try hoisting out to an outer loop. 1955b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch loop_header = loop_header->parent_loop_header(); 1956b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1957b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1958b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return pos; 1959b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 1960b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1961b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1962b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SplitAndSpillIntersecting(LiveRange* current) { 1963b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(current->HasRegisterAssigned()); 1964b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int reg = current->assigned_register(); 1965b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition split_pos = current->Start(); 1966b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1967b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = active_live_ranges_[i]; 1968b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->assigned_register() == reg) { 1969b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_pos = range->NextRegisterPosition(current->Start()); 1970b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos); 1971b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_pos == NULL) { 1972b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SpillAfter(range, spill_pos); 1973b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1974b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // When spilling between spill_pos and next_pos ensure that the range 1975b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // remains spilled at least until the start of the current live range. 1976b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This guarantees that we will not introduce new unhandled ranges that 1977b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // start before the current range as this violates allocation invariant 1978b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // and will lead to an inconsistent state of active and inactive 1979b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // live-ranges: ranges are allocated in order of their start positions, 1980b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // ranges are retired from active/inactive when the start of the 1981b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // current live-range is larger than their end. 1982b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos()); 1983b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1984b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 1985b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ActiveToHandled(range); 1986b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; 1987b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1988b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1989b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1990b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1991b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = inactive_live_ranges_[i]; 1992b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(range->End().Value() > current->Start().Value()); 1993b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->assigned_register() == reg && !range->IsFixed()) { 1994b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = range->FirstIntersection(current); 1995b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_intersection.IsValid()) { 1996b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_pos = range->NextRegisterPosition(current->Start()); 1997b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_pos == NULL) { 1998b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillAfter(range, split_pos); 1999b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 2000b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_intersection = Min(next_intersection, next_pos->pos()); 2001b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(range, split_pos, next_intersection); 2002b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2003b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 2004b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InactiveToHandled(range); 2005b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; 2006b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2007b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2008b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2009b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2010b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2011b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2012b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::IsBlockBoundary(LifetimePosition pos) { 2013b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos.IsInstructionStart() && 20141e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block InstructionAt(pos.InstructionIndex())->IsLabel(); 2015b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2016b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2017b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 20183ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLiveRange* LAllocator::SplitRangeAt(LiveRange* range, LifetimePosition pos) { 2019b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->IsFixed()); 2020b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value()); 2021b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2022b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() <= range->Start().Value()) return range; 2023b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 20241e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block // We can't properly connect liveranges if split occured at the end 20251e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block // of control instruction. 2026b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pos.IsInstructionStart() || 20271e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block !chunk_->instructions()->at(pos.InstructionIndex())->IsControl()); 20281e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 2029b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int vreg = GetVirtualRegister(); 20303ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return NULL; 2031b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* result = LiveRangeFor(vreg); 2032b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->SplitAt(pos, result, zone()); 2033b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 2034b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2035b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2036b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2037b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::SplitBetween(LiveRange* range, 2038b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 2039b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2040b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->IsFixed()); 2041b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Splitting live range %d in position between [%d, %d]\n", 2042b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->id(), 2043b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 2044b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 2045b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2046b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition split_pos = FindOptimalSplitPos(start, end); 2047b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(split_pos.Value() >= start.Value()); 20483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return SplitRangeAt(range, split_pos); 2049b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2050b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2051b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2052b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLifetimePosition LAllocator::FindOptimalSplitPos(LifetimePosition start, 2053b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2054b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int start_instr = start.InstructionIndex(); 2055b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int end_instr = end.InstructionIndex(); 2056b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(start_instr <= end_instr); 2057b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2058b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We have no choice 2059b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start_instr == end_instr) return end; 2060b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2061257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch HBasicBlock* start_block = GetBlock(start); 2062257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch HBasicBlock* end_block = GetBlock(end); 2063b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2064b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (end_block == start_block) { 2065257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // The interval is split in the same basic block. Split at the latest 2066257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // possible position. 2067b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return end; 2068b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2069b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2070b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = end_block; 2071b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find header of outermost loop. 2072b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (block->parent_loop_header() != NULL && 2073b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->parent_loop_header()->block_id() > start_block->block_id()) { 2074b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block = block->parent_loop_header(); 2075b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2076b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2077257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // We did not find any suitable outer loop. Split at the latest possible 2078257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // position unless end_block is a loop header itself. 2079257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch if (block == end_block && !end_block->IsLoopHeader()) return end; 2080b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2081b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition::FromInstructionIndex( 2082b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 2083b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2084b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2085b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2086b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) { 20873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* second_part = SplitRangeAt(range, pos); 20883ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 2089b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(second_part); 2090b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2091b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2092b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2093b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SpillBetween(LiveRange* range, 2094b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 2095b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2096b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SpillBetweenUntil(range, start, start, end); 2097b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 2098b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2099b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid LAllocator::SpillBetweenUntil(LiveRange* range, 2101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition start, 2102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition until, 2103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end) { 2104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(start.Value() < end.Value()); 21053ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* second_part = SplitRangeAt(range, start); 21063ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 2107b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2108b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second_part->Start().Value() < end.Value()) { 2109b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split result intersects with [start, end[. 2110b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split it at position between ]start+1, end[, spill the middle part 2111b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // and put the rest to unhandled. 2112b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* third_part = SplitBetween( 2113b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch second_part, 2114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Max(second_part->Start().InstructionEnd(), until), 2115b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.PrevInstruction().InstructionEnd()); 2116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 2117b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(third_part != second_part); 2119b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2120b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(second_part); 2121b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(third_part); 2122b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 2123b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split result does not intersect with [start, end[. 2124b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Nothing to spill. Just put it to unhandled as whole. 2125b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(second_part); 2126b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2127b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2128b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2129b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2130b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Spill(LiveRange* range) { 2131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->IsSpilled()); 2132b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Spilling live range %d\n", range->id()); 2133b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* first = range->TopLevel(); 2134b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2135b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!first->HasAllocatedSpillOperand()) { 2136b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* op = TryReuseSpillSlot(range); 2137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (op == NULL) op = chunk_->GetNextSpillSlot(range->Kind()); 2138b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first->SetSpillOperand(op); 2139b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->MakeSpilled(chunk()->zone()); 2141b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2142b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2143b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2144b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochint LAllocator::RegisterCount() const { 2145b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return num_registers_; 2146b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2147b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2148b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2149b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 2150b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2151b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2152b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Verify() const { 2153b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges()->length(); ++i) { 2154b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = live_ranges()->at(i); 2155b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) current->Verify(); 2156b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2157b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2158b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2159b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2160b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 2161b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2162b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2163b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochLAllocatorPhase::LAllocatorPhase(const char* name, LAllocator* allocator) 2164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : CompilationPhase(name, allocator->graph()->info()), 2165b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocator_(allocator) { 2166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_hydrogen_stats) { 2167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocator_zone_start_allocation_size_ = 2168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocator->zone()->allocation_size(); 2169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 2170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 2171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochLAllocatorPhase::~LAllocatorPhase() { 2174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_hydrogen_stats) { 2175014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t size = allocator_->zone()->allocation_size() - 2176014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch allocator_zone_start_allocation_size_; 2177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch isolate()->GetHStatistics()->SaveTiming(name(), base::TimeDelta(), size); 2178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 2179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (ShouldProduceTraceOutput()) { 2181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch isolate()->GetHTracer()->TraceLithium(name(), allocator_->chunk()); 2182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch isolate()->GetHTracer()->TraceLiveRanges(name(), allocator_); 2183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 2184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2185b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifdef DEBUG 2186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (allocator_ != NULL) allocator_->Verify(); 2187b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 2188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 2189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2190b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2191014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace internal 2192014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace v8 2193