Allow bailing out of the register allocator when running out of virtual registers.

src/lithium-allocator.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 528 matching lines @@
     } else {
       b = b->next();
     }
   }
   return LifetimePosition::Invalid();
 }
 
 
 LAllocator::LAllocator(int num_values, HGraph* graph)
     : chunk_(NULL),
+      allocation_ok_(true),
       live_in_sets_(graph->blocks()->length()),
       live_ranges_(num_values * 2),
       fixed_live_ranges_(NULL),
       fixed_double_live_ranges_(NULL),
       unhandled_live_ranges_(num_values * 2),
       active_live_ranges_(8),
       inactive_live_ranges_(8),
       reusable_slots_(8),
       next_virtual_register_(num_values),
       first_artificial_register_(num_values),
@@ skipping 221 matching lines @@
 void LAllocator::MeetRegisterConstraints(HBasicBlock* block) {
   int start = block->first_instruction_index();
   int end = block->last_instruction_index();
   for (int i = start; i <= end; ++i) {
     if (IsGapAt(i)) {
       LInstruction* instr = NULL;
       LInstruction* prev_instr = NULL;
       if (i < end) instr = InstructionAt(i + 1);
       if (i > start) prev_instr = InstructionAt(i - 1);
       MeetConstraintsBetween(prev_instr, instr, i);
+      if (!AllocationOk()) return;
     }
   }
 }
 
 
 void LAllocator::MeetConstraintsBetween(LInstruction* first,
                                         LInstruction* second,
                                         int gap_index) {
   // Handle fixed temporaries.
   if (first != NULL) {
@@ skipping 45 matching lines @@
         LUnallocated* input_copy = cur_input->CopyUnconstrained();
         bool is_tagged = HasTaggedValue(cur_input->virtual_register());
         AllocateFixed(cur_input, gap_index + 1, is_tagged);
         AddConstraintsGapMove(gap_index, input_copy, cur_input);
       } else if (cur_input->policy() == LUnallocated::WRITABLE_REGISTER) {
         // The live range of writable input registers always goes until the end
         // of the instruction.
         ASSERT(!cur_input->IsUsedAtStart());
 
         LUnallocated* input_copy = cur_input->CopyUnconstrained();
-        cur_input->set_virtual_register(next_virtual_register_++);
+        cur_input->set_virtual_register(GetVirtualRegister());
+        if(!AllocationOk()) return;
 
         if (RequiredRegisterKind(input_copy->virtual_register()) ==
             DOUBLE_REGISTERS) {
           double_artificial_registers_.Add(
               cur_input->virtual_register() - first_artificial_register_);
         }
 
         AddConstraintsGapMove(gap_index, input_copy, cur_input);
       }
     }
@@ skipping 196 matching lines @@
 
     LiveRange* live_range = LiveRangeFor(phi->id());
     LLabel* label = chunk_->GetLabel(phi->block()->block_id());
     label->GetOrCreateParallelMove(LGap::START)->
         AddMove(phi_operand, live_range->GetSpillOperand());
     live_range->SetSpillStartIndex(phi->block()->first_instruction_index());
   }
 }
 
 
-void LAllocator::Allocate(LChunk* chunk) {
+bool LAllocator::Allocate(LChunk* chunk) {
   ASSERT(chunk_ == NULL);
   chunk_ = chunk;
   MeetRegisterConstraints();
+  if (!AllocationOk()) return false;
   ResolvePhis();
   BuildLiveRanges();
   AllocateGeneralRegisters();
+  if (!AllocationOk()) return false;
   AllocateDoubleRegisters();
+  if (!AllocationOk()) return false;
   PopulatePointerMaps();
   if (has_osr_entry_) ProcessOsrEntry();
   ConnectRanges();
   ResolveControlFlow();
+  return true;
 }
 
 
 void LAllocator::MeetRegisterConstraints() {
   HPhase phase("Register constraints", chunk_);
   first_artificial_register_ = next_virtual_register_;
   const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
   for (int i = 0; i < blocks->length(); ++i) {
     HBasicBlock* block = blocks->at(i);
     MeetRegisterConstraints(block);
+    if (!AllocationOk()) return;
   }
 }
 
 
 void LAllocator::ResolvePhis() {
   HPhase phase("Resolve phis", chunk_);
 
   // Process the blocks in reverse order.
   const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
   for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) {
@@ skipping 433 matching lines @@
       // If the range already has a spill operand and it doesn't need a
       // register immediately, split it and spill the first part of the range.
       if (pos == NULL) {
         Spill(current);
         continue;
       } else if (pos->pos().Value() >
                  current->Start().NextInstruction().Value()) {
         // Do not spill live range eagerly if use position that can benefit from
         // the register is too close to the start of live range.
         SpillBetween(current, current->Start(), pos->pos());
+        if (!AllocationOk()) return;
         ASSERT(UnhandledIsSorted());
         continue;
       }
     }
 
     for (int i = 0; i < active_live_ranges_.length(); ++i) {
       LiveRange* cur_active = active_live_ranges_.at(i);
       if (cur_active->End().Value() <= position.Value()) {
         ActiveToHandled(cur_active);
         --i;  // The live range was removed from the list of active live ranges.
@@ skipping 10 matching lines @@
         --i;  // Live range was removed from the list of inactive live ranges.
       } else if (cur_inactive->Covers(position)) {
         InactiveToActive(cur_inactive);
         --i;  // Live range was removed from the list of inactive live ranges.
       }
     }
 
     ASSERT(!current->HasRegisterAssigned() && !current->IsSpilled());
 
     bool result = TryAllocateFreeReg(current);
-    if (!result) {
-      AllocateBlockedReg(current);
-    }
+    if (!AllocationOk()) return;
+
+    if (!result) AllocateBlockedReg(current);
+    if (!AllocationOk()) return;
 
     if (current->HasRegisterAssigned()) {
       AddToActive(current);
     }
   }
 
   reusable_slots_.Rewind(0);
   active_live_ranges_.Rewind(0);
   inactive_live_ranges_.Rewind(0);
 }
@@ skipping 33 matching lines @@
     }
   } else if (double_artificial_registers_.Contains(
       virtual_register - first_artificial_register_)) {
     return DOUBLE_REGISTERS;
   }
 
   return GENERAL_REGISTERS;
 }
 
 
-void LAllocator::RecordDefinition(HInstruction* instr, LUnallocated* operand) {
-  operand->set_virtual_register(instr->id());
-}
-
-
-void LAllocator::RecordTemporary(LUnallocated* operand) {
-  ASSERT(next_virtual_register_ < LUnallocated::kMaxVirtualRegisters);
-  if (!operand->HasFixedPolicy()) {
-    operand->set_virtual_register(next_virtual_register_++);
-  }
-}
-
-
-void LAllocator::RecordUse(HValue* value, LUnallocated* operand) {
-  operand->set_virtual_register(value->id());
-}
-
-
-int LAllocator::max_initial_value_ids() {
-  return LUnallocated::kMaxVirtualRegisters / 16;
-}
-
-
 void LAllocator::AddToActive(LiveRange* range) {
   TraceAlloc("Add live range %d to active\n", range->id());
   active_live_ranges_.Add(range);
 }
 
 
 void LAllocator::AddToInactive(LiveRange* range) {
   TraceAlloc("Add live range %d to inactive\n", range->id());
   inactive_live_ranges_.Add(range);
 }
@@ skipping 174 matching lines @@
   LifetimePosition pos = free_until_pos[reg];
 
   if (pos.Value() <= current->Start().Value()) {
     // All registers are blocked.
     return false;
   }
 
   if (pos.Value() < current->End().Value()) {
     // Register reg is available at the range start but becomes blocked before
     // the range end. Split current at position where it becomes blocked.
-    LiveRange* tail = SplitAt(current, pos);
+    LiveRange* tail = SplitRangeAt(current, pos);
+    if (!AllocationOk()) return false;
     AddToUnhandledSorted(tail);
   }
 
 
   // Register reg is available at the range start and is free until
   // the range end.
   ASSERT(pos.Value() >= current->End().Value());
   TraceAlloc("Assigning free reg %s to live range %d\n",
              RegisterName(reg),
              current->id());
@@ skipping 134 matching lines @@
   }
 }
 
 
 bool LAllocator::IsBlockBoundary(LifetimePosition pos) {
   return pos.IsInstructionStart() &&
       InstructionAt(pos.InstructionIndex())->IsLabel();
 }
 
 
-LiveRange* LAllocator::SplitAt(LiveRange* range, LifetimePosition pos) {
+LiveRange* LAllocator::SplitRangeAt(LiveRange* range, LifetimePosition pos) {
   ASSERT(!range->IsFixed());
   TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value());
 
   if (pos.Value() <= range->Start().Value()) return range;
 
   // We can't properly connect liveranges if split occured at the end
   // of control instruction.
   ASSERT(pos.IsInstructionStart() ||
          !chunk_->instructions()->at(pos.InstructionIndex())->IsControl());
 
-  LiveRange* result = LiveRangeFor(next_virtual_register_++);
+  LiveRange* result = LiveRangeFor(GetVirtualRegister());
+  if (!AllocationOk()) return NULL;
   range->SplitAt(pos, result);
   return result;
 }
 
 
 LiveRange* LAllocator::SplitBetween(LiveRange* range,
                                     LifetimePosition start,
                                     LifetimePosition end) {
   ASSERT(!range->IsFixed());
   TraceAlloc("Splitting live range %d in position between [%d, %d]\n",
              range->id(),
              start.Value(),
              end.Value());
 
   LifetimePosition split_pos = FindOptimalSplitPos(start, end);
   ASSERT(split_pos.Value() >= start.Value());
-  return SplitAt(range, split_pos);
+  return SplitRangeAt(range, split_pos);
 }
 
 
 LifetimePosition LAllocator::FindOptimalSplitPos(LifetimePosition start,
                                                  LifetimePosition end) {
   int start_instr = start.InstructionIndex();
   int end_instr = end.InstructionIndex();
   ASSERT(start_instr <= end_instr);
 
   // We have no choice
@@ skipping 18 matching lines @@
   // We did not find any suitable outer loop. Split at the latest possible
   // position unless end_block is a loop header itself.
   if (block == end_block && !end_block->IsLoopHeader()) return end;
 
   return LifetimePosition::FromInstructionIndex(
       block->first_instruction_index());
 }
 
 
 void LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) {
-  LiveRange* second_part = SplitAt(range, pos);
+  LiveRange* second_part = SplitRangeAt(range, pos);
+  if (!AllocationOk()) return;
   Spill(second_part);
 }
 
 
 void LAllocator::SpillBetween(LiveRange* range,
                               LifetimePosition start,
                               LifetimePosition end) {
   ASSERT(start.Value() < end.Value());
-  LiveRange* second_part = SplitAt(range, start);
+  LiveRange* second_part = SplitRangeAt(range, start);
+  if (!AllocationOk()) return;
 
   if (second_part->Start().Value() < end.Value()) {
     // The split result intersects with [start, end[.
     // Split it at position between ]start+1, end[, spill the middle part
     // and put the rest to unhandled.
     LiveRange* third_part = SplitBetween(
         second_part,
         second_part->Start().InstructionEnd(),
         end.PrevInstruction().InstructionEnd());
 
@@ skipping 36 matching lines @@
     LiveRange* current = live_ranges()->at(i);
     if (current != NULL) current->Verify();
   }
 }
 
 
 #endif
 
 
 } }  // namespace v8::internal