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/linkage.h" | 5 #include "src/compiler/linkage.h" |
6 #include "src/compiler/pipeline-statistics.h" | 6 #include "src/compiler/pipeline-statistics.h" |
7 #include "src/compiler/register-allocator.h" | 7 #include "src/compiler/register-allocator.h" |
8 #include "src/string-stream.h" | 8 #include "src/string-stream.h" |
9 | 9 |
10 namespace v8 { | 10 namespace v8 { |
11 namespace internal { | 11 namespace internal { |
12 namespace compiler { | 12 namespace compiler { |
13 | 13 |
14 static inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) { | 14 static inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) { |
15 return a.Value() < b.Value() ? a : b; | 15 return a.Value() < b.Value() ? a : b; |
16 } | 16 } |
17 | 17 |
18 | 18 |
19 static inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) { | 19 static inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) { |
20 return a.Value() > b.Value() ? a : b; | 20 return a.Value() > b.Value() ? a : b; |
21 } | 21 } |
22 | 22 |
23 | 23 |
| 24 static void TraceAlloc(const char* msg, ...) { |
| 25 if (FLAG_trace_alloc) { |
| 26 va_list arguments; |
| 27 va_start(arguments, msg); |
| 28 base::OS::VPrint(msg, arguments); |
| 29 va_end(arguments); |
| 30 } |
| 31 } |
| 32 |
| 33 |
24 UsePosition::UsePosition(LifetimePosition pos, InstructionOperand* operand, | 34 UsePosition::UsePosition(LifetimePosition pos, InstructionOperand* operand, |
25 InstructionOperand* hint) | 35 InstructionOperand* hint) |
26 : operand_(operand), | 36 : operand_(operand), |
27 hint_(hint), | 37 hint_(hint), |
28 pos_(pos), | 38 pos_(pos), |
29 next_(NULL), | 39 next_(NULL), |
30 requires_reg_(false), | 40 requires_reg_(false), |
31 register_beneficial_(true) { | 41 register_beneficial_(true) { |
32 if (operand_ != NULL && operand_->IsUnallocated()) { | 42 if (operand_ != NULL && operand_->IsUnallocated()) { |
33 const UnallocatedOperand* unalloc = UnallocatedOperand::cast(operand_); | 43 const UnallocatedOperand* unalloc = UnallocatedOperand::cast(operand_); |
(...skipping 307 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
341 if (pos == NULL) return false; | 351 if (pos == NULL) return false; |
342 UsePosition* other_pos = other->first_pos(); | 352 UsePosition* other_pos = other->first_pos(); |
343 if (other_pos == NULL) return true; | 353 if (other_pos == NULL) return true; |
344 return pos->pos().Value() < other_pos->pos().Value(); | 354 return pos->pos().Value() < other_pos->pos().Value(); |
345 } | 355 } |
346 return start.Value() < other_start.Value(); | 356 return start.Value() < other_start.Value(); |
347 } | 357 } |
348 | 358 |
349 | 359 |
350 void LiveRange::ShortenTo(LifetimePosition start) { | 360 void LiveRange::ShortenTo(LifetimePosition start) { |
351 RegisterAllocator::TraceAlloc("Shorten live range %d to [%d\n", id_, | 361 TraceAlloc("Shorten live range %d to [%d\n", id_, start.Value()); |
352 start.Value()); | |
353 DCHECK(first_interval_ != NULL); | 362 DCHECK(first_interval_ != NULL); |
354 DCHECK(first_interval_->start().Value() <= start.Value()); | 363 DCHECK(first_interval_->start().Value() <= start.Value()); |
355 DCHECK(start.Value() < first_interval_->end().Value()); | 364 DCHECK(start.Value() < first_interval_->end().Value()); |
356 first_interval_->set_start(start); | 365 first_interval_->set_start(start); |
357 } | 366 } |
358 | 367 |
359 | 368 |
360 void LiveRange::EnsureInterval(LifetimePosition start, LifetimePosition end, | 369 void LiveRange::EnsureInterval(LifetimePosition start, LifetimePosition end, |
361 Zone* zone) { | 370 Zone* zone) { |
362 RegisterAllocator::TraceAlloc("Ensure live range %d in interval [%d %d[\n", | 371 TraceAlloc("Ensure live range %d in interval [%d %d[\n", id_, start.Value(), |
363 id_, start.Value(), end.Value()); | 372 end.Value()); |
364 LifetimePosition new_end = end; | 373 LifetimePosition new_end = end; |
365 while (first_interval_ != NULL && | 374 while (first_interval_ != NULL && |
366 first_interval_->start().Value() <= end.Value()) { | 375 first_interval_->start().Value() <= end.Value()) { |
367 if (first_interval_->end().Value() > end.Value()) { | 376 if (first_interval_->end().Value() > end.Value()) { |
368 new_end = first_interval_->end(); | 377 new_end = first_interval_->end(); |
369 } | 378 } |
370 first_interval_ = first_interval_->next(); | 379 first_interval_ = first_interval_->next(); |
371 } | 380 } |
372 | 381 |
373 UseInterval* new_interval = new (zone) UseInterval(start, new_end); | 382 UseInterval* new_interval = new (zone) UseInterval(start, new_end); |
374 new_interval->next_ = first_interval_; | 383 new_interval->next_ = first_interval_; |
375 first_interval_ = new_interval; | 384 first_interval_ = new_interval; |
376 if (new_interval->next() == NULL) { | 385 if (new_interval->next() == NULL) { |
377 last_interval_ = new_interval; | 386 last_interval_ = new_interval; |
378 } | 387 } |
379 } | 388 } |
380 | 389 |
381 | 390 |
382 void LiveRange::AddUseInterval(LifetimePosition start, LifetimePosition end, | 391 void LiveRange::AddUseInterval(LifetimePosition start, LifetimePosition end, |
383 Zone* zone) { | 392 Zone* zone) { |
384 RegisterAllocator::TraceAlloc("Add to live range %d interval [%d %d[\n", id_, | 393 TraceAlloc("Add to live range %d interval [%d %d[\n", id_, start.Value(), |
385 start.Value(), end.Value()); | 394 end.Value()); |
386 if (first_interval_ == NULL) { | 395 if (first_interval_ == NULL) { |
387 UseInterval* interval = new (zone) UseInterval(start, end); | 396 UseInterval* interval = new (zone) UseInterval(start, end); |
388 first_interval_ = interval; | 397 first_interval_ = interval; |
389 last_interval_ = interval; | 398 last_interval_ = interval; |
390 } else { | 399 } else { |
391 if (end.Value() == first_interval_->start().Value()) { | 400 if (end.Value() == first_interval_->start().Value()) { |
392 first_interval_->set_start(start); | 401 first_interval_->set_start(start); |
393 } else if (end.Value() < first_interval_->start().Value()) { | 402 } else if (end.Value() < first_interval_->start().Value()) { |
394 UseInterval* interval = new (zone) UseInterval(start, end); | 403 UseInterval* interval = new (zone) UseInterval(start, end); |
395 interval->set_next(first_interval_); | 404 interval->set_next(first_interval_); |
396 first_interval_ = interval; | 405 first_interval_ = interval; |
397 } else { | 406 } else { |
398 // Order of instruction's processing (see ProcessInstructions) guarantees | 407 // Order of instruction's processing (see ProcessInstructions) guarantees |
399 // that each new use interval either precedes or intersects with | 408 // that each new use interval either precedes or intersects with |
400 // last added interval. | 409 // last added interval. |
401 DCHECK(start.Value() < first_interval_->end().Value()); | 410 DCHECK(start.Value() < first_interval_->end().Value()); |
402 first_interval_->start_ = Min(start, first_interval_->start_); | 411 first_interval_->start_ = Min(start, first_interval_->start_); |
403 first_interval_->end_ = Max(end, first_interval_->end_); | 412 first_interval_->end_ = Max(end, first_interval_->end_); |
404 } | 413 } |
405 } | 414 } |
406 } | 415 } |
407 | 416 |
408 | 417 |
409 void LiveRange::AddUsePosition(LifetimePosition pos, | 418 void LiveRange::AddUsePosition(LifetimePosition pos, |
410 InstructionOperand* operand, | 419 InstructionOperand* operand, |
411 InstructionOperand* hint, Zone* zone) { | 420 InstructionOperand* hint, Zone* zone) { |
412 RegisterAllocator::TraceAlloc("Add to live range %d use position %d\n", id_, | 421 TraceAlloc("Add to live range %d use position %d\n", id_, pos.Value()); |
413 pos.Value()); | |
414 UsePosition* use_pos = new (zone) UsePosition(pos, operand, hint); | 422 UsePosition* use_pos = new (zone) UsePosition(pos, operand, hint); |
415 UsePosition* prev_hint = NULL; | 423 UsePosition* prev_hint = NULL; |
416 UsePosition* prev = NULL; | 424 UsePosition* prev = NULL; |
417 UsePosition* current = first_pos_; | 425 UsePosition* current = first_pos_; |
418 while (current != NULL && current->pos().Value() < pos.Value()) { | 426 while (current != NULL && current->pos().Value() < pos.Value()) { |
419 prev_hint = current->HasHint() ? current : prev_hint; | 427 prev_hint = current->HasHint() ? current : prev_hint; |
420 prev = current; | 428 prev = current; |
421 current = current->next(); | 429 current = current->next(); |
422 } | 430 } |
423 | 431 |
(...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
492 AdvanceLastProcessedMarker(a, advance_last_processed_up_to); | 500 AdvanceLastProcessedMarker(a, advance_last_processed_up_to); |
493 } else { | 501 } else { |
494 b = b->next(); | 502 b = b->next(); |
495 } | 503 } |
496 } | 504 } |
497 return LifetimePosition::Invalid(); | 505 return LifetimePosition::Invalid(); |
498 } | 506 } |
499 | 507 |
500 | 508 |
501 RegisterAllocator::RegisterAllocator(Zone* local_zone, Frame* frame, | 509 RegisterAllocator::RegisterAllocator(Zone* local_zone, Frame* frame, |
502 CompilationInfo* info, | 510 InstructionSequence* code, |
503 InstructionSequence* code) | 511 const char* debug_name) |
504 : zone_(local_zone), | 512 : zone_(local_zone), |
505 frame_(frame), | 513 frame_(frame), |
506 info_(info), | |
507 code_(code), | 514 code_(code), |
| 515 debug_name_(debug_name), |
508 live_in_sets_(code->InstructionBlockCount(), zone()), | 516 live_in_sets_(code->InstructionBlockCount(), zone()), |
509 live_ranges_(code->VirtualRegisterCount() * 2, zone()), | 517 live_ranges_(code->VirtualRegisterCount() * 2, zone()), |
510 fixed_live_ranges_(NULL), | 518 fixed_live_ranges_(NULL), |
511 fixed_double_live_ranges_(NULL), | 519 fixed_double_live_ranges_(NULL), |
512 unhandled_live_ranges_(code->VirtualRegisterCount() * 2, zone()), | 520 unhandled_live_ranges_(code->VirtualRegisterCount() * 2, zone()), |
513 active_live_ranges_(8, zone()), | 521 active_live_ranges_(8, zone()), |
514 inactive_live_ranges_(8, zone()), | 522 inactive_live_ranges_(8, zone()), |
515 reusable_slots_(8, zone()), | 523 reusable_slots_(8, zone()), |
516 mode_(UNALLOCATED_REGISTERS), | 524 mode_(UNALLOCATED_REGISTERS), |
517 num_registers_(-1), | 525 num_registers_(-1), |
(...skipping 849 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1367 if (block_id == 0) { | 1375 if (block_id == 0) { |
1368 BitVector::Iterator iterator(live); | 1376 BitVector::Iterator iterator(live); |
1369 bool found = false; | 1377 bool found = false; |
1370 while (!iterator.Done()) { | 1378 while (!iterator.Done()) { |
1371 found = true; | 1379 found = true; |
1372 int operand_index = iterator.Current(); | 1380 int operand_index = iterator.Current(); |
1373 PrintF("Register allocator error: live v%d reached first block.\n", | 1381 PrintF("Register allocator error: live v%d reached first block.\n", |
1374 operand_index); | 1382 operand_index); |
1375 LiveRange* range = LiveRangeFor(operand_index); | 1383 LiveRange* range = LiveRangeFor(operand_index); |
1376 PrintF(" (first use is at %d)\n", range->first_pos()->pos().Value()); | 1384 PrintF(" (first use is at %d)\n", range->first_pos()->pos().Value()); |
1377 CompilationInfo* info = this->info(); | 1385 if (debug_name() == nullptr) { |
1378 if (info->IsStub()) { | 1386 PrintF("\n"); |
1379 if (info->code_stub() == NULL) { | |
1380 PrintF("\n"); | |
1381 } else { | |
1382 CodeStub::Major major_key = info->code_stub()->MajorKey(); | |
1383 PrintF(" (function: %s)\n", CodeStub::MajorName(major_key, false)); | |
1384 } | |
1385 } else { | 1387 } else { |
1386 DCHECK(info->IsOptimizing()); | 1388 PrintF(" (function: %s)\n", debug_name()); |
1387 AllowHandleDereference allow_deref; | |
1388 PrintF(" (function: %s)\n", | |
1389 info->function()->debug_name()->ToCString().get()); | |
1390 } | 1389 } |
1391 iterator.Advance(); | 1390 iterator.Advance(); |
1392 } | 1391 } |
1393 DCHECK(!found); | 1392 DCHECK(!found); |
1394 } | 1393 } |
1395 #endif | 1394 #endif |
1396 } | 1395 } |
1397 | 1396 |
1398 for (int i = 0; i < live_ranges_.length(); ++i) { | 1397 for (int i = 0; i < live_ranges_.length(); ++i) { |
1399 if (live_ranges_[i] != NULL) { | 1398 if (live_ranges_[i] != NULL) { |
(...skipping 237 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1637 | 1636 |
1638 const char* RegisterAllocator::RegisterName(int allocation_index) { | 1637 const char* RegisterAllocator::RegisterName(int allocation_index) { |
1639 if (mode_ == GENERAL_REGISTERS) { | 1638 if (mode_ == GENERAL_REGISTERS) { |
1640 return Register::AllocationIndexToString(allocation_index); | 1639 return Register::AllocationIndexToString(allocation_index); |
1641 } else { | 1640 } else { |
1642 return DoubleRegister::AllocationIndexToString(allocation_index); | 1641 return DoubleRegister::AllocationIndexToString(allocation_index); |
1643 } | 1642 } |
1644 } | 1643 } |
1645 | 1644 |
1646 | 1645 |
1647 void RegisterAllocator::TraceAlloc(const char* msg, ...) { | |
1648 if (FLAG_trace_alloc) { | |
1649 va_list arguments; | |
1650 va_start(arguments, msg); | |
1651 base::OS::VPrint(msg, arguments); | |
1652 va_end(arguments); | |
1653 } | |
1654 } | |
1655 | |
1656 | |
1657 bool RegisterAllocator::HasTaggedValue(int virtual_register) const { | 1646 bool RegisterAllocator::HasTaggedValue(int virtual_register) const { |
1658 return code()->IsReference(virtual_register); | 1647 return code()->IsReference(virtual_register); |
1659 } | 1648 } |
1660 | 1649 |
1661 | 1650 |
1662 RegisterKind RegisterAllocator::RequiredRegisterKind( | 1651 RegisterKind RegisterAllocator::RequiredRegisterKind( |
1663 int virtual_register) const { | 1652 int virtual_register) const { |
1664 return (code()->IsDouble(virtual_register)) ? DOUBLE_REGISTERS | 1653 return (code()->IsDouble(virtual_register)) ? DOUBLE_REGISTERS |
1665 : GENERAL_REGISTERS; | 1654 : GENERAL_REGISTERS; |
1666 } | 1655 } |
(...skipping 548 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2215 } else { | 2204 } else { |
2216 DCHECK(range->Kind() == GENERAL_REGISTERS); | 2205 DCHECK(range->Kind() == GENERAL_REGISTERS); |
2217 assigned_registers_->Add(reg); | 2206 assigned_registers_->Add(reg); |
2218 } | 2207 } |
2219 range->set_assigned_register(reg, code_zone()); | 2208 range->set_assigned_register(reg, code_zone()); |
2220 } | 2209 } |
2221 | 2210 |
2222 } | 2211 } |
2223 } | 2212 } |
2224 } // namespace v8::internal::compiler | 2213 } // namespace v8::internal::compiler |
OLD | NEW |