Revision: 10597
Author: [email protected]
Date: Fri Feb 3 04:05:08 2012
Log: Allow bailing out of the register allocator when running out of
virtual registers.
1. Instead of checking upfront and estimating a limit for the number, we
now are able to stop register allocation and bailout when we don't
have enough virtual registers.
2. GCed some out-dated flags from flag-definition.h
3. Simplified the interface from the Lithium builder to the
register allocator in lithium-*.cc: For uses and definitions, we
just record the virtual register number given by the Hydrogen value id.
For temporaries, we request a new virtual register from the allocator.
For fixed temps, we don't need to do anything.
4. Increased number of deoptimization entries to 16K. Eventually we
probably want to make this array grow dynamically.
Review URL: https://chromiumcodereview.appspot.com/9325019
http://code.google.com/p/v8/source/detail?r=10597
Modified:
/branches/bleeding_edge/src/arm/lithium-arm.cc
/branches/bleeding_edge/src/compiler.cc
/branches/bleeding_edge/src/deoptimizer.h
/branches/bleeding_edge/src/flag-definitions.h
/branches/bleeding_edge/src/hydrogen.cc
/branches/bleeding_edge/src/ia32/lithium-ia32.cc
/branches/bleeding_edge/src/lithium-allocator.cc
/branches/bleeding_edge/src/lithium-allocator.h
/branches/bleeding_edge/src/mips/lithium-mips.cc
/branches/bleeding_edge/src/x64/lithium-x64.cc
=======================================
--- /branches/bleeding_edge/src/arm/lithium-arm.cc Tue Jan 31 07:00:13 2012
+++ /branches/bleeding_edge/src/arm/lithium-arm.cc Fri Feb 3 04:05:08 2012
@@ -671,7 +671,7 @@
HInstruction* instr = HInstruction::cast(value);
VisitInstruction(instr);
}
- allocator_->RecordUse(value, operand);
+ operand->set_virtual_register(value->id());
return operand;
}
@@ -679,7 +679,7 @@
template<int I, int T>
LInstruction* LChunkBuilder::Define(LTemplateInstruction<1, I, T>* instr,
LUnallocated* result) {
- allocator_->RecordDefinition(current_instruction_, result);
+ result->set_virtual_register(current_instruction_->id());
instr->set_result(result);
return instr;
}
@@ -791,21 +791,22 @@
LUnallocated* LChunkBuilder::TempRegister() {
LUnallocated* operand = new
LUnallocated(LUnallocated::MUST_HAVE_REGISTER);
- allocator_->RecordTemporary(operand);
+ operand->set_virtual_register(allocator_->GetVirtualRegister());
+ if (!allocator_->AllocationOk()) Abort("Not enough virtual registers.");
return operand;
}
LOperand* LChunkBuilder::FixedTemp(Register reg) {
LUnallocated* operand = ToUnallocated(reg);
- allocator_->RecordTemporary(operand);
+ ASSERT(operand->HasFixedPolicy());
return operand;
}
LOperand* LChunkBuilder::FixedTemp(DoubleRegister reg) {
LUnallocated* operand = ToUnallocated(reg);
- allocator_->RecordTemporary(operand);
+ ASSERT(operand->HasFixedPolicy());
return operand;
}
=======================================
--- /branches/bleeding_edge/src/compiler.cc Mon Jan 16 01:46:21 2012
+++ /branches/bleeding_edge/src/compiler.cc Fri Feb 3 04:05:08 2012
@@ -194,7 +194,7 @@
// Fall back to using the full code generator if it's not possible
// to use the Hydrogen-based optimizing compiler. We already have
// generated code for this from the shared function object.
- if (AlwaysFullCompiler() || !FLAG_use_hydrogen) {
+ if (AlwaysFullCompiler()) {
info->SetCode(code);
return true;
}
@@ -291,7 +291,7 @@
return false;
}
- if (graph != NULL && FLAG_build_lithium) {
+ if (graph != NULL) {
Handle<Code> optimized_code = graph->Compile(info);
if (!optimized_code.is_null()) {
info->SetCode(optimized_code);
=======================================
--- /branches/bleeding_edge/src/deoptimizer.h Tue Jan 31 04:08:33 2012
+++ /branches/bleeding_edge/src/deoptimizer.h Fri Feb 3 04:05:08 2012
@@ -270,7 +270,7 @@
#ifdef V8_TARGET_ARCH_MIPS
static const int kNumberOfEntries = 4096;
#else
- static const int kNumberOfEntries = 8192;
+ static const int kNumberOfEntries = 16384;
#endif
Deoptimizer(Isolate* isolate,
=======================================
--- /branches/bleeding_edge/src/flag-definitions.h Wed Feb 1 00:49:18 2012
+++ /branches/bleeding_edge/src/flag-definitions.h Fri Feb 3 04:05:08 2012
@@ -130,10 +130,6 @@
// Flags for Crankshaft.
DEFINE_bool(crankshaft, true, "use crankshaft")
DEFINE_string(hydrogen_filter, "", "hydrogen use/trace filter")
-DEFINE_bool(use_hydrogen, true, "use generated hydrogen for compilation")
-DEFINE_bool(build_lithium, true, "use lithium chunk builder")
-DEFINE_bool(alloc_lithium, true, "use lithium register allocator")
-DEFINE_bool(use_lithium, true, "use lithium code generator")
DEFINE_bool(use_range, true, "use hydrogen range analysis")
DEFINE_bool(eliminate_dead_phis, true, "eliminate dead phis")
DEFINE_bool(use_gvn, true, "use hydrogen global value numbering")
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Wed Feb 1 00:49:18 2012
+++ /branches/bleeding_edge/src/hydrogen.cc Fri Feb 3 04:05:08 2012
@@ -625,25 +625,23 @@
Handle<Code> HGraph::Compile(CompilationInfo* info) {
int values = GetMaximumValueID();
- if (values > LAllocator::max_initial_value_ids()) {
+ if (values > LUnallocated::kMaxVirtualRegisters) {
if (FLAG_trace_bailout) {
- SmartArrayPointer<char> name(
- info->shared_info()->DebugName()->ToCString());
- PrintF("Function @\"%s\" is too big.\n", *name);
+ PrintF("Not enough virtual registers for (values).\n");
}
return Handle<Code>::null();
}
-
LAllocator allocator(values, this);
LChunkBuilder builder(info, this, &allocator);
LChunk* chunk = builder.Build();
if (chunk == NULL) return Handle<Code>::null();
- if (!FLAG_alloc_lithium) return Handle<Code>::null();
-
- allocator.Allocate(chunk);
-
- if (!FLAG_use_lithium) return Handle<Code>::null();
+ if (!allocator.Allocate(chunk)) {
+ if (FLAG_trace_bailout) {
+ PrintF("Not enough virtual registers (regalloc).\n");
+ }
+ return Handle<Code>::null();
+ }
MacroAssembler assembler(info->isolate(), NULL, 0);
LCodeGen generator(chunk, &assembler, info);
=======================================
--- /branches/bleeding_edge/src/ia32/lithium-ia32.cc Tue Jan 31 07:00:13
2012
+++ /branches/bleeding_edge/src/ia32/lithium-ia32.cc Fri Feb 3 04:05:08
2012
@@ -670,7 +670,7 @@
HInstruction* instr = HInstruction::cast(value);
VisitInstruction(instr);
}
- allocator_->RecordUse(value, operand);
+ operand->set_virtual_register(value->id());
return operand;
}
@@ -678,7 +678,7 @@
template<int I, int T>
LInstruction* LChunkBuilder::Define(LTemplateInstruction<1, I, T>* instr,
LUnallocated* result) {
- allocator_->RecordDefinition(current_instruction_, result);
+ result->set_virtual_register(current_instruction_->id());
instr->set_result(result);
return instr;
}
@@ -796,21 +796,22 @@
LUnallocated* LChunkBuilder::TempRegister() {
LUnallocated* operand =
new(zone()) LUnallocated(LUnallocated::MUST_HAVE_REGISTER);
- allocator_->RecordTemporary(operand);
+ operand->set_virtual_register(allocator_->GetVirtualRegister());
+ if (!allocator_->AllocationOk()) Abort("Not enough virtual registers
(temps).");
return operand;
}
LOperand* LChunkBuilder::FixedTemp(Register reg) {
LUnallocated* operand = ToUnallocated(reg);
- allocator_->RecordTemporary(operand);
+ ASSERT(operand->HasFixedPolicy());
return operand;
}
LOperand* LChunkBuilder::FixedTemp(XMMRegister reg) {
LUnallocated* operand = ToUnallocated(reg);
- allocator_->RecordTemporary(operand);
+ ASSERT(operand->HasFixedPolicy());
return operand;
}
=======================================
--- /branches/bleeding_edge/src/lithium-allocator.cc Mon Jan 30 07:40:50
2012
+++ /branches/bleeding_edge/src/lithium-allocator.cc Fri Feb 3 04:05:08
2012
@@ -546,6 +546,7 @@
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),
@@ -787,6 +788,7 @@
if (i < end) instr = InstructionAt(i + 1);
if (i > start) prev_instr = InstructionAt(i - 1);
MeetConstraintsBetween(prev_instr, instr, i);
+ if (!AllocationOk()) return;
}
}
}
@@ -852,7 +854,8 @@
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) {
@@ -1069,18 +1072,22 @@
}
-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;
}
@@ -1091,6 +1098,7 @@
for (int i = 0; i < blocks->length(); ++i) {
HBasicBlock* block = blocks->at(i);
MeetRegisterConstraints(block);
+ if (!AllocationOk()) return;
}
}
@@ -1544,6 +1552,7 @@
// 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;
}
@@ -1574,9 +1583,10 @@
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);
@@ -1628,29 +1638,6 @@
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) {
@@ -1847,7 +1834,8 @@
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);
}
@@ -2002,7 +1990,7 @@
}
-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());
@@ -2013,7 +2001,8 @@
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;
}
@@ -2030,7 +2019,7 @@
LifetimePosition split_pos = FindOptimalSplitPos(start, end);
ASSERT(split_pos.Value() >= start.Value());
- return SplitAt(range, split_pos);
+ return SplitRangeAt(range, split_pos);
}
@@ -2069,7 +2058,8 @@
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);
}
@@ -2078,7 +2068,8 @@
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[.
=======================================
--- /branches/bleeding_edge/src/lithium-allocator.h Thu Nov 10 07:37:24 2011
+++ /branches/bleeding_edge/src/lithium-allocator.h Fri Feb 3 04:05:08 2012
@@ -431,24 +431,13 @@
static void TraceAlloc(const char* msg, ...);
- // Lithium translation support.
- // Record a use of an input operand in the current instruction.
- void RecordUse(HValue* value, LUnallocated* operand);
- // Record the definition of the output operand.
- void RecordDefinition(HInstruction* instr, LUnallocated* operand);
- // Record a temporary operand.
- void RecordTemporary(LUnallocated* operand);
-
// Checks whether the value of a given virtual register is tagged.
bool HasTaggedValue(int virtual_register) const;
// Returns the register kind required by the given virtual register.
RegisterKind RequiredRegisterKind(int virtual_register) const;
- // Control max function size.
- static int max_initial_value_ids();
-
- void Allocate(LChunk* chunk);
+ bool Allocate(LChunk* chunk);
const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; }
const Vector<LiveRange*>* fixed_live_ranges() const {
@@ -460,6 +449,15 @@
LChunk* chunk() const { return chunk_; }
HGraph* graph() const { return graph_; }
+
+ int GetVirtualRegister() {
+ if (next_virtual_register_ > LUnallocated::kMaxVirtualRegisters) {
+ allocation_ok_ = false;
+ }
+ return next_virtual_register_++;
+ }
+
+ bool AllocationOk() { return allocation_ok_; }
void MarkAsOsrEntry() {
// There can be only one.
@@ -533,7 +531,7 @@
// Otherwise returns the live range that starts at pos and contains
// all uses from the original range that follow pos. Uses at pos will
// still be owned by the original range after splitting.
- LiveRange* SplitAt(LiveRange* range, LifetimePosition pos);
+ LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos);
// Split the given range in a position from the interval [start, end].
LiveRange* SplitBetween(LiveRange* range,
@@ -591,6 +589,9 @@
LChunk* chunk_;
+ // Indicates success or failure during register allocation.
+ bool allocation_ok_;
+
// During liveness analysis keep a mapping from block id to live_in sets
// for blocks already analyzed.
ZoneList<BitVector*> live_in_sets_;
=======================================
--- /branches/bleeding_edge/src/mips/lithium-mips.cc Tue Jan 31 07:00:13
2012
+++ /branches/bleeding_edge/src/mips/lithium-mips.cc Fri Feb 3 04:05:08
2012
@@ -671,7 +671,7 @@
HInstruction* instr = HInstruction::cast(value);
VisitInstruction(instr);
}
- allocator_->RecordUse(value, operand);
+ operand->set_virtual_register(value->id());
return operand;
}
@@ -679,7 +679,7 @@
template<int I, int T>
LInstruction* LChunkBuilder::Define(LTemplateInstruction<1, I, T>* instr,
LUnallocated* result) {
- allocator_->RecordDefinition(current_instruction_, result);
+ result->set_virtual_register(current_instruction_->id());
instr->set_result(result);
return instr;
}
@@ -791,21 +791,22 @@
LUnallocated* LChunkBuilder::TempRegister() {
LUnallocated* operand = new
LUnallocated(LUnallocated::MUST_HAVE_REGISTER);
- allocator_->RecordTemporary(operand);
+ operand->set_virtual_register(allocator_->GetVirtualRegister());
+ if (!allocator_->AllocationOk()) Abort("Not enough virtual registers.");
return operand;
}
LOperand* LChunkBuilder::FixedTemp(Register reg) {
LUnallocated* operand = ToUnallocated(reg);
- allocator_->RecordTemporary(operand);
+ ASSERT(operand->HasFixedPolicy());
return operand;
}
LOperand* LChunkBuilder::FixedTemp(DoubleRegister reg) {
LUnallocated* operand = ToUnallocated(reg);
- allocator_->RecordTemporary(operand);
+ ASSERT(operand->HasFixedPolicy());
return operand;
}
=======================================
--- /branches/bleeding_edge/src/x64/lithium-x64.cc Tue Jan 31 07:00:13 2012
+++ /branches/bleeding_edge/src/x64/lithium-x64.cc Fri Feb 3 04:05:08 2012
@@ -664,7 +664,7 @@
HInstruction* instr = HInstruction::cast(value);
VisitInstruction(instr);
}
- allocator_->RecordUse(value, operand);
+ operand->set_virtual_register(value->id());
return operand;
}
@@ -672,7 +672,7 @@
template<int I, int T>
LInstruction* LChunkBuilder::Define(LTemplateInstruction<1, I, T>* instr,
LUnallocated* result) {
- allocator_->RecordDefinition(current_instruction_, result);
+ result->set_virtual_register(current_instruction_->id());
instr->set_result(result);
return instr;
}
@@ -786,21 +786,22 @@
LUnallocated* LChunkBuilder::TempRegister() {
LUnallocated* operand = new
LUnallocated(LUnallocated::MUST_HAVE_REGISTER);
- allocator_->RecordTemporary(operand);
+ operand->set_virtual_register(allocator_->GetVirtualRegister());
+ if (!allocator_->AllocationOk()) Abort("Not enough virtual registers.");
return operand;
}
LOperand* LChunkBuilder::FixedTemp(Register reg) {
LUnallocated* operand = ToUnallocated(reg);
- allocator_->RecordTemporary(operand);
+ ASSERT(operand->HasFixedPolicy());
return operand;
}
LOperand* LChunkBuilder::FixedTemp(XMMRegister reg) {
LUnallocated* operand = ToUnallocated(reg);
- allocator_->RecordTemporary(operand);
+ ASSERT(operand->HasFixedPolicy());
return operand;
}
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
