OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/register-allocator.h" | 5 #include "src/compiler/register-allocator.h" |
6 | 6 |
7 #include "src/compiler/linkage.h" | 7 #include "src/compiler/linkage.h" |
8 #include "src/hydrogen.h" | 8 #include "src/hydrogen.h" |
9 #include "src/string-stream.h" | 9 #include "src/string-stream.h" |
10 | 10 |
(...skipping 17 matching lines...) Expand all Loading... |
28 hint_(hint), | 28 hint_(hint), |
29 pos_(pos), | 29 pos_(pos), |
30 next_(NULL), | 30 next_(NULL), |
31 requires_reg_(false), | 31 requires_reg_(false), |
32 register_beneficial_(true) { | 32 register_beneficial_(true) { |
33 if (operand_ != NULL && operand_->IsUnallocated()) { | 33 if (operand_ != NULL && operand_->IsUnallocated()) { |
34 const UnallocatedOperand* unalloc = UnallocatedOperand::cast(operand_); | 34 const UnallocatedOperand* unalloc = UnallocatedOperand::cast(operand_); |
35 requires_reg_ = unalloc->HasRegisterPolicy(); | 35 requires_reg_ = unalloc->HasRegisterPolicy(); |
36 register_beneficial_ = !unalloc->HasAnyPolicy(); | 36 register_beneficial_ = !unalloc->HasAnyPolicy(); |
37 } | 37 } |
38 ASSERT(pos_.IsValid()); | 38 DCHECK(pos_.IsValid()); |
39 } | 39 } |
40 | 40 |
41 | 41 |
42 bool UsePosition::HasHint() const { | 42 bool UsePosition::HasHint() const { |
43 return hint_ != NULL && !hint_->IsUnallocated(); | 43 return hint_ != NULL && !hint_->IsUnallocated(); |
44 } | 44 } |
45 | 45 |
46 | 46 |
47 bool UsePosition::RequiresRegister() const { return requires_reg_; } | 47 bool UsePosition::RequiresRegister() const { return requires_reg_; } |
48 | 48 |
49 | 49 |
50 bool UsePosition::RegisterIsBeneficial() const { return register_beneficial_; } | 50 bool UsePosition::RegisterIsBeneficial() const { return register_beneficial_; } |
51 | 51 |
52 | 52 |
53 void UseInterval::SplitAt(LifetimePosition pos, Zone* zone) { | 53 void UseInterval::SplitAt(LifetimePosition pos, Zone* zone) { |
54 ASSERT(Contains(pos) && pos.Value() != start().Value()); | 54 DCHECK(Contains(pos) && pos.Value() != start().Value()); |
55 UseInterval* after = new (zone) UseInterval(pos, end_); | 55 UseInterval* after = new (zone) UseInterval(pos, end_); |
56 after->next_ = next_; | 56 after->next_ = next_; |
57 next_ = after; | 57 next_ = after; |
58 end_ = pos; | 58 end_ = pos; |
59 } | 59 } |
60 | 60 |
61 | 61 |
62 #ifdef DEBUG | 62 #ifdef DEBUG |
63 | 63 |
64 | 64 |
65 void LiveRange::Verify() const { | 65 void LiveRange::Verify() const { |
66 UsePosition* cur = first_pos_; | 66 UsePosition* cur = first_pos_; |
67 while (cur != NULL) { | 67 while (cur != NULL) { |
68 ASSERT(Start().Value() <= cur->pos().Value() && | 68 DCHECK(Start().Value() <= cur->pos().Value() && |
69 cur->pos().Value() <= End().Value()); | 69 cur->pos().Value() <= End().Value()); |
70 cur = cur->next(); | 70 cur = cur->next(); |
71 } | 71 } |
72 } | 72 } |
73 | 73 |
74 | 74 |
75 bool LiveRange::HasOverlap(UseInterval* target) const { | 75 bool LiveRange::HasOverlap(UseInterval* target) const { |
76 UseInterval* current_interval = first_interval_; | 76 UseInterval* current_interval = first_interval_; |
77 while (current_interval != NULL) { | 77 while (current_interval != NULL) { |
78 // Intervals overlap if the start of one is contained in the other. | 78 // Intervals overlap if the start of one is contained in the other. |
(...skipping 23 matching lines...) Expand all Loading... |
102 parent_(NULL), | 102 parent_(NULL), |
103 next_(NULL), | 103 next_(NULL), |
104 current_interval_(NULL), | 104 current_interval_(NULL), |
105 last_processed_use_(NULL), | 105 last_processed_use_(NULL), |
106 current_hint_operand_(NULL), | 106 current_hint_operand_(NULL), |
107 spill_operand_(new (zone) InstructionOperand()), | 107 spill_operand_(new (zone) InstructionOperand()), |
108 spill_start_index_(kMaxInt) {} | 108 spill_start_index_(kMaxInt) {} |
109 | 109 |
110 | 110 |
111 void LiveRange::set_assigned_register(int reg, Zone* zone) { | 111 void LiveRange::set_assigned_register(int reg, Zone* zone) { |
112 ASSERT(!HasRegisterAssigned() && !IsSpilled()); | 112 DCHECK(!HasRegisterAssigned() && !IsSpilled()); |
113 assigned_register_ = reg; | 113 assigned_register_ = reg; |
114 ConvertOperands(zone); | 114 ConvertOperands(zone); |
115 } | 115 } |
116 | 116 |
117 | 117 |
118 void LiveRange::MakeSpilled(Zone* zone) { | 118 void LiveRange::MakeSpilled(Zone* zone) { |
119 ASSERT(!IsSpilled()); | 119 DCHECK(!IsSpilled()); |
120 ASSERT(TopLevel()->HasAllocatedSpillOperand()); | 120 DCHECK(TopLevel()->HasAllocatedSpillOperand()); |
121 spilled_ = true; | 121 spilled_ = true; |
122 assigned_register_ = kInvalidAssignment; | 122 assigned_register_ = kInvalidAssignment; |
123 ConvertOperands(zone); | 123 ConvertOperands(zone); |
124 } | 124 } |
125 | 125 |
126 | 126 |
127 bool LiveRange::HasAllocatedSpillOperand() const { | 127 bool LiveRange::HasAllocatedSpillOperand() const { |
128 ASSERT(spill_operand_ != NULL); | 128 DCHECK(spill_operand_ != NULL); |
129 return !spill_operand_->IsIgnored(); | 129 return !spill_operand_->IsIgnored(); |
130 } | 130 } |
131 | 131 |
132 | 132 |
133 void LiveRange::SetSpillOperand(InstructionOperand* operand) { | 133 void LiveRange::SetSpillOperand(InstructionOperand* operand) { |
134 ASSERT(!operand->IsUnallocated()); | 134 DCHECK(!operand->IsUnallocated()); |
135 ASSERT(spill_operand_ != NULL); | 135 DCHECK(spill_operand_ != NULL); |
136 ASSERT(spill_operand_->IsIgnored()); | 136 DCHECK(spill_operand_->IsIgnored()); |
137 spill_operand_->ConvertTo(operand->kind(), operand->index()); | 137 spill_operand_->ConvertTo(operand->kind(), operand->index()); |
138 } | 138 } |
139 | 139 |
140 | 140 |
141 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) { | 141 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) { |
142 UsePosition* use_pos = last_processed_use_; | 142 UsePosition* use_pos = last_processed_use_; |
143 if (use_pos == NULL) use_pos = first_pos(); | 143 if (use_pos == NULL) use_pos = first_pos(); |
144 while (use_pos != NULL && use_pos->pos().Value() < start.Value()) { | 144 while (use_pos != NULL && use_pos->pos().Value() < start.Value()) { |
145 use_pos = use_pos->next(); | 145 use_pos = use_pos->next(); |
146 } | 146 } |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
186 UsePosition* use_pos = NextRegisterPosition(pos); | 186 UsePosition* use_pos = NextRegisterPosition(pos); |
187 if (use_pos == NULL) return true; | 187 if (use_pos == NULL) return true; |
188 return use_pos->pos().Value() > | 188 return use_pos->pos().Value() > |
189 pos.NextInstruction().InstructionEnd().Value(); | 189 pos.NextInstruction().InstructionEnd().Value(); |
190 } | 190 } |
191 | 191 |
192 | 192 |
193 InstructionOperand* LiveRange::CreateAssignedOperand(Zone* zone) { | 193 InstructionOperand* LiveRange::CreateAssignedOperand(Zone* zone) { |
194 InstructionOperand* op = NULL; | 194 InstructionOperand* op = NULL; |
195 if (HasRegisterAssigned()) { | 195 if (HasRegisterAssigned()) { |
196 ASSERT(!IsSpilled()); | 196 DCHECK(!IsSpilled()); |
197 switch (Kind()) { | 197 switch (Kind()) { |
198 case GENERAL_REGISTERS: | 198 case GENERAL_REGISTERS: |
199 op = RegisterOperand::Create(assigned_register(), zone); | 199 op = RegisterOperand::Create(assigned_register(), zone); |
200 break; | 200 break; |
201 case DOUBLE_REGISTERS: | 201 case DOUBLE_REGISTERS: |
202 op = DoubleRegisterOperand::Create(assigned_register(), zone); | 202 op = DoubleRegisterOperand::Create(assigned_register(), zone); |
203 break; | 203 break; |
204 default: | 204 default: |
205 UNREACHABLE(); | 205 UNREACHABLE(); |
206 } | 206 } |
207 } else if (IsSpilled()) { | 207 } else if (IsSpilled()) { |
208 ASSERT(!HasRegisterAssigned()); | 208 DCHECK(!HasRegisterAssigned()); |
209 op = TopLevel()->GetSpillOperand(); | 209 op = TopLevel()->GetSpillOperand(); |
210 ASSERT(!op->IsUnallocated()); | 210 DCHECK(!op->IsUnallocated()); |
211 } else { | 211 } else { |
212 UnallocatedOperand* unalloc = | 212 UnallocatedOperand* unalloc = |
213 new (zone) UnallocatedOperand(UnallocatedOperand::NONE); | 213 new (zone) UnallocatedOperand(UnallocatedOperand::NONE); |
214 unalloc->set_virtual_register(id_); | 214 unalloc->set_virtual_register(id_); |
215 op = unalloc; | 215 op = unalloc; |
216 } | 216 } |
217 return op; | 217 return op; |
218 } | 218 } |
219 | 219 |
220 | 220 |
(...skipping 16 matching lines...) Expand all Loading... |
237 ? LifetimePosition::Invalid() | 237 ? LifetimePosition::Invalid() |
238 : current_interval_->start(); | 238 : current_interval_->start(); |
239 if (to_start_of->start().Value() > start.Value()) { | 239 if (to_start_of->start().Value() > start.Value()) { |
240 current_interval_ = to_start_of; | 240 current_interval_ = to_start_of; |
241 } | 241 } |
242 } | 242 } |
243 | 243 |
244 | 244 |
245 void LiveRange::SplitAt(LifetimePosition position, LiveRange* result, | 245 void LiveRange::SplitAt(LifetimePosition position, LiveRange* result, |
246 Zone* zone) { | 246 Zone* zone) { |
247 ASSERT(Start().Value() < position.Value()); | 247 DCHECK(Start().Value() < position.Value()); |
248 ASSERT(result->IsEmpty()); | 248 DCHECK(result->IsEmpty()); |
249 // Find the last interval that ends before the position. If the | 249 // Find the last interval that ends before the position. If the |
250 // position is contained in one of the intervals in the chain, we | 250 // position is contained in one of the intervals in the chain, we |
251 // split that interval and use the first part. | 251 // split that interval and use the first part. |
252 UseInterval* current = FirstSearchIntervalForPosition(position); | 252 UseInterval* current = FirstSearchIntervalForPosition(position); |
253 | 253 |
254 // If the split position coincides with the beginning of a use interval | 254 // If the split position coincides with the beginning of a use interval |
255 // we need to split use positons in a special way. | 255 // we need to split use positons in a special way. |
256 bool split_at_start = false; | 256 bool split_at_start = false; |
257 | 257 |
258 if (current->start().Value() == position.Value()) { | 258 if (current->start().Value() == position.Value()) { |
(...skipping 85 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
344 if (other_pos == NULL) return true; | 344 if (other_pos == NULL) return true; |
345 return pos->pos().Value() < other_pos->pos().Value(); | 345 return pos->pos().Value() < other_pos->pos().Value(); |
346 } | 346 } |
347 return start.Value() < other_start.Value(); | 347 return start.Value() < other_start.Value(); |
348 } | 348 } |
349 | 349 |
350 | 350 |
351 void LiveRange::ShortenTo(LifetimePosition start) { | 351 void LiveRange::ShortenTo(LifetimePosition start) { |
352 RegisterAllocator::TraceAlloc("Shorten live range %d to [%d\n", id_, | 352 RegisterAllocator::TraceAlloc("Shorten live range %d to [%d\n", id_, |
353 start.Value()); | 353 start.Value()); |
354 ASSERT(first_interval_ != NULL); | 354 DCHECK(first_interval_ != NULL); |
355 ASSERT(first_interval_->start().Value() <= start.Value()); | 355 DCHECK(first_interval_->start().Value() <= start.Value()); |
356 ASSERT(start.Value() < first_interval_->end().Value()); | 356 DCHECK(start.Value() < first_interval_->end().Value()); |
357 first_interval_->set_start(start); | 357 first_interval_->set_start(start); |
358 } | 358 } |
359 | 359 |
360 | 360 |
361 void LiveRange::EnsureInterval(LifetimePosition start, LifetimePosition end, | 361 void LiveRange::EnsureInterval(LifetimePosition start, LifetimePosition end, |
362 Zone* zone) { | 362 Zone* zone) { |
363 RegisterAllocator::TraceAlloc("Ensure live range %d in interval [%d %d[\n", | 363 RegisterAllocator::TraceAlloc("Ensure live range %d in interval [%d %d[\n", |
364 id_, start.Value(), end.Value()); | 364 id_, start.Value(), end.Value()); |
365 LifetimePosition new_end = end; | 365 LifetimePosition new_end = end; |
366 while (first_interval_ != NULL && | 366 while (first_interval_ != NULL && |
(...skipping 25 matching lines...) Expand all Loading... |
392 if (end.Value() == first_interval_->start().Value()) { | 392 if (end.Value() == first_interval_->start().Value()) { |
393 first_interval_->set_start(start); | 393 first_interval_->set_start(start); |
394 } else if (end.Value() < first_interval_->start().Value()) { | 394 } else if (end.Value() < first_interval_->start().Value()) { |
395 UseInterval* interval = new (zone) UseInterval(start, end); | 395 UseInterval* interval = new (zone) UseInterval(start, end); |
396 interval->set_next(first_interval_); | 396 interval->set_next(first_interval_); |
397 first_interval_ = interval; | 397 first_interval_ = interval; |
398 } else { | 398 } else { |
399 // Order of instruction's processing (see ProcessInstructions) guarantees | 399 // Order of instruction's processing (see ProcessInstructions) guarantees |
400 // that each new use interval either precedes or intersects with | 400 // that each new use interval either precedes or intersects with |
401 // last added interval. | 401 // last added interval. |
402 ASSERT(start.Value() < first_interval_->end().Value()); | 402 DCHECK(start.Value() < first_interval_->end().Value()); |
403 first_interval_->start_ = Min(start, first_interval_->start_); | 403 first_interval_->start_ = Min(start, first_interval_->start_); |
404 first_interval_->end_ = Max(end, first_interval_->end_); | 404 first_interval_->end_ = Max(end, first_interval_->end_); |
405 } | 405 } |
406 } | 406 } |
407 } | 407 } |
408 | 408 |
409 | 409 |
410 void LiveRange::AddUsePosition(LifetimePosition pos, | 410 void LiveRange::AddUsePosition(LifetimePosition pos, |
411 InstructionOperand* operand, | 411 InstructionOperand* operand, |
412 InstructionOperand* hint, Zone* zone) { | 412 InstructionOperand* hint, Zone* zone) { |
(...skipping 20 matching lines...) Expand all Loading... |
433 if (prev_hint == NULL && use_pos->HasHint()) { | 433 if (prev_hint == NULL && use_pos->HasHint()) { |
434 current_hint_operand_ = hint; | 434 current_hint_operand_ = hint; |
435 } | 435 } |
436 } | 436 } |
437 | 437 |
438 | 438 |
439 void LiveRange::ConvertOperands(Zone* zone) { | 439 void LiveRange::ConvertOperands(Zone* zone) { |
440 InstructionOperand* op = CreateAssignedOperand(zone); | 440 InstructionOperand* op = CreateAssignedOperand(zone); |
441 UsePosition* use_pos = first_pos(); | 441 UsePosition* use_pos = first_pos(); |
442 while (use_pos != NULL) { | 442 while (use_pos != NULL) { |
443 ASSERT(Start().Value() <= use_pos->pos().Value() && | 443 DCHECK(Start().Value() <= use_pos->pos().Value() && |
444 use_pos->pos().Value() <= End().Value()); | 444 use_pos->pos().Value() <= End().Value()); |
445 | 445 |
446 if (use_pos->HasOperand()) { | 446 if (use_pos->HasOperand()) { |
447 ASSERT(op->IsRegister() || op->IsDoubleRegister() || | 447 DCHECK(op->IsRegister() || op->IsDoubleRegister() || |
448 !use_pos->RequiresRegister()); | 448 !use_pos->RequiresRegister()); |
449 use_pos->operand()->ConvertTo(op->kind(), op->index()); | 449 use_pos->operand()->ConvertTo(op->kind(), op->index()); |
450 } | 450 } |
451 use_pos = use_pos->next(); | 451 use_pos = use_pos->next(); |
452 } | 452 } |
453 } | 453 } |
454 | 454 |
455 | 455 |
456 bool LiveRange::CanCover(LifetimePosition position) const { | 456 bool LiveRange::CanCover(LifetimePosition position) const { |
457 if (IsEmpty()) return false; | 457 if (IsEmpty()) return false; |
458 return Start().Value() <= position.Value() && | 458 return Start().Value() <= position.Value() && |
459 position.Value() < End().Value(); | 459 position.Value() < End().Value(); |
460 } | 460 } |
461 | 461 |
462 | 462 |
463 bool LiveRange::Covers(LifetimePosition position) { | 463 bool LiveRange::Covers(LifetimePosition position) { |
464 if (!CanCover(position)) return false; | 464 if (!CanCover(position)) return false; |
465 UseInterval* start_search = FirstSearchIntervalForPosition(position); | 465 UseInterval* start_search = FirstSearchIntervalForPosition(position); |
466 for (UseInterval* interval = start_search; interval != NULL; | 466 for (UseInterval* interval = start_search; interval != NULL; |
467 interval = interval->next()) { | 467 interval = interval->next()) { |
468 ASSERT(interval->next() == NULL || | 468 DCHECK(interval->next() == NULL || |
469 interval->next()->start().Value() >= interval->start().Value()); | 469 interval->next()->start().Value() >= interval->start().Value()); |
470 AdvanceLastProcessedMarker(interval, position); | 470 AdvanceLastProcessedMarker(interval, position); |
471 if (interval->Contains(position)) return true; | 471 if (interval->Contains(position)) return true; |
472 if (interval->start().Value() > position.Value()) return false; | 472 if (interval->start().Value() > position.Value()) return false; |
473 } | 473 } |
474 return false; | 474 return false; |
475 } | 475 } |
476 | 476 |
477 | 477 |
478 LifetimePosition LiveRange::FirstIntersection(LiveRange* other) { | 478 LifetimePosition LiveRange::FirstIntersection(LiveRange* other) { |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
535 i != successors.end(); ++i) { | 535 i != successors.end(); ++i) { |
536 // Add values live on entry to the successor. Note the successor's | 536 // Add values live on entry to the successor. Note the successor's |
537 // live_in will not be computed yet for backwards edges. | 537 // live_in will not be computed yet for backwards edges. |
538 BasicBlock* successor = *i; | 538 BasicBlock* successor = *i; |
539 BitVector* live_in = live_in_sets_[successor->rpo_number_]; | 539 BitVector* live_in = live_in_sets_[successor->rpo_number_]; |
540 if (live_in != NULL) live_out->Union(*live_in); | 540 if (live_in != NULL) live_out->Union(*live_in); |
541 | 541 |
542 // All phi input operands corresponding to this successor edge are live | 542 // All phi input operands corresponding to this successor edge are live |
543 // out from this block. | 543 // out from this block. |
544 int index = successor->PredecessorIndexOf(block); | 544 int index = successor->PredecessorIndexOf(block); |
545 ASSERT(index >= 0); | 545 DCHECK(index >= 0); |
546 ASSERT(index < static_cast<int>(successor->PredecessorCount())); | 546 DCHECK(index < static_cast<int>(successor->PredecessorCount())); |
547 for (BasicBlock::const_iterator j = successor->begin(); | 547 for (BasicBlock::const_iterator j = successor->begin(); |
548 j != successor->end(); ++j) { | 548 j != successor->end(); ++j) { |
549 Node* phi = *j; | 549 Node* phi = *j; |
550 if (phi->opcode() != IrOpcode::kPhi) continue; | 550 if (phi->opcode() != IrOpcode::kPhi) continue; |
551 Node* input = phi->InputAt(index); | 551 Node* input = phi->InputAt(index); |
552 live_out->Add(input->id()); | 552 live_out->Add(input->id()); |
553 } | 553 } |
554 } | 554 } |
555 | 555 |
556 return live_out; | 556 return live_out; |
(...skipping 19 matching lines...) Expand all Loading... |
576 | 576 |
577 | 577 |
578 int RegisterAllocator::FixedDoubleLiveRangeID(int index) { | 578 int RegisterAllocator::FixedDoubleLiveRangeID(int index) { |
579 return -index - 1 - Register::kMaxNumAllocatableRegisters; | 579 return -index - 1 - Register::kMaxNumAllocatableRegisters; |
580 } | 580 } |
581 | 581 |
582 | 582 |
583 InstructionOperand* RegisterAllocator::AllocateFixed( | 583 InstructionOperand* RegisterAllocator::AllocateFixed( |
584 UnallocatedOperand* operand, int pos, bool is_tagged) { | 584 UnallocatedOperand* operand, int pos, bool is_tagged) { |
585 TraceAlloc("Allocating fixed reg for op %d\n", operand->virtual_register()); | 585 TraceAlloc("Allocating fixed reg for op %d\n", operand->virtual_register()); |
586 ASSERT(operand->HasFixedPolicy()); | 586 DCHECK(operand->HasFixedPolicy()); |
587 if (operand->HasFixedSlotPolicy()) { | 587 if (operand->HasFixedSlotPolicy()) { |
588 operand->ConvertTo(InstructionOperand::STACK_SLOT, | 588 operand->ConvertTo(InstructionOperand::STACK_SLOT, |
589 operand->fixed_slot_index()); | 589 operand->fixed_slot_index()); |
590 } else if (operand->HasFixedRegisterPolicy()) { | 590 } else if (operand->HasFixedRegisterPolicy()) { |
591 int reg_index = operand->fixed_register_index(); | 591 int reg_index = operand->fixed_register_index(); |
592 operand->ConvertTo(InstructionOperand::REGISTER, reg_index); | 592 operand->ConvertTo(InstructionOperand::REGISTER, reg_index); |
593 } else if (operand->HasFixedDoubleRegisterPolicy()) { | 593 } else if (operand->HasFixedDoubleRegisterPolicy()) { |
594 int reg_index = operand->fixed_register_index(); | 594 int reg_index = operand->fixed_register_index(); |
595 operand->ConvertTo(InstructionOperand::DOUBLE_REGISTER, reg_index); | 595 operand->ConvertTo(InstructionOperand::DOUBLE_REGISTER, reg_index); |
596 } else { | 596 } else { |
597 UNREACHABLE(); | 597 UNREACHABLE(); |
598 } | 598 } |
599 if (is_tagged) { | 599 if (is_tagged) { |
600 TraceAlloc("Fixed reg is tagged at %d\n", pos); | 600 TraceAlloc("Fixed reg is tagged at %d\n", pos); |
601 Instruction* instr = InstructionAt(pos); | 601 Instruction* instr = InstructionAt(pos); |
602 if (instr->HasPointerMap()) { | 602 if (instr->HasPointerMap()) { |
603 instr->pointer_map()->RecordPointer(operand, code_zone()); | 603 instr->pointer_map()->RecordPointer(operand, code_zone()); |
604 } | 604 } |
605 } | 605 } |
606 return operand; | 606 return operand; |
607 } | 607 } |
608 | 608 |
609 | 609 |
610 LiveRange* RegisterAllocator::FixedLiveRangeFor(int index) { | 610 LiveRange* RegisterAllocator::FixedLiveRangeFor(int index) { |
611 ASSERT(index < Register::kMaxNumAllocatableRegisters); | 611 DCHECK(index < Register::kMaxNumAllocatableRegisters); |
612 LiveRange* result = fixed_live_ranges_[index]; | 612 LiveRange* result = fixed_live_ranges_[index]; |
613 if (result == NULL) { | 613 if (result == NULL) { |
614 // TODO(titzer): add a utility method to allocate a new LiveRange: | 614 // TODO(titzer): add a utility method to allocate a new LiveRange: |
615 // The LiveRange object itself can go in this zone, but the | 615 // The LiveRange object itself can go in this zone, but the |
616 // InstructionOperand needs | 616 // InstructionOperand needs |
617 // to go in the code zone, since it may survive register allocation. | 617 // to go in the code zone, since it may survive register allocation. |
618 result = new (zone()) LiveRange(FixedLiveRangeID(index), code_zone()); | 618 result = new (zone()) LiveRange(FixedLiveRangeID(index), code_zone()); |
619 ASSERT(result->IsFixed()); | 619 DCHECK(result->IsFixed()); |
620 result->kind_ = GENERAL_REGISTERS; | 620 result->kind_ = GENERAL_REGISTERS; |
621 SetLiveRangeAssignedRegister(result, index); | 621 SetLiveRangeAssignedRegister(result, index); |
622 fixed_live_ranges_[index] = result; | 622 fixed_live_ranges_[index] = result; |
623 } | 623 } |
624 return result; | 624 return result; |
625 } | 625 } |
626 | 626 |
627 | 627 |
628 LiveRange* RegisterAllocator::FixedDoubleLiveRangeFor(int index) { | 628 LiveRange* RegisterAllocator::FixedDoubleLiveRangeFor(int index) { |
629 ASSERT(index < DoubleRegister::NumAllocatableRegisters()); | 629 DCHECK(index < DoubleRegister::NumAllocatableRegisters()); |
630 LiveRange* result = fixed_double_live_ranges_[index]; | 630 LiveRange* result = fixed_double_live_ranges_[index]; |
631 if (result == NULL) { | 631 if (result == NULL) { |
632 result = new (zone()) LiveRange(FixedDoubleLiveRangeID(index), code_zone()); | 632 result = new (zone()) LiveRange(FixedDoubleLiveRangeID(index), code_zone()); |
633 ASSERT(result->IsFixed()); | 633 DCHECK(result->IsFixed()); |
634 result->kind_ = DOUBLE_REGISTERS; | 634 result->kind_ = DOUBLE_REGISTERS; |
635 SetLiveRangeAssignedRegister(result, index); | 635 SetLiveRangeAssignedRegister(result, index); |
636 fixed_double_live_ranges_[index] = result; | 636 fixed_double_live_ranges_[index] = result; |
637 } | 637 } |
638 return result; | 638 return result; |
639 } | 639 } |
640 | 640 |
641 | 641 |
642 LiveRange* RegisterAllocator::LiveRangeFor(int index) { | 642 LiveRange* RegisterAllocator::LiveRangeFor(int index) { |
643 if (index >= live_ranges_.length()) { | 643 if (index >= live_ranges_.length()) { |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
726 } | 726 } |
727 } | 727 } |
728 } | 728 } |
729 move->AddMove(from, to, code_zone()); | 729 move->AddMove(from, to, code_zone()); |
730 } | 730 } |
731 | 731 |
732 | 732 |
733 void RegisterAllocator::MeetRegisterConstraints(BasicBlock* block) { | 733 void RegisterAllocator::MeetRegisterConstraints(BasicBlock* block) { |
734 int start = block->first_instruction_index(); | 734 int start = block->first_instruction_index(); |
735 int end = block->last_instruction_index(); | 735 int end = block->last_instruction_index(); |
736 ASSERT_NE(-1, start); | 736 DCHECK_NE(-1, start); |
737 for (int i = start; i <= end; ++i) { | 737 for (int i = start; i <= end; ++i) { |
738 if (code()->IsGapAt(i)) { | 738 if (code()->IsGapAt(i)) { |
739 Instruction* instr = NULL; | 739 Instruction* instr = NULL; |
740 Instruction* prev_instr = NULL; | 740 Instruction* prev_instr = NULL; |
741 if (i < end) instr = InstructionAt(i + 1); | 741 if (i < end) instr = InstructionAt(i + 1); |
742 if (i > start) prev_instr = InstructionAt(i - 1); | 742 if (i > start) prev_instr = InstructionAt(i - 1); |
743 MeetConstraintsBetween(prev_instr, instr, i); | 743 MeetConstraintsBetween(prev_instr, instr, i); |
744 if (!AllocationOk()) return; | 744 if (!AllocationOk()) return; |
745 } | 745 } |
746 } | 746 } |
(...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
816 AddConstraintsGapMove(gap_index, input_copy, cur_input); | 816 AddConstraintsGapMove(gap_index, input_copy, cur_input); |
817 } | 817 } |
818 } | 818 } |
819 | 819 |
820 // Handle "output same as input" for second instruction. | 820 // Handle "output same as input" for second instruction. |
821 for (size_t i = 0; i < second->OutputCount(); i++) { | 821 for (size_t i = 0; i < second->OutputCount(); i++) { |
822 InstructionOperand* output = second->OutputAt(i); | 822 InstructionOperand* output = second->OutputAt(i); |
823 if (!output->IsUnallocated()) continue; | 823 if (!output->IsUnallocated()) continue; |
824 UnallocatedOperand* second_output = UnallocatedOperand::cast(output); | 824 UnallocatedOperand* second_output = UnallocatedOperand::cast(output); |
825 if (second_output->HasSameAsInputPolicy()) { | 825 if (second_output->HasSameAsInputPolicy()) { |
826 ASSERT(i == 0); // Only valid for first output. | 826 DCHECK(i == 0); // Only valid for first output. |
827 UnallocatedOperand* cur_input = | 827 UnallocatedOperand* cur_input = |
828 UnallocatedOperand::cast(second->InputAt(0)); | 828 UnallocatedOperand::cast(second->InputAt(0)); |
829 int output_vreg = second_output->virtual_register(); | 829 int output_vreg = second_output->virtual_register(); |
830 int input_vreg = cur_input->virtual_register(); | 830 int input_vreg = cur_input->virtual_register(); |
831 | 831 |
832 UnallocatedOperand* input_copy = | 832 UnallocatedOperand* input_copy = |
833 cur_input->CopyUnconstrained(code_zone()); | 833 cur_input->CopyUnconstrained(code_zone()); |
834 cur_input->set_virtual_register(second_output->virtual_register()); | 834 cur_input->set_virtual_register(second_output->virtual_register()); |
835 AddConstraintsGapMove(gap_index, input_copy, cur_input); | 835 AddConstraintsGapMove(gap_index, input_copy, cur_input); |
836 | 836 |
(...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
879 | 879 |
880 LifetimePosition block_start_position = | 880 LifetimePosition block_start_position = |
881 LifetimePosition::FromInstructionIndex(block_start); | 881 LifetimePosition::FromInstructionIndex(block_start); |
882 | 882 |
883 for (int index = block->last_instruction_index(); index >= block_start; | 883 for (int index = block->last_instruction_index(); index >= block_start; |
884 index--) { | 884 index--) { |
885 LifetimePosition curr_position = | 885 LifetimePosition curr_position = |
886 LifetimePosition::FromInstructionIndex(index); | 886 LifetimePosition::FromInstructionIndex(index); |
887 | 887 |
888 Instruction* instr = InstructionAt(index); | 888 Instruction* instr = InstructionAt(index); |
889 ASSERT(instr != NULL); | 889 DCHECK(instr != NULL); |
890 if (instr->IsGapMoves()) { | 890 if (instr->IsGapMoves()) { |
891 // Process the moves of the gap instruction, making their sources live. | 891 // Process the moves of the gap instruction, making their sources live. |
892 GapInstruction* gap = code()->GapAt(index); | 892 GapInstruction* gap = code()->GapAt(index); |
893 | 893 |
894 // TODO(titzer): no need to create the parallel move if it doesn't exist. | 894 // TODO(titzer): no need to create the parallel move if it doesn't exist. |
895 ParallelMove* move = | 895 ParallelMove* move = |
896 gap->GetOrCreateParallelMove(GapInstruction::START, code_zone()); | 896 gap->GetOrCreateParallelMove(GapInstruction::START, code_zone()); |
897 const ZoneList<MoveOperands>* move_operands = move->move_operands(); | 897 const ZoneList<MoveOperands>* move_operands = move->move_operands(); |
898 for (int i = 0; i < move_operands->length(); ++i) { | 898 for (int i = 0; i < move_operands->length(); ++i) { |
899 MoveOperands* cur = &move_operands->at(i); | 899 MoveOperands* cur = &move_operands->at(i); |
(...skipping 114 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1014 UnallocatedOperand* operand = | 1014 UnallocatedOperand* operand = |
1015 new (code_zone()) UnallocatedOperand(UnallocatedOperand::ANY); | 1015 new (code_zone()) UnallocatedOperand(UnallocatedOperand::ANY); |
1016 operand->set_virtual_register(op->id()); | 1016 operand->set_virtual_register(op->id()); |
1017 BasicBlock* cur_block = block->PredecessorAt(j); | 1017 BasicBlock* cur_block = block->PredecessorAt(j); |
1018 // The gap move must be added without any special processing as in | 1018 // The gap move must be added without any special processing as in |
1019 // the AddConstraintsGapMove. | 1019 // the AddConstraintsGapMove. |
1020 code()->AddGapMove(cur_block->last_instruction_index() - 1, operand, | 1020 code()->AddGapMove(cur_block->last_instruction_index() - 1, operand, |
1021 phi_operand); | 1021 phi_operand); |
1022 | 1022 |
1023 Instruction* branch = InstructionAt(cur_block->last_instruction_index()); | 1023 Instruction* branch = InstructionAt(cur_block->last_instruction_index()); |
1024 ASSERT(!branch->HasPointerMap()); | 1024 DCHECK(!branch->HasPointerMap()); |
1025 USE(branch); | 1025 USE(branch); |
1026 } | 1026 } |
1027 | 1027 |
1028 LiveRange* live_range = LiveRangeFor(phi->id()); | 1028 LiveRange* live_range = LiveRangeFor(phi->id()); |
1029 BlockStartInstruction* block_start = code()->GetBlockStart(block); | 1029 BlockStartInstruction* block_start = code()->GetBlockStart(block); |
1030 block_start->GetOrCreateParallelMove(GapInstruction::START, code_zone()) | 1030 block_start->GetOrCreateParallelMove(GapInstruction::START, code_zone()) |
1031 ->AddMove(phi_operand, live_range->GetSpillOperand(), code_zone()); | 1031 ->AddMove(phi_operand, live_range->GetSpillOperand(), code_zone()); |
1032 live_range->SetSpillStartIndex(block->first_instruction_index()); | 1032 live_range->SetSpillStartIndex(block->first_instruction_index()); |
1033 | 1033 |
1034 // We use the phi-ness of some nodes in some later heuristics. | 1034 // We use the phi-ness of some nodes in some later heuristics. |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1085 BasicBlock* pred) { | 1085 BasicBlock* pred) { |
1086 LifetimePosition pred_end = | 1086 LifetimePosition pred_end = |
1087 LifetimePosition::FromInstructionIndex(pred->last_instruction_index()); | 1087 LifetimePosition::FromInstructionIndex(pred->last_instruction_index()); |
1088 LifetimePosition cur_start = | 1088 LifetimePosition cur_start = |
1089 LifetimePosition::FromInstructionIndex(block->first_instruction_index()); | 1089 LifetimePosition::FromInstructionIndex(block->first_instruction_index()); |
1090 LiveRange* pred_cover = NULL; | 1090 LiveRange* pred_cover = NULL; |
1091 LiveRange* cur_cover = NULL; | 1091 LiveRange* cur_cover = NULL; |
1092 LiveRange* cur_range = range; | 1092 LiveRange* cur_range = range; |
1093 while (cur_range != NULL && (cur_cover == NULL || pred_cover == NULL)) { | 1093 while (cur_range != NULL && (cur_cover == NULL || pred_cover == NULL)) { |
1094 if (cur_range->CanCover(cur_start)) { | 1094 if (cur_range->CanCover(cur_start)) { |
1095 ASSERT(cur_cover == NULL); | 1095 DCHECK(cur_cover == NULL); |
1096 cur_cover = cur_range; | 1096 cur_cover = cur_range; |
1097 } | 1097 } |
1098 if (cur_range->CanCover(pred_end)) { | 1098 if (cur_range->CanCover(pred_end)) { |
1099 ASSERT(pred_cover == NULL); | 1099 DCHECK(pred_cover == NULL); |
1100 pred_cover = cur_range; | 1100 pred_cover = cur_range; |
1101 } | 1101 } |
1102 cur_range = cur_range->next(); | 1102 cur_range = cur_range->next(); |
1103 } | 1103 } |
1104 | 1104 |
1105 if (cur_cover->IsSpilled()) return; | 1105 if (cur_cover->IsSpilled()) return; |
1106 ASSERT(pred_cover != NULL && cur_cover != NULL); | 1106 DCHECK(pred_cover != NULL && cur_cover != NULL); |
1107 if (pred_cover != cur_cover) { | 1107 if (pred_cover != cur_cover) { |
1108 InstructionOperand* pred_op = | 1108 InstructionOperand* pred_op = |
1109 pred_cover->CreateAssignedOperand(code_zone()); | 1109 pred_cover->CreateAssignedOperand(code_zone()); |
1110 InstructionOperand* cur_op = cur_cover->CreateAssignedOperand(code_zone()); | 1110 InstructionOperand* cur_op = cur_cover->CreateAssignedOperand(code_zone()); |
1111 if (!pred_op->Equals(cur_op)) { | 1111 if (!pred_op->Equals(cur_op)) { |
1112 GapInstruction* gap = NULL; | 1112 GapInstruction* gap = NULL; |
1113 if (block->PredecessorCount() == 1) { | 1113 if (block->PredecessorCount() == 1) { |
1114 gap = code()->GapAt(block->first_instruction_index()); | 1114 gap = code()->GapAt(block->first_instruction_index()); |
1115 } else { | 1115 } else { |
1116 ASSERT(pred->SuccessorCount() == 1); | 1116 DCHECK(pred->SuccessorCount() == 1); |
1117 gap = GetLastGap(pred); | 1117 gap = GetLastGap(pred); |
1118 | 1118 |
1119 Instruction* branch = InstructionAt(pred->last_instruction_index()); | 1119 Instruction* branch = InstructionAt(pred->last_instruction_index()); |
1120 ASSERT(!branch->HasPointerMap()); | 1120 DCHECK(!branch->HasPointerMap()); |
1121 USE(branch); | 1121 USE(branch); |
1122 } | 1122 } |
1123 gap->GetOrCreateParallelMove(GapInstruction::START, code_zone()) | 1123 gap->GetOrCreateParallelMove(GapInstruction::START, code_zone()) |
1124 ->AddMove(pred_op, cur_op, code_zone()); | 1124 ->AddMove(pred_op, cur_op, code_zone()); |
1125 } | 1125 } |
1126 } | 1126 } |
1127 } | 1127 } |
1128 | 1128 |
1129 | 1129 |
1130 ParallelMove* RegisterAllocator::GetConnectingParallelMove( | 1130 ParallelMove* RegisterAllocator::GetConnectingParallelMove( |
(...skipping 115 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1246 gap->GetOrCreateParallelMove(GapInstruction::START, code_zone()); | 1246 gap->GetOrCreateParallelMove(GapInstruction::START, code_zone()); |
1247 for (int j = 0; j < move->move_operands()->length(); ++j) { | 1247 for (int j = 0; j < move->move_operands()->length(); ++j) { |
1248 InstructionOperand* to = move->move_operands()->at(j).destination(); | 1248 InstructionOperand* to = move->move_operands()->at(j).destination(); |
1249 if (to->IsUnallocated() && | 1249 if (to->IsUnallocated() && |
1250 UnallocatedOperand::cast(to)->virtual_register() == phi->id()) { | 1250 UnallocatedOperand::cast(to)->virtual_register() == phi->id()) { |
1251 hint = move->move_operands()->at(j).source(); | 1251 hint = move->move_operands()->at(j).source(); |
1252 phi_operand = to; | 1252 phi_operand = to; |
1253 break; | 1253 break; |
1254 } | 1254 } |
1255 } | 1255 } |
1256 ASSERT(hint != NULL); | 1256 DCHECK(hint != NULL); |
1257 | 1257 |
1258 LifetimePosition block_start = LifetimePosition::FromInstructionIndex( | 1258 LifetimePosition block_start = LifetimePosition::FromInstructionIndex( |
1259 block->first_instruction_index()); | 1259 block->first_instruction_index()); |
1260 Define(block_start, phi_operand, hint); | 1260 Define(block_start, phi_operand, hint); |
1261 } | 1261 } |
1262 | 1262 |
1263 // Now live is live_in for this block except not including values live | 1263 // Now live is live_in for this block except not including values live |
1264 // out on backward successor edges. | 1264 // out on backward successor edges. |
1265 live_in_sets_[block_id] = live; | 1265 live_in_sets_[block_id] = live; |
1266 | 1266 |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1300 PrintF(" (first use is at %d)\n", range->first_pos()->pos().Value()); | 1300 PrintF(" (first use is at %d)\n", range->first_pos()->pos().Value()); |
1301 CompilationInfo* info = code()->linkage()->info(); | 1301 CompilationInfo* info = code()->linkage()->info(); |
1302 if (info->IsStub()) { | 1302 if (info->IsStub()) { |
1303 if (info->code_stub() == NULL) { | 1303 if (info->code_stub() == NULL) { |
1304 PrintF("\n"); | 1304 PrintF("\n"); |
1305 } else { | 1305 } else { |
1306 CodeStub::Major major_key = info->code_stub()->MajorKey(); | 1306 CodeStub::Major major_key = info->code_stub()->MajorKey(); |
1307 PrintF(" (function: %s)\n", CodeStub::MajorName(major_key, false)); | 1307 PrintF(" (function: %s)\n", CodeStub::MajorName(major_key, false)); |
1308 } | 1308 } |
1309 } else { | 1309 } else { |
1310 ASSERT(info->IsOptimizing()); | 1310 DCHECK(info->IsOptimizing()); |
1311 AllowHandleDereference allow_deref; | 1311 AllowHandleDereference allow_deref; |
1312 PrintF(" (function: %s)\n", | 1312 PrintF(" (function: %s)\n", |
1313 info->function()->debug_name()->ToCString().get()); | 1313 info->function()->debug_name()->ToCString().get()); |
1314 } | 1314 } |
1315 iterator.Advance(); | 1315 iterator.Advance(); |
1316 } | 1316 } |
1317 ASSERT(!found); | 1317 DCHECK(!found); |
1318 } | 1318 } |
1319 #endif | 1319 #endif |
1320 } | 1320 } |
1321 | 1321 |
1322 for (int i = 0; i < live_ranges_.length(); ++i) { | 1322 for (int i = 0; i < live_ranges_.length(); ++i) { |
1323 if (live_ranges_[i] != NULL) { | 1323 if (live_ranges_[i] != NULL) { |
1324 live_ranges_[i]->kind_ = RequiredRegisterKind(live_ranges_[i]->id()); | 1324 live_ranges_[i]->kind_ = RequiredRegisterKind(live_ranges_[i]->id()); |
1325 | 1325 |
1326 // TODO(bmeurer): This is a horrible hack to make sure that for constant | 1326 // TODO(bmeurer): This is a horrible hack to make sure that for constant |
1327 // live ranges, every use requires the constant to be in a register. | 1327 // live ranges, every use requires the constant to be in a register. |
(...skipping 22 matching lines...) Expand all Loading... |
1350 if (safe_point > map->instruction_position()) return false; | 1350 if (safe_point > map->instruction_position()) return false; |
1351 safe_point = map->instruction_position(); | 1351 safe_point = map->instruction_position(); |
1352 } | 1352 } |
1353 return true; | 1353 return true; |
1354 } | 1354 } |
1355 | 1355 |
1356 | 1356 |
1357 void RegisterAllocator::PopulatePointerMaps() { | 1357 void RegisterAllocator::PopulatePointerMaps() { |
1358 RegisterAllocatorPhase phase("L_Populate pointer maps", this); | 1358 RegisterAllocatorPhase phase("L_Populate pointer maps", this); |
1359 | 1359 |
1360 ASSERT(SafePointsAreInOrder()); | 1360 DCHECK(SafePointsAreInOrder()); |
1361 | 1361 |
1362 // Iterate over all safe point positions and record a pointer | 1362 // Iterate over all safe point positions and record a pointer |
1363 // for all spilled live ranges at this point. | 1363 // for all spilled live ranges at this point. |
1364 int last_range_start = 0; | 1364 int last_range_start = 0; |
1365 const PointerMapDeque* pointer_maps = code()->pointer_maps(); | 1365 const PointerMapDeque* pointer_maps = code()->pointer_maps(); |
1366 PointerMapDeque::const_iterator first_it = pointer_maps->begin(); | 1366 PointerMapDeque::const_iterator first_it = pointer_maps->begin(); |
1367 for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { | 1367 for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { |
1368 LiveRange* range = live_ranges()->at(range_idx); | 1368 LiveRange* range = live_ranges()->at(range_idx); |
1369 if (range == NULL) continue; | 1369 if (range == NULL) continue; |
1370 // Iterate over the first parts of multi-part live ranges. | 1370 // Iterate over the first parts of multi-part live ranges. |
1371 if (range->parent() != NULL) continue; | 1371 if (range->parent() != NULL) continue; |
1372 // Skip non-reference values. | 1372 // Skip non-reference values. |
1373 if (!HasTaggedValue(range->id())) continue; | 1373 if (!HasTaggedValue(range->id())) continue; |
1374 // Skip empty live ranges. | 1374 // Skip empty live ranges. |
1375 if (range->IsEmpty()) continue; | 1375 if (range->IsEmpty()) continue; |
1376 | 1376 |
1377 // Find the extent of the range and its children. | 1377 // Find the extent of the range and its children. |
1378 int start = range->Start().InstructionIndex(); | 1378 int start = range->Start().InstructionIndex(); |
1379 int end = 0; | 1379 int end = 0; |
1380 for (LiveRange* cur = range; cur != NULL; cur = cur->next()) { | 1380 for (LiveRange* cur = range; cur != NULL; cur = cur->next()) { |
1381 LifetimePosition this_end = cur->End(); | 1381 LifetimePosition this_end = cur->End(); |
1382 if (this_end.InstructionIndex() > end) end = this_end.InstructionIndex(); | 1382 if (this_end.InstructionIndex() > end) end = this_end.InstructionIndex(); |
1383 ASSERT(cur->Start().InstructionIndex() >= start); | 1383 DCHECK(cur->Start().InstructionIndex() >= start); |
1384 } | 1384 } |
1385 | 1385 |
1386 // Most of the ranges are in order, but not all. Keep an eye on when they | 1386 // Most of the ranges are in order, but not all. Keep an eye on when they |
1387 // step backwards and reset the first_it so we don't miss any safe points. | 1387 // step backwards and reset the first_it so we don't miss any safe points. |
1388 if (start < last_range_start) first_it = pointer_maps->begin(); | 1388 if (start < last_range_start) first_it = pointer_maps->begin(); |
1389 last_range_start = start; | 1389 last_range_start = start; |
1390 | 1390 |
1391 // Step across all the safe points that are before the start of this range, | 1391 // Step across all the safe points that are before the start of this range, |
1392 // recording how far we step in order to save doing this for the next range. | 1392 // recording how far we step in order to save doing this for the next range. |
1393 for (; first_it != pointer_maps->end(); ++first_it) { | 1393 for (; first_it != pointer_maps->end(); ++first_it) { |
(...skipping 29 matching lines...) Expand all Loading... |
1423 range->id(), range->spill_start_index(), safe_point); | 1423 range->id(), range->spill_start_index(), safe_point); |
1424 map->RecordPointer(range->GetSpillOperand(), code_zone()); | 1424 map->RecordPointer(range->GetSpillOperand(), code_zone()); |
1425 } | 1425 } |
1426 | 1426 |
1427 if (!cur->IsSpilled()) { | 1427 if (!cur->IsSpilled()) { |
1428 TraceAlloc( | 1428 TraceAlloc( |
1429 "Pointer in register for range %d (start at %d) " | 1429 "Pointer in register for range %d (start at %d) " |
1430 "at safe point %d\n", | 1430 "at safe point %d\n", |
1431 cur->id(), cur->Start().Value(), safe_point); | 1431 cur->id(), cur->Start().Value(), safe_point); |
1432 InstructionOperand* operand = cur->CreateAssignedOperand(code_zone()); | 1432 InstructionOperand* operand = cur->CreateAssignedOperand(code_zone()); |
1433 ASSERT(!operand->IsStackSlot()); | 1433 DCHECK(!operand->IsStackSlot()); |
1434 map->RecordPointer(operand, code_zone()); | 1434 map->RecordPointer(operand, code_zone()); |
1435 } | 1435 } |
1436 } | 1436 } |
1437 } | 1437 } |
1438 } | 1438 } |
1439 | 1439 |
1440 | 1440 |
1441 void RegisterAllocator::AllocateGeneralRegisters() { | 1441 void RegisterAllocator::AllocateGeneralRegisters() { |
1442 RegisterAllocatorPhase phase("L_Allocate general registers", this); | 1442 RegisterAllocatorPhase phase("L_Allocate general registers", this); |
1443 num_registers_ = Register::NumAllocatableRegisters(); | 1443 num_registers_ = Register::NumAllocatableRegisters(); |
1444 mode_ = GENERAL_REGISTERS; | 1444 mode_ = GENERAL_REGISTERS; |
1445 AllocateRegisters(); | 1445 AllocateRegisters(); |
1446 } | 1446 } |
1447 | 1447 |
1448 | 1448 |
1449 void RegisterAllocator::AllocateDoubleRegisters() { | 1449 void RegisterAllocator::AllocateDoubleRegisters() { |
1450 RegisterAllocatorPhase phase("L_Allocate double registers", this); | 1450 RegisterAllocatorPhase phase("L_Allocate double registers", this); |
1451 num_registers_ = DoubleRegister::NumAllocatableRegisters(); | 1451 num_registers_ = DoubleRegister::NumAllocatableRegisters(); |
1452 mode_ = DOUBLE_REGISTERS; | 1452 mode_ = DOUBLE_REGISTERS; |
1453 AllocateRegisters(); | 1453 AllocateRegisters(); |
1454 } | 1454 } |
1455 | 1455 |
1456 | 1456 |
1457 void RegisterAllocator::AllocateRegisters() { | 1457 void RegisterAllocator::AllocateRegisters() { |
1458 ASSERT(unhandled_live_ranges_.is_empty()); | 1458 DCHECK(unhandled_live_ranges_.is_empty()); |
1459 | 1459 |
1460 for (int i = 0; i < live_ranges_.length(); ++i) { | 1460 for (int i = 0; i < live_ranges_.length(); ++i) { |
1461 if (live_ranges_[i] != NULL) { | 1461 if (live_ranges_[i] != NULL) { |
1462 if (live_ranges_[i]->Kind() == mode_) { | 1462 if (live_ranges_[i]->Kind() == mode_) { |
1463 AddToUnhandledUnsorted(live_ranges_[i]); | 1463 AddToUnhandledUnsorted(live_ranges_[i]); |
1464 } | 1464 } |
1465 } | 1465 } |
1466 } | 1466 } |
1467 SortUnhandled(); | 1467 SortUnhandled(); |
1468 ASSERT(UnhandledIsSorted()); | 1468 DCHECK(UnhandledIsSorted()); |
1469 | 1469 |
1470 ASSERT(reusable_slots_.is_empty()); | 1470 DCHECK(reusable_slots_.is_empty()); |
1471 ASSERT(active_live_ranges_.is_empty()); | 1471 DCHECK(active_live_ranges_.is_empty()); |
1472 ASSERT(inactive_live_ranges_.is_empty()); | 1472 DCHECK(inactive_live_ranges_.is_empty()); |
1473 | 1473 |
1474 if (mode_ == DOUBLE_REGISTERS) { | 1474 if (mode_ == DOUBLE_REGISTERS) { |
1475 for (int i = 0; i < DoubleRegister::NumAllocatableRegisters(); ++i) { | 1475 for (int i = 0; i < DoubleRegister::NumAllocatableRegisters(); ++i) { |
1476 LiveRange* current = fixed_double_live_ranges_.at(i); | 1476 LiveRange* current = fixed_double_live_ranges_.at(i); |
1477 if (current != NULL) { | 1477 if (current != NULL) { |
1478 AddToInactive(current); | 1478 AddToInactive(current); |
1479 } | 1479 } |
1480 } | 1480 } |
1481 } else { | 1481 } else { |
1482 ASSERT(mode_ == GENERAL_REGISTERS); | 1482 DCHECK(mode_ == GENERAL_REGISTERS); |
1483 for (int i = 0; i < fixed_live_ranges_.length(); ++i) { | 1483 for (int i = 0; i < fixed_live_ranges_.length(); ++i) { |
1484 LiveRange* current = fixed_live_ranges_.at(i); | 1484 LiveRange* current = fixed_live_ranges_.at(i); |
1485 if (current != NULL) { | 1485 if (current != NULL) { |
1486 AddToInactive(current); | 1486 AddToInactive(current); |
1487 } | 1487 } |
1488 } | 1488 } |
1489 } | 1489 } |
1490 | 1490 |
1491 while (!unhandled_live_ranges_.is_empty()) { | 1491 while (!unhandled_live_ranges_.is_empty()) { |
1492 ASSERT(UnhandledIsSorted()); | 1492 DCHECK(UnhandledIsSorted()); |
1493 LiveRange* current = unhandled_live_ranges_.RemoveLast(); | 1493 LiveRange* current = unhandled_live_ranges_.RemoveLast(); |
1494 ASSERT(UnhandledIsSorted()); | 1494 DCHECK(UnhandledIsSorted()); |
1495 LifetimePosition position = current->Start(); | 1495 LifetimePosition position = current->Start(); |
1496 #ifdef DEBUG | 1496 #ifdef DEBUG |
1497 allocation_finger_ = position; | 1497 allocation_finger_ = position; |
1498 #endif | 1498 #endif |
1499 TraceAlloc("Processing interval %d start=%d\n", current->id(), | 1499 TraceAlloc("Processing interval %d start=%d\n", current->id(), |
1500 position.Value()); | 1500 position.Value()); |
1501 | 1501 |
1502 if (current->HasAllocatedSpillOperand()) { | 1502 if (current->HasAllocatedSpillOperand()) { |
1503 TraceAlloc("Live range %d already has a spill operand\n", current->id()); | 1503 TraceAlloc("Live range %d already has a spill operand\n", current->id()); |
1504 LifetimePosition next_pos = position; | 1504 LifetimePosition next_pos = position; |
1505 if (code()->IsGapAt(next_pos.InstructionIndex())) { | 1505 if (code()->IsGapAt(next_pos.InstructionIndex())) { |
1506 next_pos = next_pos.NextInstruction(); | 1506 next_pos = next_pos.NextInstruction(); |
1507 } | 1507 } |
1508 UsePosition* pos = current->NextUsePositionRegisterIsBeneficial(next_pos); | 1508 UsePosition* pos = current->NextUsePositionRegisterIsBeneficial(next_pos); |
1509 // If the range already has a spill operand and it doesn't need a | 1509 // If the range already has a spill operand and it doesn't need a |
1510 // register immediately, split it and spill the first part of the range. | 1510 // register immediately, split it and spill the first part of the range. |
1511 if (pos == NULL) { | 1511 if (pos == NULL) { |
1512 Spill(current); | 1512 Spill(current); |
1513 continue; | 1513 continue; |
1514 } else if (pos->pos().Value() > | 1514 } else if (pos->pos().Value() > |
1515 current->Start().NextInstruction().Value()) { | 1515 current->Start().NextInstruction().Value()) { |
1516 // Do not spill live range eagerly if use position that can benefit from | 1516 // Do not spill live range eagerly if use position that can benefit from |
1517 // the register is too close to the start of live range. | 1517 // the register is too close to the start of live range. |
1518 SpillBetween(current, current->Start(), pos->pos()); | 1518 SpillBetween(current, current->Start(), pos->pos()); |
1519 if (!AllocationOk()) return; | 1519 if (!AllocationOk()) return; |
1520 ASSERT(UnhandledIsSorted()); | 1520 DCHECK(UnhandledIsSorted()); |
1521 continue; | 1521 continue; |
1522 } | 1522 } |
1523 } | 1523 } |
1524 | 1524 |
1525 for (int i = 0; i < active_live_ranges_.length(); ++i) { | 1525 for (int i = 0; i < active_live_ranges_.length(); ++i) { |
1526 LiveRange* cur_active = active_live_ranges_.at(i); | 1526 LiveRange* cur_active = active_live_ranges_.at(i); |
1527 if (cur_active->End().Value() <= position.Value()) { | 1527 if (cur_active->End().Value() <= position.Value()) { |
1528 ActiveToHandled(cur_active); | 1528 ActiveToHandled(cur_active); |
1529 --i; // The live range was removed from the list of active live ranges. | 1529 --i; // The live range was removed from the list of active live ranges. |
1530 } else if (!cur_active->Covers(position)) { | 1530 } else if (!cur_active->Covers(position)) { |
1531 ActiveToInactive(cur_active); | 1531 ActiveToInactive(cur_active); |
1532 --i; // The live range was removed from the list of active live ranges. | 1532 --i; // The live range was removed from the list of active live ranges. |
1533 } | 1533 } |
1534 } | 1534 } |
1535 | 1535 |
1536 for (int i = 0; i < inactive_live_ranges_.length(); ++i) { | 1536 for (int i = 0; i < inactive_live_ranges_.length(); ++i) { |
1537 LiveRange* cur_inactive = inactive_live_ranges_.at(i); | 1537 LiveRange* cur_inactive = inactive_live_ranges_.at(i); |
1538 if (cur_inactive->End().Value() <= position.Value()) { | 1538 if (cur_inactive->End().Value() <= position.Value()) { |
1539 InactiveToHandled(cur_inactive); | 1539 InactiveToHandled(cur_inactive); |
1540 --i; // Live range was removed from the list of inactive live ranges. | 1540 --i; // Live range was removed from the list of inactive live ranges. |
1541 } else if (cur_inactive->Covers(position)) { | 1541 } else if (cur_inactive->Covers(position)) { |
1542 InactiveToActive(cur_inactive); | 1542 InactiveToActive(cur_inactive); |
1543 --i; // Live range was removed from the list of inactive live ranges. | 1543 --i; // Live range was removed from the list of inactive live ranges. |
1544 } | 1544 } |
1545 } | 1545 } |
1546 | 1546 |
1547 ASSERT(!current->HasRegisterAssigned() && !current->IsSpilled()); | 1547 DCHECK(!current->HasRegisterAssigned() && !current->IsSpilled()); |
1548 | 1548 |
1549 bool result = TryAllocateFreeReg(current); | 1549 bool result = TryAllocateFreeReg(current); |
1550 if (!AllocationOk()) return; | 1550 if (!AllocationOk()) return; |
1551 | 1551 |
1552 if (!result) AllocateBlockedReg(current); | 1552 if (!result) AllocateBlockedReg(current); |
1553 if (!AllocationOk()) return; | 1553 if (!AllocationOk()) return; |
1554 | 1554 |
1555 if (current->HasRegisterAssigned()) { | 1555 if (current->HasRegisterAssigned()) { |
1556 AddToActive(current); | 1556 AddToActive(current); |
1557 } | 1557 } |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1601 | 1601 |
1602 | 1602 |
1603 void RegisterAllocator::AddToInactive(LiveRange* range) { | 1603 void RegisterAllocator::AddToInactive(LiveRange* range) { |
1604 TraceAlloc("Add live range %d to inactive\n", range->id()); | 1604 TraceAlloc("Add live range %d to inactive\n", range->id()); |
1605 inactive_live_ranges_.Add(range, zone()); | 1605 inactive_live_ranges_.Add(range, zone()); |
1606 } | 1606 } |
1607 | 1607 |
1608 | 1608 |
1609 void RegisterAllocator::AddToUnhandledSorted(LiveRange* range) { | 1609 void RegisterAllocator::AddToUnhandledSorted(LiveRange* range) { |
1610 if (range == NULL || range->IsEmpty()) return; | 1610 if (range == NULL || range->IsEmpty()) return; |
1611 ASSERT(!range->HasRegisterAssigned() && !range->IsSpilled()); | 1611 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); |
1612 ASSERT(allocation_finger_.Value() <= range->Start().Value()); | 1612 DCHECK(allocation_finger_.Value() <= range->Start().Value()); |
1613 for (int i = unhandled_live_ranges_.length() - 1; i >= 0; --i) { | 1613 for (int i = unhandled_live_ranges_.length() - 1; i >= 0; --i) { |
1614 LiveRange* cur_range = unhandled_live_ranges_.at(i); | 1614 LiveRange* cur_range = unhandled_live_ranges_.at(i); |
1615 if (range->ShouldBeAllocatedBefore(cur_range)) { | 1615 if (range->ShouldBeAllocatedBefore(cur_range)) { |
1616 TraceAlloc("Add live range %d to unhandled at %d\n", range->id(), i + 1); | 1616 TraceAlloc("Add live range %d to unhandled at %d\n", range->id(), i + 1); |
1617 unhandled_live_ranges_.InsertAt(i + 1, range, zone()); | 1617 unhandled_live_ranges_.InsertAt(i + 1, range, zone()); |
1618 ASSERT(UnhandledIsSorted()); | 1618 DCHECK(UnhandledIsSorted()); |
1619 return; | 1619 return; |
1620 } | 1620 } |
1621 } | 1621 } |
1622 TraceAlloc("Add live range %d to unhandled at start\n", range->id()); | 1622 TraceAlloc("Add live range %d to unhandled at start\n", range->id()); |
1623 unhandled_live_ranges_.InsertAt(0, range, zone()); | 1623 unhandled_live_ranges_.InsertAt(0, range, zone()); |
1624 ASSERT(UnhandledIsSorted()); | 1624 DCHECK(UnhandledIsSorted()); |
1625 } | 1625 } |
1626 | 1626 |
1627 | 1627 |
1628 void RegisterAllocator::AddToUnhandledUnsorted(LiveRange* range) { | 1628 void RegisterAllocator::AddToUnhandledUnsorted(LiveRange* range) { |
1629 if (range == NULL || range->IsEmpty()) return; | 1629 if (range == NULL || range->IsEmpty()) return; |
1630 ASSERT(!range->HasRegisterAssigned() && !range->IsSpilled()); | 1630 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); |
1631 TraceAlloc("Add live range %d to unhandled unsorted at end\n", range->id()); | 1631 TraceAlloc("Add live range %d to unhandled unsorted at end\n", range->id()); |
1632 unhandled_live_ranges_.Add(range, zone()); | 1632 unhandled_live_ranges_.Add(range, zone()); |
1633 } | 1633 } |
1634 | 1634 |
1635 | 1635 |
1636 static int UnhandledSortHelper(LiveRange* const* a, LiveRange* const* b) { | 1636 static int UnhandledSortHelper(LiveRange* const* a, LiveRange* const* b) { |
1637 ASSERT(!(*a)->ShouldBeAllocatedBefore(*b) || | 1637 DCHECK(!(*a)->ShouldBeAllocatedBefore(*b) || |
1638 !(*b)->ShouldBeAllocatedBefore(*a)); | 1638 !(*b)->ShouldBeAllocatedBefore(*a)); |
1639 if ((*a)->ShouldBeAllocatedBefore(*b)) return 1; | 1639 if ((*a)->ShouldBeAllocatedBefore(*b)) return 1; |
1640 if ((*b)->ShouldBeAllocatedBefore(*a)) return -1; | 1640 if ((*b)->ShouldBeAllocatedBefore(*a)) return -1; |
1641 return (*a)->id() - (*b)->id(); | 1641 return (*a)->id() - (*b)->id(); |
1642 } | 1642 } |
1643 | 1643 |
1644 | 1644 |
1645 // Sort the unhandled live ranges so that the ranges to be processed first are | 1645 // Sort the unhandled live ranges so that the ranges to be processed first are |
1646 // at the end of the array list. This is convenient for the register allocation | 1646 // at the end of the array list. This is convenient for the register allocation |
1647 // algorithm because it is efficient to remove elements from the end. | 1647 // algorithm because it is efficient to remove elements from the end. |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1683 return NULL; | 1683 return NULL; |
1684 } | 1684 } |
1685 InstructionOperand* result = | 1685 InstructionOperand* result = |
1686 reusable_slots_.first()->TopLevel()->GetSpillOperand(); | 1686 reusable_slots_.first()->TopLevel()->GetSpillOperand(); |
1687 reusable_slots_.Remove(0); | 1687 reusable_slots_.Remove(0); |
1688 return result; | 1688 return result; |
1689 } | 1689 } |
1690 | 1690 |
1691 | 1691 |
1692 void RegisterAllocator::ActiveToHandled(LiveRange* range) { | 1692 void RegisterAllocator::ActiveToHandled(LiveRange* range) { |
1693 ASSERT(active_live_ranges_.Contains(range)); | 1693 DCHECK(active_live_ranges_.Contains(range)); |
1694 active_live_ranges_.RemoveElement(range); | 1694 active_live_ranges_.RemoveElement(range); |
1695 TraceAlloc("Moving live range %d from active to handled\n", range->id()); | 1695 TraceAlloc("Moving live range %d from active to handled\n", range->id()); |
1696 FreeSpillSlot(range); | 1696 FreeSpillSlot(range); |
1697 } | 1697 } |
1698 | 1698 |
1699 | 1699 |
1700 void RegisterAllocator::ActiveToInactive(LiveRange* range) { | 1700 void RegisterAllocator::ActiveToInactive(LiveRange* range) { |
1701 ASSERT(active_live_ranges_.Contains(range)); | 1701 DCHECK(active_live_ranges_.Contains(range)); |
1702 active_live_ranges_.RemoveElement(range); | 1702 active_live_ranges_.RemoveElement(range); |
1703 inactive_live_ranges_.Add(range, zone()); | 1703 inactive_live_ranges_.Add(range, zone()); |
1704 TraceAlloc("Moving live range %d from active to inactive\n", range->id()); | 1704 TraceAlloc("Moving live range %d from active to inactive\n", range->id()); |
1705 } | 1705 } |
1706 | 1706 |
1707 | 1707 |
1708 void RegisterAllocator::InactiveToHandled(LiveRange* range) { | 1708 void RegisterAllocator::InactiveToHandled(LiveRange* range) { |
1709 ASSERT(inactive_live_ranges_.Contains(range)); | 1709 DCHECK(inactive_live_ranges_.Contains(range)); |
1710 inactive_live_ranges_.RemoveElement(range); | 1710 inactive_live_ranges_.RemoveElement(range); |
1711 TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); | 1711 TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); |
1712 FreeSpillSlot(range); | 1712 FreeSpillSlot(range); |
1713 } | 1713 } |
1714 | 1714 |
1715 | 1715 |
1716 void RegisterAllocator::InactiveToActive(LiveRange* range) { | 1716 void RegisterAllocator::InactiveToActive(LiveRange* range) { |
1717 ASSERT(inactive_live_ranges_.Contains(range)); | 1717 DCHECK(inactive_live_ranges_.Contains(range)); |
1718 inactive_live_ranges_.RemoveElement(range); | 1718 inactive_live_ranges_.RemoveElement(range); |
1719 active_live_ranges_.Add(range, zone()); | 1719 active_live_ranges_.Add(range, zone()); |
1720 TraceAlloc("Moving live range %d from inactive to active\n", range->id()); | 1720 TraceAlloc("Moving live range %d from inactive to active\n", range->id()); |
1721 } | 1721 } |
1722 | 1722 |
1723 | 1723 |
1724 // TryAllocateFreeReg and AllocateBlockedReg assume this | 1724 // TryAllocateFreeReg and AllocateBlockedReg assume this |
1725 // when allocating local arrays. | 1725 // when allocating local arrays. |
1726 STATIC_ASSERT(DoubleRegister::kMaxNumAllocatableRegisters >= | 1726 STATIC_ASSERT(DoubleRegister::kMaxNumAllocatableRegisters >= |
1727 Register::kMaxNumAllocatableRegisters); | 1727 Register::kMaxNumAllocatableRegisters); |
1728 | 1728 |
1729 | 1729 |
1730 bool RegisterAllocator::TryAllocateFreeReg(LiveRange* current) { | 1730 bool RegisterAllocator::TryAllocateFreeReg(LiveRange* current) { |
1731 LifetimePosition free_until_pos[DoubleRegister::kMaxNumAllocatableRegisters]; | 1731 LifetimePosition free_until_pos[DoubleRegister::kMaxNumAllocatableRegisters]; |
1732 | 1732 |
1733 for (int i = 0; i < num_registers_; i++) { | 1733 for (int i = 0; i < num_registers_; i++) { |
1734 free_until_pos[i] = LifetimePosition::MaxPosition(); | 1734 free_until_pos[i] = LifetimePosition::MaxPosition(); |
1735 } | 1735 } |
1736 | 1736 |
1737 for (int i = 0; i < active_live_ranges_.length(); ++i) { | 1737 for (int i = 0; i < active_live_ranges_.length(); ++i) { |
1738 LiveRange* cur_active = active_live_ranges_.at(i); | 1738 LiveRange* cur_active = active_live_ranges_.at(i); |
1739 free_until_pos[cur_active->assigned_register()] = | 1739 free_until_pos[cur_active->assigned_register()] = |
1740 LifetimePosition::FromInstructionIndex(0); | 1740 LifetimePosition::FromInstructionIndex(0); |
1741 } | 1741 } |
1742 | 1742 |
1743 for (int i = 0; i < inactive_live_ranges_.length(); ++i) { | 1743 for (int i = 0; i < inactive_live_ranges_.length(); ++i) { |
1744 LiveRange* cur_inactive = inactive_live_ranges_.at(i); | 1744 LiveRange* cur_inactive = inactive_live_ranges_.at(i); |
1745 ASSERT(cur_inactive->End().Value() > current->Start().Value()); | 1745 DCHECK(cur_inactive->End().Value() > current->Start().Value()); |
1746 LifetimePosition next_intersection = | 1746 LifetimePosition next_intersection = |
1747 cur_inactive->FirstIntersection(current); | 1747 cur_inactive->FirstIntersection(current); |
1748 if (!next_intersection.IsValid()) continue; | 1748 if (!next_intersection.IsValid()) continue; |
1749 int cur_reg = cur_inactive->assigned_register(); | 1749 int cur_reg = cur_inactive->assigned_register(); |
1750 free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection); | 1750 free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection); |
1751 } | 1751 } |
1752 | 1752 |
1753 InstructionOperand* hint = current->FirstHint(); | 1753 InstructionOperand* hint = current->FirstHint(); |
1754 if (hint != NULL && (hint->IsRegister() || hint->IsDoubleRegister())) { | 1754 if (hint != NULL && (hint->IsRegister() || hint->IsDoubleRegister())) { |
1755 int register_index = hint->index(); | 1755 int register_index = hint->index(); |
(...skipping 30 matching lines...) Expand all Loading... |
1786 // Register reg is available at the range start but becomes blocked before | 1786 // Register reg is available at the range start but becomes blocked before |
1787 // the range end. Split current at position where it becomes blocked. | 1787 // the range end. Split current at position where it becomes blocked. |
1788 LiveRange* tail = SplitRangeAt(current, pos); | 1788 LiveRange* tail = SplitRangeAt(current, pos); |
1789 if (!AllocationOk()) return false; | 1789 if (!AllocationOk()) return false; |
1790 AddToUnhandledSorted(tail); | 1790 AddToUnhandledSorted(tail); |
1791 } | 1791 } |
1792 | 1792 |
1793 | 1793 |
1794 // Register reg is available at the range start and is free until | 1794 // Register reg is available at the range start and is free until |
1795 // the range end. | 1795 // the range end. |
1796 ASSERT(pos.Value() >= current->End().Value()); | 1796 DCHECK(pos.Value() >= current->End().Value()); |
1797 TraceAlloc("Assigning free reg %s to live range %d\n", RegisterName(reg), | 1797 TraceAlloc("Assigning free reg %s to live range %d\n", RegisterName(reg), |
1798 current->id()); | 1798 current->id()); |
1799 SetLiveRangeAssignedRegister(current, reg); | 1799 SetLiveRangeAssignedRegister(current, reg); |
1800 | 1800 |
1801 return true; | 1801 return true; |
1802 } | 1802 } |
1803 | 1803 |
1804 | 1804 |
1805 void RegisterAllocator::AllocateBlockedReg(LiveRange* current) { | 1805 void RegisterAllocator::AllocateBlockedReg(LiveRange* current) { |
1806 UsePosition* register_use = current->NextRegisterPosition(current->Start()); | 1806 UsePosition* register_use = current->NextRegisterPosition(current->Start()); |
(...skipping 24 matching lines...) Expand all Loading... |
1831 if (next_use == NULL) { | 1831 if (next_use == NULL) { |
1832 use_pos[cur_reg] = range->End(); | 1832 use_pos[cur_reg] = range->End(); |
1833 } else { | 1833 } else { |
1834 use_pos[cur_reg] = next_use->pos(); | 1834 use_pos[cur_reg] = next_use->pos(); |
1835 } | 1835 } |
1836 } | 1836 } |
1837 } | 1837 } |
1838 | 1838 |
1839 for (int i = 0; i < inactive_live_ranges_.length(); ++i) { | 1839 for (int i = 0; i < inactive_live_ranges_.length(); ++i) { |
1840 LiveRange* range = inactive_live_ranges_.at(i); | 1840 LiveRange* range = inactive_live_ranges_.at(i); |
1841 ASSERT(range->End().Value() > current->Start().Value()); | 1841 DCHECK(range->End().Value() > current->Start().Value()); |
1842 LifetimePosition next_intersection = range->FirstIntersection(current); | 1842 LifetimePosition next_intersection = range->FirstIntersection(current); |
1843 if (!next_intersection.IsValid()) continue; | 1843 if (!next_intersection.IsValid()) continue; |
1844 int cur_reg = range->assigned_register(); | 1844 int cur_reg = range->assigned_register(); |
1845 if (range->IsFixed()) { | 1845 if (range->IsFixed()) { |
1846 block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection); | 1846 block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection); |
1847 use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]); | 1847 use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]); |
1848 } else { | 1848 } else { |
1849 use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection); | 1849 use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection); |
1850 } | 1850 } |
1851 } | 1851 } |
(...skipping 17 matching lines...) Expand all Loading... |
1869 if (block_pos[reg].Value() < current->End().Value()) { | 1869 if (block_pos[reg].Value() < current->End().Value()) { |
1870 // Register becomes blocked before the current range end. Split before that | 1870 // Register becomes blocked before the current range end. Split before that |
1871 // position. | 1871 // position. |
1872 LiveRange* tail = SplitBetween(current, current->Start(), | 1872 LiveRange* tail = SplitBetween(current, current->Start(), |
1873 block_pos[reg].InstructionStart()); | 1873 block_pos[reg].InstructionStart()); |
1874 if (!AllocationOk()) return; | 1874 if (!AllocationOk()) return; |
1875 AddToUnhandledSorted(tail); | 1875 AddToUnhandledSorted(tail); |
1876 } | 1876 } |
1877 | 1877 |
1878 // Register reg is not blocked for the whole range. | 1878 // Register reg is not blocked for the whole range. |
1879 ASSERT(block_pos[reg].Value() >= current->End().Value()); | 1879 DCHECK(block_pos[reg].Value() >= current->End().Value()); |
1880 TraceAlloc("Assigning blocked reg %s to live range %d\n", RegisterName(reg), | 1880 TraceAlloc("Assigning blocked reg %s to live range %d\n", RegisterName(reg), |
1881 current->id()); | 1881 current->id()); |
1882 SetLiveRangeAssignedRegister(current, reg); | 1882 SetLiveRangeAssignedRegister(current, reg); |
1883 | 1883 |
1884 // This register was not free. Thus we need to find and spill | 1884 // This register was not free. Thus we need to find and spill |
1885 // parts of active and inactive live regions that use the same register | 1885 // parts of active and inactive live regions that use the same register |
1886 // at the same lifetime positions as current. | 1886 // at the same lifetime positions as current. |
1887 SplitAndSpillIntersecting(current); | 1887 SplitAndSpillIntersecting(current); |
1888 } | 1888 } |
1889 | 1889 |
(...skipping 24 matching lines...) Expand all Loading... |
1914 | 1914 |
1915 // Try hoisting out to an outer loop. | 1915 // Try hoisting out to an outer loop. |
1916 loop_header = code()->GetContainingLoop(loop_header); | 1916 loop_header = code()->GetContainingLoop(loop_header); |
1917 } | 1917 } |
1918 | 1918 |
1919 return pos; | 1919 return pos; |
1920 } | 1920 } |
1921 | 1921 |
1922 | 1922 |
1923 void RegisterAllocator::SplitAndSpillIntersecting(LiveRange* current) { | 1923 void RegisterAllocator::SplitAndSpillIntersecting(LiveRange* current) { |
1924 ASSERT(current->HasRegisterAssigned()); | 1924 DCHECK(current->HasRegisterAssigned()); |
1925 int reg = current->assigned_register(); | 1925 int reg = current->assigned_register(); |
1926 LifetimePosition split_pos = current->Start(); | 1926 LifetimePosition split_pos = current->Start(); |
1927 for (int i = 0; i < active_live_ranges_.length(); ++i) { | 1927 for (int i = 0; i < active_live_ranges_.length(); ++i) { |
1928 LiveRange* range = active_live_ranges_[i]; | 1928 LiveRange* range = active_live_ranges_[i]; |
1929 if (range->assigned_register() == reg) { | 1929 if (range->assigned_register() == reg) { |
1930 UsePosition* next_pos = range->NextRegisterPosition(current->Start()); | 1930 UsePosition* next_pos = range->NextRegisterPosition(current->Start()); |
1931 LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos); | 1931 LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos); |
1932 if (next_pos == NULL) { | 1932 if (next_pos == NULL) { |
1933 SpillAfter(range, spill_pos); | 1933 SpillAfter(range, spill_pos); |
1934 } else { | 1934 } else { |
1935 // When spilling between spill_pos and next_pos ensure that the range | 1935 // When spilling between spill_pos and next_pos ensure that the range |
1936 // remains spilled at least until the start of the current live range. | 1936 // remains spilled at least until the start of the current live range. |
1937 // This guarantees that we will not introduce new unhandled ranges that | 1937 // This guarantees that we will not introduce new unhandled ranges that |
1938 // start before the current range as this violates allocation invariant | 1938 // start before the current range as this violates allocation invariant |
1939 // and will lead to an inconsistent state of active and inactive | 1939 // and will lead to an inconsistent state of active and inactive |
1940 // live-ranges: ranges are allocated in order of their start positions, | 1940 // live-ranges: ranges are allocated in order of their start positions, |
1941 // ranges are retired from active/inactive when the start of the | 1941 // ranges are retired from active/inactive when the start of the |
1942 // current live-range is larger than their end. | 1942 // current live-range is larger than their end. |
1943 SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos()); | 1943 SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos()); |
1944 } | 1944 } |
1945 if (!AllocationOk()) return; | 1945 if (!AllocationOk()) return; |
1946 ActiveToHandled(range); | 1946 ActiveToHandled(range); |
1947 --i; | 1947 --i; |
1948 } | 1948 } |
1949 } | 1949 } |
1950 | 1950 |
1951 for (int i = 0; i < inactive_live_ranges_.length(); ++i) { | 1951 for (int i = 0; i < inactive_live_ranges_.length(); ++i) { |
1952 LiveRange* range = inactive_live_ranges_[i]; | 1952 LiveRange* range = inactive_live_ranges_[i]; |
1953 ASSERT(range->End().Value() > current->Start().Value()); | 1953 DCHECK(range->End().Value() > current->Start().Value()); |
1954 if (range->assigned_register() == reg && !range->IsFixed()) { | 1954 if (range->assigned_register() == reg && !range->IsFixed()) { |
1955 LifetimePosition next_intersection = range->FirstIntersection(current); | 1955 LifetimePosition next_intersection = range->FirstIntersection(current); |
1956 if (next_intersection.IsValid()) { | 1956 if (next_intersection.IsValid()) { |
1957 UsePosition* next_pos = range->NextRegisterPosition(current->Start()); | 1957 UsePosition* next_pos = range->NextRegisterPosition(current->Start()); |
1958 if (next_pos == NULL) { | 1958 if (next_pos == NULL) { |
1959 SpillAfter(range, split_pos); | 1959 SpillAfter(range, split_pos); |
1960 } else { | 1960 } else { |
1961 next_intersection = Min(next_intersection, next_pos->pos()); | 1961 next_intersection = Min(next_intersection, next_pos->pos()); |
1962 SpillBetween(range, split_pos, next_intersection); | 1962 SpillBetween(range, split_pos, next_intersection); |
1963 } | 1963 } |
1964 if (!AllocationOk()) return; | 1964 if (!AllocationOk()) return; |
1965 InactiveToHandled(range); | 1965 InactiveToHandled(range); |
1966 --i; | 1966 --i; |
1967 } | 1967 } |
1968 } | 1968 } |
1969 } | 1969 } |
1970 } | 1970 } |
1971 | 1971 |
1972 | 1972 |
1973 bool RegisterAllocator::IsBlockBoundary(LifetimePosition pos) { | 1973 bool RegisterAllocator::IsBlockBoundary(LifetimePosition pos) { |
1974 return pos.IsInstructionStart() && | 1974 return pos.IsInstructionStart() && |
1975 InstructionAt(pos.InstructionIndex())->IsBlockStart(); | 1975 InstructionAt(pos.InstructionIndex())->IsBlockStart(); |
1976 } | 1976 } |
1977 | 1977 |
1978 | 1978 |
1979 LiveRange* RegisterAllocator::SplitRangeAt(LiveRange* range, | 1979 LiveRange* RegisterAllocator::SplitRangeAt(LiveRange* range, |
1980 LifetimePosition pos) { | 1980 LifetimePosition pos) { |
1981 ASSERT(!range->IsFixed()); | 1981 DCHECK(!range->IsFixed()); |
1982 TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value()); | 1982 TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value()); |
1983 | 1983 |
1984 if (pos.Value() <= range->Start().Value()) return range; | 1984 if (pos.Value() <= range->Start().Value()) return range; |
1985 | 1985 |
1986 // We can't properly connect liveranges if split occured at the end | 1986 // We can't properly connect liveranges if split occured at the end |
1987 // of control instruction. | 1987 // of control instruction. |
1988 ASSERT(pos.IsInstructionStart() || | 1988 DCHECK(pos.IsInstructionStart() || |
1989 !InstructionAt(pos.InstructionIndex())->IsControl()); | 1989 !InstructionAt(pos.InstructionIndex())->IsControl()); |
1990 | 1990 |
1991 int vreg = GetVirtualRegister(); | 1991 int vreg = GetVirtualRegister(); |
1992 if (!AllocationOk()) return NULL; | 1992 if (!AllocationOk()) return NULL; |
1993 LiveRange* result = LiveRangeFor(vreg); | 1993 LiveRange* result = LiveRangeFor(vreg); |
1994 range->SplitAt(pos, result, zone()); | 1994 range->SplitAt(pos, result, zone()); |
1995 return result; | 1995 return result; |
1996 } | 1996 } |
1997 | 1997 |
1998 | 1998 |
1999 LiveRange* RegisterAllocator::SplitBetween(LiveRange* range, | 1999 LiveRange* RegisterAllocator::SplitBetween(LiveRange* range, |
2000 LifetimePosition start, | 2000 LifetimePosition start, |
2001 LifetimePosition end) { | 2001 LifetimePosition end) { |
2002 ASSERT(!range->IsFixed()); | 2002 DCHECK(!range->IsFixed()); |
2003 TraceAlloc("Splitting live range %d in position between [%d, %d]\n", | 2003 TraceAlloc("Splitting live range %d in position between [%d, %d]\n", |
2004 range->id(), start.Value(), end.Value()); | 2004 range->id(), start.Value(), end.Value()); |
2005 | 2005 |
2006 LifetimePosition split_pos = FindOptimalSplitPos(start, end); | 2006 LifetimePosition split_pos = FindOptimalSplitPos(start, end); |
2007 ASSERT(split_pos.Value() >= start.Value()); | 2007 DCHECK(split_pos.Value() >= start.Value()); |
2008 return SplitRangeAt(range, split_pos); | 2008 return SplitRangeAt(range, split_pos); |
2009 } | 2009 } |
2010 | 2010 |
2011 | 2011 |
2012 LifetimePosition RegisterAllocator::FindOptimalSplitPos(LifetimePosition start, | 2012 LifetimePosition RegisterAllocator::FindOptimalSplitPos(LifetimePosition start, |
2013 LifetimePosition end) { | 2013 LifetimePosition end) { |
2014 int start_instr = start.InstructionIndex(); | 2014 int start_instr = start.InstructionIndex(); |
2015 int end_instr = end.InstructionIndex(); | 2015 int end_instr = end.InstructionIndex(); |
2016 ASSERT(start_instr <= end_instr); | 2016 DCHECK(start_instr <= end_instr); |
2017 | 2017 |
2018 // We have no choice | 2018 // We have no choice |
2019 if (start_instr == end_instr) return end; | 2019 if (start_instr == end_instr) return end; |
2020 | 2020 |
2021 BasicBlock* start_block = GetBlock(start); | 2021 BasicBlock* start_block = GetBlock(start); |
2022 BasicBlock* end_block = GetBlock(end); | 2022 BasicBlock* end_block = GetBlock(end); |
2023 | 2023 |
2024 if (end_block == start_block) { | 2024 if (end_block == start_block) { |
2025 // The interval is split in the same basic block. Split at the latest | 2025 // The interval is split in the same basic block. Split at the latest |
2026 // possible position. | 2026 // possible position. |
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2068 | 2068 |
2069 if (second_part->Start().Value() < end.Value()) { | 2069 if (second_part->Start().Value() < end.Value()) { |
2070 // The split result intersects with [start, end[. | 2070 // The split result intersects with [start, end[. |
2071 // Split it at position between ]start+1, end[, spill the middle part | 2071 // Split it at position between ]start+1, end[, spill the middle part |
2072 // and put the rest to unhandled. | 2072 // and put the rest to unhandled. |
2073 LiveRange* third_part = SplitBetween( | 2073 LiveRange* third_part = SplitBetween( |
2074 second_part, Max(second_part->Start().InstructionEnd(), until), | 2074 second_part, Max(second_part->Start().InstructionEnd(), until), |
2075 end.PrevInstruction().InstructionEnd()); | 2075 end.PrevInstruction().InstructionEnd()); |
2076 if (!AllocationOk()) return; | 2076 if (!AllocationOk()) return; |
2077 | 2077 |
2078 ASSERT(third_part != second_part); | 2078 DCHECK(third_part != second_part); |
2079 | 2079 |
2080 Spill(second_part); | 2080 Spill(second_part); |
2081 AddToUnhandledSorted(third_part); | 2081 AddToUnhandledSorted(third_part); |
2082 } else { | 2082 } else { |
2083 // The split result does not intersect with [start, end[. | 2083 // The split result does not intersect with [start, end[. |
2084 // Nothing to spill. Just put it to unhandled as whole. | 2084 // Nothing to spill. Just put it to unhandled as whole. |
2085 AddToUnhandledSorted(second_part); | 2085 AddToUnhandledSorted(second_part); |
2086 } | 2086 } |
2087 } | 2087 } |
2088 | 2088 |
2089 | 2089 |
2090 void RegisterAllocator::Spill(LiveRange* range) { | 2090 void RegisterAllocator::Spill(LiveRange* range) { |
2091 ASSERT(!range->IsSpilled()); | 2091 DCHECK(!range->IsSpilled()); |
2092 TraceAlloc("Spilling live range %d\n", range->id()); | 2092 TraceAlloc("Spilling live range %d\n", range->id()); |
2093 LiveRange* first = range->TopLevel(); | 2093 LiveRange* first = range->TopLevel(); |
2094 | 2094 |
2095 if (!first->HasAllocatedSpillOperand()) { | 2095 if (!first->HasAllocatedSpillOperand()) { |
2096 InstructionOperand* op = TryReuseSpillSlot(range); | 2096 InstructionOperand* op = TryReuseSpillSlot(range); |
2097 if (op == NULL) { | 2097 if (op == NULL) { |
2098 // Allocate a new operand referring to the spill slot. | 2098 // Allocate a new operand referring to the spill slot. |
2099 RegisterKind kind = range->Kind(); | 2099 RegisterKind kind = range->Kind(); |
2100 int index = code()->frame()->AllocateSpillSlot(kind == DOUBLE_REGISTERS); | 2100 int index = code()->frame()->AllocateSpillSlot(kind == DOUBLE_REGISTERS); |
2101 if (kind == DOUBLE_REGISTERS) { | 2101 if (kind == DOUBLE_REGISTERS) { |
2102 op = DoubleStackSlotOperand::Create(index, zone()); | 2102 op = DoubleStackSlotOperand::Create(index, zone()); |
2103 } else { | 2103 } else { |
2104 ASSERT(kind == GENERAL_REGISTERS); | 2104 DCHECK(kind == GENERAL_REGISTERS); |
2105 op = StackSlotOperand::Create(index, zone()); | 2105 op = StackSlotOperand::Create(index, zone()); |
2106 } | 2106 } |
2107 } | 2107 } |
2108 first->SetSpillOperand(op); | 2108 first->SetSpillOperand(op); |
2109 } | 2109 } |
2110 range->MakeSpilled(code_zone()); | 2110 range->MakeSpilled(code_zone()); |
2111 } | 2111 } |
2112 | 2112 |
2113 | 2113 |
2114 int RegisterAllocator::RegisterCount() const { return num_registers_; } | 2114 int RegisterAllocator::RegisterCount() const { return num_registers_; } |
(...skipping 11 matching lines...) Expand all Loading... |
2126 | 2126 |
2127 | 2127 |
2128 #endif | 2128 #endif |
2129 | 2129 |
2130 | 2130 |
2131 void RegisterAllocator::SetLiveRangeAssignedRegister(LiveRange* range, | 2131 void RegisterAllocator::SetLiveRangeAssignedRegister(LiveRange* range, |
2132 int reg) { | 2132 int reg) { |
2133 if (range->Kind() == DOUBLE_REGISTERS) { | 2133 if (range->Kind() == DOUBLE_REGISTERS) { |
2134 assigned_double_registers_->Add(reg); | 2134 assigned_double_registers_->Add(reg); |
2135 } else { | 2135 } else { |
2136 ASSERT(range->Kind() == GENERAL_REGISTERS); | 2136 DCHECK(range->Kind() == GENERAL_REGISTERS); |
2137 assigned_registers_->Add(reg); | 2137 assigned_registers_->Add(reg); |
2138 } | 2138 } |
2139 range->set_assigned_register(reg, code_zone()); | 2139 range->set_assigned_register(reg, code_zone()); |
2140 } | 2140 } |
2141 | 2141 |
2142 | 2142 |
2143 RegisterAllocatorPhase::RegisterAllocatorPhase(const char* name, | 2143 RegisterAllocatorPhase::RegisterAllocatorPhase(const char* name, |
2144 RegisterAllocator* allocator) | 2144 RegisterAllocator* allocator) |
2145 : CompilationPhase(name, allocator->code()->linkage()->info()), | 2145 : CompilationPhase(name, allocator->code()->linkage()->info()), |
2146 allocator_(allocator) { | 2146 allocator_(allocator) { |
(...skipping 10 matching lines...) Expand all Loading... |
2157 allocator_zone_start_allocation_size_; | 2157 allocator_zone_start_allocation_size_; |
2158 isolate()->GetTStatistics()->SaveTiming(name(), base::TimeDelta(), size); | 2158 isolate()->GetTStatistics()->SaveTiming(name(), base::TimeDelta(), size); |
2159 } | 2159 } |
2160 #ifdef DEBUG | 2160 #ifdef DEBUG |
2161 if (allocator_ != NULL) allocator_->Verify(); | 2161 if (allocator_ != NULL) allocator_->Verify(); |
2162 #endif | 2162 #endif |
2163 } | 2163 } |
2164 } | 2164 } |
2165 } | 2165 } |
2166 } // namespace v8::internal::compiler | 2166 } // namespace v8::internal::compiler |
OLD | NEW |