Lines Matching refs:range
188 // We cannot spill a live range that has a use requiring a register
284 ? after // Only interval in the range after split.
285 : last_interval_; // Last interval of the original range.
317 // to the use that no longer belongs to this live range.
321 // Link the new live range in the chain before any of the other
322 // ranges linked from the range before the split.
355 LAllocator::TraceAlloc("Shorten live range %d to [%d\n", id_, start.Value());
366 LAllocator::TraceAlloc("Ensure live range %d in interval [%d %d[\n",
391 LAllocator::TraceAlloc("Add to live range %d interval [%d %d[\n",
422 LAllocator::TraceAlloc("Add to live range %d use position %d\n",
572 // Add an interval that includes the entire block to the live range for
581 LiveRange* range = LiveRangeFor(operand_index);
582 range->AddUseInterval(start, end, zone());
696 LiveRange* range = LiveRangeFor(operand);
697 if (range == NULL) return;
699 if (range->IsEmpty() || range->Start().Value() > position.Value()) {
701 range->AddUseInterval(position, position.NextInstruction(), zone());
702 range->AddUsePosition(position.NextInstruction(), NULL, NULL, zone());
704 range->ShortenTo(position);
709 range->AddUsePosition(position, unalloc_operand, hint, zone());
718 LiveRange* range = LiveRangeFor(operand);
719 if (range == NULL) return;
722 range->AddUsePosition(position, unalloc_operand, hint, zone());
724 range->AddUseInterval(block_start, position, zone());
785 LiveRange* range = LiveRangeFor(first_output->virtual_register());
795 range->SetSpillOperand(first_output);
796 range->SetSpillStartIndex(gap_index - 1);
803 range->SetSpillStartIndex(gap_index);
812 move->AddMove(first_output, range->GetSpillOperand(),
828 // The live range of writable input registers always goes until the end
946 LiveRange* range = FixedLiveRangeFor(i);
947 range->AddUseInterval(curr_position,
958 LiveRange* range = FixedDoubleLiveRangeFor(i);
959 range->AddUseInterval(curr_position,
1046 // it into a location different from the operand of a live range
1116 void LAllocator::ResolveControlFlow(LiveRange* range,
1125 LiveRange* cur_range = range;
1156 // it into a location different from the operand of a live range
1161 if (HasTaggedValue(range->id())) {
1278 // The live range interval already ends at the first instruction of the
1312 // in the loop information. Add a live range stretching from the first
1323 LiveRange* range = LiveRangeFor(operand_index);
1324 range->EnsureInterval(start, end, zone());
1350 LiveRange* range = LiveRangeFor(operand_index);
1351 PrintF("First use is at %d\n", range->first_pos()->pos().Value());
1390 LiveRange* range = live_ranges()->at(range_idx);
1391 if (range == NULL) continue;
1393 if (range->parent() != NULL) continue;
1395 if (!HasTaggedValue(range->id())) continue;
1397 if (range->IsEmpty()) continue;
1399 // Find the extent of the range and its children.
1400 int start = range->Start().InstructionIndex();
1402 for (LiveRange* cur = range; cur != NULL; cur = cur->next()) {
1416 // Step across all the safe points that are before the start of this range,
1417 // recording how far we step in order to save doing this for the next range.
1425 // Step through the safe points to see whether they are in the range.
1435 // Advance to the next active range that covers the current
1439 LiveRange* cur = range;
1445 // Check if the live range is spilled and the safe point is after
1447 if (range->HasAllocatedSpillOperand() &&
1448 safe_point >= range->spill_start_index()) {
1449 TraceAlloc("Pointer for range %d (spilled at %d) at safe point %d\n",
1450 range->id(), range->spill_start_index(), safe_point);
1451 map->RecordPointer(range->GetSpillOperand(), chunk()->zone());
1455 TraceAlloc("Pointer in register for range %d (start at %d) "
1530 TraceAlloc("Live range %d already has a spill operand\n", current->id());
1536 // If the range already has a spill operand and it doesn't need a
1537 // register immediately, split it and spill the first part of the range.
1543 // Do not spill live range eagerly if use position that can benefit from
1544 // the register is too close to the start of live range.
1556 --i; // The live range was removed from the list of active live ranges.
1559 --i; // The live range was removed from the list of active live ranges.
1567 --i; // Live range was removed from the list of inactive live ranges.
1570 --i; // Live range was removed from the list of inactive live ranges.
1634 void LAllocator::AddToActive(LiveRange* range) {
1635 TraceAlloc("Add live range %d to active\n", range->id());
1636 active_live_ranges_.Add(range, zone());
1640 void LAllocator::AddToInactive(LiveRange* range) {
1641 TraceAlloc("Add live range %d to inactive\n", range->id());
1642 inactive_live_ranges_.Add(range, zone());
1646 void LAllocator::AddToUnhandledSorted(LiveRange* range) {
1647 if (range == NULL || range->IsEmpty()) return;
1648 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled());
1649 DCHECK(allocation_finger_.Value() <= range->Start().Value());
1652 if (range->ShouldBeAllocatedBefore(cur_range)) {
1653 TraceAlloc("Add live range %d to unhandled at %d\n", range->id(), i + 1);
1654 unhandled_live_ranges_.InsertAt(i + 1, range, zone());
1659 TraceAlloc("Add live range %d to unhandled at start\n", range->id());
1660 unhandled_live_ranges_.InsertAt(0, range, zone());
1665 void LAllocator::AddToUnhandledUnsorted(LiveRange* range) {
1666 if (range == NULL || range->IsEmpty()) return;
1667 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled());
1668 TraceAlloc("Add live range %d to unhandled unsorted at end\n", range->id());
1669 unhandled_live_ranges_.Add(range, zone());
1702 void LAllocator::FreeSpillSlot(LiveRange* range) {
1703 // Check that we are the last range.
1704 if (range->next() != NULL) return;
1706 if (!range->TopLevel()->HasAllocatedSpillOperand()) return;
1708 int index = range->TopLevel()->GetSpillOperand()->index();
1710 reusable_slots_.Add(range, zone());
1715 LOperand* LAllocator::TryReuseSpillSlot(LiveRange* range) {
1718 range->TopLevel()->Start().Value()) {
1727 void LAllocator::ActiveToHandled(LiveRange* range) {
1728 DCHECK(active_live_ranges_.Contains(range));
1729 active_live_ranges_.RemoveElement(range);
1730 TraceAlloc("Moving live range %d from active to handled\n", range->id());
1731 FreeSpillSlot(range);
1735 void LAllocator::ActiveToInactive(LiveRange* range) {
1736 DCHECK(active_live_ranges_.Contains(range));
1737 active_live_ranges_.RemoveElement(range);
1738 inactive_live_ranges_.Add(range, zone());
1739 TraceAlloc("Moving live range %d from active to inactive\n", range->id());
1743 void LAllocator::InactiveToHandled(LiveRange* range) {
1744 DCHECK(inactive_live_ranges_.Contains(range));
1745 inactive_live_ranges_.RemoveElement(range);
1746 TraceAlloc("Moving live range %d from inactive to handled\n", range->id());
1747 FreeSpillSlot(range);
1751 void LAllocator::InactiveToActive(LiveRange* range) {
1752 DCHECK(inactive_live_ranges_.Contains(range));
1753 inactive_live_ranges_.RemoveElement(range);
1754 active_live_ranges_.Add(range, zone());
1755 TraceAlloc("Moving live range %d from inactive to active\n", range->id());
1792 "Found reg hint %s (free until [%d) for live range %d (end %d[).\n",
1798 // The desired register is free until the end of the current live range.
1800 TraceAlloc("Assigning preferred reg %s to live range %d\n",
1824 // Register reg is available at the range start but becomes blocked before
1825 // the range end. Split current at position where it becomes blocked.
1832 // Register reg is available at the range start and is free until
1833 // the range end.
1835 TraceAlloc("Assigning free reg %s to live range %d\n",
1847 // There is no use in the current live range that requires a register.
1862 LiveRange* range = active_live_ranges_[i];
1863 int cur_reg = range->assigned_register();
1864 if (range->IsFixed() || !range->CanBeSpilled(current->Start())) {
1868 UsePosition* next_use = range->NextUsePositionRegisterIsBeneficial(
1871 use_pos[cur_reg] = range->End();
1879 LiveRange* range = inactive_live_ranges_.at(i);
1880 DCHECK(range->End().Value() > current->Start().Value());
1881 LifetimePosition next_intersection = range->FirstIntersection(current);
1883 int cur_reg = range->assigned_register();
1884 if (range->IsFixed()) {
1903 // Spill starting part of live range up to that use.
1909 // Register becomes blocked before the current range
1918 // Register reg is not blocked for the whole range.
1920 TraceAlloc("Assigning blocked reg %s to live range %d\n",
1932 LifetimePosition LAllocator::FindOptimalSpillingPos(LiveRange* range,
1941 range->PreviousUsePositionRegisterIsBeneficial(pos);
1944 // We are going to spill live range inside the loop.
1950 if (range->Covers(loop_start)) {
1970 LiveRange* range = active_live_ranges_[i];
1971 if (range->assigned_register() == reg) {
1972 UsePosition* next_pos = range->NextRegisterPosition(current->Start());
1973 LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos);
1975 SpillAfter(range, spill_pos);
1977 // When spilling between spill_pos and next_pos ensure that the range
1978 // remains spilled at least until the start of the current live range.
1980 // start before the current range as this violates allocation invariant
1984 // current live-range is larger than their end.
1985 SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos());
1988 ActiveToHandled(range);
1994 LiveRange* range = inactive_live_ranges_[i];
1995 DCHECK(range->End().Value() > current->Start().Value());
1996 if (range->assigned_register() == reg && !range->IsFixed()) {
1997 LifetimePosition next_intersection = range->FirstIntersection(current);
1999 UsePosition* next_pos = range->NextRegisterPosition(current->Start());
2001 SpillAfter(range, split_pos);
2004 SpillBetween(range, split_pos, next_intersection);
2007 InactiveToHandled(range);
2021 LiveRange* LAllocator::SplitRangeAt(LiveRange* range, LifetimePosition pos) {
2022 DCHECK(!range->IsFixed());
2023 TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value());
2025 if (pos.Value() <= range->Start().Value()) return range;
2035 range->SplitAt(pos, result, zone());
2040 LiveRange* LAllocator::SplitBetween(LiveRange* range,
2043 DCHECK(!range->IsFixed());
2044 TraceAlloc("Splitting live range %d in position between [%d, %d]\n",
2045 range->id(),
2051 return SplitRangeAt(range, split_pos);
2089 void LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) {
2090 LiveRange* second_part = SplitRangeAt(range, pos);
2096 void LAllocator::SpillBetween(LiveRange* range,
2099 SpillBetweenUntil(range, start, start, end);
2103 void LAllocator::SpillBetweenUntil(LiveRange* range,
2108 LiveRange* second_part = SplitRangeAt(range, start);
2133 void LAllocator::Spill(LiveRange* range) {
2134 DCHECK(!range->IsSpilled());
2135 TraceAlloc("Spilling live range %d\n", range->id());
2136 LiveRange* first = range->TopLevel();
2139 LOperand* op = TryReuseSpillSlot(range);
2140 if (op == NULL) op = chunk_->GetNextSpillSlot(range->Kind());
2143 range->MakeSpilled(chunk()->zone());
