From c3297c8d2ef4089d9bdae71f436a1ba7c20db340 Mon Sep 17 00:00:00 2001 From: "fschneider@chromium.org" Date: Tue, 21 Feb 2012 16:47:02 +0000 Subject: [PATCH] Use placement-new operator in the register allocator. Pass the zone explicitly to avoid calling Isolate::Current()->zone(). Review URL: https://chromiumcodereview.appspot.com/9430002 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@10785 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen.cc | 2 +- src/lithium-allocator.cc | 117 ++++++++++++++++++++++----------------- src/lithium-allocator.h | 44 +++++++++------ 3 files changed, 93 insertions(+), 70 deletions(-) diff --git a/src/hydrogen.cc b/src/hydrogen.cc index c733864b6..fac3c6074 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -7617,7 +7617,7 @@ void HTracer::TraceLiveRange(LiveRange* range, const char* type) { PrintIndent(); trace_.Add("%d %s", range->id(), type); if (range->HasRegisterAssigned()) { - LOperand* op = range->CreateAssignedOperand(); + LOperand* op = range->CreateAssignedOperand(ZONE); int assigned_reg = op->index(); if (op->IsDoubleRegister()) { trace_.Add(" \"%s\"", diff --git a/src/lithium-allocator.cc b/src/lithium-allocator.cc index 2cab9a766..df48ace7d 100644 --- a/src/lithium-allocator.cc +++ b/src/lithium-allocator.cc @@ -110,9 +110,9 @@ bool UsePosition::RegisterIsBeneficial() const { } -void UseInterval::SplitAt(LifetimePosition pos) { +void UseInterval::SplitAt(LifetimePosition pos, Zone* zone) { ASSERT(Contains(pos) && pos.Value() != start().Value()); - UseInterval* after = new UseInterval(pos, end_); + UseInterval* after = new(zone) UseInterval(pos, end_); after->next_ = next_; next_ = after; end_ = pos; @@ -149,7 +149,7 @@ bool LiveRange::HasOverlap(UseInterval* target) const { #endif -LiveRange::LiveRange(int id) +LiveRange::LiveRange(int id, Zone* zone) : id_(id), spilled_(false), is_double_(false), @@ -161,24 +161,26 @@ LiveRange::LiveRange(int id) next_(NULL), current_interval_(NULL), last_processed_use_(NULL), - spill_operand_(new LOperand()), + spill_operand_(new(zone) LOperand()), spill_start_index_(kMaxInt) { } -void LiveRange::set_assigned_register(int reg, RegisterKind register_kind) { +void LiveRange::set_assigned_register(int reg, + RegisterKind register_kind, + Zone* zone) { ASSERT(!HasRegisterAssigned() && !IsSpilled()); assigned_register_ = reg; is_double_ = (register_kind == DOUBLE_REGISTERS); - ConvertOperands(); + ConvertOperands(zone); } -void LiveRange::MakeSpilled() { +void LiveRange::MakeSpilled(Zone* zone) { ASSERT(!IsSpilled()); ASSERT(TopLevel()->HasAllocatedSpillOperand()); spilled_ = true; assigned_register_ = kInvalidAssignment; - ConvertOperands(); + ConvertOperands(zone); } @@ -246,7 +248,7 @@ UsePosition* LiveRange::FirstPosWithHint() const { } -LOperand* LiveRange::CreateAssignedOperand() { +LOperand* LiveRange::CreateAssignedOperand(Zone* zone) { LOperand* op = NULL; if (HasRegisterAssigned()) { ASSERT(!IsSpilled()); @@ -260,7 +262,7 @@ LOperand* LiveRange::CreateAssignedOperand() { op = TopLevel()->GetSpillOperand(); ASSERT(!op->IsUnallocated()); } else { - LUnallocated* unalloc = new LUnallocated(LUnallocated::NONE); + LUnallocated* unalloc = new(zone) LUnallocated(LUnallocated::NONE); unalloc->set_virtual_register(id_); op = unalloc; } @@ -292,7 +294,9 @@ void LiveRange::AdvanceLastProcessedMarker( } -void LiveRange::SplitAt(LifetimePosition position, LiveRange* result) { +void LiveRange::SplitAt(LifetimePosition position, + LiveRange* result, + Zone* zone) { ASSERT(Start().Value() < position.Value()); ASSERT(result->IsEmpty()); // Find the last interval that ends before the position. If the @@ -311,7 +315,7 @@ void LiveRange::SplitAt(LifetimePosition position, LiveRange* result) { while (current != NULL) { if (current->Contains(position)) { - current->SplitAt(position); + current->SplitAt(position, zone); break; } UseInterval* next = current->next(); @@ -404,7 +408,9 @@ void LiveRange::ShortenTo(LifetimePosition start) { } -void LiveRange::EnsureInterval(LifetimePosition start, LifetimePosition end) { +void LiveRange::EnsureInterval(LifetimePosition start, + LifetimePosition end, + Zone* zone) { LAllocator::TraceAlloc("Ensure live range %d in interval [%d %d[\n", id_, start.Value(), @@ -418,7 +424,7 @@ void LiveRange::EnsureInterval(LifetimePosition start, LifetimePosition end) { first_interval_ = first_interval_->next(); } - UseInterval* new_interval = new UseInterval(start, new_end); + UseInterval* new_interval = new(zone) UseInterval(start, new_end); new_interval->next_ = first_interval_; first_interval_ = new_interval; if (new_interval->next() == NULL) { @@ -427,20 +433,22 @@ void LiveRange::EnsureInterval(LifetimePosition start, LifetimePosition end) { } -void LiveRange::AddUseInterval(LifetimePosition start, LifetimePosition end) { +void LiveRange::AddUseInterval(LifetimePosition start, + LifetimePosition end, + Zone* zone) { LAllocator::TraceAlloc("Add to live range %d interval [%d %d[\n", id_, start.Value(), end.Value()); if (first_interval_ == NULL) { - UseInterval* interval = new UseInterval(start, end); + UseInterval* interval = new(zone) UseInterval(start, end); first_interval_ = interval; last_interval_ = interval; } else { if (end.Value() == first_interval_->start().Value()) { first_interval_->set_start(start); } else if (end.Value() < first_interval_->start().Value()) { - UseInterval* interval = new UseInterval(start, end); + UseInterval* interval = new(zone) UseInterval(start, end); interval->set_next(first_interval_); first_interval_ = interval; } else { @@ -456,11 +464,12 @@ void LiveRange::AddUseInterval(LifetimePosition start, LifetimePosition end) { UsePosition* LiveRange::AddUsePosition(LifetimePosition pos, - LOperand* operand) { + LOperand* operand, + Zone* zone) { LAllocator::TraceAlloc("Add to live range %d use position %d\n", id_, pos.Value()); - UsePosition* use_pos = new UsePosition(pos, operand); + UsePosition* use_pos = new(zone) UsePosition(pos, operand); UsePosition* prev = NULL; UsePosition* current = first_pos_; while (current != NULL && current->pos().Value() < pos.Value()) { @@ -480,8 +489,8 @@ UsePosition* LiveRange::AddUsePosition(LifetimePosition pos, } -void LiveRange::ConvertOperands() { - LOperand* op = CreateAssignedOperand(); +void LiveRange::ConvertOperands(Zone* zone) { + LOperand* op = CreateAssignedOperand(zone); UsePosition* use_pos = first_pos(); while (use_pos != NULL) { ASSERT(Start().Value() <= use_pos->pos().Value() && @@ -545,8 +554,8 @@ LifetimePosition LiveRange::FirstIntersection(LiveRange* other) { LAllocator::LAllocator(int num_values, HGraph* graph) - : chunk_(NULL), - allocation_ok_(true), + : zone_(graph->zone()), + chunk_(NULL), live_in_sets_(graph->blocks()->length()), live_ranges_(num_values * 2), fixed_live_ranges_(NULL), @@ -560,7 +569,8 @@ LAllocator::LAllocator(int num_values, HGraph* graph) mode_(GENERAL_REGISTERS), num_registers_(-1), graph_(graph), - has_osr_entry_(false) {} + has_osr_entry_(false), + allocation_ok_(true) { } void LAllocator::InitializeLivenessAnalysis() { @@ -574,7 +584,7 @@ void LAllocator::InitializeLivenessAnalysis() { BitVector* LAllocator::ComputeLiveOut(HBasicBlock* block) { // Compute live out for the given block, except not including backward // successor edges. - BitVector* live_out = new BitVector(next_virtual_register_); + BitVector* live_out = new(zone_) BitVector(next_virtual_register_); // Process all successor blocks. for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) { @@ -612,7 +622,7 @@ void LAllocator::AddInitialIntervals(HBasicBlock* block, while (!iterator.Done()) { int operand_index = iterator.Current(); LiveRange* range = LiveRangeFor(operand_index); - range->AddUseInterval(start, end); + range->AddUseInterval(start, end, zone_); iterator.Advance(); } } @@ -654,9 +664,9 @@ LiveRange* LAllocator::FixedLiveRangeFor(int index) { ASSERT(index < Register::kNumAllocatableRegisters); LiveRange* result = fixed_live_ranges_[index]; if (result == NULL) { - result = new LiveRange(FixedLiveRangeID(index)); + result = new(zone_) LiveRange(FixedLiveRangeID(index), zone_); ASSERT(result->IsFixed()); - result->set_assigned_register(index, GENERAL_REGISTERS); + result->set_assigned_register(index, GENERAL_REGISTERS, zone_); fixed_live_ranges_[index] = result; } return result; @@ -667,9 +677,9 @@ LiveRange* LAllocator::FixedDoubleLiveRangeFor(int index) { ASSERT(index < DoubleRegister::kNumAllocatableRegisters); LiveRange* result = fixed_double_live_ranges_[index]; if (result == NULL) { - result = new LiveRange(FixedDoubleLiveRangeID(index)); + result = new(zone_) LiveRange(FixedDoubleLiveRangeID(index), zone_); ASSERT(result->IsFixed()); - result->set_assigned_register(index, DOUBLE_REGISTERS); + result->set_assigned_register(index, DOUBLE_REGISTERS, zone_); fixed_double_live_ranges_[index] = result; } return result; @@ -682,7 +692,7 @@ LiveRange* LAllocator::LiveRangeFor(int index) { } LiveRange* result = live_ranges_[index]; if (result == NULL) { - result = new LiveRange(index); + result = new(zone_) LiveRange(index, zone_); live_ranges_[index] = result; } return result; @@ -728,15 +738,15 @@ void LAllocator::Define(LifetimePosition position, if (range->IsEmpty() || range->Start().Value() > position.Value()) { // Can happen if there is a definition without use. - range->AddUseInterval(position, position.NextInstruction()); - range->AddUsePosition(position.NextInstruction(), NULL); + range->AddUseInterval(position, position.NextInstruction(), zone_); + range->AddUsePosition(position.NextInstruction(), NULL, zone_); } else { range->ShortenTo(position); } if (operand->IsUnallocated()) { LUnallocated* unalloc_operand = LUnallocated::cast(operand); - range->AddUsePosition(position, unalloc_operand)->set_hint(hint); + range->AddUsePosition(position, unalloc_operand, zone_)->set_hint(hint); } } @@ -749,9 +759,9 @@ void LAllocator::Use(LifetimePosition block_start, if (range == NULL) return; if (operand->IsUnallocated()) { LUnallocated* unalloc_operand = LUnallocated::cast(operand); - range->AddUsePosition(position, unalloc_operand)->set_hint(hint); + range->AddUsePosition(position, unalloc_operand, zone_)->set_hint(hint); } - range->AddUseInterval(block_start, position); + range->AddUseInterval(block_start, position, zone_); } @@ -860,7 +870,8 @@ void LAllocator::MeetConstraintsBetween(LInstruction* first, if (RequiredRegisterKind(input_copy->virtual_register()) == DOUBLE_REGISTERS) { double_artificial_registers_.Add( - cur_input->virtual_register() - first_artificial_register_); + cur_input->virtual_register() - first_artificial_register_, + zone_); } AddConstraintsGapMove(gap_index, input_copy, cur_input); @@ -964,7 +975,8 @@ void LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) { output->index() != i) { LiveRange* range = FixedLiveRangeFor(i); range->AddUseInterval(curr_position, - curr_position.InstructionEnd()); + curr_position.InstructionEnd(), + zone_); } } } @@ -975,7 +987,8 @@ void LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) { output->index() != i) { LiveRange* range = FixedDoubleLiveRangeFor(i); range->AddUseInterval(curr_position, - curr_position.InstructionEnd()); + curr_position.InstructionEnd(), + zone_); } } } @@ -1023,7 +1036,7 @@ void LAllocator::ResolvePhis(HBasicBlock* block) { const ZoneList* phis = block->phis(); for (int i = 0; i < phis->length(); ++i) { HPhi* phi = phis->at(i); - LUnallocated* phi_operand = new LUnallocated(LUnallocated::NONE); + LUnallocated* phi_operand = new(zone_) LUnallocated(LUnallocated::NONE); phi_operand->set_virtual_register(phi->id()); for (int j = 0; j < phi->OperandCount(); ++j) { HValue* op = phi->OperandAt(j); @@ -1033,7 +1046,7 @@ void LAllocator::ResolvePhis(HBasicBlock* block) { operand = chunk_->DefineConstantOperand(constant); } else { ASSERT(!op->EmitAtUses()); - LUnallocated* unalloc = new LUnallocated(LUnallocated::ANY); + LUnallocated* unalloc = new(zone_) LUnallocated(LUnallocated::ANY); unalloc->set_virtual_register(op->id()); operand = unalloc; } @@ -1140,8 +1153,8 @@ void LAllocator::ResolveControlFlow(LiveRange* range, if (cur_cover->IsSpilled()) return; ASSERT(pred_cover != NULL && cur_cover != NULL); if (pred_cover != cur_cover) { - LOperand* pred_op = pred_cover->CreateAssignedOperand(); - LOperand* cur_op = cur_cover->CreateAssignedOperand(); + LOperand* pred_op = pred_cover->CreateAssignedOperand(zone_); + LOperand* cur_op = cur_cover->CreateAssignedOperand(zone_); if (!pred_op->Equals(cur_op)) { LGap* gap = NULL; if (block->predecessors()->length() == 1) { @@ -1213,8 +1226,8 @@ void LAllocator::ConnectRanges() { } if (should_insert) { LParallelMove* move = GetConnectingParallelMove(pos); - LOperand* prev_operand = first_range->CreateAssignedOperand(); - LOperand* cur_operand = second_range->CreateAssignedOperand(); + LOperand* prev_operand = first_range->CreateAssignedOperand(zone_); + LOperand* cur_operand = second_range->CreateAssignedOperand(zone_); move->AddMove(prev_operand, cur_operand); } } @@ -1317,7 +1330,7 @@ void LAllocator::BuildLiveRanges() { while (!iterator.Done()) { int operand_index = iterator.Current(); LiveRange* range = LiveRangeFor(operand_index); - range->EnsureInterval(start, end); + range->EnsureInterval(start, end, zone_); iterator.Advance(); } @@ -1438,7 +1451,7 @@ void LAllocator::PopulatePointerMaps() { TraceAlloc("Pointer in register for range %d (start at %d) " "at safe point %d\n", cur->id(), cur->Start().Value(), safe_point); - LOperand* operand = cur->CreateAssignedOperand(); + LOperand* operand = cur->CreateAssignedOperand(zone_); ASSERT(!operand->IsStackSlot()); map->RecordPointer(operand); } @@ -1810,7 +1823,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_); + current->set_assigned_register(register_index, mode_, zone_); return true; } } @@ -1846,7 +1859,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_); + current->set_assigned_register(reg, mode_, zone_); return true; } @@ -1936,7 +1949,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_); + current->set_assigned_register(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 @@ -2003,7 +2016,7 @@ LiveRange* LAllocator::SplitRangeAt(LiveRange* range, LifetimePosition pos) { LiveRange* result = LiveRangeFor(GetVirtualRegister()); if (!AllocationOk()) return NULL; - range->SplitAt(pos, result); + range->SplitAt(pos, result, zone_); return result; } @@ -2102,7 +2115,7 @@ void LAllocator::Spill(LiveRange* range) { if (op == NULL) op = chunk_->GetNextSpillSlot(mode_ == DOUBLE_REGISTERS); first->SetSpillOperand(op); } - range->MakeSpilled(); + range->MakeSpilled(zone_); } diff --git a/src/lithium-allocator.h b/src/lithium-allocator.h index 43a48cc61..aa6db7d99 100644 --- a/src/lithium-allocator.h +++ b/src/lithium-allocator.h @@ -216,7 +216,7 @@ class UseInterval: public ZoneObject { // Split this interval at the given position without effecting the // live range that owns it. The interval must contain the position. - void SplitAt(LifetimePosition pos); + void SplitAt(LifetimePosition pos, Zone* zone); // If this interval intersects with other return smallest position // that belongs to both of them. @@ -277,7 +277,7 @@ class LiveRange: public ZoneObject { public: static const int kInvalidAssignment = 0x7fffffff; - explicit LiveRange(int id); + LiveRange(int id, Zone* zone); UseInterval* first_interval() const { return first_interval_; } UsePosition* first_pos() const { return first_pos_; } @@ -288,11 +288,13 @@ class LiveRange: public ZoneObject { int id() const { return id_; } bool IsFixed() const { return id_ < 0; } bool IsEmpty() const { return first_interval() == NULL; } - LOperand* CreateAssignedOperand(); + LOperand* CreateAssignedOperand(Zone* zone); int assigned_register() const { return assigned_register_; } int spill_start_index() const { return spill_start_index_; } - void set_assigned_register(int reg, RegisterKind register_kind); - void MakeSpilled(); + void set_assigned_register(int reg, + RegisterKind register_kind, + Zone* zone); + void MakeSpilled(Zone* zone); // Returns use position in this live range that follows both start // and last processed use position. @@ -316,7 +318,7 @@ class LiveRange: public ZoneObject { // the range. // All uses following the given position will be moved from this // live range to the result live range. - void SplitAt(LifetimePosition position, LiveRange* result); + void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone); bool IsDouble() const { return is_double_; } bool HasRegisterAssigned() const { @@ -355,9 +357,15 @@ class LiveRange: public ZoneObject { LifetimePosition FirstIntersection(LiveRange* other); // Add a new interval or a new use position to this live range. - void EnsureInterval(LifetimePosition start, LifetimePosition end); - void AddUseInterval(LifetimePosition start, LifetimePosition end); - UsePosition* AddUsePosition(LifetimePosition pos, LOperand* operand); + void EnsureInterval(LifetimePosition start, + LifetimePosition end, + Zone* zone); + void AddUseInterval(LifetimePosition start, + LifetimePosition end, + Zone* zone); + UsePosition* AddUsePosition(LifetimePosition pos, + LOperand* operand, + Zone* zone); // Shorten the most recently added interval by setting a new start. void ShortenTo(LifetimePosition start); @@ -369,7 +377,7 @@ class LiveRange: public ZoneObject { #endif private: - void ConvertOperands(); + void ConvertOperands(Zone* zone); UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; void AdvanceLastProcessedMarker(UseInterval* to_start_of, LifetimePosition but_not_past) const; @@ -400,8 +408,8 @@ class GrowableBitVector BASE_EMBEDDED { return bits_->Contains(value); } - void Add(int value) { - EnsureCapacity(value); + void Add(int value, Zone* zone) { + EnsureCapacity(value, zone); bits_->Add(value); } @@ -412,11 +420,11 @@ class GrowableBitVector BASE_EMBEDDED { return bits_ != NULL && bits_->length() > value; } - void EnsureCapacity(int value) { + void EnsureCapacity(int value, Zone* zone) { if (InBitsRange(value)) return; int new_length = bits_ == NULL ? kInitialLength : bits_->length(); while (new_length <= value) new_length *= 2; - BitVector* new_bits = new BitVector(new_length); + BitVector* new_bits = new(zone) BitVector(new_length); if (bits_ != NULL) new_bits->CopyFrom(*bits_); bits_ = new_bits; } @@ -587,10 +595,9 @@ class LAllocator BASE_EMBEDDED { inline LGap* GapAt(int index); - LChunk* chunk_; + Zone* zone_; - // Indicates success or failure during register allocation. - bool allocation_ok_; + LChunk* chunk_; // During liveness analysis keep a mapping from block id to live_in sets // for blocks already analyzed. @@ -621,6 +628,9 @@ class LAllocator BASE_EMBEDDED { bool has_osr_entry_; + // Indicates success or failure during register allocation. + bool allocation_ok_; + DISALLOW_COPY_AND_ASSIGN(LAllocator); }; -- 2.34.1