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-inl.h" 9014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/crankshaft/lithium-allocator-inl.h" 10014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/register-configuration.h" 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/string-stream.h" 12b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 13b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochnamespace v8 { 14b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochnamespace internal { 15b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 16b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) { 17b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return a.Value() < b.Value() ? a : b; 18b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 19b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 20b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 21b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) { 22b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return a.Value() > b.Value() ? a : b; 23b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 24b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 25b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochUsePosition::UsePosition(LifetimePosition pos, 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* operand, 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* hint) 291e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block : operand_(operand), 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch hint_(hint), 311e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block pos_(pos), 321e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block next_(NULL), 331e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block requires_reg_(false), 341e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block register_beneficial_(true) { 351e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (operand_ != NULL && operand_->IsUnallocated()) { 361e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LUnallocated* unalloc = LUnallocated::cast(operand_); 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch requires_reg_ = unalloc->HasRegisterPolicy() || 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unalloc->HasDoubleRegisterPolicy(); 391e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block register_beneficial_ = !unalloc->HasAnyPolicy(); 40b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pos_.IsValid()); 42b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 43b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 441e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 451e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockbool UsePosition::HasHint() const { 461e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return hint_ != NULL && !hint_->IsUnallocated(); 47b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 48b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 49b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 50b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool UsePosition::RequiresRegister() const { 51b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return requires_reg_; 52b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 53b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 54b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 55b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool UsePosition::RegisterIsBeneficial() const { 56b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return register_beneficial_; 57b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 58b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 59b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 603ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid UseInterval::SplitAt(LifetimePosition pos, Zone* zone) { 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Contains(pos) && pos.Value() != start().Value()); 623ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* after = new(zone) UseInterval(pos, end_); 63b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch after->next_ = next_; 64b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_ = after; 65b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end_ = pos; 66b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 67b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 68b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 69b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 70b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 71b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 72b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::Verify() const { 73b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* cur = first_pos_; 74b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (cur != NULL) { 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Start().Value() <= cur->pos().Value() && 76b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur->pos().Value() <= End().Value()); 77b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur = cur->next(); 78b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 79b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 80b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 81b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 82b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::HasOverlap(UseInterval* target) const { 83b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* current_interval = first_interval_; 84b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current_interval != NULL) { 85b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Intervals overlap if the start of one is contained in the other. 86b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval->Contains(target->start()) || 87b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch target->Contains(current_interval->start())) { 88b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 89b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 90b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval = current_interval->next(); 91b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 92b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 93b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 94b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 95b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 96b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 97b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 98b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 993ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLiveRange::LiveRange(int id, Zone* zone) 1001e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block : id_(id), 1011e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spilled_(false), 102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch kind_(UNALLOCATED_REGISTERS), 1031e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_(kInvalidAssignment), 1041e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block last_interval_(NULL), 1051e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block first_interval_(NULL), 1061e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block first_pos_(NULL), 1071e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block parent_(NULL), 1081e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block next_(NULL), 1091e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block current_interval_(NULL), 1101e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block last_processed_use_(NULL), 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current_hint_operand_(NULL), 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch spill_operand_(new (zone) LOperand()), 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch spill_start_index_(kMaxInt) {} 1141e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1151e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid LiveRange::set_assigned_register(int reg, Zone* zone) { 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!HasRegisterAssigned() && !IsSpilled()); 1181e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_ = reg; 1193ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ConvertOperands(zone); 1201e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1211e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1221e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1233ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::MakeSpilled(Zone* zone) { 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsSpilled()); 125b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(TopLevel()->HasAllocatedSpillOperand()); 1261e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spilled_ = true; 1271e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_ = kInvalidAssignment; 1283ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ConvertOperands(zone); 1291e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1301e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1311e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1321e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockbool LiveRange::HasAllocatedSpillOperand() const { 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(spill_operand_ != NULL); 1343ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return !spill_operand_->IsIgnored(); 1351e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1361e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1371e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1381e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockvoid LiveRange::SetSpillOperand(LOperand* operand) { 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!operand->IsUnallocated()); 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(spill_operand_ != NULL); 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(spill_operand_->IsIgnored()); 1421e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spill_operand_->ConvertTo(operand->kind(), operand->index()); 1431e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1441e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1451e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 146b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextUsePosition(LifetimePosition start) { 147b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = last_processed_use_; 148b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos == NULL) use_pos = first_pos(); 149b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_pos != NULL && use_pos->pos().Value() < start.Value()) { 150b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = use_pos->next(); 151b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 152b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_processed_use_ = use_pos; 153b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return use_pos; 154b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 155b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 156b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 157b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextUsePositionRegisterIsBeneficial( 158b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start) { 159b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = NextUsePosition(start); 160b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (pos != NULL && !pos->RegisterIsBeneficial()) { 161b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos = pos->next(); 162b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 163b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos; 164b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 165b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 166b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochUsePosition* LiveRange::PreviousUsePositionRegisterIsBeneficial( 168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition start) { 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* pos = first_pos(); 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* prev = NULL; 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (pos != NULL && pos->pos().Value() < start.Value()) { 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (pos->RegisterIsBeneficial()) prev = pos; 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch pos = pos->next(); 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return prev; 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 179b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) { 180b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = NextUsePosition(start); 181b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (pos != NULL && !pos->RequiresRegister()) { 182b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos = pos->next(); 183b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 184b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos; 185b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 186b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 187b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 188b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::CanBeSpilled(LifetimePosition pos) { 189b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We cannot spill a live range that has a use requiring a register 190b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // at the current or the immediate next position. 191b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = NextRegisterPosition(pos); 192b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos == NULL) return true; 1933ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return 1943ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch use_pos->pos().Value() > pos.NextInstruction().InstructionEnd().Value(); 195b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 196b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 197b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1983ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLOperand* LiveRange::CreateAssignedOperand(Zone* zone) { 199b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* op = NULL; 200b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (HasRegisterAssigned()) { 201b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsSpilled()); 202b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch switch (Kind()) { 203b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case GENERAL_REGISTERS: 204b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch op = LRegister::Create(assigned_register(), zone); 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 206b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case DOUBLE_REGISTERS: 207b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch op = LDoubleRegister::Create(assigned_register(), zone); 208b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 209b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch default: 210b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UNREACHABLE(); 211b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 212b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (IsSpilled()) { 213b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!HasRegisterAssigned()); 214b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch op = TopLevel()->GetSpillOperand(); 215b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!op->IsUnallocated()); 216b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 2173ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated* unalloc = new(zone) LUnallocated(LUnallocated::NONE); 218b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unalloc->set_virtual_register(id_); 219b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch op = unalloc; 220b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 221b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return op; 222b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 223b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 224b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 225b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUseInterval* LiveRange::FirstSearchIntervalForPosition( 226b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position) const { 227b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval_ == NULL) return first_interval_; 228b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval_->start().Value() > position.Value()) { 229b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ = NULL; 230b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return first_interval_; 231b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 232b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return current_interval_; 233b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 234b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 235b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 236b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::AdvanceLastProcessedMarker( 237b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* to_start_of, LifetimePosition but_not_past) const { 238b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of == NULL) return; 239b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of->start().Value() > but_not_past.Value()) return; 240b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = 241b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ == NULL ? LifetimePosition::Invalid() 242b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch : current_interval_->start(); 243b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of->start().Value() > start.Value()) { 244b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ = to_start_of; 245b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 246b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 247b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 248b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::SplitAt(LifetimePosition position, 2503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* result, 2513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 252b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Start().Value() < position.Value()); 253b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(result->IsEmpty()); 254b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the last interval that ends before the position. If the 255b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position is contained in one of the intervals in the chain, we 256b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // split that interval and use the first part. 257b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* current = FirstSearchIntervalForPosition(position); 258b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 259b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If the split position coincides with the beginning of a use interval 260b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // we need to split use positons in a special way. 261b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool split_at_start = false; 262b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2633fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch if (current->start().Value() == position.Value()) { 2643fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // When splitting at start we need to locate the previous use interval. 2653fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch current = first_interval_; 2663fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch } 2673fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 268b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current != NULL) { 269b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current->Contains(position)) { 2703ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch current->SplitAt(position, zone); 271b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch break; 272b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 273b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* next = current->next(); 274b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next->start().Value() >= position.Value()) { 275b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch split_at_start = (next->start().Value() == position.Value()); 276b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch break; 277b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 278b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current = next; 279b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 280b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 281b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Partition original use intervals to the two live ranges. 282b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* before = current; 283b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* after = before->next(); 284b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->last_interval_ = (last_interval_ == before) 285b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ? after // Only interval in the range after split. 286b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch : last_interval_; // Last interval of the original range. 287b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->first_interval_ = after; 288b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = before; 289b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 290b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the last use position before the split and the first use 291b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position after it. 292b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_after = first_pos_; 293b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_before = NULL; 294b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (split_at_start) { 295b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split position coincides with the beginning of a use interval (the 296b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // end of a lifetime hole). Use at this position should be attributed to 297b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the split child because split child owns use interval covering it. 298b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_after != NULL && use_after->pos().Value() < position.Value()) { 299b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before = use_after; 300b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_after = use_after->next(); 301b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 302b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 303b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_after != NULL && use_after->pos().Value() <= position.Value()) { 304b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before = use_after; 305b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_after = use_after->next(); 306b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 307b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 308b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 309b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Partition original use positions to the two live ranges. 310b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_before != NULL) { 311b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before->next_ = NULL; 312b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 313b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_pos_ = NULL; 314b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 315b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->first_pos_ = use_after; 316b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3173fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Discard cached iteration state. It might be pointing 3183fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // to the use that no longer belongs to this live range. 3193fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch last_processed_use_ = NULL; 3203fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch current_interval_ = NULL; 3213fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 322b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Link the new live range in the chain before any of the other 323b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // ranges linked from the range before the split. 324b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->parent_ = (parent_ == NULL) ? this : parent_; 325b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result->kind_ = result->parent_->kind_; 326b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->next_ = next_; 327b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_ = result; 328b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 329b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 330b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Verify(); 331b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->Verify(); 332b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 333b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 334b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 335b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 336b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// This implements an ordering on live ranges so that they are ordered by their 337b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// start positions. This is needed for the correctness of the register 338b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// allocation algorithm. If two live ranges start at the same offset then there 339b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// is a tie breaker based on where the value is first used. This part of the 340b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// ordering is merely a heuristic. 341b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const { 342b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = Start(); 343b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition other_start = other->Start(); 344b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start.Value() == other_start.Value()) { 345b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* pos = first_pos(); 346b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos == NULL) return false; 347b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* other_pos = other->first_pos(); 348b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (other_pos == NULL) return true; 349b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos->pos().Value() < other_pos->pos().Value(); 350b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 351b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return start.Value() < other_start.Value(); 352b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 353b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 354b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 355b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::ShortenTo(LifetimePosition start) { 356b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Shorten live range %d to [%d\n", id_, start.Value()); 357b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(first_interval_ != NULL); 358b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(first_interval_->start().Value() <= start.Value()); 359b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(start.Value() < first_interval_->end().Value()); 360b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->set_start(start); 361b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 362b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 363b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3643ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::EnsureInterval(LifetimePosition start, 3653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LifetimePosition end, 3663ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 367b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Ensure live range %d in interval [%d %d[\n", 368b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 369b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 370b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 371b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition new_end = end; 372b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (first_interval_ != NULL && 373b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->start().Value() <= end.Value()) { 374b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_interval_->end().Value() > end.Value()) { 375b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch new_end = first_interval_->end(); 376b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 377b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = first_interval_->next(); 378b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 379b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* new_interval = new(zone) UseInterval(start, new_end); 381b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch new_interval->next_ = first_interval_; 382b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = new_interval; 383b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (new_interval->next() == NULL) { 384b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = new_interval; 385b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 386b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 387b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 388b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3893ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::AddUseInterval(LifetimePosition start, 3903ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LifetimePosition end, 3913ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 392b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Add to live range %d interval [%d %d[\n", 393b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 394b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 395b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 396b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_interval_ == NULL) { 3973ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* interval = new(zone) UseInterval(start, end); 398b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = interval; 399b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = interval; 400b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 401b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (end.Value() == first_interval_->start().Value()) { 402b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->set_start(start); 403b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (end.Value() < first_interval_->start().Value()) { 4043ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* interval = new(zone) UseInterval(start, end); 405b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval->set_next(first_interval_); 406b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = interval; 407b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 408b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Order of instruction's processing (see ProcessInstructions) guarantees 409b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // that each new use interval either precedes or intersects with 410b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // last added interval. 411b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(start.Value() < first_interval_->end().Value()); 412b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->start_ = Min(start, first_interval_->start_); 413b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->end_ = Max(end, first_interval_->end_); 414b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 415b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 416b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 417b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 418b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 419b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid LiveRange::AddUsePosition(LifetimePosition pos, 420b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* operand, 421b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* hint, 422b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone) { 423b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Add to live range %d use position %d\n", 424b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 425b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos.Value()); 426b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* use_pos = new(zone) UsePosition(pos, operand, hint); 427b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* prev_hint = NULL; 428b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* prev = NULL; 429b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* current = first_pos_; 430b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current != NULL && current->pos().Value() < pos.Value()) { 431b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch prev_hint = current->HasHint() ? current : prev_hint; 432b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch prev = current; 433b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current = current->next(); 434b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 435b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 436b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (prev == NULL) { 437b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->set_next(first_pos_); 438b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_pos_ = use_pos; 439b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 440b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->next_ = prev->next_; 441b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch prev->next_ = use_pos; 442b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 443b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 444b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (prev_hint == NULL && use_pos->HasHint()) { 445b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current_hint_operand_ = hint; 446b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 447b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 448b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 449b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 4503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::ConvertOperands(Zone* zone) { 4513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* op = CreateAssignedOperand(zone); 452b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = first_pos(); 453b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_pos != NULL) { 454b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Start().Value() <= use_pos->pos().Value() && 455b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->pos().Value() <= End().Value()); 456b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 457b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos->HasOperand()) { 458b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(op->IsRegister() || op->IsDoubleRegister() || 459b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch !use_pos->RequiresRegister()); 460b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->operand()->ConvertTo(op->kind(), op->index()); 461b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 462b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = use_pos->next(); 463b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 464b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 465b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 466b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 467b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::CanCover(LifetimePosition position) const { 468b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (IsEmpty()) return false; 469b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return Start().Value() <= position.Value() && 470b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch position.Value() < End().Value(); 471b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 472b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 473b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 474b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::Covers(LifetimePosition position) { 475b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!CanCover(position)) return false; 476b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* start_search = FirstSearchIntervalForPosition(position); 477b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (UseInterval* interval = start_search; 478b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval != NULL; 479b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval = interval->next()) { 480b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(interval->next() == NULL || 481b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval->next()->start().Value() >= interval->start().Value()); 482b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AdvanceLastProcessedMarker(interval, position); 483b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (interval->Contains(position)) return true; 484b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (interval->start().Value() > position.Value()) return false; 485b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 486b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 487b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 488b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 489b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 490b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLifetimePosition LiveRange::FirstIntersection(LiveRange* other) { 491b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* b = other->first_interval(); 492b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (b == NULL) return LifetimePosition::Invalid(); 493b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition advance_last_processed_up_to = b->start(); 494b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* a = FirstSearchIntervalForPosition(b->start()); 495b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (a != NULL && b != NULL) { 496b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->start().Value() > other->End().Value()) break; 497b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (b->start().Value() > End().Value()) break; 498b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition cur_intersection = a->Intersect(b); 499b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_intersection.IsValid()) { 500b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return cur_intersection; 501b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 502b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->start().Value() < b->start().Value()) { 503b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch a = a->next(); 504b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a == NULL || a->start().Value() > other->End().Value()) break; 505b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AdvanceLastProcessedMarker(a, advance_last_processed_up_to); 506b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 507b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch b = b->next(); 508b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 509b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 510b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition::Invalid(); 511b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 512b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 513b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 51444f0eee88ff00398ff7f715fab053374d808c90dSteve BlockLAllocator::LAllocator(int num_values, HGraph* graph) 515014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : chunk_(NULL), 516b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_in_sets_(graph->blocks()->length(), zone()), 517b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_ranges_(num_values * 2, zone()), 51844f0eee88ff00398ff7f715fab053374d808c90dSteve Block fixed_live_ranges_(NULL), 51944f0eee88ff00398ff7f715fab053374d808c90dSteve Block fixed_double_live_ranges_(NULL), 520b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unhandled_live_ranges_(num_values * 2, zone()), 521b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch active_live_ranges_(8, zone()), 522b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inactive_live_ranges_(8, zone()), 523b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch reusable_slots_(8, zone()), 52444f0eee88ff00398ff7f715fab053374d808c90dSteve Block next_virtual_register_(num_values), 52544f0eee88ff00398ff7f715fab053374d808c90dSteve Block first_artificial_register_(num_values), 526b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch mode_(UNALLOCATED_REGISTERS), 52744f0eee88ff00398ff7f715fab053374d808c90dSteve Block num_registers_(-1), 52844f0eee88ff00398ff7f715fab053374d808c90dSteve Block graph_(graph), 5293ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch has_osr_entry_(false), 530b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocation_ok_(true) {} 53144f0eee88ff00398ff7f715fab053374d808c90dSteve Block 53244f0eee88ff00398ff7f715fab053374d808c90dSteve Block 533b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::InitializeLivenessAnalysis() { 534b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Initialize the live_in sets for each block to NULL. 5351e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block int block_count = graph_->blocks()->length(); 536b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_in_sets_.Initialize(block_count, zone()); 537b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_in_sets_.AddBlock(NULL, block_count, zone()); 538b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 539b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 540b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 541b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochBitVector* LAllocator::ComputeLiveOut(HBasicBlock* block) { 542b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Compute live out for the given block, except not including backward 543b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // successor edges. 544b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BitVector* live_out = new(zone()) BitVector(next_virtual_register_, zone()); 545b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 546b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process all successor blocks. 5473fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) { 548b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Add values live on entry to the successor. Note the successor's 549b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // live_in will not be computed yet for backwards edges. 5503fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch HBasicBlock* successor = it.Current(); 551b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live_in = live_in_sets_[successor->block_id()]; 552b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (live_in != NULL) live_out->Union(*live_in); 553b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 554b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All phi input operands corresponding to this successor edge are live 555b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // out from this block. 556b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = successor->PredecessorIndexOf(block); 557b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<HPhi*>* phis = successor->phis(); 558b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < phis->length(); ++i) { 559b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = phis->at(i); 560b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!phi->OperandAt(index)->IsConstant()) { 561b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_out->Add(phi->OperandAt(index)->id()); 562b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 563b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 564b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 565b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 566b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return live_out; 567b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 568b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 569b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 570b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddInitialIntervals(HBasicBlock* block, 571b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live_out) { 572b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Add an interval that includes the entire block to the live range for 573b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // each live_out value. 574b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = LifetimePosition::FromInstructionIndex( 575b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 576b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end = LifetimePosition::FromInstructionIndex( 577b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->last_instruction_index()).NextInstruction(); 578b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live_out); 579b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 580b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 581b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand_index); 582b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUseInterval(start, end, zone()); 583b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 584b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 585b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 586b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 587b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 588b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochint LAllocator::FixedDoubleLiveRangeID(int index) { 589014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return -index - 1 - Register::kNumRegisters; 590b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 591b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 592b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 593b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLOperand* LAllocator::AllocateFixed(LUnallocated* operand, 594b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int pos, 595b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool is_tagged) { 596b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Allocating fixed reg for op %d\n", operand->virtual_register()); 597b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(operand->HasFixedPolicy()); 598b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (operand->HasFixedSlotPolicy()) { 599b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch operand->ConvertTo(LOperand::STACK_SLOT, operand->fixed_slot_index()); 600b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (operand->HasFixedRegisterPolicy()) { 601b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int reg_index = operand->fixed_register_index(); 602b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand->ConvertTo(LOperand::REGISTER, reg_index); 603b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (operand->HasFixedDoubleRegisterPolicy()) { 604b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int reg_index = operand->fixed_register_index(); 605b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand->ConvertTo(LOperand::DOUBLE_REGISTER, reg_index); 606b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 607b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UNREACHABLE(); 608b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 609b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (is_tagged) { 610b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Fixed reg is tagged at %d\n", pos); 6111e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = InstructionAt(pos); 612b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (instr->HasPointerMap()) { 613b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->pointer_map()->RecordPointer(operand, chunk()->zone()); 614b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 615b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 616b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return operand; 617b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 618b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 619b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 620b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::FixedLiveRangeFor(int index) { 621014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(index < Register::kNumRegisters); 622b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* result = fixed_live_ranges_[index]; 623b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (result == NULL) { 624b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = new(zone()) LiveRange(FixedLiveRangeID(index), chunk()->zone()); 625b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(result->IsFixed()); 626b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result->kind_ = GENERAL_REGISTERS; 627b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(result, index); 628b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch fixed_live_ranges_[index] = result; 629b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 630b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 631b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 632b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 633b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 634b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::FixedDoubleLiveRangeFor(int index) { 635014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(index < DoubleRegister::kMaxNumRegisters); 636b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* result = fixed_double_live_ranges_[index]; 637b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (result == NULL) { 638b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = new(zone()) LiveRange(FixedDoubleLiveRangeID(index), 639b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 640b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(result->IsFixed()); 641b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result->kind_ = DOUBLE_REGISTERS; 642b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(result, index); 643b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch fixed_double_live_ranges_[index] = result; 644b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 645b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 646b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 647b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 64844f0eee88ff00398ff7f715fab053374d808c90dSteve Block 649b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::LiveRangeFor(int index) { 650b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (index >= live_ranges_.length()) { 651b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_ranges_.AddBlock(NULL, index - live_ranges_.length() + 1, zone()); 652b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 653b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* result = live_ranges_[index]; 654b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (result == NULL) { 655b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = new(zone()) LiveRange(index, chunk()->zone()); 656b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_ranges_[index] = result; 657b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 658b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 659b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 660b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 661b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 6621e0659c275bb392c045087af4f6b0d7565cb3d77Steve BlockLGap* LAllocator::GetLastGap(HBasicBlock* block) { 663b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int last_instruction = block->last_instruction_index(); 664b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = chunk_->NearestGapPos(last_instruction); 6651e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return GapAt(index); 666b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 667b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 668b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 669b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochHPhi* LAllocator::LookupPhi(LOperand* operand) const { 670b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!operand->IsUnallocated()) return NULL; 6713ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int index = LUnallocated::cast(operand)->virtual_register(); 6721e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block HValue* instr = graph_->LookupValue(index); 673b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (instr != NULL && instr->IsPhi()) { 674b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return HPhi::cast(instr); 675b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 676b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 677b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 678b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 679b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 680b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::LiveRangeFor(LOperand* operand) { 681b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (operand->IsUnallocated()) { 682b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LiveRangeFor(LUnallocated::cast(operand)->virtual_register()); 683b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (operand->IsRegister()) { 684b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return FixedLiveRangeFor(operand->index()); 685b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (operand->IsDoubleRegister()) { 686b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return FixedDoubleLiveRangeFor(operand->index()); 687b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 688b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 689b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 690b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 691b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 692b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 693b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Define(LifetimePosition position, 694b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand, 695b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint) { 696b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand); 697b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL) return; 698b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 699b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsEmpty() || range->Start().Value() > position.Value()) { 700b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Can happen if there is a definition without use. 701b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUseInterval(position, position.NextInstruction(), zone()); 702b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUsePosition(position.NextInstruction(), NULL, NULL, zone()); 703b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 704b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->ShortenTo(position); 705b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 706b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 707b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (operand->IsUnallocated()) { 708b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* unalloc_operand = LUnallocated::cast(operand); 709b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUsePosition(position, unalloc_operand, hint, zone()); 710b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 711b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 712b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 713b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 714b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Use(LifetimePosition block_start, 715b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position, 716b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand, 717b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint) { 718b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand); 719b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL) return; 720b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (operand->IsUnallocated()) { 721b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* unalloc_operand = LUnallocated::cast(operand); 722b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUsePosition(position, unalloc_operand, hint, zone()); 723b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 724b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->AddUseInterval(block_start, position, zone()); 725b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 726b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 727b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 728b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddConstraintsGapMove(int index, 729b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* from, 730b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* to) { 7311e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(index); 732b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, 733b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 734b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (from->IsUnallocated()) { 735b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LMoveOperands>* move_operands = move->move_operands(); 736b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < move_operands->length(); ++i) { 737b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LMoveOperands cur = move_operands->at(i); 738b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* cur_to = cur.destination(); 739b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_to->IsUnallocated()) { 7403ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (LUnallocated::cast(cur_to)->virtual_register() == 7413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated::cast(from)->virtual_register()) { 742b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch move->AddMove(cur.source(), to, chunk()->zone()); 743b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 744b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 745b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 746b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 747b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 748b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch move->AddMove(from, to, chunk()->zone()); 749b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 750b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 751b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 752b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::MeetRegisterConstraints(HBasicBlock* block) { 753b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int start = block->first_instruction_index(); 754b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int end = block->last_instruction_index(); 755b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (start == -1) return; 756b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = start; i <= end; ++i) { 7571e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(i)) { 7581e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = NULL; 7591e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* prev_instr = NULL; 7601e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (i < end) instr = InstructionAt(i + 1); 7611e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (i > start) prev_instr = InstructionAt(i - 1); 7621e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block MeetConstraintsBetween(prev_instr, instr, i); 7633ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 764b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 765b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 766b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 767b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 768b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 7691e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockvoid LAllocator::MeetConstraintsBetween(LInstruction* first, 7701e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* second, 771b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int gap_index) { 772b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle fixed temporaries. 773b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first != NULL) { 7743fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (TempIterator it(first); !it.Done(); it.Advance()) { 7753fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LUnallocated* temp = LUnallocated::cast(it.Current()); 776b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp->HasFixedPolicy()) { 777b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateFixed(temp, gap_index - 1, false); 778b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 779b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 780b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 781b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 782b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle fixed output operand. 783b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first != NULL && first->Output() != NULL) { 784b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* first_output = LUnallocated::cast(first->Output()); 7853ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* range = LiveRangeFor(first_output->virtual_register()); 786b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool assigned = false; 787b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_output->HasFixedPolicy()) { 788b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* output_copy = first_output->CopyUnconstrained( 789b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 7903ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool is_tagged = HasTaggedValue(first_output->virtual_register()); 791b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateFixed(first_output, gap_index, is_tagged); 792b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 793b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This value is produced on the stack, we never need to spill it. 794b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_output->IsStackSlot()) { 795b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->SetSpillOperand(first_output); 796b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->SetSpillStartIndex(gap_index - 1); 797b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch assigned = true; 798b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 799b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch chunk_->AddGapMove(gap_index, first_output, output_copy); 800b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 801b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 802b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!assigned) { 803b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->SetSpillStartIndex(gap_index); 804b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 805b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This move to spill operand is not a real use. Liveness analysis 806b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // and splitting of live ranges do not account for it. 807b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Thus it should be inserted to a lifetime position corresponding to 808b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the instruction end. 8091e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(gap_index); 810b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::BEFORE, 811b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 812b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch move->AddMove(first_output, range->GetSpillOperand(), 813b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 814b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 815b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 816b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 817b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle fixed input operands of second instruction. 818b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second != NULL) { 8193fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (UseIterator it(second); !it.Done(); it.Advance()) { 8203fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LUnallocated* cur_input = LUnallocated::cast(it.Current()); 821b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_input->HasFixedPolicy()) { 822b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* input_copy = cur_input->CopyUnconstrained( 823b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 8243ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool is_tagged = HasTaggedValue(cur_input->virtual_register()); 825b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateFixed(cur_input, gap_index + 1, is_tagged); 826b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddConstraintsGapMove(gap_index, input_copy, cur_input); 827b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (cur_input->HasWritableRegisterPolicy()) { 828b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch // The live range of writable input registers always goes until the end 829b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch // of the instruction. 830b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!cur_input->IsUsedAtStart()); 831b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch 832b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* input_copy = cur_input->CopyUnconstrained( 833b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 834b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int vreg = GetVirtualRegister(); 8353ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 836b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch cur_input->set_virtual_register(vreg); 8379fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 8389fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (RequiredRegisterKind(input_copy->virtual_register()) == 8399fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block DOUBLE_REGISTERS) { 8409fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block double_artificial_registers_.Add( 8413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch cur_input->virtual_register() - first_artificial_register_, 842b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch zone()); 8439fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 8449fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 845b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddConstraintsGapMove(gap_index, input_copy, cur_input); 846b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 847b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 848b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 849b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 850b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Handle "output same as input" for second instruction. 851b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second != NULL && second->Output() != NULL) { 852b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* second_output = LUnallocated::cast(second->Output()); 853b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second_output->HasSameAsInputPolicy()) { 8541e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LUnallocated* cur_input = LUnallocated::cast(second->FirstInput()); 8553ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int output_vreg = second_output->virtual_register(); 8563ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int input_vreg = cur_input->virtual_register(); 857b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 858b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* input_copy = cur_input->CopyUnconstrained( 859b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 860b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_input->set_virtual_register(second_output->virtual_register()); 861b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddConstraintsGapMove(gap_index, input_copy, cur_input); 862b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 863b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (HasTaggedValue(input_vreg) && !HasTaggedValue(output_vreg)) { 864b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = gap_index + 1; 8651e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = InstructionAt(index); 866b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (instr->HasPointerMap()) { 867b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->pointer_map()->RecordPointer(input_copy, chunk()->zone()); 868b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 869b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (!HasTaggedValue(input_vreg) && HasTaggedValue(output_vreg)) { 870b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The input is assumed to immediately have a tagged representation, 871b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // before the pointer map can be used. I.e. the pointer map at the 872b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // instruction will include the output operand (whose value at the 873b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // beginning of the instruction is equal to the input operand). If 874b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // this is not desired, then the pointer map at this instruction needs 875b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // to be adjusted manually. 876b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 877b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 878b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 879b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 880b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 881b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 882b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) { 883b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int block_start = block->first_instruction_index(); 884b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = block->last_instruction_index(); 885b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 886b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition block_start_position = 887b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(block_start); 888b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 889b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (index >= block_start) { 890b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition curr_position = 891b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(index); 892b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 8931e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(index)) { 894b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We have a gap at this position. 8951e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(index); 896b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, 897b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 898b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LMoveOperands>* move_operands = move->move_operands(); 899b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < move_operands->length(); ++i) { 900b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LMoveOperands* cur = &move_operands->at(i); 901b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur->IsIgnored()) continue; 902b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* from = cur->source(); 903b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* to = cur->destination(); 904b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = LookupPhi(to); 905b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint = to; 906b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (phi != NULL) { 907b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This is a phi resolving move. 908b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!phi->block()->IsLoopHeader()) { 909b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch hint = LiveRangeFor(phi->id())->current_hint_operand(); 910b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 911b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 912b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to->IsUnallocated()) { 9133ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (live->Contains(LUnallocated::cast(to)->virtual_register())) { 914b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, to, from); 9153ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Remove(LUnallocated::cast(to)->virtual_register()); 916b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 917b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur->Eliminate(); 918b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 919b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 920b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 921b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, to, from); 922b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 923b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 924b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Use(block_start_position, curr_position, from, hint); 925b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (from->IsUnallocated()) { 9263ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Add(LUnallocated::cast(from)->virtual_register()); 927b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 928b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 929b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 930b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsGapAt(index)); 9311e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LInstruction* instr = InstructionAt(index); 932b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9331e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (instr != NULL) { 9341e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LOperand* output = instr->Output(); 935b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (output != NULL) { 9363ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (output->IsUnallocated()) { 9373ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Remove(LUnallocated::cast(output)->virtual_register()); 9383ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 939b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, output, NULL); 940b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 941b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 942b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->ClobbersRegisters()) { 943014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < Register::kNumRegisters; ++i) { 944014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (Register::from_code(i).IsAllocatable()) { 945014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (output == NULL || !output->IsRegister() || 946014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch output->index() != i) { 947014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LiveRange* range = FixedLiveRangeFor(i); 948014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch range->AddUseInterval(curr_position, 949014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch curr_position.InstructionEnd(), zone()); 950014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 951b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 952b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 953086aeeaae12517475c22695a200be45495516549Ben Murdoch } 954086aeeaae12517475c22695a200be45495516549Ben Murdoch 955b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->ClobbersDoubleRegisters(isolate())) { 956014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < DoubleRegister::kMaxNumRegisters; ++i) { 957014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (DoubleRegister::from_code(i).IsAllocatable()) { 958014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (output == NULL || !output->IsDoubleRegister() || 959014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch output->index() != i) { 960014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LiveRange* range = FixedDoubleLiveRangeFor(i); 961014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch range->AddUseInterval(curr_position, 962014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch curr_position.InstructionEnd(), zone()); 963014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 964b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 965b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 966b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 967b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9683fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (UseIterator it(instr); !it.Done(); it.Advance()) { 9693fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LOperand* input = it.Current(); 970b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 971b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition use_pos; 972b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (input->IsUnallocated() && 973b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated::cast(input)->IsUsedAtStart()) { 974b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = curr_position; 975b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 976b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = curr_position.InstructionEnd(); 977b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 978b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 979b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Use(block_start_position, use_pos, input, NULL); 9803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (input->IsUnallocated()) { 9813ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Add(LUnallocated::cast(input)->virtual_register()); 9823ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 983b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 984b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9853fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (TempIterator it(instr); !it.Done(); it.Advance()) { 9863fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LOperand* temp = it.Current(); 987b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->ClobbersTemps()) { 988b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp->IsRegister()) continue; 989b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp->IsUnallocated()) { 990b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* temp_unalloc = LUnallocated::cast(temp); 991b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp_unalloc->HasFixedPolicy()) { 992b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 993b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 994b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 995b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 996b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Use(block_start_position, curr_position.InstructionEnd(), temp, NULL); 997b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, temp, NULL); 998b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 999b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (temp->IsUnallocated()) { 1000b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* temp_unalloc = LUnallocated::cast(temp); 1001b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (temp_unalloc->HasDoubleRegisterPolicy()) { 1002b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch double_artificial_registers_.Add( 1003b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch temp_unalloc->virtual_register() - first_artificial_register_, 1004b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch zone()); 1005b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1006b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1007b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1008b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1009b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1010b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1011b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch index = index - 1; 1012b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1013b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1014b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1015b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1016b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolvePhis(HBasicBlock* block) { 1017b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<HPhi*>* phis = block->phis(); 1018b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < phis->length(); ++i) { 1019b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = phis->at(i); 1020b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* phi_operand = 1021b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new (chunk()->zone()) LUnallocated(LUnallocated::NONE); 1022b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch phi_operand->set_virtual_register(phi->id()); 1023b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int j = 0; j < phi->OperandCount(); ++j) { 1024b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HValue* op = phi->OperandAt(j); 1025b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand = NULL; 1026b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (op->IsConstant() && op->EmitAtUses()) { 1027b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HConstant* constant = HConstant::cast(op); 1028b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand = chunk_->DefineConstantOperand(constant); 1029b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1030b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!op->EmitAtUses()); 1031b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* unalloc = 1032b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new(chunk()->zone()) LUnallocated(LUnallocated::ANY); 1033b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unalloc->set_virtual_register(op->id()); 1034b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand = unalloc; 1035b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1036b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* cur_block = block->predecessors()->at(j); 1037b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The gap move must be added without any special processing as in 1038b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the AddConstraintsGapMove. 1039b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch chunk_->AddGapMove(cur_block->last_instruction_index() - 1, 1040b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand, 1041b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch phi_operand); 1042257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 1043257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // We are going to insert a move before the branch instruction. 1044257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // Some branch instructions (e.g. loops' back edges) 1045257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // can potentially cause a GC so they have a pointer map. 1046257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // By inserting a move we essentially create a copy of a 1047257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // value which is invisible to PopulatePointerMaps(), because we store 1048257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // it into a location different from the operand of a live range 1049257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // covering a branch instruction. 1050257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // Thus we need to manually record a pointer. 10513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LInstruction* branch = 10523ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch InstructionAt(cur_block->last_instruction_index()); 10533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (branch->HasPointerMap()) { 1054b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (phi->representation().IsTagged() && !phi->type().IsSmi()) { 1055b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch branch->pointer_map()->RecordPointer(phi_operand, chunk()->zone()); 10563ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } else if (!phi->representation().IsDouble()) { 1057b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch branch->pointer_map()->RecordUntagged(phi_operand, chunk()->zone()); 1058257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch } 1059257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch } 1060b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1061b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1062b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* live_range = LiveRangeFor(phi->id()); 1063b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LLabel* label = chunk_->GetLabel(phi->block()->block_id()); 1064b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch label->GetOrCreateParallelMove(LGap::START, chunk()->zone())-> 1065b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AddMove(phi_operand, live_range->GetSpillOperand(), chunk()->zone()); 1066b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_range->SetSpillStartIndex(phi->block()->first_instruction_index()); 1067b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1068b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1069b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1070b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 10713ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochbool LAllocator::Allocate(LChunk* chunk) { 1072b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(chunk_ == NULL); 1073b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk_ = static_cast<LPlatformChunk*>(chunk); 1074b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch assigned_registers_ = 1075014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch new (chunk->zone()) BitVector(Register::kNumRegisters, chunk->zone()); 1076014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch assigned_double_registers_ = new (chunk->zone()) 1077014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BitVector(DoubleRegister::kMaxNumRegisters, chunk->zone()); 1078b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch MeetRegisterConstraints(); 10793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1080b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolvePhis(); 1081b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BuildLiveRanges(); 1082b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateGeneralRegisters(); 10833ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1084b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateDoubleRegisters(); 10853ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1086b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PopulatePointerMaps(); 1087b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ConnectRanges(); 1088b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolveControlFlow(); 10893ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return true; 1090b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1091b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1092b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1093b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::MeetRegisterConstraints() { 1094b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Register constraints", this); 10951e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1096b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < blocks->length(); ++i) { 1097b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(i); 1098b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch MeetRegisterConstraints(block); 10993ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 1100b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1101b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1102b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1103b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1104b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolvePhis() { 1105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Resolve phis", this); 1106b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1107b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process the blocks in reverse order. 11081e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1109b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { 1110b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(block_id); 1111b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolvePhis(block); 1112b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1113b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1114b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1115b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1116b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolveControlFlow(LiveRange* range, 1117b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block, 1118b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* pred) { 1119b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pred_end = 11201e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LifetimePosition::FromInstructionIndex(pred->last_instruction_index()); 1121b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition cur_start = 1122b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(block->first_instruction_index()); 1123b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* pred_cover = NULL; 1124b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_cover = NULL; 1125b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_range = range; 1126b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (cur_range != NULL && (cur_cover == NULL || pred_cover == NULL)) { 1127b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_range->CanCover(cur_start)) { 1128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(cur_cover == NULL); 1129b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_cover = cur_range; 1130b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1131b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_range->CanCover(pred_end)) { 1132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pred_cover == NULL); 1133b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pred_cover = cur_range; 1134b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1135b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_range = cur_range->next(); 1136b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1137b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1138b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_cover->IsSpilled()) return; 1139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pred_cover != NULL && cur_cover != NULL); 1140b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pred_cover != cur_cover) { 1141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* pred_op = pred_cover->CreateAssignedOperand(chunk()->zone()); 1142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* cur_op = cur_cover->CreateAssignedOperand(chunk()->zone()); 1143b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!pred_op->Equals(cur_op)) { 1144b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LGap* gap = NULL; 1145b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block->predecessors()->length() == 1) { 11461e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block gap = GapAt(block->first_instruction_index()); 1147b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pred->end()->SecondSuccessor() == NULL); 1149b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch gap = GetLastGap(pred); 1150e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch 1151e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // We are going to insert a move before the branch instruction. 1152e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // Some branch instructions (e.g. loops' back edges) 1153e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // can potentially cause a GC so they have a pointer map. 1154257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // By inserting a move we essentially create a copy of a 1155e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // value which is invisible to PopulatePointerMaps(), because we store 1156e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // it into a location different from the operand of a live range 1157e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // covering a branch instruction. 1158e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch // Thus we need to manually record a pointer. 11593ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LInstruction* branch = InstructionAt(pred->last_instruction_index()); 11603ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (branch->HasPointerMap()) { 11613ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (HasTaggedValue(range->id())) { 1162b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch branch->pointer_map()->RecordPointer(cur_op, chunk()->zone()); 11633ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } else if (!cur_op->IsDoubleStackSlot() && 11643ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch !cur_op->IsDoubleRegister()) { 11653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch branch->pointer_map()->RemovePointer(cur_op); 1166e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch } 1167e0cee9b3ed82e2391fd85d118aeaa4ea361c687dBen Murdoch } 1168b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch gap->GetOrCreateParallelMove( 1170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LGap::START, chunk()->zone())->AddMove(pred_op, cur_op, 1171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 1172b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1173b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1174b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1175b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1176b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1177b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLParallelMove* LAllocator::GetConnectingParallelMove(LifetimePosition pos) { 1178b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = pos.InstructionIndex(); 11791e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(index)) { 11801e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(index); 1181b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return gap->GetOrCreateParallelMove( 1182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch pos.IsInstructionStart() ? LGap::START : LGap::END, chunk()->zone()); 1183b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1184b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int gap_pos = pos.IsInstructionStart() ? (index - 1) : (index + 1); 11851e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return GapAt(gap_pos)->GetOrCreateParallelMove( 1186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch (gap_pos < index) ? LGap::AFTER : LGap::BEFORE, chunk()->zone()); 1187b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1188b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1189b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1190b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochHBasicBlock* LAllocator::GetBlock(LifetimePosition pos) { 11911e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex())); 1192b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return gap->block(); 1193b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1194b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1195b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1196b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ConnectRanges() { 1197b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Connect ranges", this); 1198b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges()->length(); ++i) { 1199b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* first_range = live_ranges()->at(i); 1200b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_range == NULL || first_range->parent() != NULL) continue; 1201b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1202b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* second_range = first_range->next(); 1203b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (second_range != NULL) { 1204b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos = second_range->Start(); 1205b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1206b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!second_range->IsSpilled()) { 1207b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Add gap move if the two live ranges touch and there is no block 1208b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // boundary. 1209b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_range->End().Value() == pos.Value()) { 1210b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool should_insert = true; 1211b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (IsBlockBoundary(pos)) { 1212b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch should_insert = CanEagerlyResolveControlFlow(GetBlock(pos)); 1213b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1214b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (should_insert) { 1215b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LParallelMove* move = GetConnectingParallelMove(pos); 1216b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* prev_operand = first_range->CreateAssignedOperand( 1217b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 1218b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* cur_operand = second_range->CreateAssignedOperand( 1219b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 1220b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch move->AddMove(prev_operand, cur_operand, 1221b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 1222b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1223b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1224b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1225b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1226b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_range = second_range; 1227b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch second_range = second_range->next(); 1228b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1229b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1230b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1231b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1232b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1233b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::CanEagerlyResolveControlFlow(HBasicBlock* block) const { 1234b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block->predecessors()->length() != 1) return false; 1235b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return block->predecessors()->first()->block_id() == block->block_id() - 1; 1236b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1237b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1238b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1239b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolveControlFlow() { 1240b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Resolve control flow", this); 12411e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1242b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int block_id = 1; block_id < blocks->length(); ++block_id) { 1243b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(block_id); 1244b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (CanEagerlyResolveControlFlow(block)) continue; 1245b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live = live_in_sets_[block->block_id()]; 1246b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live); 1247b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 1248b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 1249b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < block->predecessors()->length(); ++i) { 1250b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* cur = block->predecessors()->at(i); 1251b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_range = LiveRangeFor(operand_index); 1252b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ResolveControlFlow(cur_range, block, cur); 1253b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1254b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 1255b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1256b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1257b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1258b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1259b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1260b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::BuildLiveRanges() { 1261b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Build live ranges", this); 1262b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InitializeLivenessAnalysis(); 1263b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process the blocks in reverse order. 12641e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1265b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { 1266b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = blocks->at(block_id); 1267b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector* live = ComputeLiveOut(block); 1268b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Initially consider all live_out values live for the entire block. We 1269b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // will shorten these intervals if necessary. 1270b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddInitialIntervals(block, live); 1271b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1272b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Process the instructions in reverse order, generating and killing 1273b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // live values. 1274b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ProcessInstructions(block, live); 1275b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All phi output operands are killed by this block. 1276b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<HPhi*>* phis = block->phis(); 1277b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < phis->length(); ++i) { 1278b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The live range interval already ends at the first instruction of the 1279b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // block. 1280b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = phis->at(i); 1281b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live->Remove(phi->id()); 1282b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1283b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* hint = NULL; 1284b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* phi_operand = NULL; 1285b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LGap* gap = GetLastGap(phi->block()->predecessors()->at(0)); 1286b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, 1287b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk()->zone()); 1288b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int j = 0; j < move->move_operands()->length(); ++j) { 1289b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch LOperand* to = move->move_operands()->at(j).destination(); 12903ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (to->IsUnallocated() && 12913ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated::cast(to)->virtual_register() == phi->id()) { 1292b8e0da25ee8efac3bb05cd6b2730aafbd96119f4Ben Murdoch hint = move->move_operands()->at(j).source(); 1293b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch phi_operand = to; 1294b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch break; 1295b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1296b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1297b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(hint != NULL); 1298b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1299b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition block_start = LifetimePosition::FromInstructionIndex( 1300b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 1301b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(block_start, phi_operand, hint); 1302b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1303b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1304b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Now live is live_in for this block except not including values live 1305b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // out on backward successor edges. 1306b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_in_sets_[block_id] = live; 1307b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1308b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If this block is a loop header go back and patch up the necessary 1309b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // predecessor blocks. 1310b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block->IsLoopHeader()) { 1311b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // TODO(kmillikin): Need to be able to get the last block of the loop 1312b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // in the loop information. Add a live range stretching from the first 1313b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // loop instruction to the last for each value live on entry to the 1314b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // header. 1315b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* back_edge = block->loop_information()->GetLastBackEdge(); 1316b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live); 1317b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = LifetimePosition::FromInstructionIndex( 1318b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 1319b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end = LifetimePosition::FromInstructionIndex( 13201e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block back_edge->last_instruction_index()).NextInstruction(); 1321b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 1322b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 1323b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand_index); 1324b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->EnsureInterval(start, end, zone()); 1325b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 1326b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1327b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1328b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = block->block_id() + 1; i <= back_edge->block_id(); ++i) { 1329b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_in_sets_[i]->Union(*live); 1330b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1331b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1332b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1333b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 1334b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block_id == 0) { 1335b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch BitVector::Iterator iterator(live); 1336b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool found = false; 1337b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!iterator.Done()) { 1338b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch found = true; 1339b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int operand_index = iterator.Current(); 1340014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch { 1341b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AllowHandleDereference allow_deref; 1342014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PrintF("Function: %s\n", chunk_->info()->GetDebugName().get()); 1343b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1344b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PrintF("Value %d used before first definition!\n", operand_index); 1345b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand_index); 1346b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PrintF("First use is at %d\n", range->first_pos()->pos().Value()); 1347b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 1348b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1349b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!found); 1350b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1351b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 1352b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1353b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1354b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < live_ranges_.length(); ++i) { 1355b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (live_ranges_[i] != NULL) { 1356b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_ranges_[i]->kind_ = RequiredRegisterKind(live_ranges_[i]->id()); 1357b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1358b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1359b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1360b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1361b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1362b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::SafePointsAreInOrder() const { 1363b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); 1364b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = 0; 1365b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < pointer_maps->length(); ++i) { 1366b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(i); 1367b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point > map->lithium_position()) return false; 1368b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point = map->lithium_position(); 1369b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1370b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1371b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1372b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1373b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1374b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::PopulatePointerMaps() { 1375b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Populate pointer maps", this); 1376b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); 1377b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1378b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(SafePointsAreInOrder()); 1379b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1380b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Iterate over all safe point positions and record a pointer 1381b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // for all spilled live ranges at this point. 1382b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int first_safe_point_index = 0; 1383b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int last_range_start = 0; 1384b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { 1385b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = live_ranges()->at(range_idx); 1386b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL) continue; 1387b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Iterate over the first parts of multi-part live ranges. 1388b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->parent() != NULL) continue; 1389b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Skip non-pointer values. 1390b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!HasTaggedValue(range->id())) continue; 1391b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Skip empty live ranges. 1392b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsEmpty()) continue; 1393b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1394b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the extent of the range and its children. 1395b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int start = range->Start().InstructionIndex(); 1396b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int end = 0; 1397b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (LiveRange* cur = range; cur != NULL; cur = cur->next()) { 1398b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition this_end = cur->End(); 1399b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (this_end.InstructionIndex() > end) end = this_end.InstructionIndex(); 1400b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(cur->Start().InstructionIndex() >= start); 1401b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1402b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1403b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Most of the ranges are in order, but not all. Keep an eye on when 1404b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // they step backwards and reset the first_safe_point_index so we don't 1405b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // miss any safe points. 1406b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start < last_range_start) { 1407b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_safe_point_index = 0; 1408b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1409b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_range_start = start; 1410b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1411b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Step across all the safe points that are before the start of this range, 1412b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // recording how far we step in order to save doing this for the next range. 1413b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (first_safe_point_index < pointer_maps->length()) { 1414b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(first_safe_point_index); 1415b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = map->lithium_position(); 1416b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point >= start) break; 1417b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_safe_point_index++; 1418b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1419b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1420b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Step through the safe points to see whether they are in the range. 1421b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int safe_point_index = first_safe_point_index; 1422b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point_index < pointer_maps->length(); 1423b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ++safe_point_index) { 1424b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(safe_point_index); 1425b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = map->lithium_position(); 1426b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1427b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The safe points are sorted so we can stop searching here. 1428b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point - 1 > end) break; 1429b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1430b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Advance to the next active range that covers the current 1431b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // safe point position. 1432b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition safe_point_pos = 1433b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(safe_point); 1434b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur = range; 1435b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (cur != NULL && !cur->Covers(safe_point_pos)) { 1436b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur = cur->next(); 1437b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1438b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur == NULL) continue; 1439b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1440b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Check if the live range is spilled and the safe point is after 1441b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the spill position. 1442b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->HasAllocatedSpillOperand() && 1443b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point >= range->spill_start_index()) { 1444b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Pointer for range %d (spilled at %d) at safe point %d\n", 1445b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->id(), range->spill_start_index(), safe_point); 1446b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch map->RecordPointer(range->GetSpillOperand(), chunk()->zone()); 1447b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1448b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1449b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!cur->IsSpilled()) { 1450b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Pointer in register for range %d (start at %d) " 1451b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch "at safe point %d\n", 1452b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur->id(), cur->Start().Value(), safe_point); 1453b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* operand = cur->CreateAssignedOperand(chunk()->zone()); 1454b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!operand->IsStackSlot()); 1455b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch map->RecordPointer(operand, chunk()->zone()); 1456b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1457b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1458b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1459b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1460b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1461b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1462b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateGeneralRegisters() { 1463b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Allocate general registers", this); 1464014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch num_registers_ = 1465014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterConfiguration::ArchDefault(RegisterConfiguration::CRANKSHAFT) 1466014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ->num_allocatable_general_registers(); 1467014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch allocatable_register_codes_ = 1468014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterConfiguration::ArchDefault(RegisterConfiguration::CRANKSHAFT) 1469014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ->allocatable_general_codes(); 1470b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch mode_ = GENERAL_REGISTERS; 1471b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateRegisters(); 1472b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1473b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1474b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1475b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateDoubleRegisters() { 1476b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Allocate double registers", this); 1477014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch num_registers_ = 1478014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterConfiguration::ArchDefault(RegisterConfiguration::CRANKSHAFT) 1479014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ->num_allocatable_double_registers(); 1480014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch allocatable_register_codes_ = 1481014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch RegisterConfiguration::ArchDefault(RegisterConfiguration::CRANKSHAFT) 1482014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ->allocatable_double_codes(); 1483b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch mode_ = DOUBLE_REGISTERS; 1484b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateRegisters(); 1485b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1486b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1487b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1488b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateRegisters() { 1489b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(unhandled_live_ranges_.is_empty()); 1490b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1491b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges_.length(); ++i) { 1492b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (live_ranges_[i] != NULL) { 1493b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (live_ranges_[i]->Kind() == mode_) { 1494b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledUnsorted(live_ranges_[i]); 1495b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1496b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1497b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1498b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SortUnhandled(); 1499b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1500b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1501b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(reusable_slots_.is_empty()); 1502b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(active_live_ranges_.is_empty()); 1503b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(inactive_live_ranges_.is_empty()); 1504b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1505b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (mode_ == DOUBLE_REGISTERS) { 1506014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < fixed_double_live_ranges_.length(); ++i) { 1507b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = fixed_double_live_ranges_.at(i); 1508b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) { 1509b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToInactive(current); 1510b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1511b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1512b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1513b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(mode_ == GENERAL_REGISTERS); 1514b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < fixed_live_ranges_.length(); ++i) { 1515b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = fixed_live_ranges_.at(i); 1516b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) { 1517b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToInactive(current); 1518b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1519b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1520b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1521b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1522b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!unhandled_live_ranges_.is_empty()) { 1523b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1524b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = unhandled_live_ranges_.RemoveLast(); 1525b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1526b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position = current->Start(); 1527b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifdef DEBUG 1528b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocation_finger_ = position; 1529b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 1530b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Processing interval %d start=%d\n", 1531b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id(), 1532b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch position.Value()); 1533b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1534b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current->HasAllocatedSpillOperand()) { 1535b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Live range %d already has a spill operand\n", current->id()); 1536b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_pos = position; 15371e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(next_pos.InstructionIndex())) { 1538b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_pos = next_pos.NextInstruction(); 1539b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1540b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = current->NextUsePositionRegisterIsBeneficial(next_pos); 1541b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If the range already has a spill operand and it doesn't need a 1542b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // register immediately, split it and spill the first part of the range. 1543b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos == NULL) { 1544b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(current); 1545b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 1546b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (pos->pos().Value() > 1547b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->Start().NextInstruction().Value()) { 1548b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Do not spill live range eagerly if use position that can benefit from 1549b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the register is too close to the start of live range. 1550b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(current, current->Start(), pos->pos()); 15513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 1552b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1553b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 1554b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1555b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1556b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1557b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1558b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_active = active_live_ranges_.at(i); 1559b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_active->End().Value() <= position.Value()) { 1560b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ActiveToHandled(cur_active); 1561b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // The live range was removed from the list of active live ranges. 1562b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (!cur_active->Covers(position)) { 1563b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ActiveToInactive(cur_active); 1564b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // The live range was removed from the list of active live ranges. 1565b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1566b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1567b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1568b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1569b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_inactive = inactive_live_ranges_.at(i); 1570b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_inactive->End().Value() <= position.Value()) { 1571b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InactiveToHandled(cur_inactive); 1572b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // Live range was removed from the list of inactive live ranges. 1573b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (cur_inactive->Covers(position)) { 1574b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InactiveToActive(cur_inactive); 1575b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // Live range was removed from the list of inactive live ranges. 1576b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1577b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1578b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1579b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!current->HasRegisterAssigned() && !current->IsSpilled()); 1580b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1581b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool result = TryAllocateFreeReg(current); 15823ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 15833ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 15843ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!result) AllocateBlockedReg(current); 15853ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 1586b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1587b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current->HasRegisterAssigned()) { 1588b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToActive(current); 1589b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1590b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1591b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 159244f0eee88ff00398ff7f715fab053374d808c90dSteve Block reusable_slots_.Rewind(0); 159344f0eee88ff00398ff7f715fab053374d808c90dSteve Block active_live_ranges_.Rewind(0); 159444f0eee88ff00398ff7f715fab053374d808c90dSteve Block inactive_live_ranges_.Rewind(0); 1595b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1596b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1597b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1598b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochconst char* LAllocator::RegisterName(int allocation_index) { 1599b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (mode_ == GENERAL_REGISTERS) { 1600014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return Register::from_code(allocation_index).ToString(); 1601b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1602014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return DoubleRegister::from_code(allocation_index).ToString(); 1603b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1604b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1605b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1606b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1607b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::TraceAlloc(const char* msg, ...) { 1608b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (FLAG_trace_alloc) { 1609b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch va_list arguments; 1610b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch va_start(arguments, msg); 1611b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch base::OS::VPrint(msg, arguments); 1612b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch va_end(arguments); 1613b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1614b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1615b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1616b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1617b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::HasTaggedValue(int virtual_register) const { 16181e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block HValue* value = graph_->LookupValue(virtual_register); 1619b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (value == NULL) return false; 1620b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return value->representation().IsTagged() && !value->type().IsSmi(); 1621b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1622b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1623b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1624b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochRegisterKind LAllocator::RequiredRegisterKind(int virtual_register) const { 16259fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (virtual_register < first_artificial_register_) { 16261e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block HValue* value = graph_->LookupValue(virtual_register); 16279fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (value != NULL && value->representation().IsDouble()) { 16289fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block return DOUBLE_REGISTERS; 16299fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 16309fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } else if (double_artificial_registers_.Contains( 16319fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block virtual_register - first_artificial_register_)) { 1632b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return DOUBLE_REGISTERS; 1633b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 16349fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 1635b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return GENERAL_REGISTERS; 1636b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1637b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1638b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1639b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToActive(LiveRange* range) { 1640b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to active\n", range->id()); 1641b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch active_live_ranges_.Add(range, zone()); 1642b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1643b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1644b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1645b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToInactive(LiveRange* range) { 1646b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to inactive\n", range->id()); 1647b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inactive_live_ranges_.Add(range, zone()); 1648b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1649b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1650b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1651b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToUnhandledSorted(LiveRange* range) { 1652b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL || range->IsEmpty()) return; 1653b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); 1654b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(allocation_finger_.Value() <= range->Start().Value()); 1655b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = unhandled_live_ranges_.length() - 1; i >= 0; --i) { 1656b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_range = unhandled_live_ranges_.at(i); 1657b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->ShouldBeAllocatedBefore(cur_range)) { 1658b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled at %d\n", range->id(), i + 1); 1659b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unhandled_live_ranges_.InsertAt(i + 1, range, zone()); 1660b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1661b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1662b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1663b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1664b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled at start\n", range->id()); 1665b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unhandled_live_ranges_.InsertAt(0, range, zone()); 1666b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1667b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1668b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1669b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1670b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToUnhandledUnsorted(LiveRange* range) { 1671b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL || range->IsEmpty()) return; 1672b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); 1673b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled unsorted at end\n", range->id()); 1674b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unhandled_live_ranges_.Add(range, zone()); 1675b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1676b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1677b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1678b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic int UnhandledSortHelper(LiveRange* const* a, LiveRange* const* b) { 1679b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!(*a)->ShouldBeAllocatedBefore(*b) || 1680b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch !(*b)->ShouldBeAllocatedBefore(*a)); 1681b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if ((*a)->ShouldBeAllocatedBefore(*b)) return 1; 1682b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if ((*b)->ShouldBeAllocatedBefore(*a)) return -1; 1683b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return (*a)->id() - (*b)->id(); 1684b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1685b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1686b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1687b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Sort the unhandled live ranges so that the ranges to be processed first are 1688b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// at the end of the array list. This is convenient for the register allocation 1689b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// algorithm because it is efficient to remove elements from the end. 1690b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SortUnhandled() { 1691b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Sort unhandled\n"); 1692b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unhandled_live_ranges_.Sort(&UnhandledSortHelper); 1693b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1694b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1695b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1696b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::UnhandledIsSorted() { 1697b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int len = unhandled_live_ranges_.length(); 1698b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < len; i++) { 1699b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* a = unhandled_live_ranges_.at(i - 1); 1700b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* b = unhandled_live_ranges_.at(i); 1701b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->Start().Value() < b->Start().Value()) return false; 1702b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1703b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1704b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1705b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1706b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1707b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::FreeSpillSlot(LiveRange* range) { 1708b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Check that we are the last range. 1709b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->next() != NULL) return; 1710b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1711b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!range->TopLevel()->HasAllocatedSpillOperand()) return; 1712b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1713b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = range->TopLevel()->GetSpillOperand()->index(); 1714b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (index >= 0) { 1715b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch reusable_slots_.Add(range, zone()); 1716b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1717b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1718b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1719b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1720b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLOperand* LAllocator::TryReuseSpillSlot(LiveRange* range) { 1721b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (reusable_slots_.is_empty()) return NULL; 1722b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (reusable_slots_.first()->End().Value() > 1723b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->TopLevel()->Start().Value()) { 1724b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 1725b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1726b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* result = reusable_slots_.first()->TopLevel()->GetSpillOperand(); 1727b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch reusable_slots_.Remove(0); 1728b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 1729b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1730b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1731b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1732b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ActiveToHandled(LiveRange* range) { 1733b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(active_live_ranges_.Contains(range)); 1734b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch active_live_ranges_.RemoveElement(range); 1735b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from active to handled\n", range->id()); 1736b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch FreeSpillSlot(range); 1737b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1738b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1739b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1740b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ActiveToInactive(LiveRange* range) { 1741b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(active_live_ranges_.Contains(range)); 1742b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch active_live_ranges_.RemoveElement(range); 1743b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inactive_live_ranges_.Add(range, zone()); 1744b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from active to inactive\n", range->id()); 1745b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1746b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1747b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1748b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::InactiveToHandled(LiveRange* range) { 1749b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(inactive_live_ranges_.Contains(range)); 1750b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inactive_live_ranges_.RemoveElement(range); 1751b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); 1752b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch FreeSpillSlot(range); 1753b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1754b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1755b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1756b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::InactiveToActive(LiveRange* range) { 1757b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(inactive_live_ranges_.Contains(range)); 1758b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inactive_live_ranges_.RemoveElement(range); 1759b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch active_live_ranges_.Add(range, zone()); 1760b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from inactive to active\n", range->id()); 1761b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1762b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1763b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1764b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::TryAllocateFreeReg(LiveRange* current) { 1765014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(DoubleRegister::kMaxNumRegisters >= Register::kNumRegisters); 1766014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 1767014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition free_until_pos[DoubleRegister::kMaxNumRegisters]; 1768b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1769014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < DoubleRegister::kMaxNumRegisters; i++) { 1770b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[i] = LifetimePosition::MaxPosition(); 1771b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1772b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1773b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1774b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_active = active_live_ranges_.at(i); 1775b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[cur_active->assigned_register()] = 1776b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(0); 1777b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1778b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1779b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1780b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_inactive = inactive_live_ranges_.at(i); 1781b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(cur_inactive->End().Value() > current->Start().Value()); 1782b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = 1783b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_inactive->FirstIntersection(current); 1784b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!next_intersection.IsValid()) continue; 1785b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = cur_inactive->assigned_register(); 1786b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection); 1787b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1788b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1789b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* hint = current->FirstHint(); 1790b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (hint != NULL && (hint->IsRegister() || hint->IsDoubleRegister())) { 1791b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int register_index = hint->index(); 1792b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TraceAlloc( 1793b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch "Found reg hint %s (free until [%d) for live range %d (end %d[).\n", 1794b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterName(register_index), 1795b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch free_until_pos[register_index].Value(), 1796b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->id(), 1797b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->End().Value()); 1798b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1799b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // The desired register is free until the end of the current live range. 1800b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (free_until_pos[register_index].Value() >= current->End().Value()) { 1801b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TraceAlloc("Assigning preferred reg %s to live range %d\n", 1802b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterName(register_index), 1803b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->id()); 1804b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(current, register_index); 1805b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return true; 1806b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1807b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1808b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1809b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the register which stays free for the longest time. 1810014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int reg = allocatable_register_codes_[0]; 1811b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < RegisterCount(); ++i) { 1812014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int code = allocatable_register_codes_[i]; 1813014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (free_until_pos[code].Value() > free_until_pos[reg].Value()) { 1814014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch reg = code; 1815b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1816b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1817b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1818b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos = free_until_pos[reg]; 1819b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1820b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() <= current->Start().Value()) { 1821b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All registers are blocked. 1822b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 1823b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1824b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1825b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() < current->End().Value()) { 1826b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is available at the range start but becomes blocked before 1827b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the range end. Split current at position where it becomes blocked. 18283ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* tail = SplitRangeAt(current, pos); 18293ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1830b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(tail); 1831b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1832b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1833b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1834b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is available at the range start and is free until 1835b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the range end. 1836b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pos.Value() >= current->End().Value()); 1837b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Assigning free reg %s to live range %d\n", 1838b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterName(reg), 1839b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id()); 1840b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(current, reg); 1841b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1842b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1843b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1844b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1845b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1846b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateBlockedReg(LiveRange* current) { 1847b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* register_use = current->NextRegisterPosition(current->Start()); 1848b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (register_use == NULL) { 1849b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // There is no use in the current live range that requires a register. 1850b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We can just spill it. 1851b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(current); 1852b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1853b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1854b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1855b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1856014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition use_pos[DoubleRegister::kMaxNumRegisters]; 1857014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LifetimePosition block_pos[DoubleRegister::kMaxNumRegisters]; 1858b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1859014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = 0; i < DoubleRegister::kMaxNumRegisters; i++) { 1860b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[i] = block_pos[i] = LifetimePosition::MaxPosition(); 1861b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1862b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1863b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1864b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = active_live_ranges_[i]; 1865b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = range->assigned_register(); 1866b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsFixed() || !range->CanBeSpilled(current->Start())) { 1867b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[cur_reg] = use_pos[cur_reg] = 1868b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(0); 1869b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1870b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_use = range->NextUsePositionRegisterIsBeneficial( 1871b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->Start()); 1872b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_use == NULL) { 1873b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = range->End(); 1874b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1875b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = next_use->pos(); 1876b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1877b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1878b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1879b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1880b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1881b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = inactive_live_ranges_.at(i); 1882b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(range->End().Value() > current->Start().Value()); 1883b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = range->FirstIntersection(current); 1884b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!next_intersection.IsValid()) continue; 1885b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = range->assigned_register(); 1886b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsFixed()) { 1887b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection); 1888b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]); 1889b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1890b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection); 1891b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1892b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1893b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1894014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int reg = allocatable_register_codes_[0]; 1895b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < RegisterCount(); ++i) { 1896014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int code = allocatable_register_codes_[i]; 1897014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (use_pos[code].Value() > use_pos[reg].Value()) { 1898014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch reg = code; 1899b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1900b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1901b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1902b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos = use_pos[reg]; 1903b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1904b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() < register_use->pos().Value()) { 1905b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All registers are blocked before the first use that requires a register. 1906b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Spill starting part of live range up to that use. 1907b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(current, current->Start(), register_use->pos()); 1908b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1909b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1910b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1911b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block_pos[reg].Value() < current->End().Value()) { 1912b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register becomes blocked before the current range end. Split before that 1913b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position. 1914b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* tail = SplitBetween(current, 1915b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->Start(), 1916b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[reg].InstructionStart()); 1917b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 1918b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(tail); 1919b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1920b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1921b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is not blocked for the whole range. 1922b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(block_pos[reg].Value() >= current->End().Value()); 1923b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Assigning blocked reg %s to live range %d\n", 1924b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterName(reg), 1925b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id()); 1926b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(current, reg); 1927b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1928b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This register was not free. Thus we need to find and spill 1929b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // parts of active and inactive live regions that use the same register 1930b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // at the same lifetime positions as current. 1931b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SplitAndSpillIntersecting(current); 1932b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1933b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1934b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1935b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochLifetimePosition LAllocator::FindOptimalSpillingPos(LiveRange* range, 1936b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition pos) { 1937b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block = GetBlock(pos.InstructionStart()); 1938b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* loop_header = 1939b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block->IsLoopHeader() ? block : block->parent_loop_header(); 1940b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1941b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (loop_header == NULL) return pos; 1942b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1943b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* prev_use = 1944b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->PreviousUsePositionRegisterIsBeneficial(pos); 1945b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1946b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (loop_header != NULL) { 1947b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // We are going to spill live range inside the loop. 1948b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If possible try to move spilling position backwards to loop header. 1949b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This will reduce number of memory moves on the back edge. 1950b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition loop_start = LifetimePosition::FromInstructionIndex( 1951b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch loop_header->first_instruction_index()); 1952b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1953b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (range->Covers(loop_start)) { 1954b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (prev_use == NULL || prev_use->pos().Value() < loop_start.Value()) { 1955b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // No register beneficial use inside the loop before the pos. 1956b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch pos = loop_start; 1957b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1958b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1959b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1960b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Try hoisting out to an outer loop. 1961b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch loop_header = loop_header->parent_loop_header(); 1962b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1963b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1964b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return pos; 1965b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 1966b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1967b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1968b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SplitAndSpillIntersecting(LiveRange* current) { 1969b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(current->HasRegisterAssigned()); 1970b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int reg = current->assigned_register(); 1971b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition split_pos = current->Start(); 1972b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1973b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = active_live_ranges_[i]; 1974b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->assigned_register() == reg) { 1975b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_pos = range->NextRegisterPosition(current->Start()); 1976b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos); 1977b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_pos == NULL) { 1978b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SpillAfter(range, spill_pos); 1979b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1980b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // When spilling between spill_pos and next_pos ensure that the range 1981b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // remains spilled at least until the start of the current live range. 1982b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This guarantees that we will not introduce new unhandled ranges that 1983b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // start before the current range as this violates allocation invariant 1984b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // and will lead to an inconsistent state of active and inactive 1985b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // live-ranges: ranges are allocated in order of their start positions, 1986b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // ranges are retired from active/inactive when the start of the 1987b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // current live-range is larger than their end. 1988b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos()); 1989b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1990b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 1991b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ActiveToHandled(range); 1992b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; 1993b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1994b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1995b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1996b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1997b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = inactive_live_ranges_[i]; 1998b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(range->End().Value() > current->Start().Value()); 1999b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->assigned_register() == reg && !range->IsFixed()) { 2000b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = range->FirstIntersection(current); 2001b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_intersection.IsValid()) { 2002b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_pos = range->NextRegisterPosition(current->Start()); 2003b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_pos == NULL) { 2004b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillAfter(range, split_pos); 2005b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 2006b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_intersection = Min(next_intersection, next_pos->pos()); 2007b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(range, split_pos, next_intersection); 2008b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2009b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 2010b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InactiveToHandled(range); 2011b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; 2012b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2013b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2014b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2015b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2016b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2017b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2018b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::IsBlockBoundary(LifetimePosition pos) { 2019b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos.IsInstructionStart() && 20201e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block InstructionAt(pos.InstructionIndex())->IsLabel(); 2021b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2022b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2023b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 20243ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLiveRange* LAllocator::SplitRangeAt(LiveRange* range, LifetimePosition pos) { 2025b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->IsFixed()); 2026b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value()); 2027b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2028b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() <= range->Start().Value()) return range; 2029b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 20301e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block // We can't properly connect liveranges if split occured at the end 20311e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block // of control instruction. 2032b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pos.IsInstructionStart() || 20331e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block !chunk_->instructions()->at(pos.InstructionIndex())->IsControl()); 20341e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 2035b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int vreg = GetVirtualRegister(); 20363ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return NULL; 2037b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* result = LiveRangeFor(vreg); 2038b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->SplitAt(pos, result, zone()); 2039b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 2040b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2041b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2042b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2043b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::SplitBetween(LiveRange* range, 2044b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 2045b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2046b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->IsFixed()); 2047b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Splitting live range %d in position between [%d, %d]\n", 2048b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->id(), 2049b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 2050b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 2051b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2052b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition split_pos = FindOptimalSplitPos(start, end); 2053b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(split_pos.Value() >= start.Value()); 20543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return SplitRangeAt(range, split_pos); 2055b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2056b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2057b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2058b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLifetimePosition LAllocator::FindOptimalSplitPos(LifetimePosition start, 2059b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2060b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int start_instr = start.InstructionIndex(); 2061b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int end_instr = end.InstructionIndex(); 2062b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(start_instr <= end_instr); 2063b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2064b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We have no choice 2065b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start_instr == end_instr) return end; 2066b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2067257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch HBasicBlock* start_block = GetBlock(start); 2068257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch HBasicBlock* end_block = GetBlock(end); 2069b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2070b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (end_block == start_block) { 2071257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // The interval is split in the same basic block. Split at the latest 2072257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // possible position. 2073b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return end; 2074b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2075b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2076b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = end_block; 2077b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find header of outermost loop. 2078b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (block->parent_loop_header() != NULL && 2079b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->parent_loop_header()->block_id() > start_block->block_id()) { 2080b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block = block->parent_loop_header(); 2081b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2082b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2083257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // We did not find any suitable outer loop. Split at the latest possible 2084257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // position unless end_block is a loop header itself. 2085257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch if (block == end_block && !end_block->IsLoopHeader()) return end; 2086b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2087b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition::FromInstructionIndex( 2088b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 2089b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2090b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2091b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2092b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) { 20933ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* second_part = SplitRangeAt(range, pos); 20943ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 2095b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(second_part); 2096b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2097b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2098b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2099b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SpillBetween(LiveRange* range, 2100b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 2101b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SpillBetweenUntil(range, start, start, end); 2103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 2104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid LAllocator::SpillBetweenUntil(LiveRange* range, 2107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition start, 2108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition until, 2109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end) { 2110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(start.Value() < end.Value()); 21113ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* second_part = SplitRangeAt(range, start); 21123ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 2113b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2114b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second_part->Start().Value() < end.Value()) { 2115b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split result intersects with [start, end[. 2116b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split it at position between ]start+1, end[, spill the middle part 2117b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // and put the rest to unhandled. 2118b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* third_part = SplitBetween( 2119b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch second_part, 2120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Max(second_part->Start().InstructionEnd(), until), 2121b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.PrevInstruction().InstructionEnd()); 2122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 2123b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(third_part != second_part); 2125b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2126b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(second_part); 2127b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(third_part); 2128b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 2129b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split result does not intersect with [start, end[. 2130b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Nothing to spill. Just put it to unhandled as whole. 2131b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(second_part); 2132b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2133b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2134b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2135b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2136b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Spill(LiveRange* range) { 2137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->IsSpilled()); 2138b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Spilling live range %d\n", range->id()); 2139b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* first = range->TopLevel(); 2140b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2141b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!first->HasAllocatedSpillOperand()) { 2142b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* op = TryReuseSpillSlot(range); 2143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (op == NULL) op = chunk_->GetNextSpillSlot(range->Kind()); 2144b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first->SetSpillOperand(op); 2145b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->MakeSpilled(chunk()->zone()); 2147b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2148b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2149b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2150b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochint LAllocator::RegisterCount() const { 2151b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return num_registers_; 2152b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2153b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2154b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2155b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 2156b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2157b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2158b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Verify() const { 2159b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges()->length(); ++i) { 2160b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = live_ranges()->at(i); 2161b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) current->Verify(); 2162b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2163b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2164b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2165b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2166b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 2167b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2168b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochLAllocatorPhase::LAllocatorPhase(const char* name, LAllocator* allocator) 2170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : CompilationPhase(name, allocator->graph()->info()), 2171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocator_(allocator) { 2172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_hydrogen_stats) { 2173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocator_zone_start_allocation_size_ = 2174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocator->zone()->allocation_size(); 2175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 2176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 2177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochLAllocatorPhase::~LAllocatorPhase() { 2180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_hydrogen_stats) { 2181014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t size = allocator_->zone()->allocation_size() - 2182014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch allocator_zone_start_allocation_size_; 2183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch isolate()->GetHStatistics()->SaveTiming(name(), base::TimeDelta(), size); 2184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 2185b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (ShouldProduceTraceOutput()) { 2187b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch isolate()->GetHTracer()->TraceLithium(name(), allocator_->chunk()); 2188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch isolate()->GetHTracer()->TraceLiveRanges(name(), allocator_); 2189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 2190b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2191b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifdef DEBUG 2192b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (allocator_ != NULL) allocator_->Verify(); 2193b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 2194b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 2195b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2196b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2197014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace internal 2198014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace v8 2199