| OLD | NEW |
| 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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 351 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 362 UNREACHABLE(); | 362 UNREACHABLE(); |
| 363 } | 363 } |
| 364 } | 364 } |
| 365 | 365 |
| 366 | 366 |
| 367 void LiveRange::Print() { | 367 void LiveRange::Print() { |
| 368 if (first_use_interval() == NULL) { | 368 if (first_use_interval() == NULL) { |
| 369 return; | 369 return; |
| 370 } | 370 } |
| 371 | 371 |
| 372 OS::Print(" live range v%"Pd" [%"Pd", %"Pd") in ", vreg(), Start(), End()); | 372 OS::Print(" live range v%" Pd " [%" Pd ", %" Pd ") in ", |
| 373 vreg(), Start(), End()); |
| 373 assigned_location().Print(); | 374 assigned_location().Print(); |
| 374 OS::Print("\n"); | 375 OS::Print("\n"); |
| 375 | 376 |
| 376 UsePosition* use_pos = uses_; | 377 UsePosition* use_pos = uses_; |
| 377 for (UseInterval* interval = first_use_interval_; | 378 for (UseInterval* interval = first_use_interval_; |
| 378 interval != NULL; | 379 interval != NULL; |
| 379 interval = interval->next()) { | 380 interval = interval->next()) { |
| 380 OS::Print(" use interval [%"Pd", %"Pd")\n", | 381 OS::Print(" use interval [%" Pd ", %" Pd ")\n", |
| 381 interval->start(), | 382 interval->start(), |
| 382 interval->end()); | 383 interval->end()); |
| 383 while ((use_pos != NULL) && (use_pos->pos() <= interval->end())) { | 384 while ((use_pos != NULL) && (use_pos->pos() <= interval->end())) { |
| 384 OS::Print(" use at %"Pd"", use_pos->pos()); | 385 OS::Print(" use at %" Pd "", use_pos->pos()); |
| 385 if (use_pos->location_slot() != NULL) { | 386 if (use_pos->location_slot() != NULL) { |
| 386 OS::Print(" as "); | 387 OS::Print(" as "); |
| 387 use_pos->location_slot()->Print(); | 388 use_pos->location_slot()->Print(); |
| 388 } | 389 } |
| 389 OS::Print("\n"); | 390 OS::Print("\n"); |
| 390 use_pos = use_pos->next(); | 391 use_pos = use_pos->next(); |
| 391 } | 392 } |
| 392 } | 393 } |
| 393 | 394 |
| 394 if (next_sibling() != NULL) { | 395 if (next_sibling() != NULL) { |
| (...skipping 1080 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1475 UseInterval* last_use_interval = (last_before_split == last_use_interval_) ? | 1476 UseInterval* last_use_interval = (last_before_split == last_use_interval_) ? |
| 1476 first_after_split : last_use_interval_; | 1477 first_after_split : last_use_interval_; |
| 1477 next_sibling_ = new LiveRange(vreg(), | 1478 next_sibling_ = new LiveRange(vreg(), |
| 1478 representation(), | 1479 representation(), |
| 1479 first_use_after_split, | 1480 first_use_after_split, |
| 1480 first_after_split, | 1481 first_after_split, |
| 1481 last_use_interval, | 1482 last_use_interval, |
| 1482 first_safepoint_after_split, | 1483 first_safepoint_after_split, |
| 1483 next_sibling_); | 1484 next_sibling_); |
| 1484 | 1485 |
| 1485 TRACE_ALLOC(OS::Print(" split sibling [%"Pd", %"Pd")\n", | 1486 TRACE_ALLOC(OS::Print(" split sibling [%" Pd ", %" Pd ")\n", |
| 1486 next_sibling_->Start(), next_sibling_->End())); | 1487 next_sibling_->Start(), next_sibling_->End())); |
| 1487 | 1488 |
| 1488 last_use_interval_ = last_before_split; | 1489 last_use_interval_ = last_before_split; |
| 1489 last_use_interval_->next_ = NULL; | 1490 last_use_interval_->next_ = NULL; |
| 1490 | 1491 |
| 1491 if (first_use_after_split != NULL) { | 1492 if (first_use_after_split != NULL) { |
| 1492 finger_.UpdateAfterSplit(first_use_after_split->pos()); | 1493 finger_.UpdateAfterSplit(first_use_after_split->pos()); |
| 1493 } | 1494 } |
| 1494 | 1495 |
| 1495 return next_sibling_; | 1496 return next_sibling_; |
| 1496 } | 1497 } |
| 1497 | 1498 |
| 1498 | 1499 |
| 1499 LiveRange* FlowGraphAllocator::SplitBetween(LiveRange* range, | 1500 LiveRange* FlowGraphAllocator::SplitBetween(LiveRange* range, |
| 1500 intptr_t from, | 1501 intptr_t from, |
| 1501 intptr_t to) { | 1502 intptr_t to) { |
| 1502 TRACE_ALLOC(OS::Print("split v%"Pd" [%"Pd", %"Pd") between [%"Pd", %"Pd")\n", | 1503 TRACE_ALLOC(OS::Print("split v%" Pd " [%" Pd ", %" Pd |
| 1504 ") between [%" Pd ", %" Pd ")\n", |
| 1503 range->vreg(), range->Start(), range->End(), from, to)); | 1505 range->vreg(), range->Start(), range->End(), from, to)); |
| 1504 | 1506 |
| 1505 intptr_t split_pos = kIllegalPosition; | 1507 intptr_t split_pos = kIllegalPosition; |
| 1506 | 1508 |
| 1507 BlockInfo* split_block = BlockInfoAt(to); | 1509 BlockInfo* split_block = BlockInfoAt(to); |
| 1508 if (from < split_block->entry()->lifetime_position()) { | 1510 if (from < split_block->entry()->lifetime_position()) { |
| 1509 // Interval [from, to) spans multiple blocks. | 1511 // Interval [from, to) spans multiple blocks. |
| 1510 | 1512 |
| 1511 // If last block is inside a loop prefer splitting at outermost loop's | 1513 // If last block is inside a loop prefer splitting at outermost loop's |
| 1512 // header. | 1514 // header. |
| (...skipping 17 matching lines...) Expand all Loading... |
| 1530 ASSERT((split_pos != kIllegalPosition) && (from < split_pos)); | 1532 ASSERT((split_pos != kIllegalPosition) && (from < split_pos)); |
| 1531 | 1533 |
| 1532 return range->SplitAt(split_pos); | 1534 return range->SplitAt(split_pos); |
| 1533 } | 1535 } |
| 1534 | 1536 |
| 1535 | 1537 |
| 1536 void FlowGraphAllocator::SpillBetween(LiveRange* range, | 1538 void FlowGraphAllocator::SpillBetween(LiveRange* range, |
| 1537 intptr_t from, | 1539 intptr_t from, |
| 1538 intptr_t to) { | 1540 intptr_t to) { |
| 1539 ASSERT(from < to); | 1541 ASSERT(from < to); |
| 1540 TRACE_ALLOC(OS::Print("spill v%"Pd" [%"Pd", %"Pd") " | 1542 TRACE_ALLOC(OS::Print("spill v%" Pd " [%" Pd ", %" Pd ") " |
| 1541 "between [%"Pd", %"Pd")\n", | 1543 "between [%" Pd ", %" Pd ")\n", |
| 1542 range->vreg(), range->Start(), range->End(), from, to)); | 1544 range->vreg(), range->Start(), range->End(), from, to)); |
| 1543 LiveRange* tail = range->SplitAt(from); | 1545 LiveRange* tail = range->SplitAt(from); |
| 1544 | 1546 |
| 1545 if (tail->Start() < to) { | 1547 if (tail->Start() < to) { |
| 1546 // There is an intersection of tail and [from, to). | 1548 // There is an intersection of tail and [from, to). |
| 1547 LiveRange* tail_tail = SplitBetween(tail, tail->Start(), to); | 1549 LiveRange* tail_tail = SplitBetween(tail, tail->Start(), to); |
| 1548 Spill(tail); | 1550 Spill(tail); |
| 1549 AddToUnallocated(tail_tail); | 1551 AddToUnallocated(tail_tail); |
| 1550 } else { | 1552 } else { |
| 1551 // No intersection between tail and [from, to). | 1553 // No intersection between tail and [from, to). |
| 1552 AddToUnallocated(tail); | 1554 AddToUnallocated(tail); |
| 1553 } | 1555 } |
| 1554 } | 1556 } |
| 1555 | 1557 |
| 1556 | 1558 |
| 1557 void FlowGraphAllocator::SpillAfter(LiveRange* range, intptr_t from) { | 1559 void FlowGraphAllocator::SpillAfter(LiveRange* range, intptr_t from) { |
| 1558 TRACE_ALLOC(OS::Print("spill v%"Pd" [%"Pd", %"Pd") after %"Pd"\n", | 1560 TRACE_ALLOC(OS::Print("spill v%" Pd " [%" Pd ", %" Pd ") after %" Pd "\n", |
| 1559 range->vreg(), range->Start(), range->End(), from)); | 1561 range->vreg(), range->Start(), range->End(), from)); |
| 1560 | 1562 |
| 1561 // When spilling the value inside the loop check if this spill can | 1563 // When spilling the value inside the loop check if this spill can |
| 1562 // be moved outside. | 1564 // be moved outside. |
| 1563 BlockInfo* block_info = BlockInfoAt(from); | 1565 BlockInfo* block_info = BlockInfoAt(from); |
| 1564 if (block_info->is_loop_header() || (block_info->loop() != NULL)) { | 1566 if (block_info->is_loop_header() || (block_info->loop() != NULL)) { |
| 1565 BlockInfo* loop_header = | 1567 BlockInfo* loop_header = |
| 1566 block_info->is_loop_header() ? block_info : block_info->loop(); | 1568 block_info->is_loop_header() ? block_info : block_info->loop(); |
| 1567 | 1569 |
| 1568 if ((range->Start() <= loop_header->entry()->start_pos()) && | 1570 if ((range->Start() <= loop_header->entry()->start_pos()) && |
| 1569 RangeHasOnlyUnconstrainedUsesInLoop(range, loop_header->loop_id())) { | 1571 RangeHasOnlyUnconstrainedUsesInLoop(range, loop_header->loop_id())) { |
| 1570 ASSERT(loop_header->entry()->start_pos() <= from); | 1572 ASSERT(loop_header->entry()->start_pos() <= from); |
| 1571 from = loop_header->entry()->start_pos(); | 1573 from = loop_header->entry()->start_pos(); |
| 1572 TRACE_ALLOC(OS::Print(" moved spill position to loop header %"Pd"\n", | 1574 TRACE_ALLOC(OS::Print(" moved spill position to loop header %" Pd "\n", |
| 1573 from)); | 1575 from)); |
| 1574 } | 1576 } |
| 1575 } | 1577 } |
| 1576 | 1578 |
| 1577 LiveRange* tail = range->SplitAt(from); | 1579 LiveRange* tail = range->SplitAt(from); |
| 1578 Spill(tail); | 1580 Spill(tail); |
| 1579 } | 1581 } |
| 1580 | 1582 |
| 1581 | 1583 |
| 1582 void FlowGraphAllocator::AllocateSpillSlotFor(LiveRange* range) { | 1584 void FlowGraphAllocator::AllocateSpillSlotFor(LiveRange* range) { |
| (...skipping 201 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1784 // If hint is available try hint first. | 1786 // If hint is available try hint first. |
| 1785 // TODO(vegorov): ensure that phis are hinted on the back edge. | 1787 // TODO(vegorov): ensure that phis are hinted on the back edge. |
| 1786 Location hint = unallocated->finger()->FirstHint(); | 1788 Location hint = unallocated->finger()->FirstHint(); |
| 1787 if (hint.IsMachineRegister()) { | 1789 if (hint.IsMachineRegister()) { |
| 1788 if (!blocked_registers_[hint.register_code()]) { | 1790 if (!blocked_registers_[hint.register_code()]) { |
| 1789 free_until = FirstIntersectionWithAllocated(hint.register_code(), | 1791 free_until = FirstIntersectionWithAllocated(hint.register_code(), |
| 1790 unallocated); | 1792 unallocated); |
| 1791 candidate = hint.register_code(); | 1793 candidate = hint.register_code(); |
| 1792 } | 1794 } |
| 1793 | 1795 |
| 1794 TRACE_ALLOC(OS::Print("found hint %s for v%"Pd": free until %"Pd"\n", | 1796 TRACE_ALLOC(OS::Print("found hint %s for v%" Pd ": free until %" Pd "\n", |
| 1795 hint.Name(), | 1797 hint.Name(), |
| 1796 unallocated->vreg(), | 1798 unallocated->vreg(), |
| 1797 free_until)); | 1799 free_until)); |
| 1798 } else { | 1800 } else { |
| 1799 for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) { | 1801 for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) { |
| 1800 if (!blocked_registers_[reg] && (registers_[reg].length() == 0)) { | 1802 if (!blocked_registers_[reg] && (registers_[reg].length() == 0)) { |
| 1801 candidate = reg; | 1803 candidate = reg; |
| 1802 free_until = kMaxPosition; | 1804 free_until = kMaxPosition; |
| 1803 break; | 1805 break; |
| 1804 } | 1806 } |
| (...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1846 const intptr_t reg = range->assigned_location().register_code(); | 1848 const intptr_t reg = range->assigned_location().register_code(); |
| 1847 | 1849 |
| 1848 if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) { | 1850 if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) { |
| 1849 used_on_backedge[reg] = true; | 1851 used_on_backedge[reg] = true; |
| 1850 } | 1852 } |
| 1851 } | 1853 } |
| 1852 } | 1854 } |
| 1853 | 1855 |
| 1854 if (used_on_backedge[candidate]) { | 1856 if (used_on_backedge[candidate]) { |
| 1855 TRACE_ALLOC(OS::Print( | 1857 TRACE_ALLOC(OS::Print( |
| 1856 "considering %s for v%"Pd": has interference on the back edge" | 1858 "considering %s for v%" Pd ": has interference on the back edge" |
| 1857 " {loop [%"Pd", %"Pd")}\n", | 1859 " {loop [%" Pd ", %" Pd ")}\n", |
| 1858 MakeRegisterLocation(candidate).Name(), | 1860 MakeRegisterLocation(candidate).Name(), |
| 1859 unallocated->vreg(), | 1861 unallocated->vreg(), |
| 1860 loop_header->entry()->start_pos(), | 1862 loop_header->entry()->start_pos(), |
| 1861 loop_header->last_block()->end_pos())); | 1863 loop_header->last_block()->end_pos())); |
| 1862 for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) { | 1864 for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) { |
| 1863 if (blocked_registers_[reg] || | 1865 if (blocked_registers_[reg] || |
| 1864 (reg == candidate) || | 1866 (reg == candidate) || |
| 1865 used_on_backedge[reg]) { | 1867 used_on_backedge[reg]) { |
| 1866 continue; | 1868 continue; |
| 1867 } | 1869 } |
| 1868 | 1870 |
| 1869 const intptr_t intersection = | 1871 const intptr_t intersection = |
| 1870 FirstIntersectionWithAllocated(reg, unallocated); | 1872 FirstIntersectionWithAllocated(reg, unallocated); |
| 1871 if (intersection >= free_until) { | 1873 if (intersection >= free_until) { |
| 1872 candidate = reg; | 1874 candidate = reg; |
| 1873 free_until = intersection; | 1875 free_until = intersection; |
| 1874 TRACE_ALLOC(OS::Print( | 1876 TRACE_ALLOC(OS::Print( |
| 1875 "found %s for v%"Pd" with no interference on the back edge\n", | 1877 "found %s for v%" Pd " with no interference on the back edge\n", |
| 1876 MakeRegisterLocation(candidate).Name(), | 1878 MakeRegisterLocation(candidate).Name(), |
| 1877 candidate)); | 1879 candidate)); |
| 1878 break; | 1880 break; |
| 1879 } | 1881 } |
| 1880 } | 1882 } |
| 1881 } | 1883 } |
| 1882 } | 1884 } |
| 1883 | 1885 |
| 1884 TRACE_ALLOC(OS::Print("assigning free register ")); | 1886 TRACE_ALLOC(OS::Print("assigning free register ")); |
| 1885 TRACE_ALLOC(MakeRegisterLocation(candidate).Print()); | 1887 TRACE_ALLOC(MakeRegisterLocation(candidate).Print()); |
| 1886 TRACE_ALLOC(OS::Print(" to v%"Pd"\n", unallocated->vreg())); | 1888 TRACE_ALLOC(OS::Print(" to v%" Pd "\n", unallocated->vreg())); |
| 1887 | 1889 |
| 1888 if (free_until != kMaxPosition) { | 1890 if (free_until != kMaxPosition) { |
| 1889 // There was an intersection. Split unallocated. | 1891 // There was an intersection. Split unallocated. |
| 1890 TRACE_ALLOC(OS::Print(" splitting at %"Pd"\n", free_until)); | 1892 TRACE_ALLOC(OS::Print(" splitting at %" Pd "\n", free_until)); |
| 1891 LiveRange* tail = unallocated->SplitAt(free_until); | 1893 LiveRange* tail = unallocated->SplitAt(free_until); |
| 1892 AddToUnallocated(tail); | 1894 AddToUnallocated(tail); |
| 1893 } | 1895 } |
| 1894 | 1896 |
| 1895 registers_[candidate].Add(unallocated); | 1897 registers_[candidate].Add(unallocated); |
| 1896 unallocated->set_assigned_location(MakeRegisterLocation(candidate)); | 1898 unallocated->set_assigned_location(MakeRegisterLocation(candidate)); |
| 1897 | 1899 |
| 1898 return true; | 1900 return true; |
| 1899 } | 1901 } |
| 1900 | 1902 |
| (...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1978 : unallocated->Start(); | 1980 : unallocated->Start(); |
| 1979 if (free_until < register_use_pos) { | 1981 if (free_until < register_use_pos) { |
| 1980 // Can't acquire free register. Spill until we really need one. | 1982 // Can't acquire free register. Spill until we really need one. |
| 1981 ASSERT(unallocated->Start() < ToInstructionStart(register_use_pos)); | 1983 ASSERT(unallocated->Start() < ToInstructionStart(register_use_pos)); |
| 1982 SpillBetween(unallocated, unallocated->Start(), register_use->pos()); | 1984 SpillBetween(unallocated, unallocated->Start(), register_use->pos()); |
| 1983 return; | 1985 return; |
| 1984 } | 1986 } |
| 1985 | 1987 |
| 1986 TRACE_ALLOC(OS::Print("assigning blocked register ")); | 1988 TRACE_ALLOC(OS::Print("assigning blocked register ")); |
| 1987 TRACE_ALLOC(MakeRegisterLocation(candidate).Print()); | 1989 TRACE_ALLOC(MakeRegisterLocation(candidate).Print()); |
| 1988 TRACE_ALLOC(OS::Print(" to live range v%"Pd" until %"Pd"\n", | 1990 TRACE_ALLOC(OS::Print(" to live range v%" Pd " until %" Pd "\n", |
| 1989 unallocated->vreg(), blocked_at)); | 1991 unallocated->vreg(), blocked_at)); |
| 1990 | 1992 |
| 1991 if (blocked_at < unallocated->End()) { | 1993 if (blocked_at < unallocated->End()) { |
| 1992 // Register is blocked before the end of the live range. Split the range | 1994 // Register is blocked before the end of the live range. Split the range |
| 1993 // at latest at blocked_at position. | 1995 // at latest at blocked_at position. |
| 1994 LiveRange* tail = SplitBetween(unallocated, | 1996 LiveRange* tail = SplitBetween(unallocated, |
| 1995 unallocated->Start(), | 1997 unallocated->Start(), |
| 1996 blocked_at + 1); | 1998 blocked_at + 1); |
| 1997 AddToUnallocated(tail); | 1999 AddToUnallocated(tail); |
| 1998 } | 2000 } |
| (...skipping 136 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2135 } | 2137 } |
| 2136 | 2138 |
| 2137 return parallel_move->AddMove(to, from); | 2139 return parallel_move->AddMove(to, from); |
| 2138 } | 2140 } |
| 2139 | 2141 |
| 2140 | 2142 |
| 2141 void FlowGraphAllocator::ConvertUseTo(UsePosition* use, Location loc) { | 2143 void FlowGraphAllocator::ConvertUseTo(UsePosition* use, Location loc) { |
| 2142 ASSERT(use->location_slot() != NULL); | 2144 ASSERT(use->location_slot() != NULL); |
| 2143 Location* slot = use->location_slot(); | 2145 Location* slot = use->location_slot(); |
| 2144 ASSERT(slot->IsUnallocated()); | 2146 ASSERT(slot->IsUnallocated()); |
| 2145 TRACE_ALLOC(OS::Print(" use at %"Pd" converted to ", use->pos())); | 2147 TRACE_ALLOC(OS::Print(" use at %" Pd " converted to ", use->pos())); |
| 2146 TRACE_ALLOC(loc.Print()); | 2148 TRACE_ALLOC(loc.Print()); |
| 2147 TRACE_ALLOC(OS::Print("\n")); | 2149 TRACE_ALLOC(OS::Print("\n")); |
| 2148 *slot = loc; | 2150 *slot = loc; |
| 2149 } | 2151 } |
| 2150 | 2152 |
| 2151 | 2153 |
| 2152 void FlowGraphAllocator::ConvertAllUses(LiveRange* range) { | 2154 void FlowGraphAllocator::ConvertAllUses(LiveRange* range) { |
| 2153 if (range->vreg() == kNoVirtualRegister) return; | 2155 if (range->vreg() == kNoVirtualRegister) return; |
| 2154 | 2156 |
| 2155 const Location loc = range->assigned_location(); | 2157 const Location loc = range->assigned_location(); |
| 2156 ASSERT(!loc.IsInvalid()); | 2158 ASSERT(!loc.IsInvalid()); |
| 2157 | 2159 |
| 2158 TRACE_ALLOC(OS::Print("range [%"Pd", %"Pd") " | 2160 TRACE_ALLOC(OS::Print("range [%" Pd ", %" Pd ") " |
| 2159 "for v%"Pd" has been allocated to ", | 2161 "for v%" Pd " has been allocated to ", |
| 2160 range->Start(), range->End(), range->vreg())); | 2162 range->Start(), range->End(), range->vreg())); |
| 2161 TRACE_ALLOC(loc.Print()); | 2163 TRACE_ALLOC(loc.Print()); |
| 2162 TRACE_ALLOC(OS::Print(":\n")); | 2164 TRACE_ALLOC(OS::Print(":\n")); |
| 2163 | 2165 |
| 2164 for (UsePosition* use = range->first_use(); use != NULL; use = use->next()) { | 2166 for (UsePosition* use = range->first_use(); use != NULL; use = use->next()) { |
| 2165 ConvertUseTo(use, loc); | 2167 ConvertUseTo(use, loc); |
| 2166 } | 2168 } |
| 2167 | 2169 |
| 2168 // Add live registers at all safepoints for instructions with slow-path | 2170 // Add live registers at all safepoints for instructions with slow-path |
| 2169 // code. | 2171 // code. |
| (...skipping 144 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2314 | 2316 |
| 2315 | 2317 |
| 2316 void FlowGraphAllocator::AllocateUnallocatedRanges() { | 2318 void FlowGraphAllocator::AllocateUnallocatedRanges() { |
| 2317 #if defined(DEBUG) | 2319 #if defined(DEBUG) |
| 2318 ASSERT(UnallocatedIsSorted()); | 2320 ASSERT(UnallocatedIsSorted()); |
| 2319 #endif | 2321 #endif |
| 2320 | 2322 |
| 2321 while (!unallocated_.is_empty()) { | 2323 while (!unallocated_.is_empty()) { |
| 2322 LiveRange* range = unallocated_.RemoveLast(); | 2324 LiveRange* range = unallocated_.RemoveLast(); |
| 2323 const intptr_t start = range->Start(); | 2325 const intptr_t start = range->Start(); |
| 2324 TRACE_ALLOC(OS::Print("Processing live range for v%"Pd" " | 2326 TRACE_ALLOC(OS::Print("Processing live range for v%" Pd " " |
| 2325 "starting at %"Pd"\n", | 2327 "starting at %" Pd "\n", |
| 2326 range->vreg(), | 2328 range->vreg(), |
| 2327 start)); | 2329 start)); |
| 2328 | 2330 |
| 2329 // TODO(vegorov): eagerly spill liveranges without register uses. | 2331 // TODO(vegorov): eagerly spill liveranges without register uses. |
| 2330 AdvanceActiveIntervals(start); | 2332 AdvanceActiveIntervals(start); |
| 2331 | 2333 |
| 2332 if (!AllocateFreeRegister(range)) { | 2334 if (!AllocateFreeRegister(range)) { |
| 2333 AllocateAnyRegister(range); | 2335 AllocateAnyRegister(range); |
| 2334 } | 2336 } |
| 2335 } | 2337 } |
| (...skipping 15 matching lines...) Expand all Loading... |
| 2351 ASSERT(GetLiveRange(range->vreg())->spill_slot().Equals(target)); | 2353 ASSERT(GetLiveRange(range->vreg())->spill_slot().Equals(target)); |
| 2352 return true; | 2354 return true; |
| 2353 } | 2355 } |
| 2354 return false; | 2356 return false; |
| 2355 } | 2357 } |
| 2356 | 2358 |
| 2357 | 2359 |
| 2358 void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* parent, | 2360 void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* parent, |
| 2359 BlockEntryInstr* source_block, | 2361 BlockEntryInstr* source_block, |
| 2360 BlockEntryInstr* target_block) { | 2362 BlockEntryInstr* target_block) { |
| 2361 TRACE_ALLOC(OS::Print("Connect v%"Pd" on the edge B%"Pd" -> B%"Pd"\n", | 2363 TRACE_ALLOC(OS::Print("Connect v%" Pd " on the edge B%" Pd " -> B%" Pd "\n", |
| 2362 parent->vreg(), | 2364 parent->vreg(), |
| 2363 source_block->block_id(), | 2365 source_block->block_id(), |
| 2364 target_block->block_id())); | 2366 target_block->block_id())); |
| 2365 if (parent->next_sibling() == NULL) { | 2367 if (parent->next_sibling() == NULL) { |
| 2366 // Nothing to connect. The whole range was allocated to the same location. | 2368 // Nothing to connect. The whole range was allocated to the same location. |
| 2367 TRACE_ALLOC(OS::Print("range v%"Pd" has no siblings\n", parent->vreg())); | 2369 TRACE_ALLOC(OS::Print("range v%" Pd " has no siblings\n", parent->vreg())); |
| 2368 return; | 2370 return; |
| 2369 } | 2371 } |
| 2370 | 2372 |
| 2371 const intptr_t source_pos = source_block->end_pos() - 1; | 2373 const intptr_t source_pos = source_block->end_pos() - 1; |
| 2372 ASSERT(IsInstructionEndPosition(source_pos)); | 2374 ASSERT(IsInstructionEndPosition(source_pos)); |
| 2373 | 2375 |
| 2374 const intptr_t target_pos = target_block->start_pos(); | 2376 const intptr_t target_pos = target_block->start_pos(); |
| 2375 | 2377 |
| 2376 Location target; | 2378 Location target; |
| 2377 Location source; | 2379 Location source; |
| (...skipping 16 matching lines...) Expand all Loading... |
| 2394 ASSERT(target.IsInvalid()); | 2396 ASSERT(target.IsInvalid()); |
| 2395 target = range->assigned_location(); | 2397 target = range->assigned_location(); |
| 2396 #if defined(DEBUG) | 2398 #if defined(DEBUG) |
| 2397 target_cover = range; | 2399 target_cover = range; |
| 2398 #endif | 2400 #endif |
| 2399 } | 2401 } |
| 2400 | 2402 |
| 2401 range = range->next_sibling(); | 2403 range = range->next_sibling(); |
| 2402 } | 2404 } |
| 2403 | 2405 |
| 2404 TRACE_ALLOC(OS::Print("connecting v%"Pd" between [%"Pd", %"Pd") {%s} " | 2406 TRACE_ALLOC(OS::Print("connecting v%" Pd " between [%" Pd ", %" Pd ") {%s} " |
| 2405 "to [%"Pd", %"Pd") {%s}\n", | 2407 "to [%" Pd ", %" Pd ") {%s}\n", |
| 2406 parent->vreg(), | 2408 parent->vreg(), |
| 2407 source_cover->Start(), | 2409 source_cover->Start(), |
| 2408 source_cover->End(), | 2410 source_cover->End(), |
| 2409 source.Name(), | 2411 source.Name(), |
| 2410 target_cover->Start(), | 2412 target_cover->Start(), |
| 2411 target_cover->End(), | 2413 target_cover->End(), |
| 2412 target.Name())); | 2414 target.Name())); |
| 2413 | 2415 |
| 2414 // Siblings were allocated to the same register. | 2416 // Siblings were allocated to the same register. |
| 2415 if (source.Equals(target)) return; | 2417 if (source.Equals(target)) return; |
| (...skipping 15 matching lines...) Expand all Loading... |
| 2431 | 2433 |
| 2432 void FlowGraphAllocator::ResolveControlFlow() { | 2434 void FlowGraphAllocator::ResolveControlFlow() { |
| 2433 // Resolve linear control flow between touching split siblings | 2435 // Resolve linear control flow between touching split siblings |
| 2434 // inside basic blocks. | 2436 // inside basic blocks. |
| 2435 for (intptr_t vreg = 0; vreg < live_ranges_.length(); vreg++) { | 2437 for (intptr_t vreg = 0; vreg < live_ranges_.length(); vreg++) { |
| 2436 LiveRange* range = live_ranges_[vreg]; | 2438 LiveRange* range = live_ranges_[vreg]; |
| 2437 if (range == NULL) continue; | 2439 if (range == NULL) continue; |
| 2438 | 2440 |
| 2439 while (range->next_sibling() != NULL) { | 2441 while (range->next_sibling() != NULL) { |
| 2440 LiveRange* sibling = range->next_sibling(); | 2442 LiveRange* sibling = range->next_sibling(); |
| 2441 TRACE_ALLOC(OS::Print("connecting [%"Pd", %"Pd") [", | 2443 TRACE_ALLOC(OS::Print("connecting [%" Pd ", %" Pd ") [", |
| 2442 range->Start(), range->End())); | 2444 range->Start(), range->End())); |
| 2443 TRACE_ALLOC(range->assigned_location().Print()); | 2445 TRACE_ALLOC(range->assigned_location().Print()); |
| 2444 TRACE_ALLOC(OS::Print("] to [%"Pd", %"Pd") [", | 2446 TRACE_ALLOC(OS::Print("] to [%" Pd ", %" Pd ") [", |
| 2445 sibling->Start(), sibling->End())); | 2447 sibling->Start(), sibling->End())); |
| 2446 TRACE_ALLOC(sibling->assigned_location().Print()); | 2448 TRACE_ALLOC(sibling->assigned_location().Print()); |
| 2447 TRACE_ALLOC(OS::Print("]\n")); | 2449 TRACE_ALLOC(OS::Print("]\n")); |
| 2448 if ((range->End() == sibling->Start()) && | 2450 if ((range->End() == sibling->Start()) && |
| 2449 !TargetLocationIsSpillSlot(range, sibling->assigned_location()) && | 2451 !TargetLocationIsSpillSlot(range, sibling->assigned_location()) && |
| 2450 !range->assigned_location().Equals(sibling->assigned_location()) && | 2452 !range->assigned_location().Equals(sibling->assigned_location()) && |
| 2451 !IsBlockEntry(range->End())) { | 2453 !IsBlockEntry(range->End())) { |
| 2452 AddMoveAt(sibling->Start(), | 2454 AddMoveAt(sibling->Start(), |
| 2453 sibling->assigned_location(), | 2455 sibling->assigned_location(), |
| 2454 range->assigned_location()); | 2456 range->assigned_location()); |
| (...skipping 144 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2599 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", | 2601 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", |
| 2600 function.ToFullyQualifiedCString()); | 2602 function.ToFullyQualifiedCString()); |
| 2601 FlowGraphPrinter printer(flow_graph_, true); | 2603 FlowGraphPrinter printer(flow_graph_, true); |
| 2602 printer.PrintBlocks(); | 2604 printer.PrintBlocks(); |
| 2603 OS::Print("----------------------------------------------\n"); | 2605 OS::Print("----------------------------------------------\n"); |
| 2604 } | 2606 } |
| 2605 } | 2607 } |
| 2606 | 2608 |
| 2607 | 2609 |
| 2608 } // namespace dart | 2610 } // namespace dart |
| OLD | NEW |