| OLD | NEW |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 #include "vm/flow_graph_allocator.h" | 5 #include "vm/flow_graph_allocator.h" |
| 6 | 6 |
| 7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
| 8 #include "vm/intermediate_language.h" | 8 #include "vm/intermediate_language.h" |
| 9 #include "vm/il_printer.h" | 9 #include "vm/il_printer.h" |
| 10 #include "vm/flow_graph.h" | 10 #include "vm/flow_graph.h" |
| (...skipping 248 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 259 } | 259 } |
| 260 | 260 |
| 261 ComputeInitialSets(); | 261 ComputeInitialSets(); |
| 262 ComputeLiveInAndLiveOutSets(); | 262 ComputeLiveInAndLiveOutSets(); |
| 263 } | 263 } |
| 264 | 264 |
| 265 | 265 |
| 266 static void PrintBitVector(const char* tag, BitVector* v) { | 266 static void PrintBitVector(const char* tag, BitVector* v) { |
| 267 OS::Print("%s:", tag); | 267 OS::Print("%s:", tag); |
| 268 for (BitVector::Iterator it(v); !it.Done(); it.Advance()) { | 268 for (BitVector::Iterator it(v); !it.Done(); it.Advance()) { |
| 269 OS::Print(" %d", it.Current()); | 269 OS::Print(" %"Pd"", it.Current()); |
| 270 } | 270 } |
| 271 OS::Print("\n"); | 271 OS::Print("\n"); |
| 272 } | 272 } |
| 273 | 273 |
| 274 | 274 |
| 275 void FlowGraphAllocator::DumpLiveness() { | 275 void FlowGraphAllocator::DumpLiveness() { |
| 276 const intptr_t block_count = postorder_.length(); | 276 const intptr_t block_count = postorder_.length(); |
| 277 for (intptr_t i = 0; i < block_count; i++) { | 277 for (intptr_t i = 0; i < block_count; i++) { |
| 278 BlockEntryInstr* block = postorder_[i]; | 278 BlockEntryInstr* block = postorder_[i]; |
| 279 OS::Print("block @%d -> ", block->block_id()); | 279 OS::Print("block @%"Pd" -> ", block->block_id()); |
| 280 | 280 |
| 281 Instruction* last = block->last_instruction(); | 281 Instruction* last = block->last_instruction(); |
| 282 for (intptr_t j = 0; j < last->SuccessorCount(); j++) { | 282 for (intptr_t j = 0; j < last->SuccessorCount(); j++) { |
| 283 BlockEntryInstr* succ = last->SuccessorAt(j); | 283 BlockEntryInstr* succ = last->SuccessorAt(j); |
| 284 OS::Print(" @%d", succ->block_id()); | 284 OS::Print(" @%"Pd"", succ->block_id()); |
| 285 } | 285 } |
| 286 OS::Print("\n"); | 286 OS::Print("\n"); |
| 287 | 287 |
| 288 PrintBitVector(" live out", live_out_[i]); | 288 PrintBitVector(" live out", live_out_[i]); |
| 289 PrintBitVector(" kill", kill_[i]); | 289 PrintBitVector(" kill", kill_[i]); |
| 290 PrintBitVector(" live in", live_in_[i]); | 290 PrintBitVector(" live in", live_in_[i]); |
| 291 } | 291 } |
| 292 } | 292 } |
| 293 | 293 |
| 294 | 294 |
| (...skipping 141 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 436 UNREACHABLE(); | 436 UNREACHABLE(); |
| 437 } | 437 } |
| 438 } | 438 } |
| 439 | 439 |
| 440 | 440 |
| 441 void LiveRange::Print() { | 441 void LiveRange::Print() { |
| 442 if (first_use_interval() == NULL) { | 442 if (first_use_interval() == NULL) { |
| 443 return; | 443 return; |
| 444 } | 444 } |
| 445 | 445 |
| 446 OS::Print(" live range v%d [%d, %d) in ", vreg(), Start(), End()); | 446 OS::Print(" live range v%"Pd" [%"Pd", %"Pd") in ", vreg(), Start(), End()); |
| 447 assigned_location().Print(); | 447 assigned_location().Print(); |
| 448 OS::Print("\n"); | 448 OS::Print("\n"); |
| 449 | 449 |
| 450 UsePosition* use_pos = uses_; | 450 UsePosition* use_pos = uses_; |
| 451 for (UseInterval* interval = first_use_interval_; | 451 for (UseInterval* interval = first_use_interval_; |
| 452 interval != NULL; | 452 interval != NULL; |
| 453 interval = interval->next()) { | 453 interval = interval->next()) { |
| 454 OS::Print(" use interval [%d, %d)\n", | 454 OS::Print(" use interval [%"Pd", %"Pd")\n", |
| 455 interval->start(), | 455 interval->start(), |
| 456 interval->end()); | 456 interval->end()); |
| 457 while ((use_pos != NULL) && (use_pos->pos() <= interval->end())) { | 457 while ((use_pos != NULL) && (use_pos->pos() <= interval->end())) { |
| 458 OS::Print(" use at %d", use_pos->pos()); | 458 OS::Print(" use at %"Pd"", use_pos->pos()); |
| 459 if (use_pos->location_slot() != NULL) { | 459 if (use_pos->location_slot() != NULL) { |
| 460 OS::Print(" as "); | 460 OS::Print(" as "); |
| 461 use_pos->location_slot()->Print(); | 461 use_pos->location_slot()->Print(); |
| 462 } | 462 } |
| 463 OS::Print("\n"); | 463 OS::Print("\n"); |
| 464 use_pos = use_pos->next(); | 464 use_pos = use_pos->next(); |
| 465 } | 465 } |
| 466 } | 466 } |
| 467 | 467 |
| 468 if (next_sibling() != NULL) { | 468 if (next_sibling() != NULL) { |
| (...skipping 883 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1352 | 1352 |
| 1353 UseInterval* last_use_interval = (last_before_split == last_use_interval_) ? | 1353 UseInterval* last_use_interval = (last_before_split == last_use_interval_) ? |
| 1354 first_after_split : last_use_interval_; | 1354 first_after_split : last_use_interval_; |
| 1355 next_sibling_ = new LiveRange(vreg(), | 1355 next_sibling_ = new LiveRange(vreg(), |
| 1356 first_use_after_split, | 1356 first_use_after_split, |
| 1357 first_after_split, | 1357 first_after_split, |
| 1358 last_use_interval, | 1358 last_use_interval, |
| 1359 first_safepoint_after_split, | 1359 first_safepoint_after_split, |
| 1360 next_sibling_); | 1360 next_sibling_); |
| 1361 | 1361 |
| 1362 TRACE_ALLOC(OS::Print(" split sibling [%d, %d)\n", | 1362 TRACE_ALLOC(OS::Print(" split sibling [%"Pd", %"Pd")\n", |
| 1363 next_sibling_->Start(), next_sibling_->End())); | 1363 next_sibling_->Start(), next_sibling_->End())); |
| 1364 | 1364 |
| 1365 last_use_interval_ = last_before_split; | 1365 last_use_interval_ = last_before_split; |
| 1366 last_use_interval_->next_ = NULL; | 1366 last_use_interval_->next_ = NULL; |
| 1367 | 1367 |
| 1368 if (first_use_after_split != NULL) { | 1368 if (first_use_after_split != NULL) { |
| 1369 finger_.UpdateAfterSplit(first_use_after_split->pos()); | 1369 finger_.UpdateAfterSplit(first_use_after_split->pos()); |
| 1370 } | 1370 } |
| 1371 | 1371 |
| 1372 return next_sibling_; | 1372 return next_sibling_; |
| 1373 } | 1373 } |
| 1374 | 1374 |
| 1375 | 1375 |
| 1376 LiveRange* FlowGraphAllocator::SplitBetween(LiveRange* range, | 1376 LiveRange* FlowGraphAllocator::SplitBetween(LiveRange* range, |
| 1377 intptr_t from, | 1377 intptr_t from, |
| 1378 intptr_t to) { | 1378 intptr_t to) { |
| 1379 TRACE_ALLOC(OS::Print("split %d [%d, %d) between [%d, %d)\n", | 1379 TRACE_ALLOC(OS::Print("split %"Pd" [%"Pd", %"Pd") between [%"Pd", %"Pd")\n", |
| 1380 range->vreg(), range->Start(), range->End(), from, to)); | 1380 range->vreg(), range->Start(), range->End(), from, to)); |
| 1381 | 1381 |
| 1382 intptr_t split_pos = kIllegalPosition; | 1382 intptr_t split_pos = kIllegalPosition; |
| 1383 | 1383 |
| 1384 BlockInfo* split_block = BlockInfoAt(to); | 1384 BlockInfo* split_block = BlockInfoAt(to); |
| 1385 if (from < split_block->entry()->lifetime_position()) { | 1385 if (from < split_block->entry()->lifetime_position()) { |
| 1386 // Interval [from, to) spans multiple blocks. | 1386 // Interval [from, to) spans multiple blocks. |
| 1387 | 1387 |
| 1388 // If last block is inside a loop prefer splitting at outermost loop's | 1388 // If last block is inside a loop prefer splitting at outermost loop's |
| 1389 // header. | 1389 // header. |
| (...skipping 17 matching lines...) Expand all Loading... |
| 1407 ASSERT((split_pos != kIllegalPosition) && (from < split_pos)); | 1407 ASSERT((split_pos != kIllegalPosition) && (from < split_pos)); |
| 1408 | 1408 |
| 1409 return range->SplitAt(split_pos); | 1409 return range->SplitAt(split_pos); |
| 1410 } | 1410 } |
| 1411 | 1411 |
| 1412 | 1412 |
| 1413 void FlowGraphAllocator::SpillBetween(LiveRange* range, | 1413 void FlowGraphAllocator::SpillBetween(LiveRange* range, |
| 1414 intptr_t from, | 1414 intptr_t from, |
| 1415 intptr_t to) { | 1415 intptr_t to) { |
| 1416 ASSERT(from < to); | 1416 ASSERT(from < to); |
| 1417 TRACE_ALLOC(OS::Print("spill %d [%d, %d) between [%d, %d)\n", | 1417 TRACE_ALLOC(OS::Print("spill %"Pd" [%"Pd", %"Pd") " |
| 1418 "between [%"Pd", %"Pd")\n", |
| 1418 range->vreg(), range->Start(), range->End(), from, to)); | 1419 range->vreg(), range->Start(), range->End(), from, to)); |
| 1419 LiveRange* tail = range->SplitAt(from); | 1420 LiveRange* tail = range->SplitAt(from); |
| 1420 | 1421 |
| 1421 if (tail->Start() < to) { | 1422 if (tail->Start() < to) { |
| 1422 // There is an intersection of tail and [from, to). | 1423 // There is an intersection of tail and [from, to). |
| 1423 LiveRange* tail_tail = SplitBetween(tail, tail->Start(), to); | 1424 LiveRange* tail_tail = SplitBetween(tail, tail->Start(), to); |
| 1424 Spill(tail); | 1425 Spill(tail); |
| 1425 AddToUnallocated(tail_tail); | 1426 AddToUnallocated(tail_tail); |
| 1426 } else { | 1427 } else { |
| 1427 // No intersection between tail and [from, to). | 1428 // No intersection between tail and [from, to). |
| 1428 AddToUnallocated(tail); | 1429 AddToUnallocated(tail); |
| 1429 } | 1430 } |
| 1430 } | 1431 } |
| 1431 | 1432 |
| 1432 | 1433 |
| 1433 void FlowGraphAllocator::SpillAfter(LiveRange* range, intptr_t from) { | 1434 void FlowGraphAllocator::SpillAfter(LiveRange* range, intptr_t from) { |
| 1434 TRACE_ALLOC(OS::Print("spill %d [%d, %d) after %d\n", | 1435 TRACE_ALLOC(OS::Print("spill %"Pd" [%"Pd", %"Pd") after %"Pd"\n", |
| 1435 range->vreg(), range->Start(), range->End(), from)); | 1436 range->vreg(), range->Start(), range->End(), from)); |
| 1436 LiveRange* tail = range->SplitAt(from); | 1437 LiveRange* tail = range->SplitAt(from); |
| 1437 Spill(tail); | 1438 Spill(tail); |
| 1438 } | 1439 } |
| 1439 | 1440 |
| 1440 | 1441 |
| 1441 void FlowGraphAllocator::AllocateSpillSlotFor(LiveRange* range) { | 1442 void FlowGraphAllocator::AllocateSpillSlotFor(LiveRange* range) { |
| 1442 ASSERT(range->spill_slot().IsInvalid()); | 1443 ASSERT(range->spill_slot().IsInvalid()); |
| 1443 | 1444 |
| 1444 intptr_t idx = 0; | 1445 intptr_t idx = 0; |
| (...skipping 85 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1530 Location hint = unallocated->finger()->FirstHint(); | 1531 Location hint = unallocated->finger()->FirstHint(); |
| 1531 if (hint.IsMachineRegister()) { | 1532 if (hint.IsMachineRegister()) { |
| 1532 if (!blocked_registers_[hint.register_code()]) { | 1533 if (!blocked_registers_[hint.register_code()]) { |
| 1533 free_until = FirstIntersectionWithAllocated(hint.register_code(), | 1534 free_until = FirstIntersectionWithAllocated(hint.register_code(), |
| 1534 unallocated); | 1535 unallocated); |
| 1535 candidate = hint.register_code(); | 1536 candidate = hint.register_code(); |
| 1536 } | 1537 } |
| 1537 | 1538 |
| 1538 TRACE_ALLOC(OS::Print("found hint ")); | 1539 TRACE_ALLOC(OS::Print("found hint ")); |
| 1539 TRACE_ALLOC(hint.Print()); | 1540 TRACE_ALLOC(hint.Print()); |
| 1540 TRACE_ALLOC(OS::Print(" for %d: free until %d\n", | 1541 TRACE_ALLOC(OS::Print(" for %"Pd": free until %"Pd"\n", |
| 1541 unallocated->vreg(), free_until)); | 1542 unallocated->vreg(), free_until)); |
| 1542 } else if (free_until != kMaxPosition) { | 1543 } else if (free_until != kMaxPosition) { |
| 1543 for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) { | 1544 for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) { |
| 1544 if (!blocked_registers_[reg] && (registers_[reg].length() == 0)) { | 1545 if (!blocked_registers_[reg] && (registers_[reg].length() == 0)) { |
| 1545 candidate = reg; | 1546 candidate = reg; |
| 1546 free_until = kMaxPosition; | 1547 free_until = kMaxPosition; |
| 1547 break; | 1548 break; |
| 1548 } | 1549 } |
| 1549 } | 1550 } |
| 1550 } | 1551 } |
| (...skipping 10 matching lines...) Expand all Loading... |
| 1561 if (free_until == kMaxPosition) break; | 1562 if (free_until == kMaxPosition) break; |
| 1562 } | 1563 } |
| 1563 } | 1564 } |
| 1564 } | 1565 } |
| 1565 | 1566 |
| 1566 // All registers are blocked by active ranges. | 1567 // All registers are blocked by active ranges. |
| 1567 if (free_until <= unallocated->Start()) return false; | 1568 if (free_until <= unallocated->Start()) return false; |
| 1568 | 1569 |
| 1569 TRACE_ALLOC(OS::Print("assigning free register ")); | 1570 TRACE_ALLOC(OS::Print("assigning free register ")); |
| 1570 TRACE_ALLOC(MakeRegisterLocation(candidate).Print()); | 1571 TRACE_ALLOC(MakeRegisterLocation(candidate).Print()); |
| 1571 TRACE_ALLOC(OS::Print(" to %d\n", unallocated->vreg())); | 1572 TRACE_ALLOC(OS::Print(" to %"Pd"\n", unallocated->vreg())); |
| 1572 | 1573 |
| 1573 if (free_until != kMaxPosition) { | 1574 if (free_until != kMaxPosition) { |
| 1574 // There was an intersection. Split unallocated. | 1575 // There was an intersection. Split unallocated. |
| 1575 TRACE_ALLOC(OS::Print(" splitting at %d\n", free_until)); | 1576 TRACE_ALLOC(OS::Print(" splitting at %"Pd"\n", free_until)); |
| 1576 LiveRange* tail = unallocated->SplitAt(free_until); | 1577 LiveRange* tail = unallocated->SplitAt(free_until); |
| 1577 AddToUnallocated(tail); | 1578 AddToUnallocated(tail); |
| 1578 } | 1579 } |
| 1579 | 1580 |
| 1580 registers_[candidate].Add(unallocated); | 1581 registers_[candidate].Add(unallocated); |
| 1581 unallocated->set_assigned_location(MakeRegisterLocation(candidate)); | 1582 unallocated->set_assigned_location(MakeRegisterLocation(candidate)); |
| 1582 | 1583 |
| 1583 return true; | 1584 return true; |
| 1584 } | 1585 } |
| 1585 | 1586 |
| (...skipping 19 matching lines...) Expand all Loading... |
| 1605 | 1606 |
| 1606 if (free_until < register_use->pos()) { | 1607 if (free_until < register_use->pos()) { |
| 1607 // Can't acquire free register. Spill until we really need one. | 1608 // Can't acquire free register. Spill until we really need one. |
| 1608 ASSERT(unallocated->Start() < ToInstructionStart(register_use->pos())); | 1609 ASSERT(unallocated->Start() < ToInstructionStart(register_use->pos())); |
| 1609 SpillBetween(unallocated, unallocated->Start(), register_use->pos()); | 1610 SpillBetween(unallocated, unallocated->Start(), register_use->pos()); |
| 1610 return; | 1611 return; |
| 1611 } | 1612 } |
| 1612 | 1613 |
| 1613 TRACE_ALLOC(OS::Print("assigning blocked register ")); | 1614 TRACE_ALLOC(OS::Print("assigning blocked register ")); |
| 1614 TRACE_ALLOC(MakeRegisterLocation(candidate).Print()); | 1615 TRACE_ALLOC(MakeRegisterLocation(candidate).Print()); |
| 1615 TRACE_ALLOC(OS::Print(" to live range %d until %d\n", | 1616 TRACE_ALLOC(OS::Print(" to live range %"Pd" until %"Pd"\n", |
| 1616 unallocated->vreg(), blocked_at)); | 1617 unallocated->vreg(), blocked_at)); |
| 1617 | 1618 |
| 1618 if (blocked_at < unallocated->End()) { | 1619 if (blocked_at < unallocated->End()) { |
| 1619 // Register is blocked before the end of the live range. Split the range | 1620 // Register is blocked before the end of the live range. Split the range |
| 1620 // at latest at blocked_at position. | 1621 // at latest at blocked_at position. |
| 1621 LiveRange* tail = SplitBetween(unallocated, | 1622 LiveRange* tail = SplitBetween(unallocated, |
| 1622 unallocated->Start(), | 1623 unallocated->Start(), |
| 1623 blocked_at + 1); | 1624 blocked_at + 1); |
| 1624 AddToUnallocated(tail); | 1625 AddToUnallocated(tail); |
| 1625 } | 1626 } |
| (...skipping 136 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1762 } | 1763 } |
| 1763 | 1764 |
| 1764 return parallel_move->AddMove(to, from); | 1765 return parallel_move->AddMove(to, from); |
| 1765 } | 1766 } |
| 1766 | 1767 |
| 1767 | 1768 |
| 1768 void FlowGraphAllocator::ConvertUseTo(UsePosition* use, Location loc) { | 1769 void FlowGraphAllocator::ConvertUseTo(UsePosition* use, Location loc) { |
| 1769 ASSERT(use->location_slot() != NULL); | 1770 ASSERT(use->location_slot() != NULL); |
| 1770 Location* slot = use->location_slot(); | 1771 Location* slot = use->location_slot(); |
| 1771 ASSERT(slot->IsUnallocated()); | 1772 ASSERT(slot->IsUnallocated()); |
| 1772 TRACE_ALLOC(OS::Print(" use at %d converted to ", use->pos())); | 1773 TRACE_ALLOC(OS::Print(" use at %"Pd" converted to ", use->pos())); |
| 1773 TRACE_ALLOC(loc.Print()); | 1774 TRACE_ALLOC(loc.Print()); |
| 1774 TRACE_ALLOC(OS::Print("\n")); | 1775 TRACE_ALLOC(OS::Print("\n")); |
| 1775 *slot = loc; | 1776 *slot = loc; |
| 1776 } | 1777 } |
| 1777 | 1778 |
| 1778 | 1779 |
| 1779 void FlowGraphAllocator::ConvertAllUses(LiveRange* range) { | 1780 void FlowGraphAllocator::ConvertAllUses(LiveRange* range) { |
| 1780 if (range->vreg() == kNoVirtualRegister) return; | 1781 if (range->vreg() == kNoVirtualRegister) return; |
| 1781 | 1782 |
| 1782 const Location loc = range->assigned_location(); | 1783 const Location loc = range->assigned_location(); |
| 1783 ASSERT(!loc.IsInvalid()); | 1784 ASSERT(!loc.IsInvalid()); |
| 1784 | 1785 |
| 1785 TRACE_ALLOC(OS::Print("range [%d, %d) for v%d has been allocated to ", | 1786 TRACE_ALLOC(OS::Print("range [%"Pd", %"Pd") " |
| 1787 "for v%"Pd" has been allocated to ", |
| 1786 range->Start(), range->End(), range->vreg())); | 1788 range->Start(), range->End(), range->vreg())); |
| 1787 TRACE_ALLOC(loc.Print()); | 1789 TRACE_ALLOC(loc.Print()); |
| 1788 TRACE_ALLOC(OS::Print(":\n")); | 1790 TRACE_ALLOC(OS::Print(":\n")); |
| 1789 | 1791 |
| 1790 for (UsePosition* use = range->first_use(); use != NULL; use = use->next()) { | 1792 for (UsePosition* use = range->first_use(); use != NULL; use = use->next()) { |
| 1791 ConvertUseTo(use, loc); | 1793 ConvertUseTo(use, loc); |
| 1792 } | 1794 } |
| 1793 | 1795 |
| 1794 // Add live registers at all safepoints for instructions with slow-path | 1796 // Add live registers at all safepoints for instructions with slow-path |
| 1795 // code. | 1797 // code. |
| (...skipping 141 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1937 | 1939 |
| 1938 void FlowGraphAllocator::AllocateUnallocatedRanges() { | 1940 void FlowGraphAllocator::AllocateUnallocatedRanges() { |
| 1939 #if defined(DEBUG) | 1941 #if defined(DEBUG) |
| 1940 ASSERT(UnallocatedIsSorted()); | 1942 ASSERT(UnallocatedIsSorted()); |
| 1941 #endif | 1943 #endif |
| 1942 | 1944 |
| 1943 while (!unallocated_.is_empty()) { | 1945 while (!unallocated_.is_empty()) { |
| 1944 LiveRange* range = unallocated_.Last(); | 1946 LiveRange* range = unallocated_.Last(); |
| 1945 unallocated_.RemoveLast(); | 1947 unallocated_.RemoveLast(); |
| 1946 const intptr_t start = range->Start(); | 1948 const intptr_t start = range->Start(); |
| 1947 TRACE_ALLOC(OS::Print("Processing live range for vreg %d starting at %d\n", | 1949 TRACE_ALLOC(OS::Print("Processing live range for vreg %"Pd" " |
| 1950 "starting at %"Pd"\n", |
| 1948 range->vreg(), | 1951 range->vreg(), |
| 1949 start)); | 1952 start)); |
| 1950 | 1953 |
| 1951 // TODO(vegorov): eagerly spill liveranges without register uses. | 1954 // TODO(vegorov): eagerly spill liveranges without register uses. |
| 1952 AdvanceActiveIntervals(start); | 1955 AdvanceActiveIntervals(start); |
| 1953 | 1956 |
| 1954 if (!AllocateFreeRegister(range)) { | 1957 if (!AllocateFreeRegister(range)) { |
| 1955 AllocateAnyRegister(range); | 1958 AllocateAnyRegister(range); |
| 1956 } | 1959 } |
| 1957 } | 1960 } |
| (...skipping 15 matching lines...) Expand all Loading... |
| 1973 ASSERT(GetLiveRange(range->vreg())->spill_slot().Equals(target)); | 1976 ASSERT(GetLiveRange(range->vreg())->spill_slot().Equals(target)); |
| 1974 return true; | 1977 return true; |
| 1975 } | 1978 } |
| 1976 return false; | 1979 return false; |
| 1977 } | 1980 } |
| 1978 | 1981 |
| 1979 | 1982 |
| 1980 void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* parent, | 1983 void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* parent, |
| 1981 BlockEntryInstr* source_block, | 1984 BlockEntryInstr* source_block, |
| 1982 BlockEntryInstr* target_block) { | 1985 BlockEntryInstr* target_block) { |
| 1983 TRACE_ALLOC(OS::Print("Connect source_block=%d, target_block=%d\n", | 1986 TRACE_ALLOC(OS::Print("Connect source_block=%"Pd", target_block=%"Pd"\n", |
| 1984 source_block->block_id(), | 1987 source_block->block_id(), |
| 1985 target_block->block_id())); | 1988 target_block->block_id())); |
| 1986 if (parent->next_sibling() == NULL) { | 1989 if (parent->next_sibling() == NULL) { |
| 1987 // Nothing to connect. The whole range was allocated to the same location. | 1990 // Nothing to connect. The whole range was allocated to the same location. |
| 1988 TRACE_ALLOC(OS::Print("range %d has no siblings\n", parent->vreg())); | 1991 TRACE_ALLOC(OS::Print("range %"Pd" has no siblings\n", parent->vreg())); |
| 1989 return; | 1992 return; |
| 1990 } | 1993 } |
| 1991 | 1994 |
| 1992 const intptr_t source_pos = source_block->end_pos() - 1; | 1995 const intptr_t source_pos = source_block->end_pos() - 1; |
| 1993 ASSERT(IsInstructionEndPosition(source_pos)); | 1996 ASSERT(IsInstructionEndPosition(source_pos)); |
| 1994 | 1997 |
| 1995 const intptr_t target_pos = target_block->start_pos(); | 1998 const intptr_t target_pos = target_block->start_pos(); |
| 1996 | 1999 |
| 1997 Location target; | 2000 Location target; |
| 1998 Location source; | 2001 Location source; |
| (...skipping 16 matching lines...) Expand all Loading... |
| 2015 ASSERT(target.IsInvalid()); | 2018 ASSERT(target.IsInvalid()); |
| 2016 target = range->assigned_location(); | 2019 target = range->assigned_location(); |
| 2017 #if defined(DEBUG) | 2020 #if defined(DEBUG) |
| 2018 target_cover = range; | 2021 target_cover = range; |
| 2019 #endif | 2022 #endif |
| 2020 } | 2023 } |
| 2021 | 2024 |
| 2022 range = range->next_sibling(); | 2025 range = range->next_sibling(); |
| 2023 } | 2026 } |
| 2024 | 2027 |
| 2025 TRACE_ALLOC(OS::Print("connecting [%d, %d) [", | 2028 TRACE_ALLOC(OS::Print("connecting [%"Pd", %"Pd") [", |
| 2026 source_cover->Start(), source_cover->End())); | 2029 source_cover->Start(), source_cover->End())); |
| 2027 TRACE_ALLOC(source.Print()); | 2030 TRACE_ALLOC(source.Print()); |
| 2028 TRACE_ALLOC(OS::Print("] to [%d, %d) [", | 2031 TRACE_ALLOC(OS::Print("] to [%"Pd", %"Pd") [", |
| 2029 target_cover->Start(), target_cover->End())); | 2032 target_cover->Start(), target_cover->End())); |
| 2030 TRACE_ALLOC(target.Print()); | 2033 TRACE_ALLOC(target.Print()); |
| 2031 TRACE_ALLOC(OS::Print("]\n")); | 2034 TRACE_ALLOC(OS::Print("]\n")); |
| 2032 | 2035 |
| 2033 // Siblings were allocated to the same register. | 2036 // Siblings were allocated to the same register. |
| 2034 if (source.Equals(target)) return; | 2037 if (source.Equals(target)) return; |
| 2035 | 2038 |
| 2036 // Values are eagerly spilled. Spill slot already contains appropriate value. | 2039 // Values are eagerly spilled. Spill slot already contains appropriate value. |
| 2037 if (TargetLocationIsSpillSlot(parent, target)) { | 2040 if (TargetLocationIsSpillSlot(parent, target)) { |
| 2038 return; | 2041 return; |
| (...skipping 11 matching lines...) Expand all Loading... |
| 2050 | 2053 |
| 2051 void FlowGraphAllocator::ResolveControlFlow() { | 2054 void FlowGraphAllocator::ResolveControlFlow() { |
| 2052 // Resolve linear control flow between touching split siblings | 2055 // Resolve linear control flow between touching split siblings |
| 2053 // inside basic blocks. | 2056 // inside basic blocks. |
| 2054 for (intptr_t vreg = 0; vreg < live_ranges_.length(); vreg++) { | 2057 for (intptr_t vreg = 0; vreg < live_ranges_.length(); vreg++) { |
| 2055 LiveRange* range = live_ranges_[vreg]; | 2058 LiveRange* range = live_ranges_[vreg]; |
| 2056 if (range == NULL) continue; | 2059 if (range == NULL) continue; |
| 2057 | 2060 |
| 2058 while (range->next_sibling() != NULL) { | 2061 while (range->next_sibling() != NULL) { |
| 2059 LiveRange* sibling = range->next_sibling(); | 2062 LiveRange* sibling = range->next_sibling(); |
| 2060 TRACE_ALLOC(OS::Print("connecting [%d, %d) [", | 2063 TRACE_ALLOC(OS::Print("connecting [%"Pd", %"Pd") [", |
| 2061 range->Start(), range->End())); | 2064 range->Start(), range->End())); |
| 2062 TRACE_ALLOC(range->assigned_location().Print()); | 2065 TRACE_ALLOC(range->assigned_location().Print()); |
| 2063 TRACE_ALLOC(OS::Print("] to [%d, %d) [", | 2066 TRACE_ALLOC(OS::Print("] to [%"Pd", %"Pd") [", |
| 2064 sibling->Start(), sibling->End())); | 2067 sibling->Start(), sibling->End())); |
| 2065 TRACE_ALLOC(sibling->assigned_location().Print()); | 2068 TRACE_ALLOC(sibling->assigned_location().Print()); |
| 2066 TRACE_ALLOC(OS::Print("]\n")); | 2069 TRACE_ALLOC(OS::Print("]\n")); |
| 2067 if ((range->End() == sibling->Start()) && | 2070 if ((range->End() == sibling->Start()) && |
| 2068 !TargetLocationIsSpillSlot(range, sibling->assigned_location()) && | 2071 !TargetLocationIsSpillSlot(range, sibling->assigned_location()) && |
| 2069 !range->assigned_location().Equals(sibling->assigned_location()) && | 2072 !range->assigned_location().Equals(sibling->assigned_location()) && |
| 2070 !IsBlockEntry(range->End())) { | 2073 !IsBlockEntry(range->End())) { |
| 2071 AddMoveAt(sibling->Start(), | 2074 AddMoveAt(sibling->Start(), |
| 2072 sibling->assigned_location(), | 2075 sibling->assigned_location(), |
| 2073 range->assigned_location()); | 2076 range->assigned_location()); |
| (...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2172 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", | 2175 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", |
| 2173 function.ToFullyQualifiedCString()); | 2176 function.ToFullyQualifiedCString()); |
| 2174 FlowGraphPrinter printer(flow_graph_, true); | 2177 FlowGraphPrinter printer(flow_graph_, true); |
| 2175 printer.PrintBlocks(); | 2178 printer.PrintBlocks(); |
| 2176 OS::Print("----------------------------------------------\n"); | 2179 OS::Print("----------------------------------------------\n"); |
| 2177 } | 2180 } |
| 2178 } | 2181 } |
| 2179 | 2182 |
| 2180 | 2183 |
| 2181 } // namespace dart | 2184 } // namespace dart |
| OLD | NEW |