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 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/v8.h" 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/hydrogen.h" 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/lithium-inl.h" 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/lithium-allocator-inl.h" 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/string-stream.h" 11b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 12b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochnamespace v8 { 13b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochnamespace internal { 14b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 15b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) { 16b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return a.Value() < b.Value() ? a : b; 17b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 18b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 19b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 20b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) { 21b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return a.Value() > b.Value() ? a : b; 22b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 23b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 24b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochUsePosition::UsePosition(LifetimePosition pos, 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* operand, 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* hint) 281e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block : operand_(operand), 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch hint_(hint), 301e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block pos_(pos), 311e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block next_(NULL), 321e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block requires_reg_(false), 331e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block register_beneficial_(true) { 341e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (operand_ != NULL && operand_->IsUnallocated()) { 351e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block LUnallocated* unalloc = LUnallocated::cast(operand_); 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch requires_reg_ = unalloc->HasRegisterPolicy() || 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unalloc->HasDoubleRegisterPolicy(); 381e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block register_beneficial_ = !unalloc->HasAnyPolicy(); 39b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pos_.IsValid()); 41b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 42b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 431e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 441e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockbool UsePosition::HasHint() const { 451e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return hint_ != NULL && !hint_->IsUnallocated(); 46b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 47b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 48b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 49b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool UsePosition::RequiresRegister() const { 50b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return requires_reg_; 51b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 52b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 53b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 54b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool UsePosition::RegisterIsBeneficial() const { 55b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return register_beneficial_; 56b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 57b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 58b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 593ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid UseInterval::SplitAt(LifetimePosition pos, Zone* zone) { 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Contains(pos) && pos.Value() != start().Value()); 613ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* after = new(zone) UseInterval(pos, end_); 62b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch after->next_ = next_; 63b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_ = after; 64b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end_ = pos; 65b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 66b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 67b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 68b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 69b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 70b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 71b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::Verify() const { 72b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* cur = first_pos_; 73b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (cur != NULL) { 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Start().Value() <= cur->pos().Value() && 75b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur->pos().Value() <= End().Value()); 76b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur = cur->next(); 77b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 78b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 79b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 80b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 81b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::HasOverlap(UseInterval* target) const { 82b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* current_interval = first_interval_; 83b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current_interval != NULL) { 84b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Intervals overlap if the start of one is contained in the other. 85b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval->Contains(target->start()) || 86b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch target->Contains(current_interval->start())) { 87b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 88b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 89b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval = current_interval->next(); 90b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 91b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 92b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 93b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 94b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 95b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 96b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 97b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 983ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLiveRange::LiveRange(int id, Zone* zone) 991e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block : id_(id), 1001e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spilled_(false), 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch kind_(UNALLOCATED_REGISTERS), 1021e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_(kInvalidAssignment), 1031e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block last_interval_(NULL), 1041e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block first_interval_(NULL), 1051e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block first_pos_(NULL), 1061e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block parent_(NULL), 1071e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block next_(NULL), 1081e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block current_interval_(NULL), 1091e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block last_processed_use_(NULL), 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current_hint_operand_(NULL), 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch spill_operand_(new (zone) LOperand()), 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch spill_start_index_(kMaxInt) {} 1131e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1141e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid LiveRange::set_assigned_register(int reg, Zone* zone) { 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!HasRegisterAssigned() && !IsSpilled()); 1171e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_ = reg; 1183ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ConvertOperands(zone); 1191e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1201e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1211e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1223ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::MakeSpilled(Zone* zone) { 123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsSpilled()); 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(TopLevel()->HasAllocatedSpillOperand()); 1251e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spilled_ = true; 1261e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block assigned_register_ = kInvalidAssignment; 1273ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch ConvertOperands(zone); 1281e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1291e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1301e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1311e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockbool LiveRange::HasAllocatedSpillOperand() const { 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(spill_operand_ != NULL); 1333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return !spill_operand_->IsIgnored(); 1341e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1351e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1361e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1371e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockvoid LiveRange::SetSpillOperand(LOperand* operand) { 138b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!operand->IsUnallocated()); 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(spill_operand_ != NULL); 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(spill_operand_->IsIgnored()); 1411e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block spill_operand_->ConvertTo(operand->kind(), operand->index()); 1421e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block} 1431e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 1441e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 145b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextUsePosition(LifetimePosition start) { 146b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = last_processed_use_; 147b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos == NULL) use_pos = first_pos(); 148b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_pos != NULL && use_pos->pos().Value() < start.Value()) { 149b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = use_pos->next(); 150b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 151b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_processed_use_ = use_pos; 152b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return use_pos; 153b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 154b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 155b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 156b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextUsePositionRegisterIsBeneficial( 157b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start) { 158b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = NextUsePosition(start); 159b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (pos != NULL && !pos->RegisterIsBeneficial()) { 160b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos = pos->next(); 161b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 162b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos; 163b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 164b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 165b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochUsePosition* LiveRange::PreviousUsePositionRegisterIsBeneficial( 167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition start) { 168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* pos = first_pos(); 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* prev = NULL; 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (pos != NULL && pos->pos().Value() < start.Value()) { 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (pos->RegisterIsBeneficial()) prev = pos; 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch pos = pos->next(); 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return prev; 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 178b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) { 179b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = NextUsePosition(start); 180b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (pos != NULL && !pos->RequiresRegister()) { 181b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos = pos->next(); 182b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 183b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos; 184b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 185b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 186b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 187b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::CanBeSpilled(LifetimePosition pos) { 188b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We cannot spill a live range that has a use requiring a register 189b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // at the current or the immediate next position. 190b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = NextRegisterPosition(pos); 191b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos == NULL) return true; 1923ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return 1933ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch use_pos->pos().Value() > pos.NextInstruction().InstructionEnd().Value(); 194b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 195b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 196b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1973ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLOperand* LiveRange::CreateAssignedOperand(Zone* zone) { 198b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* op = NULL; 199b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (HasRegisterAssigned()) { 200b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!IsSpilled()); 201b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch switch (Kind()) { 202b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case GENERAL_REGISTERS: 203b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch op = LRegister::Create(assigned_register(), zone); 204b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case DOUBLE_REGISTERS: 206b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch op = LDoubleRegister::Create(assigned_register(), zone); 207b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 208b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch default: 209b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UNREACHABLE(); 210b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 211b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (IsSpilled()) { 212b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!HasRegisterAssigned()); 213b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch op = TopLevel()->GetSpillOperand(); 214b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!op->IsUnallocated()); 215b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 2163ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LUnallocated* unalloc = new(zone) LUnallocated(LUnallocated::NONE); 217b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unalloc->set_virtual_register(id_); 218b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch op = unalloc; 219b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 220b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return op; 221b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 222b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 223b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 224b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochUseInterval* LiveRange::FirstSearchIntervalForPosition( 225b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position) const { 226b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval_ == NULL) return first_interval_; 227b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current_interval_->start().Value() > position.Value()) { 228b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ = NULL; 229b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return first_interval_; 230b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 231b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return current_interval_; 232b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 233b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 234b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 235b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::AdvanceLastProcessedMarker( 236b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* to_start_of, LifetimePosition but_not_past) const { 237b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of == NULL) return; 238b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of->start().Value() > but_not_past.Value()) return; 239b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = 240b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ == NULL ? LifetimePosition::Invalid() 241b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch : current_interval_->start(); 242b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (to_start_of->start().Value() > start.Value()) { 243b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current_interval_ = to_start_of; 244b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 245b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 246b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 247b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::SplitAt(LifetimePosition position, 2493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* result, 2503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 251b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Start().Value() < position.Value()); 252b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(result->IsEmpty()); 253b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the last interval that ends before the position. If the 254b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position is contained in one of the intervals in the chain, we 255b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // split that interval and use the first part. 256b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* current = FirstSearchIntervalForPosition(position); 257b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 258b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If the split position coincides with the beginning of a use interval 259b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // we need to split use positons in a special way. 260b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool split_at_start = false; 261b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2623fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch if (current->start().Value() == position.Value()) { 2633fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // When splitting at start we need to locate the previous use interval. 2643fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch current = first_interval_; 2653fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch } 2663fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 267b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current != NULL) { 268b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current->Contains(position)) { 2693ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch current->SplitAt(position, zone); 270b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch break; 271b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 272b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* next = current->next(); 273b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next->start().Value() >= position.Value()) { 274b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch split_at_start = (next->start().Value() == position.Value()); 275b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch break; 276b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 277b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current = next; 278b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 279b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 280b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Partition original use intervals to the two live ranges. 281b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* before = current; 282b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* after = before->next(); 283b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->last_interval_ = (last_interval_ == before) 284b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ? after // Only interval in the range after split. 285b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch : last_interval_; // Last interval of the original range. 286b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->first_interval_ = after; 287b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = before; 288b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 289b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the last use position before the split and the first use 290b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position after it. 291b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_after = first_pos_; 292b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_before = NULL; 293b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (split_at_start) { 294b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split position coincides with the beginning of a use interval (the 295b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // end of a lifetime hole). Use at this position should be attributed to 296b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the split child because split child owns use interval covering it. 297b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_after != NULL && use_after->pos().Value() < position.Value()) { 298b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before = use_after; 299b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_after = use_after->next(); 300b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 301b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 302b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_after != NULL && use_after->pos().Value() <= position.Value()) { 303b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before = use_after; 304b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_after = use_after->next(); 305b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 306b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 307b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 308b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Partition original use positions to the two live ranges. 309b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_before != NULL) { 310b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_before->next_ = NULL; 311b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 312b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_pos_ = NULL; 313b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 314b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->first_pos_ = use_after; 315b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3163fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Discard cached iteration state. It might be pointing 3173fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // to the use that no longer belongs to this live range. 3183fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch last_processed_use_ = NULL; 3193fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch current_interval_ = NULL; 3203fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 321b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Link the new live range in the chain before any of the other 322b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // ranges linked from the range before the split. 323b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->parent_ = (parent_ == NULL) ? this : parent_; 324b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result->kind_ = result->parent_->kind_; 325b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->next_ = next_; 326b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_ = result; 327b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 328b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 329b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Verify(); 330b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch result->Verify(); 331b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 332b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 333b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 334b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 335b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// This implements an ordering on live ranges so that they are ordered by their 336b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// start positions. This is needed for the correctness of the register 337b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// allocation algorithm. If two live ranges start at the same offset then there 338b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// is a tie breaker based on where the value is first used. This part of the 339b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// ordering is merely a heuristic. 340b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const { 341b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start = Start(); 342b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition other_start = other->Start(); 343b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start.Value() == other_start.Value()) { 344b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* pos = first_pos(); 345b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos == NULL) return false; 346b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* other_pos = other->first_pos(); 347b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (other_pos == NULL) return true; 348b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos->pos().Value() < other_pos->pos().Value(); 349b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 350b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return start.Value() < other_start.Value(); 351b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 352b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 353b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 354b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LiveRange::ShortenTo(LifetimePosition start) { 355b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Shorten live range %d to [%d\n", id_, start.Value()); 356b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(first_interval_ != NULL); 357b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(first_interval_->start().Value() <= start.Value()); 358b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(start.Value() < first_interval_->end().Value()); 359b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->set_start(start); 360b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 361b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 362b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3633ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::EnsureInterval(LifetimePosition start, 3643ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LifetimePosition end, 3653ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 366b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Ensure live range %d in interval [%d %d[\n", 367b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 368b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 369b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 370b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition new_end = end; 371b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (first_interval_ != NULL && 372b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->start().Value() <= end.Value()) { 373b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_interval_->end().Value() > end.Value()) { 374b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch new_end = first_interval_->end(); 375b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 376b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = first_interval_->next(); 377b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 378b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* new_interval = new(zone) UseInterval(start, new_end); 380b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch new_interval->next_ = first_interval_; 381b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = new_interval; 382b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (new_interval->next() == NULL) { 383b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = new_interval; 384b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 385b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 386b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 387b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 3883ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::AddUseInterval(LifetimePosition start, 3893ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LifetimePosition end, 3903ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Zone* zone) { 391b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Add to live range %d interval [%d %d[\n", 392b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 393b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 394b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 395b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (first_interval_ == NULL) { 3963ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* interval = new(zone) UseInterval(start, end); 397b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = interval; 398b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_interval_ = interval; 399b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 400b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (end.Value() == first_interval_->start().Value()) { 401b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->set_start(start); 402b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (end.Value() < first_interval_->start().Value()) { 4033ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch UseInterval* interval = new(zone) UseInterval(start, end); 404b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval->set_next(first_interval_); 405b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_ = interval; 406b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 407b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Order of instruction's processing (see ProcessInstructions) guarantees 408b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // that each new use interval either precedes or intersects with 409b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // last added interval. 410b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(start.Value() < first_interval_->end().Value()); 411b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->start_ = Min(start, first_interval_->start_); 412b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_interval_->end_ = Max(end, first_interval_->end_); 413b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 414b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 415b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 416b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 417b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 418b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid LiveRange::AddUsePosition(LifetimePosition pos, 419b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* operand, 420b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* hint, 421b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone) { 422b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LAllocator::TraceAlloc("Add to live range %d use position %d\n", 423b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch id_, 424b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pos.Value()); 425b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* use_pos = new(zone) UsePosition(pos, operand, hint); 426b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* prev_hint = NULL; 427b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* prev = NULL; 428b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* current = first_pos_; 429b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (current != NULL && current->pos().Value() < pos.Value()) { 430b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch prev_hint = current->HasHint() ? current : prev_hint; 431b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch prev = current; 432b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current = current->next(); 433b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 434b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 435b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (prev == NULL) { 436b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->set_next(first_pos_); 437b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_pos_ = use_pos; 438b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 439b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->next_ = prev->next_; 440b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch prev->next_ = use_pos; 441b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 442b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 443b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (prev_hint == NULL && use_pos->HasHint()) { 444b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current_hint_operand_ = hint; 445b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 446b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 447b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 448b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 4493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochvoid LiveRange::ConvertOperands(Zone* zone) { 4503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LOperand* op = CreateAssignedOperand(zone); 451b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* use_pos = first_pos(); 452b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (use_pos != NULL) { 453b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Start().Value() <= use_pos->pos().Value() && 454b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->pos().Value() <= End().Value()); 455b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 456b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos->HasOperand()) { 457b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(op->IsRegister() || op->IsDoubleRegister() || 458b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch !use_pos->RequiresRegister()); 459b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos->operand()->ConvertTo(op->kind(), op->index()); 460b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 461b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = use_pos->next(); 462b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 463b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 464b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 465b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 466b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::CanCover(LifetimePosition position) const { 467b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (IsEmpty()) return false; 468b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return Start().Value() <= position.Value() && 469b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch position.Value() < End().Value(); 470b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 471b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 472b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 473b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LiveRange::Covers(LifetimePosition position) { 474b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!CanCover(position)) return false; 475b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* start_search = FirstSearchIntervalForPosition(position); 476b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (UseInterval* interval = start_search; 477b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval != NULL; 478b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval = interval->next()) { 479b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(interval->next() == NULL || 480b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch interval->next()->start().Value() >= interval->start().Value()); 481b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AdvanceLastProcessedMarker(interval, position); 482b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (interval->Contains(position)) return true; 483b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (interval->start().Value() > position.Value()) return false; 484b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 485b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 486b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 487b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 488b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 489b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLifetimePosition LiveRange::FirstIntersection(LiveRange* other) { 490b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* b = other->first_interval(); 491b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (b == NULL) return LifetimePosition::Invalid(); 492b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition advance_last_processed_up_to = b->start(); 493b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UseInterval* a = FirstSearchIntervalForPosition(b->start()); 494b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (a != NULL && b != NULL) { 495b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->start().Value() > other->End().Value()) break; 496b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (b->start().Value() > End().Value()) break; 497b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition cur_intersection = a->Intersect(b); 498b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_intersection.IsValid()) { 499b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return cur_intersection; 500b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 501b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->start().Value() < b->start().Value()) { 502b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch a = a->next(); 503b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a == NULL || a->start().Value() > other->End().Value()) break; 504b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AdvanceLastProcessedMarker(a, advance_last_processed_up_to); 505b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 506b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch b = b->next(); 507b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 508b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 509b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition::Invalid(); 510b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 511b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 512b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 51344f0eee88ff00398ff7f715fab053374d808c90dSteve BlockLAllocator::LAllocator(int num_values, HGraph* graph) 514b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : zone_(graph->isolate()), 5153ef787dbeca8a5fb1086949cda830dccee07bfbdBen 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) { 589b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return -index - 1 - Register::kMaxNumAllocatableRegisters; 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) { 621b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(index < Register::kMaxNumAllocatableRegisters); 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) { 635b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(index < DoubleRegister::NumAllocatableRegisters()); 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()) { 943b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < Register::kMaxNumAllocatableRegisters; ++i) { 944b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (output == NULL || !output->IsRegister() || 945b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch output->index() != i) { 946b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = FixedLiveRangeFor(i); 947b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->AddUseInterval(curr_position, 9483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch curr_position.InstructionEnd(), 949b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch zone()); 950b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 951b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 952086aeeaae12517475c22695a200be45495516549Ben Murdoch } 953086aeeaae12517475c22695a200be45495516549Ben Murdoch 954b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->ClobbersDoubleRegisters(isolate())) { 955b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < DoubleRegister::NumAllocatableRegisters(); ++i) { 956b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (output == NULL || !output->IsDoubleRegister() || 957b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch output->index() != i) { 958b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = FixedDoubleLiveRangeFor(i); 959b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->AddUseInterval(curr_position, 9603ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch curr_position.InstructionEnd(), 961b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch zone()); 962b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 963b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 964b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 965b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9663fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (UseIterator it(instr); !it.Done(); it.Advance()) { 9673fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LOperand* input = it.Current(); 968b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 969b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition use_pos; 970b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (input->IsUnallocated() && 971b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated::cast(input)->IsUsedAtStart()) { 972b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = curr_position; 973b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 974b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos = curr_position.InstructionEnd(); 975b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 976b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 977b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Use(block_start_position, use_pos, input, NULL); 9783ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (input->IsUnallocated()) { 9793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch live->Add(LUnallocated::cast(input)->virtual_register()); 9803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 981b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 982b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 9833fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch for (TempIterator it(instr); !it.Done(); it.Advance()) { 9843fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch LOperand* temp = it.Current(); 985b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->ClobbersTemps()) { 986b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp->IsRegister()) continue; 987b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp->IsUnallocated()) { 988b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LUnallocated* temp_unalloc = LUnallocated::cast(temp); 989b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (temp_unalloc->HasFixedPolicy()) { 990b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 991b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 992b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 993b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 994b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Use(block_start_position, curr_position.InstructionEnd(), temp, NULL); 995b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Define(curr_position, temp, NULL); 996b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 997b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (temp->IsUnallocated()) { 998b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* temp_unalloc = LUnallocated::cast(temp); 999b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (temp_unalloc->HasDoubleRegisterPolicy()) { 1000b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch double_artificial_registers_.Add( 1001b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch temp_unalloc->virtual_register() - first_artificial_register_, 1002b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch zone()); 1003b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1004b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1005b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1006b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1007b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1008b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1009b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch index = index - 1; 1010b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1011b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1012b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1013b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1014b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ResolvePhis(HBasicBlock* block) { 1015b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<HPhi*>* phis = block->phis(); 1016b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < phis->length(); ++i) { 1017b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HPhi* phi = phis->at(i); 1018b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* phi_operand = 1019b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new (chunk()->zone()) LUnallocated(LUnallocated::NONE); 1020b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch phi_operand->set_virtual_register(phi->id()); 1021b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int j = 0; j < phi->OperandCount(); ++j) { 1022b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HValue* op = phi->OperandAt(j); 1023b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* operand = NULL; 1024b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (op->IsConstant() && op->EmitAtUses()) { 1025b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HConstant* constant = HConstant::cast(op); 1026b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand = chunk_->DefineConstantOperand(constant); 1027b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1028b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!op->EmitAtUses()); 1029b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LUnallocated* unalloc = 1030b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new(chunk()->zone()) LUnallocated(LUnallocated::ANY); 1031b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unalloc->set_virtual_register(op->id()); 1032b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand = unalloc; 1033b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1034b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* cur_block = block->predecessors()->at(j); 1035b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The gap move must be added without any special processing as in 1036b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the AddConstraintsGapMove. 1037b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch chunk_->AddGapMove(cur_block->last_instruction_index() - 1, 1038b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch operand, 1039b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch phi_operand); 1040257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 1041257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // We are going to insert a move before the branch instruction. 1042257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // Some branch instructions (e.g. loops' back edges) 1043257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // can potentially cause a GC so they have a pointer map. 1044257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // By inserting a move we essentially create a copy of a 1045257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // value which is invisible to PopulatePointerMaps(), because we store 1046257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // it into a location different from the operand of a live range 1047257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // covering a branch instruction. 1048257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // Thus we need to manually record a pointer. 10493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LInstruction* branch = 10503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch InstructionAt(cur_block->last_instruction_index()); 10513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (branch->HasPointerMap()) { 1052b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (phi->representation().IsTagged() && !phi->type().IsSmi()) { 1053b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch branch->pointer_map()->RecordPointer(phi_operand, chunk()->zone()); 10543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } else if (!phi->representation().IsDouble()) { 1055b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch branch->pointer_map()->RecordUntagged(phi_operand, chunk()->zone()); 1056257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch } 1057257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch } 1058b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1059b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1060b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* live_range = LiveRangeFor(phi->id()); 1061b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LLabel* label = chunk_->GetLabel(phi->block()->block_id()); 1062b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch label->GetOrCreateParallelMove(LGap::START, chunk()->zone())-> 1063b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AddMove(phi_operand, live_range->GetSpillOperand(), chunk()->zone()); 1064b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch live_range->SetSpillStartIndex(phi->block()->first_instruction_index()); 1065b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1066b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1067b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1068b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 10693ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochbool LAllocator::Allocate(LChunk* chunk) { 1070b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(chunk_ == NULL); 1071b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk_ = static_cast<LPlatformChunk*>(chunk); 1072b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch assigned_registers_ = 1073b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new(chunk->zone()) BitVector(Register::NumAllocatableRegisters(), 1074b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk->zone()); 1075b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch assigned_double_registers_ = 1076b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new(chunk->zone()) BitVector(DoubleRegister::NumAllocatableRegisters(), 1077b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 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(); 1340b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (chunk_->info()->IsStub()) { 1341b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CodeStub::Major major_key = chunk_->info()->code_stub()->MajorKey(); 1342b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PrintF("Function: %s\n", CodeStub::MajorName(major_key, false)); 1343b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 1344b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(chunk_->info()->IsOptimizing()); 1345b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AllowHandleDereference allow_deref; 1346b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PrintF("Function: %s\n", 1347b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch chunk_->info()->function()->debug_name()->ToCString().get()); 1348b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1349b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PrintF("Value %d used before first definition!\n", operand_index); 1350b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = LiveRangeFor(operand_index); 1351b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch PrintF("First use is at %d\n", range->first_pos()->pos().Value()); 1352b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch iterator.Advance(); 1353b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1354b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!found); 1355b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1356b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 1357b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1358b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1359b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < live_ranges_.length(); ++i) { 1360b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (live_ranges_[i] != NULL) { 1361b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch live_ranges_[i]->kind_ = RequiredRegisterKind(live_ranges_[i]->id()); 1362b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1363b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1364b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1365b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1366b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1367b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::SafePointsAreInOrder() const { 1368b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); 1369b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = 0; 1370b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < pointer_maps->length(); ++i) { 1371b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(i); 1372b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point > map->lithium_position()) return false; 1373b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point = map->lithium_position(); 1374b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1375b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1376b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1377b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1378b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1379b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::PopulatePointerMaps() { 1380b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Populate pointer maps", this); 1381b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); 1382b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1383b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(SafePointsAreInOrder()); 1384b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1385b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Iterate over all safe point positions and record a pointer 1386b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // for all spilled live ranges at this point. 1387b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int first_safe_point_index = 0; 1388b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int last_range_start = 0; 1389b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { 1390b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = live_ranges()->at(range_idx); 1391b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL) continue; 1392b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Iterate over the first parts of multi-part live ranges. 1393b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->parent() != NULL) continue; 1394b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Skip non-pointer values. 1395b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!HasTaggedValue(range->id())) continue; 1396b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Skip empty live ranges. 1397b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsEmpty()) continue; 1398b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1399b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the extent of the range and its children. 1400b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int start = range->Start().InstructionIndex(); 1401b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int end = 0; 1402b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (LiveRange* cur = range; cur != NULL; cur = cur->next()) { 1403b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition this_end = cur->End(); 1404b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (this_end.InstructionIndex() > end) end = this_end.InstructionIndex(); 1405b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(cur->Start().InstructionIndex() >= start); 1406b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1407b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1408b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Most of the ranges are in order, but not all. Keep an eye on when 1409b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // they step backwards and reset the first_safe_point_index so we don't 1410b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // miss any safe points. 1411b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start < last_range_start) { 1412b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_safe_point_index = 0; 1413b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1414b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch last_range_start = start; 1415b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1416b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Step across all the safe points that are before the start of this range, 1417b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // recording how far we step in order to save doing this for the next range. 1418b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (first_safe_point_index < pointer_maps->length()) { 1419b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(first_safe_point_index); 1420b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = map->lithium_position(); 1421b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point >= start) break; 1422b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first_safe_point_index++; 1423b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1424b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1425b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Step through the safe points to see whether they are in the range. 1426b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int safe_point_index = first_safe_point_index; 1427b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point_index < pointer_maps->length(); 1428b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ++safe_point_index) { 1429b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LPointerMap* map = pointer_maps->at(safe_point_index); 1430b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int safe_point = map->lithium_position(); 1431b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1432b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The safe points are sorted so we can stop searching here. 1433b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (safe_point - 1 > end) break; 1434b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1435b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Advance to the next active range that covers the current 1436b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // safe point position. 1437b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition safe_point_pos = 1438b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(safe_point); 1439b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur = range; 1440b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (cur != NULL && !cur->Covers(safe_point_pos)) { 1441b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur = cur->next(); 1442b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1443b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur == NULL) continue; 1444b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1445b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Check if the live range is spilled and the safe point is after 1446b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the spill position. 1447b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->HasAllocatedSpillOperand() && 1448b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch safe_point >= range->spill_start_index()) { 1449b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Pointer for range %d (spilled at %d) at safe point %d\n", 1450b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->id(), range->spill_start_index(), safe_point); 1451b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch map->RecordPointer(range->GetSpillOperand(), chunk()->zone()); 1452b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1453b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1454b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!cur->IsSpilled()) { 1455b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Pointer in register for range %d (start at %d) " 1456b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch "at safe point %d\n", 1457b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur->id(), cur->Start().Value(), safe_point); 1458b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* operand = cur->CreateAssignedOperand(chunk()->zone()); 1459b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!operand->IsStackSlot()); 1460b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch map->RecordPointer(operand, chunk()->zone()); 1461b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1462b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1463b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1464b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1465b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1466b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1467b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateGeneralRegisters() { 1468b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LAllocatorPhase phase("L_Allocate general registers", this); 1469b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch num_registers_ = Register::NumAllocatableRegisters(); 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); 1477b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch num_registers_ = DoubleRegister::NumAllocatableRegisters(); 1478b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch mode_ = DOUBLE_REGISTERS; 1479b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AllocateRegisters(); 1480b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1481b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1482b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1483b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateRegisters() { 1484b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(unhandled_live_ranges_.is_empty()); 1485b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1486b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges_.length(); ++i) { 1487b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (live_ranges_[i] != NULL) { 1488b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (live_ranges_[i]->Kind() == mode_) { 1489b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledUnsorted(live_ranges_[i]); 1490b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1491b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1492b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1493b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SortUnhandled(); 1494b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1495b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1496b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(reusable_slots_.is_empty()); 1497b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(active_live_ranges_.is_empty()); 1498b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(inactive_live_ranges_.is_empty()); 1499b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1500b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (mode_ == DOUBLE_REGISTERS) { 1501b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < DoubleRegister::NumAllocatableRegisters(); ++i) { 1502b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = fixed_double_live_ranges_.at(i); 1503b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) { 1504b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToInactive(current); 1505b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1506b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1507b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1508b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(mode_ == GENERAL_REGISTERS); 1509b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < fixed_live_ranges_.length(); ++i) { 1510b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = fixed_live_ranges_.at(i); 1511b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) { 1512b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToInactive(current); 1513b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1514b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1515b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1516b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1517b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (!unhandled_live_ranges_.is_empty()) { 1518b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1519b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = unhandled_live_ranges_.RemoveLast(); 1520b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1521b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition position = current->Start(); 1522b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifdef DEBUG 1523b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocation_finger_ = position; 1524b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 1525b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Processing interval %d start=%d\n", 1526b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id(), 1527b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch position.Value()); 1528b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1529b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current->HasAllocatedSpillOperand()) { 1530b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Live range %d already has a spill operand\n", current->id()); 1531b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_pos = position; 15321e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block if (IsGapAt(next_pos.InstructionIndex())) { 1533b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_pos = next_pos.NextInstruction(); 1534b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1535b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* pos = current->NextUsePositionRegisterIsBeneficial(next_pos); 1536b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // If the range already has a spill operand and it doesn't need a 1537b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // register immediately, split it and spill the first part of the range. 1538b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos == NULL) { 1539b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(current); 1540b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 1541b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (pos->pos().Value() > 1542b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->Start().NextInstruction().Value()) { 1543b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Do not spill live range eagerly if use position that can benefit from 1544b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the register is too close to the start of live range. 1545b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(current, current->Start(), pos->pos()); 15463ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 1547b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1548b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch continue; 1549b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1550b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1551b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1552b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1553b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_active = active_live_ranges_.at(i); 1554b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_active->End().Value() <= position.Value()) { 1555b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ActiveToHandled(cur_active); 1556b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // The live range was removed from the list of active live ranges. 1557b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (!cur_active->Covers(position)) { 1558b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ActiveToInactive(cur_active); 1559b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // The live range was removed from the list of active live ranges. 1560b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1561b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1562b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1563b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1564b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_inactive = inactive_live_ranges_.at(i); 1565b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (cur_inactive->End().Value() <= position.Value()) { 1566b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InactiveToHandled(cur_inactive); 1567b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // Live range was removed from the list of inactive live ranges. 1568b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else if (cur_inactive->Covers(position)) { 1569b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InactiveToActive(cur_inactive); 1570b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; // Live range was removed from the list of inactive live ranges. 1571b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1572b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1573b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1574b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!current->HasRegisterAssigned() && !current->IsSpilled()); 1575b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1576b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool result = TryAllocateFreeReg(current); 15773ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 15783ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 15793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!result) AllocateBlockedReg(current); 15803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 1581b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1582b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current->HasRegisterAssigned()) { 1583b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToActive(current); 1584b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1585b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1586b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 158744f0eee88ff00398ff7f715fab053374d808c90dSteve Block reusable_slots_.Rewind(0); 158844f0eee88ff00398ff7f715fab053374d808c90dSteve Block active_live_ranges_.Rewind(0); 158944f0eee88ff00398ff7f715fab053374d808c90dSteve Block inactive_live_ranges_.Rewind(0); 1590b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1591b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1592b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1593b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochconst char* LAllocator::RegisterName(int allocation_index) { 1594b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (mode_ == GENERAL_REGISTERS) { 1595b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return Register::AllocationIndexToString(allocation_index); 1596b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1597b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return DoubleRegister::AllocationIndexToString(allocation_index); 1598b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1599b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1600b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1601b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1602b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::TraceAlloc(const char* msg, ...) { 1603b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (FLAG_trace_alloc) { 1604b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch va_list arguments; 1605b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch va_start(arguments, msg); 1606b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch base::OS::VPrint(msg, arguments); 1607b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch va_end(arguments); 1608b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1609b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1610b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1611b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1612b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::HasTaggedValue(int virtual_register) const { 16131e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block HValue* value = graph_->LookupValue(virtual_register); 1614b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (value == NULL) return false; 1615b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return value->representation().IsTagged() && !value->type().IsSmi(); 1616b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1617b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1618b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1619b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochRegisterKind LAllocator::RequiredRegisterKind(int virtual_register) const { 16209fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (virtual_register < first_artificial_register_) { 16211e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block HValue* value = graph_->LookupValue(virtual_register); 16229fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (value != NULL && value->representation().IsDouble()) { 16239fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block return DOUBLE_REGISTERS; 16249fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 16259fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } else if (double_artificial_registers_.Contains( 16269fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block virtual_register - first_artificial_register_)) { 1627b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return DOUBLE_REGISTERS; 1628b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 16299fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 1630b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return GENERAL_REGISTERS; 1631b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1632b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1633b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1634b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToActive(LiveRange* range) { 1635b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to active\n", range->id()); 1636b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch active_live_ranges_.Add(range, zone()); 1637b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1638b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1639b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1640b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToInactive(LiveRange* range) { 1641b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to inactive\n", range->id()); 1642b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inactive_live_ranges_.Add(range, zone()); 1643b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1644b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1645b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1646b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToUnhandledSorted(LiveRange* range) { 1647b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL || range->IsEmpty()) return; 1648b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); 1649b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(allocation_finger_.Value() <= range->Start().Value()); 1650b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = unhandled_live_ranges_.length() - 1; i >= 0; --i) { 1651b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_range = unhandled_live_ranges_.at(i); 1652b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->ShouldBeAllocatedBefore(cur_range)) { 1653b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled at %d\n", range->id(), i + 1); 1654b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unhandled_live_ranges_.InsertAt(i + 1, range, zone()); 1655b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1656b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1657b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1658b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1659b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled at start\n", range->id()); 1660b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unhandled_live_ranges_.InsertAt(0, range, zone()); 1661b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(UnhandledIsSorted()); 1662b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1663b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1664b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1665b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AddToUnhandledUnsorted(LiveRange* range) { 1666b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range == NULL || range->IsEmpty()) return; 1667b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); 1668b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Add live range %d to unhandled unsorted at end\n", range->id()); 1669b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unhandled_live_ranges_.Add(range, zone()); 1670b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1671b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1672b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1673b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochstatic int UnhandledSortHelper(LiveRange* const* a, LiveRange* const* b) { 1674b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!(*a)->ShouldBeAllocatedBefore(*b) || 1675b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch !(*b)->ShouldBeAllocatedBefore(*a)); 1676b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if ((*a)->ShouldBeAllocatedBefore(*b)) return 1; 1677b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if ((*b)->ShouldBeAllocatedBefore(*a)) return -1; 1678b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return (*a)->id() - (*b)->id(); 1679b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1680b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1681b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1682b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// Sort the unhandled live ranges so that the ranges to be processed first are 1683b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// at the end of the array list. This is convenient for the register allocation 1684b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// algorithm because it is efficient to remove elements from the end. 1685b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SortUnhandled() { 1686b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Sort unhandled\n"); 1687b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch unhandled_live_ranges_.Sort(&UnhandledSortHelper); 1688b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1689b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1690b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1691b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::UnhandledIsSorted() { 1692b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int len = unhandled_live_ranges_.length(); 1693b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < len; i++) { 1694b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* a = unhandled_live_ranges_.at(i - 1); 1695b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* b = unhandled_live_ranges_.at(i); 1696b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (a->Start().Value() < b->Start().Value()) return false; 1697b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1698b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1699b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1700b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1701b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1702b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::FreeSpillSlot(LiveRange* range) { 1703b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Check that we are the last range. 1704b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->next() != NULL) return; 1705b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1706b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!range->TopLevel()->HasAllocatedSpillOperand()) return; 1707b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1708b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int index = range->TopLevel()->GetSpillOperand()->index(); 1709b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (index >= 0) { 1710b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch reusable_slots_.Add(range, zone()); 1711b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1712b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1713b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1714b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1715b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLOperand* LAllocator::TryReuseSpillSlot(LiveRange* range) { 1716b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (reusable_slots_.is_empty()) return NULL; 1717b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (reusable_slots_.first()->End().Value() > 1718b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->TopLevel()->Start().Value()) { 1719b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return NULL; 1720b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1721b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* result = reusable_slots_.first()->TopLevel()->GetSpillOperand(); 1722b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch reusable_slots_.Remove(0); 1723b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 1724b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1725b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1726b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1727b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ActiveToHandled(LiveRange* range) { 1728b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(active_live_ranges_.Contains(range)); 1729b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch active_live_ranges_.RemoveElement(range); 1730b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from active to handled\n", range->id()); 1731b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch FreeSpillSlot(range); 1732b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1733b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1734b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1735b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::ActiveToInactive(LiveRange* range) { 1736b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(active_live_ranges_.Contains(range)); 1737b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch active_live_ranges_.RemoveElement(range); 1738b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inactive_live_ranges_.Add(range, zone()); 1739b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from active to inactive\n", range->id()); 1740b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1741b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1742b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1743b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::InactiveToHandled(LiveRange* range) { 1744b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(inactive_live_ranges_.Contains(range)); 1745b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inactive_live_ranges_.RemoveElement(range); 1746b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); 1747b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch FreeSpillSlot(range); 1748b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1749b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1750b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1751b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::InactiveToActive(LiveRange* range) { 1752b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(inactive_live_ranges_.Contains(range)); 1753b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch inactive_live_ranges_.RemoveElement(range); 1754b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch active_live_ranges_.Add(range, zone()); 1755b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Moving live range %d from inactive to active\n", range->id()); 1756b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1757b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1758b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1759b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// TryAllocateFreeReg and AllocateBlockedReg assume this 1760b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// when allocating local arrays. 1761b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochSTATIC_ASSERT(DoubleRegister::kMaxNumAllocatableRegisters >= 1762b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Register::kMaxNumAllocatableRegisters); 1763b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1764b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1765b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::TryAllocateFreeReg(LiveRange* current) { 1766b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition free_until_pos[DoubleRegister::kMaxNumAllocatableRegisters]; 1767b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1768b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < num_registers_; i++) { 1769b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[i] = LifetimePosition::MaxPosition(); 1770b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1771b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1772b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1773b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_active = active_live_ranges_.at(i); 1774b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[cur_active->assigned_register()] = 1775b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(0); 1776b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1777b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1778b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1779b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* cur_inactive = inactive_live_ranges_.at(i); 1780b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(cur_inactive->End().Value() > current->Start().Value()); 1781b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = 1782b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch cur_inactive->FirstIntersection(current); 1783b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!next_intersection.IsValid()) continue; 1784b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = cur_inactive->assigned_register(); 1785b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection); 1786b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1787b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1788b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LOperand* hint = current->FirstHint(); 1789b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (hint != NULL && (hint->IsRegister() || hint->IsDoubleRegister())) { 1790b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int register_index = hint->index(); 1791b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TraceAlloc( 1792b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch "Found reg hint %s (free until [%d) for live range %d (end %d[).\n", 1793b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterName(register_index), 1794b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch free_until_pos[register_index].Value(), 1795b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->id(), 1796b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->End().Value()); 1797b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1798b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // The desired register is free until the end of the current live range. 1799b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (free_until_pos[register_index].Value() >= current->End().Value()) { 1800b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TraceAlloc("Assigning preferred reg %s to live range %d\n", 1801b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch RegisterName(register_index), 1802b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch current->id()); 1803b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(current, register_index); 1804b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return true; 1805b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1806b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1807b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1808b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find the register which stays free for the longest time. 1809b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int reg = 0; 1810b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < RegisterCount(); ++i) { 1811b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (free_until_pos[i].Value() > free_until_pos[reg].Value()) { 1812b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch reg = i; 1813b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1814b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1815b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1816b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos = free_until_pos[reg]; 1817b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1818b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() <= current->Start().Value()) { 1819b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All registers are blocked. 1820b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 1821b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1822b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1823b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() < current->End().Value()) { 1824b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is available at the range start but becomes blocked before 1825b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the range end. Split current at position where it becomes blocked. 18263ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* tail = SplitRangeAt(current, pos); 18273ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return false; 1828b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(tail); 1829b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1830b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1831b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1832b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is available at the range start and is free until 1833b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // the range end. 1834b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pos.Value() >= current->End().Value()); 1835b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Assigning free reg %s to live range %d\n", 1836b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterName(reg), 1837b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id()); 1838b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(current, reg); 1839b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1840b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 1841b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1842b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1843b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1844b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::AllocateBlockedReg(LiveRange* current) { 1845b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* register_use = current->NextRegisterPosition(current->Start()); 1846b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (register_use == NULL) { 1847b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // There is no use in the current live range that requires a register. 1848b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We can just spill it. 1849b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(current); 1850b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1851b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1852b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1853b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1854b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition use_pos[DoubleRegister::kMaxNumAllocatableRegisters]; 1855b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition block_pos[DoubleRegister::kMaxNumAllocatableRegisters]; 1856b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1857b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < num_registers_; i++) { 1858b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[i] = block_pos[i] = LifetimePosition::MaxPosition(); 1859b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1860b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1861b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1862b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = active_live_ranges_[i]; 1863b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = range->assigned_register(); 1864b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsFixed() || !range->CanBeSpilled(current->Start())) { 1865b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[cur_reg] = use_pos[cur_reg] = 1866b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition::FromInstructionIndex(0); 1867b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1868b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_use = range->NextUsePositionRegisterIsBeneficial( 1869b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->Start()); 1870b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_use == NULL) { 1871b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = range->End(); 1872b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1873b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = next_use->pos(); 1874b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1875b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1876b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1877b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1878b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1879b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = inactive_live_ranges_.at(i); 1880b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(range->End().Value() > current->Start().Value()); 1881b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = range->FirstIntersection(current); 1882b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!next_intersection.IsValid()) continue; 1883b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int cur_reg = range->assigned_register(); 1884b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->IsFixed()) { 1885b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection); 1886b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]); 1887b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1888b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection); 1889b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1890b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1891b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1892b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int reg = 0; 1893b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 1; i < RegisterCount(); ++i) { 1894b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (use_pos[i].Value() > use_pos[reg].Value()) { 1895b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch reg = i; 1896b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1897b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1898b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1899b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition pos = use_pos[reg]; 1900b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1901b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() < register_use->pos().Value()) { 1902b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // All registers are blocked before the first use that requires a register. 1903b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Spill starting part of live range up to that use. 1904b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(current, current->Start(), register_use->pos()); 1905b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return; 1906b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1907b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1908b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (block_pos[reg].Value() < current->End().Value()) { 1909b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register becomes blocked before the current range end. Split before that 1910b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // position. 1911b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* tail = SplitBetween(current, 1912b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->Start(), 1913b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block_pos[reg].InstructionStart()); 1914b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 1915b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(tail); 1916b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1917b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1918b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Register reg is not blocked for the whole range. 1919b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(block_pos[reg].Value() >= current->End().Value()); 1920b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Assigning blocked reg %s to live range %d\n", 1921b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch RegisterName(reg), 1922b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch current->id()); 1923b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SetLiveRangeAssignedRegister(current, reg); 1924b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1925b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // This register was not free. Thus we need to find and spill 1926b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // parts of active and inactive live regions that use the same register 1927b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // at the same lifetime positions as current. 1928b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SplitAndSpillIntersecting(current); 1929b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 1930b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1931b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1932b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochLifetimePosition LAllocator::FindOptimalSpillingPos(LiveRange* range, 1933b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition pos) { 1934b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block = GetBlock(pos.InstructionStart()); 1935b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* loop_header = 1936b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block->IsLoopHeader() ? block : block->parent_loop_header(); 1937b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1938b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (loop_header == NULL) return pos; 1939b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1940b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UsePosition* prev_use = 1941b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->PreviousUsePositionRegisterIsBeneficial(pos); 1942b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1943b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (loop_header != NULL) { 1944b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // We are going to spill live range inside the loop. 1945b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If possible try to move spilling position backwards to loop header. 1946b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This will reduce number of memory moves on the back edge. 1947b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition loop_start = LifetimePosition::FromInstructionIndex( 1948b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch loop_header->first_instruction_index()); 1949b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1950b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (range->Covers(loop_start)) { 1951b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (prev_use == NULL || prev_use->pos().Value() < loop_start.Value()) { 1952b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // No register beneficial use inside the loop before the pos. 1953b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch pos = loop_start; 1954b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1955b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1956b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1957b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Try hoisting out to an outer loop. 1958b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch loop_header = loop_header->parent_loop_header(); 1959b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 1960b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1961b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return pos; 1962b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 1963b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1964b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1965b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SplitAndSpillIntersecting(LiveRange* current) { 1966b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(current->HasRegisterAssigned()); 1967b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int reg = current->assigned_register(); 1968b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition split_pos = current->Start(); 1969b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < active_live_ranges_.length(); ++i) { 1970b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = active_live_ranges_[i]; 1971b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->assigned_register() == reg) { 1972b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_pos = range->NextRegisterPosition(current->Start()); 1973b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos); 1974b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_pos == NULL) { 1975b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SpillAfter(range, spill_pos); 1976b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 1977b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // When spilling between spill_pos and next_pos ensure that the range 1978b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // remains spilled at least until the start of the current live range. 1979b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This guarantees that we will not introduce new unhandled ranges that 1980b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // start before the current range as this violates allocation invariant 1981b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // and will lead to an inconsistent state of active and inactive 1982b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // live-ranges: ranges are allocated in order of their start positions, 1983b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // ranges are retired from active/inactive when the start of the 1984b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // current live-range is larger than their end. 1985b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos()); 1986b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1987b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 1988b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ActiveToHandled(range); 1989b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; 1990b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1991b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 1992b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 1993b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < inactive_live_ranges_.length(); ++i) { 1994b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* range = inactive_live_ranges_[i]; 1995b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(range->End().Value() > current->Start().Value()); 1996b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (range->assigned_register() == reg && !range->IsFixed()) { 1997b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition next_intersection = range->FirstIntersection(current); 1998b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_intersection.IsValid()) { 1999b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch UsePosition* next_pos = range->NextRegisterPosition(current->Start()); 2000b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (next_pos == NULL) { 2001b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillAfter(range, split_pos); 2002b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 2003b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch next_intersection = Min(next_intersection, next_pos->pos()); 2004b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SpillBetween(range, split_pos, next_intersection); 2005b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2006b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 2007b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch InactiveToHandled(range); 2008b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch --i; 2009b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2010b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2011b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2012b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2013b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2014b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2015b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool LAllocator::IsBlockBoundary(LifetimePosition pos) { 2016b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pos.IsInstructionStart() && 20171e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block InstructionAt(pos.InstructionIndex())->IsLabel(); 2018b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2019b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2020b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 20213ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochLiveRange* LAllocator::SplitRangeAt(LiveRange* range, LifetimePosition pos) { 2022b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->IsFixed()); 2023b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value()); 2024b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2025b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (pos.Value() <= range->Start().Value()) return range; 2026b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 20271e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block // We can't properly connect liveranges if split occured at the end 20281e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block // of control instruction. 2029b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pos.IsInstructionStart() || 20301e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block !chunk_->instructions()->at(pos.InstructionIndex())->IsControl()); 20311e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 2032b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int vreg = GetVirtualRegister(); 20333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return NULL; 2034b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LiveRange* result = LiveRangeFor(vreg); 2035b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->SplitAt(pos, result, zone()); 2036b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 2037b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2038b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2039b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2040b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLiveRange* LAllocator::SplitBetween(LiveRange* range, 2041b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 2042b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2043b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->IsFixed()); 2044b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Splitting live range %d in position between [%d, %d]\n", 2045b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch range->id(), 2046b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch start.Value(), 2047b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.Value()); 2048b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2049b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition split_pos = FindOptimalSplitPos(start, end); 2050b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(split_pos.Value() >= start.Value()); 20513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return SplitRangeAt(range, split_pos); 2052b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2053b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2054b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2055b0fe1620dcb4135ac3ab2d66ff93072373911299Ben MurdochLifetimePosition LAllocator::FindOptimalSplitPos(LifetimePosition start, 2056b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2057b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int start_instr = start.InstructionIndex(); 2058b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int end_instr = end.InstructionIndex(); 2059b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(start_instr <= end_instr); 2060b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2061b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // We have no choice 2062b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (start_instr == end_instr) return end; 2063b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2064257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch HBasicBlock* start_block = GetBlock(start); 2065257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch HBasicBlock* end_block = GetBlock(end); 2066b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2067b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (end_block == start_block) { 2068257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // The interval is split in the same basic block. Split at the latest 2069257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // possible position. 2070b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return end; 2071b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2072b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2073b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch HBasicBlock* block = end_block; 2074b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Find header of outermost loop. 2075b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch while (block->parent_loop_header() != NULL && 2076b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->parent_loop_header()->block_id() > start_block->block_id()) { 2077b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block = block->parent_loop_header(); 2078b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2079b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2080257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // We did not find any suitable outer loop. Split at the latest possible 2081257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // position unless end_block is a loop header itself. 2082257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch if (block == end_block && !end_block->IsLoopHeader()) return end; 2083b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2084b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return LifetimePosition::FromInstructionIndex( 2085b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch block->first_instruction_index()); 2086b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2087b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2088b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2089b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) { 20903ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* second_part = SplitRangeAt(range, pos); 20913ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 2092b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(second_part); 2093b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2094b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2095b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2096b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::SpillBetween(LiveRange* range, 2097b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition start, 2098b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LifetimePosition end) { 2099b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SpillBetweenUntil(range, start, start, end); 2100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 2101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid LAllocator::SpillBetweenUntil(LiveRange* range, 2104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition start, 2105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition until, 2106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LifetimePosition end) { 2107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(start.Value() < end.Value()); 21083ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LiveRange* second_part = SplitRangeAt(range, start); 21093ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (!AllocationOk()) return; 2110b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2111b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (second_part->Start().Value() < end.Value()) { 2112b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split result intersects with [start, end[. 2113b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Split it at position between ]start+1, end[, spill the middle part 2114b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // and put the rest to unhandled. 2115b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* third_part = SplitBetween( 2116b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch second_part, 2117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Max(second_part->Start().InstructionEnd(), until), 2118b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch end.PrevInstruction().InstructionEnd()); 2119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!AllocationOk()) return; 2120b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(third_part != second_part); 2122b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2123b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Spill(second_part); 2124b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(third_part); 2125b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } else { 2126b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // The split result does not intersect with [start, end[. 2127b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Nothing to spill. Just put it to unhandled as whole. 2128b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch AddToUnhandledSorted(second_part); 2129b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2130b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2131b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2132b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2133b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Spill(LiveRange* range) { 2134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!range->IsSpilled()); 2135b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch TraceAlloc("Spilling live range %d\n", range->id()); 2136b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* first = range->TopLevel(); 2137b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2138b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (!first->HasAllocatedSpillOperand()) { 2139b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LOperand* op = TryReuseSpillSlot(range); 2140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (op == NULL) op = chunk_->GetNextSpillSlot(range->Kind()); 2141b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch first->SetSpillOperand(op); 2142b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch range->MakeSpilled(chunk()->zone()); 2144b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2145b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2146b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2147b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochint LAllocator::RegisterCount() const { 2148b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return num_registers_; 2149b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2150b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2151b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2152b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#ifdef DEBUG 2153b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2154b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2155b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochvoid LAllocator::Verify() const { 2156b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < live_ranges()->length(); ++i) { 2157b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch LiveRange* current = live_ranges()->at(i); 2158b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (current != NULL) current->Verify(); 2159b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 2160b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 2161b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2162b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2163b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch#endif 2164b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2165b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 2166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochLAllocatorPhase::LAllocatorPhase(const char* name, LAllocator* allocator) 2167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : CompilationPhase(name, allocator->graph()->info()), 2168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocator_(allocator) { 2169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_hydrogen_stats) { 2170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocator_zone_start_allocation_size_ = 2171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocator->zone()->allocation_size(); 2172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 2173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 2174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochLAllocatorPhase::~LAllocatorPhase() { 2177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_hydrogen_stats) { 2178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unsigned size = allocator_->zone()->allocation_size() - 2179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch allocator_zone_start_allocation_size_; 2180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch isolate()->GetHStatistics()->SaveTiming(name(), base::TimeDelta(), size); 2181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 2182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (ShouldProduceTraceOutput()) { 2184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch isolate()->GetHTracer()->TraceLithium(name(), allocator_->chunk()); 2185b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch isolate()->GetHTracer()->TraceLiveRanges(name(), allocator_); 2186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 2187b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifdef DEBUG 2189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (allocator_ != NULL) allocator_->Verify(); 2190b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 2191b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 2192b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2193b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2194b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} } // namespace v8::internal 2195