Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(335)

Side by Side Diff: src/compiler/register-allocator.cc

Issue 1100713003: [turbofan] split all functions off of LinearScanAllocator which are unrelated to LinearScan (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 5 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/compiler/register-allocator.h ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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/base/adapters.h" 5 #include "src/base/adapters.h"
6 #include "src/compiler/linkage.h" 6 #include "src/compiler/linkage.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 {
(...skipping 1444 matching lines...) Expand 10 before | Expand all | Expand 10 after
1455 } 1455 }
1456 1456
1457 1457
1458 void LiveRangeBuilder::Verify() const { 1458 void LiveRangeBuilder::Verify() const {
1459 for (auto current : data()->live_ranges()) { 1459 for (auto current : data()->live_ranges()) {
1460 if (current != nullptr) current->Verify(); 1460 if (current != nullptr) current->Verify();
1461 } 1461 }
1462 } 1462 }
1463 1463
1464 1464
1465 RegisterAllocator::RegisterAllocator(RegisterAllocationData* data)
1466 : data_(data) {}
1467
1468
1469 LiveRange* RegisterAllocator::SplitRangeAt(LiveRange* range,
1470 LifetimePosition pos) {
1471 DCHECK(!range->IsFixed());
1472 TRACE("Splitting live range %d at %d\n", range->id(), pos.Value());
1473
1474 if (pos.Value() <= range->Start().Value()) return range;
1475
1476 // We can't properly connect liveranges if splitting occurred at the end
1477 // a block.
1478 DCHECK(pos.IsStart() || pos.IsGapPosition() ||
1479 (GetInstructionBlock(code(), pos)->last_instruction_index() !=
1480 pos.ToInstructionIndex()));
1481
1482 int vreg = code()->NextVirtualRegister();
1483 auto result = LiveRangeFor(vreg);
1484 range->SplitAt(pos, result, allocation_zone());
1485 return result;
1486 }
1487
1488
1489 LiveRange* RegisterAllocator::SplitBetween(LiveRange* range,
1490 LifetimePosition start,
1491 LifetimePosition end) {
1492 DCHECK(!range->IsFixed());
1493 TRACE("Splitting live range %d in position between [%d, %d]\n", range->id(),
1494 start.Value(), end.Value());
1495
1496 auto split_pos = FindOptimalSplitPos(start, end);
1497 DCHECK(split_pos.Value() >= start.Value());
1498 return SplitRangeAt(range, split_pos);
1499 }
1500
1501
1502 LifetimePosition RegisterAllocator::FindOptimalSplitPos(LifetimePosition start,
1503 LifetimePosition end) {
1504 int start_instr = start.ToInstructionIndex();
1505 int end_instr = end.ToInstructionIndex();
1506 DCHECK(start_instr <= end_instr);
1507
1508 // We have no choice
1509 if (start_instr == end_instr) return end;
1510
1511 auto start_block = GetInstructionBlock(code(), start);
1512 auto end_block = GetInstructionBlock(code(), end);
1513
1514 if (end_block == start_block) {
1515 // The interval is split in the same basic block. Split at the latest
1516 // possible position.
1517 return end;
1518 }
1519
1520 auto block = end_block;
1521 // Find header of outermost loop.
1522 // TODO(titzer): fix redundancy below.
1523 while (GetContainingLoop(code(), block) != nullptr &&
1524 GetContainingLoop(code(), block)->rpo_number().ToInt() >
1525 start_block->rpo_number().ToInt()) {
1526 block = GetContainingLoop(code(), block);
1527 }
1528
1529 // We did not find any suitable outer loop. Split at the latest possible
1530 // position unless end_block is a loop header itself.
1531 if (block == end_block && !end_block->IsLoopHeader()) return end;
1532
1533 return LifetimePosition::GapFromInstructionIndex(
1534 block->first_instruction_index());
1535 }
1536
1537
1538 LifetimePosition RegisterAllocator::FindOptimalSpillingPos(
1539 LiveRange* range, LifetimePosition pos) {
1540 auto block = GetInstructionBlock(code(), pos.Start());
1541 auto loop_header =
1542 block->IsLoopHeader() ? block : GetContainingLoop(code(), block);
1543
1544 if (loop_header == nullptr) return pos;
1545
1546 auto prev_use = range->PreviousUsePositionRegisterIsBeneficial(pos);
1547
1548 while (loop_header != nullptr) {
1549 // We are going to spill live range inside the loop.
1550 // If possible try to move spilling position backwards to loop header.
1551 // This will reduce number of memory moves on the back edge.
1552 auto loop_start = LifetimePosition::GapFromInstructionIndex(
1553 loop_header->first_instruction_index());
1554
1555 if (range->Covers(loop_start)) {
1556 if (prev_use == nullptr || prev_use->pos().Value() < loop_start.Value()) {
1557 // No register beneficial use inside the loop before the pos.
1558 pos = loop_start;
1559 }
1560 }
1561
1562 // Try hoisting out to an outer loop.
1563 loop_header = GetContainingLoop(code(), loop_header);
1564 }
1565
1566 return pos;
1567 }
1568
1569
1570 void RegisterAllocator::Spill(LiveRange* range) {
1571 DCHECK(!range->IsSpilled());
1572 TRACE("Spilling live range %d\n", range->id());
1573 auto first = range->TopLevel();
1574 if (first->HasNoSpillType()) {
1575 data()->AssignSpillRangeToLiveRange(first);
1576 }
1577 range->MakeSpilled();
1578 }
1579
1580
1465 LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data, 1581 LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data,
1466 RegisterKind kind, Zone* local_zone) 1582 RegisterKind kind, Zone* local_zone)
1467 : data_(data), 1583 : RegisterAllocator(data),
1468 mode_(kind), 1584 mode_(kind),
1469 num_registers_(GetRegisterCount(data->config(), kind)), 1585 num_registers_(GetRegisterCount(data->config(), kind)),
1470 unhandled_live_ranges_(local_zone), 1586 unhandled_live_ranges_(local_zone),
1471 active_live_ranges_(local_zone), 1587 active_live_ranges_(local_zone),
1472 inactive_live_ranges_(local_zone) { 1588 inactive_live_ranges_(local_zone) {
1473 unhandled_live_ranges().reserve( 1589 unhandled_live_ranges().reserve(
1474 static_cast<size_t>(code()->VirtualRegisterCount() * 2)); 1590 static_cast<size_t>(code()->VirtualRegisterCount() * 2));
1475 active_live_ranges().reserve(8); 1591 active_live_ranges().reserve(8);
1476 inactive_live_ranges().reserve(8); 1592 inactive_live_ranges().reserve(8);
1477 // TryAllocateFreeReg and AllocateBlockedReg assume this 1593 // TryAllocateFreeReg and AllocateBlockedReg assume this
(...skipping 340 matching lines...) Expand 10 before | Expand all | Expand 10 after
1818 current->id()); 1934 current->id());
1819 data()->SetLiveRangeAssignedRegister(current, reg); 1935 data()->SetLiveRangeAssignedRegister(current, reg);
1820 1936
1821 // This register was not free. Thus we need to find and spill 1937 // This register was not free. Thus we need to find and spill
1822 // parts of active and inactive live regions that use the same register 1938 // parts of active and inactive live regions that use the same register
1823 // at the same lifetime positions as current. 1939 // at the same lifetime positions as current.
1824 SplitAndSpillIntersecting(current); 1940 SplitAndSpillIntersecting(current);
1825 } 1941 }
1826 1942
1827 1943
1828 LifetimePosition LinearScanAllocator::FindOptimalSpillingPos(
1829 LiveRange* range, LifetimePosition pos) {
1830 auto block = GetInstructionBlock(code(), pos.Start());
1831 auto loop_header =
1832 block->IsLoopHeader() ? block : GetContainingLoop(code(), block);
1833
1834 if (loop_header == nullptr) return pos;
1835
1836 auto prev_use = range->PreviousUsePositionRegisterIsBeneficial(pos);
1837
1838 while (loop_header != nullptr) {
1839 // We are going to spill live range inside the loop.
1840 // If possible try to move spilling position backwards to loop header.
1841 // This will reduce number of memory moves on the back edge.
1842 auto loop_start = LifetimePosition::GapFromInstructionIndex(
1843 loop_header->first_instruction_index());
1844
1845 if (range->Covers(loop_start)) {
1846 if (prev_use == nullptr || prev_use->pos().Value() < loop_start.Value()) {
1847 // No register beneficial use inside the loop before the pos.
1848 pos = loop_start;
1849 }
1850 }
1851
1852 // Try hoisting out to an outer loop.
1853 loop_header = GetContainingLoop(code(), loop_header);
1854 }
1855
1856 return pos;
1857 }
1858
1859
1860 void LinearScanAllocator::SplitAndSpillIntersecting(LiveRange* current) { 1944 void LinearScanAllocator::SplitAndSpillIntersecting(LiveRange* current) {
1861 DCHECK(current->HasRegisterAssigned()); 1945 DCHECK(current->HasRegisterAssigned());
1862 int reg = current->assigned_register(); 1946 int reg = current->assigned_register();
1863 auto split_pos = current->Start(); 1947 auto split_pos = current->Start();
1864 for (size_t i = 0; i < active_live_ranges().size(); ++i) { 1948 for (size_t i = 0; i < active_live_ranges().size(); ++i) {
1865 auto range = active_live_ranges()[i]; 1949 auto range = active_live_ranges()[i];
1866 if (range->assigned_register() == reg) { 1950 if (range->assigned_register() == reg) {
1867 auto next_pos = range->NextRegisterPosition(current->Start()); 1951 auto next_pos = range->NextRegisterPosition(current->Start());
1868 auto spill_pos = FindOptimalSpillingPos(range, split_pos); 1952 auto spill_pos = FindOptimalSpillingPos(range, split_pos);
1869 if (next_pos == nullptr) { 1953 if (next_pos == nullptr) {
(...skipping 114 matching lines...) Expand 10 before | Expand all | Expand 10 after
1984 bool merged = first_op_spill->TryMerge(spill_range); 2068 bool merged = first_op_spill->TryMerge(spill_range);
1985 CHECK(merged); 2069 CHECK(merged);
1986 SpillBetween(range, range->Start(), pos->pos()); 2070 SpillBetween(range, range->Start(), pos->pos());
1987 DCHECK(UnhandledIsSorted()); 2071 DCHECK(UnhandledIsSorted());
1988 return true; 2072 return true;
1989 } 2073 }
1990 return false; 2074 return false;
1991 } 2075 }
1992 2076
1993 2077
1994 LiveRange* LinearScanAllocator::SplitRangeAt(LiveRange* range,
1995 LifetimePosition pos) {
1996 DCHECK(!range->IsFixed());
1997 TRACE("Splitting live range %d at %d\n", range->id(), pos.Value());
1998
1999 if (pos.Value() <= range->Start().Value()) return range;
2000
2001 // We can't properly connect liveranges if splitting occurred at the end
2002 // a block.
2003 DCHECK(pos.IsStart() || pos.IsGapPosition() ||
2004 (GetInstructionBlock(code(), pos)->last_instruction_index() !=
2005 pos.ToInstructionIndex()));
2006
2007 int vreg = code()->NextVirtualRegister();
2008 auto result = LiveRangeFor(vreg);
2009 range->SplitAt(pos, result, allocation_zone());
2010 return result;
2011 }
2012
2013
2014 LiveRange* LinearScanAllocator::SplitBetween(LiveRange* range,
2015 LifetimePosition start,
2016 LifetimePosition end) {
2017 DCHECK(!range->IsFixed());
2018 TRACE("Splitting live range %d in position between [%d, %d]\n", range->id(),
2019 start.Value(), end.Value());
2020
2021 auto split_pos = FindOptimalSplitPos(start, end);
2022 DCHECK(split_pos.Value() >= start.Value());
2023 return SplitRangeAt(range, split_pos);
2024 }
2025
2026
2027 LifetimePosition LinearScanAllocator::FindOptimalSplitPos(
2028 LifetimePosition start, LifetimePosition end) {
2029 int start_instr = start.ToInstructionIndex();
2030 int end_instr = end.ToInstructionIndex();
2031 DCHECK(start_instr <= end_instr);
2032
2033 // We have no choice
2034 if (start_instr == end_instr) return end;
2035
2036 auto start_block = GetInstructionBlock(code(), start);
2037 auto end_block = GetInstructionBlock(code(), end);
2038
2039 if (end_block == start_block) {
2040 // The interval is split in the same basic block. Split at the latest
2041 // possible position.
2042 return end;
2043 }
2044
2045 auto block = end_block;
2046 // Find header of outermost loop.
2047 // TODO(titzer): fix redundancy below.
2048 while (GetContainingLoop(code(), block) != nullptr &&
2049 GetContainingLoop(code(), block)->rpo_number().ToInt() >
2050 start_block->rpo_number().ToInt()) {
2051 block = GetContainingLoop(code(), block);
2052 }
2053
2054 // We did not find any suitable outer loop. Split at the latest possible
2055 // position unless end_block is a loop header itself.
2056 if (block == end_block && !end_block->IsLoopHeader()) return end;
2057
2058 return LifetimePosition::GapFromInstructionIndex(
2059 block->first_instruction_index());
2060 }
2061
2062
2063 void LinearScanAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) { 2078 void LinearScanAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) {
2064 auto second_part = SplitRangeAt(range, pos); 2079 auto second_part = SplitRangeAt(range, pos);
2065 Spill(second_part); 2080 Spill(second_part);
2066 } 2081 }
2067 2082
2068 2083
2069 void LinearScanAllocator::SpillBetween(LiveRange* range, LifetimePosition start, 2084 void LinearScanAllocator::SpillBetween(LiveRange* range, LifetimePosition start,
2070 LifetimePosition end) { 2085 LifetimePosition end) {
2071 SpillBetweenUntil(range, start, start, end); 2086 SpillBetweenUntil(range, start, start, end);
2072 } 2087 }
(...skipping 22 matching lines...) Expand all
2095 Spill(second_part); 2110 Spill(second_part);
2096 AddToUnhandledSorted(third_part); 2111 AddToUnhandledSorted(third_part);
2097 } else { 2112 } else {
2098 // The split result does not intersect with [start, end[. 2113 // The split result does not intersect with [start, end[.
2099 // Nothing to spill. Just put it to unhandled as whole. 2114 // Nothing to spill. Just put it to unhandled as whole.
2100 AddToUnhandledSorted(second_part); 2115 AddToUnhandledSorted(second_part);
2101 } 2116 }
2102 } 2117 }
2103 2118
2104 2119
2105 void LinearScanAllocator::Spill(LiveRange* range) {
2106 DCHECK(!range->IsSpilled());
2107 TRACE("Spilling live range %d\n", range->id());
2108 auto first = range->TopLevel();
2109 if (first->HasNoSpillType()) {
2110 data()->AssignSpillRangeToLiveRange(first);
2111 }
2112 range->MakeSpilled();
2113 }
2114
2115
2116 OperandAssigner::OperandAssigner(RegisterAllocationData* data) : data_(data) {} 2120 OperandAssigner::OperandAssigner(RegisterAllocationData* data) : data_(data) {}
2117 2121
2118 2122
2119 void OperandAssigner::AssignSpillSlots() { 2123 void OperandAssigner::AssignSpillSlots() {
2120 auto& spill_ranges = data()->spill_ranges(); 2124 auto& spill_ranges = data()->spill_ranges();
2121 // Merge disjoint spill ranges 2125 // Merge disjoint spill ranges
2122 for (size_t i = 0; i < spill_ranges.size(); i++) { 2126 for (size_t i = 0; i < spill_ranges.size(); i++) {
2123 auto range = spill_ranges[i]; 2127 auto range = spill_ranges[i];
2124 if (range->IsEmpty()) continue; 2128 if (range->IsEmpty()) continue;
2125 for (size_t j = i + 1; j < spill_ranges.size(); j++) { 2129 for (size_t j = i + 1; j < spill_ranges.size(); j++) {
(...skipping 396 matching lines...) Expand 10 before | Expand all | Expand 10 after
2522 auto move = new (code_zone()) MoveOperands(it->first.second, it->second); 2526 auto move = new (code_zone()) MoveOperands(it->first.second, it->second);
2523 auto eliminate = moves->PrepareInsertAfter(move); 2527 auto eliminate = moves->PrepareInsertAfter(move);
2524 to_insert.push_back(move); 2528 to_insert.push_back(move);
2525 if (eliminate != nullptr) to_eliminate.push_back(eliminate); 2529 if (eliminate != nullptr) to_eliminate.push_back(eliminate);
2526 } 2530 }
2527 } 2531 }
2528 2532
2529 } // namespace compiler 2533 } // namespace compiler
2530 } // namespace internal 2534 } // namespace internal
2531 } // namespace v8 2535 } // namespace v8
OLDNEW
« no previous file with comments | « src/compiler/register-allocator.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698