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 |