From 83261e789eb903da39f279cb5a161611482e7df5 Mon Sep 17 00:00:00 2001 From: Trevor Norris Date: Mon, 18 Mar 2013 13:49:34 -0700 Subject: deps: update v8 to 3.17.13 --- deps/v8/src/lithium-allocator.cc | 137 +++++++++++++++++++++++++++------------ 1 file changed, 97 insertions(+), 40 deletions(-) (limited to 'deps/v8/src/lithium-allocator.cc') diff --git a/deps/v8/src/lithium-allocator.cc b/deps/v8/src/lithium-allocator.cc index 91a98112b6..7049a58fdf 100644 --- a/deps/v8/src/lithium-allocator.cc +++ b/deps/v8/src/lithium-allocator.cc @@ -196,6 +196,18 @@ UsePosition* LiveRange::NextUsePositionRegisterIsBeneficial( } +UsePosition* LiveRange::PreviousUsePositionRegisterIsBeneficial( + LifetimePosition start) { + UsePosition* pos = first_pos(); + UsePosition* prev = NULL; + while (pos != NULL && pos->pos().Value() < start.Value()) { + if (pos->RegisterIsBeneficial()) prev = pos; + pos = pos->next(); + } + return prev; +} + + UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) { UsePosition* pos = NextUsePosition(start); while (pos != NULL && !pos->RequiresRegister()) { @@ -206,9 +218,6 @@ UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) { bool LiveRange::CanBeSpilled(LifetimePosition pos) { - // TODO(kmillikin): Comment. Now. - if (pos.Value() <= Start().Value() && HasRegisterAssigned()) return false; - // We cannot spill a live range that has a use requiring a register // at the current or the immediate next position. UsePosition* use_pos = NextRegisterPosition(pos); @@ -606,7 +615,7 @@ void LAllocator::AddInitialIntervals(HBasicBlock* block, int LAllocator::FixedDoubleLiveRangeID(int index) { - return -index - 1 - Register::kNumAllocatableRegisters; + return -index - 1 - Register::kMaxNumAllocatableRegisters; } @@ -638,12 +647,12 @@ LOperand* LAllocator::AllocateFixed(LUnallocated* operand, LiveRange* LAllocator::FixedLiveRangeFor(int index) { - ASSERT(index < Register::kNumAllocatableRegisters); + ASSERT(index < Register::kMaxNumAllocatableRegisters); LiveRange* result = fixed_live_ranges_[index]; if (result == NULL) { result = new(zone_) LiveRange(FixedLiveRangeID(index), zone_); ASSERT(result->IsFixed()); - result->set_assigned_register(index, GENERAL_REGISTERS, zone_); + SetLiveRangeAssignedRegister(result, index, GENERAL_REGISTERS, zone_); fixed_live_ranges_[index] = result; } return result; @@ -651,12 +660,12 @@ LiveRange* LAllocator::FixedLiveRangeFor(int index) { LiveRange* LAllocator::FixedDoubleLiveRangeFor(int index) { - ASSERT(index < DoubleRegister::kNumAllocatableRegisters); + ASSERT(index < DoubleRegister::NumAllocatableRegisters()); LiveRange* result = fixed_double_live_ranges_[index]; if (result == NULL) { result = new(zone_) LiveRange(FixedDoubleLiveRangeID(index), zone_); ASSERT(result->IsFixed()); - result->set_assigned_register(index, DOUBLE_REGISTERS, zone_); + SetLiveRangeAssignedRegister(result, index, DOUBLE_REGISTERS, zone_); fixed_double_live_ranges_[index] = result; } return result; @@ -768,6 +777,7 @@ void LAllocator::AddConstraintsGapMove(int index, void LAllocator::MeetRegisterConstraints(HBasicBlock* block) { int start = block->first_instruction_index(); int end = block->last_instruction_index(); + if (start == -1) return; for (int i = start; i <= end; ++i) { if (IsGapAt(i)) { LInstruction* instr = NULL; @@ -841,8 +851,9 @@ void LAllocator::MeetConstraintsBetween(LInstruction* first, ASSERT(!cur_input->IsUsedAtStart()); LUnallocated* input_copy = cur_input->CopyUnconstrained(zone()); - cur_input->set_virtual_register(GetVirtualRegister()); + int vreg = GetVirtualRegister(); if (!AllocationOk()) return; + cur_input->set_virtual_register(vreg); if (RequiredRegisterKind(input_copy->virtual_register()) == DOUBLE_REGISTERS) { @@ -946,8 +957,8 @@ void LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) { Define(curr_position, output, NULL); } - if (instr->IsMarkedAsCall()) { - for (int i = 0; i < Register::kNumAllocatableRegisters; ++i) { + if (instr->ClobbersRegisters()) { + for (int i = 0; i < Register::kMaxNumAllocatableRegisters; ++i) { if (output == NULL || !output->IsRegister() || output->index() != i) { LiveRange* range = FixedLiveRangeFor(i); @@ -958,8 +969,8 @@ void LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) { } } - if (instr->IsMarkedAsCall()) { - for (int i = 0; i < DoubleRegister::kNumAllocatableRegisters; ++i) { + if (instr->ClobbersDoubleRegisters()) { + for (int i = 0; i < DoubleRegister::NumAllocatableRegisters(); ++i) { if (output == NULL || !output->IsDoubleRegister() || output->index() != i) { LiveRange* range = FixedDoubleLiveRangeFor(i); @@ -989,7 +1000,7 @@ void LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) { for (TempIterator it(instr); !it.Done(); it.Advance()) { LOperand* temp = it.Current(); - if (instr->IsMarkedAsCall()) { + if (instr->ClobbersTemps()) { if (temp->IsRegister()) continue; if (temp->IsUnallocated()) { LUnallocated* temp_unalloc = LUnallocated::cast(temp); @@ -1065,6 +1076,13 @@ void LAllocator::ResolvePhis(HBasicBlock* block) { bool LAllocator::Allocate(LChunk* chunk) { ASSERT(chunk_ == NULL); chunk_ = static_cast(chunk); + assigned_registers_ = + new(zone()) BitVector(Register::NumAllocatableRegisters(), zone()); + assigned_registers_->Clear(); + assigned_double_registers_ = + new(zone()) BitVector(DoubleRegister::NumAllocatableRegisters(), + zone()); + assigned_double_registers_->Clear(); MeetRegisterConstraints(); if (!AllocationOk()) return false; ResolvePhis(); @@ -1324,8 +1342,14 @@ void LAllocator::BuildLiveRanges() { while (!iterator.Done()) { found = true; int operand_index = iterator.Current(); - PrintF("Function: %s\n", - *chunk_->info()->function()->debug_name()->ToCString()); + if (chunk_->info()->IsStub()) { + CodeStub::Major major_key = chunk_->info()->code_stub()->MajorKey(); + PrintF("Function: %s\n", CodeStub::MajorName(major_key, false)); + } else { + ASSERT(chunk_->info()->IsOptimizing()); + PrintF("Function: %s\n", + *chunk_->info()->function()->debug_name()->ToCString()); + } PrintF("Value %d used before first definition!\n", operand_index); LiveRange* range = LiveRangeFor(operand_index); PrintF("First use is at %d\n", range->first_pos()->pos().Value()); @@ -1411,7 +1435,7 @@ void LAllocator::PopulatePointerMaps() { LifetimePosition safe_point_pos = LifetimePosition::FromInstructionIndex(safe_point); LiveRange* cur = range; - while (cur != NULL && !cur->Covers(safe_point_pos.PrevInstruction())) { + while (cur != NULL && !cur->Covers(safe_point_pos)) { cur = cur->next(); } if (cur == NULL) continue; @@ -1471,14 +1495,14 @@ void LAllocator::ProcessOsrEntry() { void LAllocator::AllocateGeneralRegisters() { HPhase phase("L_Allocate general registers", this); - num_registers_ = Register::kNumAllocatableRegisters; + num_registers_ = Register::NumAllocatableRegisters(); AllocateRegisters(); } void LAllocator::AllocateDoubleRegisters() { HPhase phase("L_Allocate double registers", this); - num_registers_ = DoubleRegister::kNumAllocatableRegisters; + num_registers_ = DoubleRegister::NumAllocatableRegisters(); mode_ = DOUBLE_REGISTERS; AllocateRegisters(); } @@ -1502,7 +1526,7 @@ void LAllocator::AllocateRegisters() { ASSERT(inactive_live_ranges_.is_empty()); if (mode_ == DOUBLE_REGISTERS) { - for (int i = 0; i < fixed_double_live_ranges_.length(); ++i) { + for (int i = 0; i < DoubleRegister::NumAllocatableRegisters(); ++i) { LiveRange* current = fixed_double_live_ranges_.at(i); if (current != NULL) { AddToInactive(current); @@ -1757,14 +1781,14 @@ void LAllocator::InactiveToActive(LiveRange* range) { // TryAllocateFreeReg and AllocateBlockedReg assume this // when allocating local arrays. -STATIC_ASSERT(DoubleRegister::kNumAllocatableRegisters >= - Register::kNumAllocatableRegisters); +STATIC_ASSERT(DoubleRegister::kMaxNumAllocatableRegisters >= + Register::kMaxNumAllocatableRegisters); bool LAllocator::TryAllocateFreeReg(LiveRange* current) { - LifetimePosition free_until_pos[DoubleRegister::kNumAllocatableRegisters]; + LifetimePosition free_until_pos[DoubleRegister::kMaxNumAllocatableRegisters]; - for (int i = 0; i < DoubleRegister::kNumAllocatableRegisters; i++) { + for (int i = 0; i < DoubleRegister::kMaxNumAllocatableRegisters; i++) { free_until_pos[i] = LifetimePosition::MaxPosition(); } @@ -1801,7 +1825,7 @@ bool LAllocator::TryAllocateFreeReg(LiveRange* current) { TraceAlloc("Assigning preferred reg %s to live range %d\n", RegisterName(register_index), current->id()); - current->set_assigned_register(register_index, mode_, zone_); + SetLiveRangeAssignedRegister(current, register_index, mode_, zone_); return true; } } @@ -1837,7 +1861,7 @@ bool LAllocator::TryAllocateFreeReg(LiveRange* current) { TraceAlloc("Assigning free reg %s to live range %d\n", RegisterName(reg), current->id()); - current->set_assigned_register(reg, mode_, zone_); + SetLiveRangeAssignedRegister(current, reg, mode_, zone_); return true; } @@ -1853,10 +1877,10 @@ void LAllocator::AllocateBlockedReg(LiveRange* current) { } - LifetimePosition use_pos[DoubleRegister::kNumAllocatableRegisters]; - LifetimePosition block_pos[DoubleRegister::kNumAllocatableRegisters]; + LifetimePosition use_pos[DoubleRegister::kMaxNumAllocatableRegisters]; + LifetimePosition block_pos[DoubleRegister::kMaxNumAllocatableRegisters]; - for (int i = 0; i < DoubleRegister::kNumAllocatableRegisters; i++) { + for (int i = 0; i < DoubleRegister::NumAllocatableRegisters(); i++) { use_pos[i] = block_pos[i] = LifetimePosition::MaxPosition(); } @@ -1903,12 +1927,6 @@ void LAllocator::AllocateBlockedReg(LiveRange* current) { if (pos.Value() < register_use->pos().Value()) { // All registers are blocked before the first use that requires a register. // Spill starting part of live range up to that use. - // - // Corner case: the first use position is equal to the start of the range. - // In this case we have nothing to spill and SpillBetween will just return - // this range to the list of unhandled ones. This will lead to the infinite - // loop. - ASSERT(current->Start().Value() < register_use->pos().Value()); SpillBetween(current, current->Start(), register_use->pos()); return; } @@ -1919,6 +1937,7 @@ void LAllocator::AllocateBlockedReg(LiveRange* current) { LiveRange* tail = SplitBetween(current, current->Start(), block_pos[reg].InstructionStart()); + if (!AllocationOk()) return; AddToUnhandledSorted(tail); } @@ -1927,7 +1946,7 @@ void LAllocator::AllocateBlockedReg(LiveRange* current) { TraceAlloc("Assigning blocked reg %s to live range %d\n", RegisterName(reg), current->id()); - current->set_assigned_register(reg, mode_, zone_); + SetLiveRangeAssignedRegister(current, reg, mode_, zone_); // This register was not free. Thus we need to find and spill // parts of active and inactive live regions that use the same register @@ -1936,6 +1955,39 @@ void LAllocator::AllocateBlockedReg(LiveRange* current) { } +LifetimePosition LAllocator::FindOptimalSpillingPos(LiveRange* range, + LifetimePosition pos) { + HBasicBlock* block = GetBlock(pos.InstructionStart()); + HBasicBlock* loop_header = + block->IsLoopHeader() ? block : block->parent_loop_header(); + + if (loop_header == NULL) return pos; + + UsePosition* prev_use = + range->PreviousUsePositionRegisterIsBeneficial(pos); + + while (loop_header != NULL) { + // We are going to spill live range inside the loop. + // If possible try to move spilling position backwards to loop header. + // This will reduce number of memory moves on the back edge. + LifetimePosition loop_start = LifetimePosition::FromInstructionIndex( + loop_header->first_instruction_index()); + + if (range->Covers(loop_start)) { + if (prev_use == NULL || prev_use->pos().Value() < loop_start.Value()) { + // No register beneficial use inside the loop before the pos. + pos = loop_start; + } + } + + // Try hoisting out to an outer loop. + loop_header = loop_header->parent_loop_header(); + } + + return pos; +} + + void LAllocator::SplitAndSpillIntersecting(LiveRange* current) { ASSERT(current->HasRegisterAssigned()); int reg = current->assigned_register(); @@ -1944,11 +1996,13 @@ void LAllocator::SplitAndSpillIntersecting(LiveRange* current) { LiveRange* range = active_live_ranges_[i]; if (range->assigned_register() == reg) { UsePosition* next_pos = range->NextRegisterPosition(current->Start()); + LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos); if (next_pos == NULL) { - SpillAfter(range, split_pos); + SpillAfter(range, spill_pos); } else { - SpillBetween(range, split_pos, next_pos->pos()); + SpillBetween(range, spill_pos, next_pos->pos()); } + if (!AllocationOk()) return; ActiveToHandled(range); --i; } @@ -1967,6 +2021,7 @@ void LAllocator::SplitAndSpillIntersecting(LiveRange* current) { next_intersection = Min(next_intersection, next_pos->pos()); SpillBetween(range, split_pos, next_intersection); } + if (!AllocationOk()) return; InactiveToHandled(range); --i; } @@ -1992,8 +2047,9 @@ LiveRange* LAllocator::SplitRangeAt(LiveRange* range, LifetimePosition pos) { ASSERT(pos.IsInstructionStart() || !chunk_->instructions()->at(pos.InstructionIndex())->IsControl()); - LiveRange* result = LiveRangeFor(GetVirtualRegister()); + int vreg = GetVirtualRegister(); if (!AllocationOk()) return NULL; + LiveRange* result = LiveRangeFor(vreg); range->SplitAt(pos, result, zone_); return result; } @@ -2058,7 +2114,7 @@ void LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) { void LAllocator::SpillBetween(LiveRange* range, LifetimePosition start, LifetimePosition end) { - ASSERT(start.Value() < end.Value()); + CHECK(start.Value() < end.Value()); LiveRange* second_part = SplitRangeAt(range, start); if (!AllocationOk()) return; @@ -2070,6 +2126,7 @@ void LAllocator::SpillBetween(LiveRange* range, second_part, second_part->Start().InstructionEnd(), end.PrevInstruction().InstructionEnd()); + if (!AllocationOk()) return; ASSERT(third_part != second_part); -- cgit v1.2.1