compiler/optimizing/register_allocator.cc - platform/art - Git at Google

 /*
  * Copyright (C) 2014 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "register_allocator.h"

 #include "code_generator.h"
 #include "ssa_liveness_analysis.h"

 namespace art {

 static constexpr size_t kMaxLifetimePosition = -1;

 RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, const CodeGenerator& codegen)
       : allocator_(allocator),
         codegen_(codegen),
         unhandled_(allocator, 0),
         handled_(allocator, 0),
         active_(allocator, 0),
         inactive_(allocator, 0),
         processing_core_registers_(false),
         number_of_registers_(-1),
         registers_array_(nullptr),
         blocked_registers_(allocator->AllocArray<bool>(codegen.GetNumberOfRegisters())) {
   codegen.SetupBlockedRegisters(blocked_registers_);
 }

 static bool ShouldProcess(bool processing_core_registers, HInstruction* instruction) {
   bool is_core_register = (instruction->GetType() != Primitive::kPrimDouble)
       && (instruction->GetType() != Primitive::kPrimFloat);
   return processing_core_registers == is_core_register;
 }

 void RegisterAllocator::AllocateRegistersInternal(const SsaLivenessAnalysis& liveness) {
   number_of_registers_ = processing_core_registers_
       ? codegen_.GetNumberOfCoreRegisters()
       : codegen_.GetNumberOfFloatingPointRegisters();

   registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_);

   // Iterate post-order, to ensure the list is sorted, and the last added interval
   // is the one with the lowest start position.
   for (size_t i = liveness.GetNumberOfSsaValues(); i > 0; --i) {
     HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i - 1);
     if (ShouldProcess(processing_core_registers_, instruction)) {
       LiveInterval* current = instruction->GetLiveInterval();
       DCHECK(unhandled_.IsEmpty() || current->StartsBefore(unhandled_.Peek()));
       unhandled_.Add(current);
     }
   }

   LinearScan();
   if (kIsDebugBuild) {
     ValidateInternal(liveness, true);
   }
 }

 bool RegisterAllocator::ValidateInternal(const SsaLivenessAnalysis& liveness,
                                          bool log_fatal_on_failure) const {
   // To simplify unit testing, we eagerly create the array of intervals, and
   // call the helper method.
   GrowableArray<LiveInterval*> intervals(allocator_, 0);
   for (size_t i = 0; i < liveness.GetNumberOfSsaValues(); ++i) {
     HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i);
     if (ShouldProcess(processing_core_registers_, instruction)) {
       intervals.Add(instruction->GetLiveInterval());
     }
   }
   return ValidateIntervals(intervals, codegen_, allocator_, processing_core_registers_,
                            log_fatal_on_failure);
 }

 bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& ranges,
                                           const CodeGenerator& codegen,
                                           ArenaAllocator* allocator,
                                           bool processing_core_registers,
                                           bool log_fatal_on_failure) {
   size_t number_of_registers = processing_core_registers
       ? codegen.GetNumberOfCoreRegisters()
       : codegen.GetNumberOfFloatingPointRegisters();
   GrowableArray<ArenaBitVector*> bit_vectors(allocator, number_of_registers);

   // Allocate a bit vector per register. A live interval that has a register
   // allocated will populate the associated bit vector based on its live ranges.
   for (size_t i = 0; i < number_of_registers; i++) {
     bit_vectors.Add(new (allocator) ArenaBitVector(allocator, 0, true));
   }

   for (size_t i = 0, e = ranges.Size(); i < e; ++i) {
     LiveInterval* current = ranges.Get(i);
     do {
       if (!current->HasRegister()) {
         continue;
       }
       BitVector* vector = bit_vectors.Get(current->GetRegister());
       LiveRange* range = current->GetFirstRange();
       do {
         for (size_t j = range->GetStart(); j < range->GetEnd(); ++j) {
           if (vector->IsBitSet(j)) {
             if (log_fatal_on_failure) {
               std::ostringstream message;
               message << "Register conflict at " << j << " for ";
               if (processing_core_registers) {
                 codegen.DumpCoreRegister(message, current->GetRegister());
               } else {
                 codegen.DumpFloatingPointRegister(message, current->GetRegister());
               }
               LOG(FATAL) << message.str();
             } else {
               return false;
             }
           } else {
             vector->SetBit(j);
           }
         }
       } while ((range = range->GetNext()) != nullptr);
     } while ((current = current->GetNextSibling()) != nullptr);
   }
   return true;
 }

 void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) {
   interval->Dump(stream);
   stream << ": ";
   if (interval->HasRegister()) {
     if (processing_core_registers_) {
       codegen_.DumpCoreRegister(stream, interval->GetRegister());
     } else {
       codegen_.DumpFloatingPointRegister(stream, interval->GetRegister());
     }
   } else {
     stream << "spilled";
   }
   stream << std::endl;
 }

 // By the book implementation of a linear scan register allocator.
 void RegisterAllocator::LinearScan() {
   while (!unhandled_.IsEmpty()) {
     // (1) Remove interval with the lowest start position from unhandled.
     LiveInterval* current = unhandled_.Pop();
     size_t position = current->GetStart();

     // (2) Remove currently active intervals that are dead at this position.
     //     Move active intervals that have a lifetime hole at this position
     //     to inactive.
     for (size_t i = 0; i < active_.Size(); ++i) {
       LiveInterval* interval = active_.Get(i);
       if (interval->IsDeadAt(position)) {
         active_.Delete(interval);
         --i;
         handled_.Add(interval);
       } else if (!interval->Covers(position)) {
         active_.Delete(interval);
         --i;
         inactive_.Add(interval);
       }
     }

     // (3) Remove currently inactive intervals that are dead at this position.
     //     Move inactive intervals that cover this position to active.
     for (size_t i = 0; i < inactive_.Size(); ++i) {
       LiveInterval* interval = inactive_.Get(i);
       if (interval->IsDeadAt(position)) {
         inactive_.Delete(interval);
         --i;
         handled_.Add(interval);
       } else if (interval->Covers(position)) {
         inactive_.Delete(interval);
         --i;
         active_.Add(interval);
       }
     }

     // (4) Try to find an available register.
     bool success = TryAllocateFreeReg(current);

     // (5) If no register could be found, we need to spill.
     if (!success) {
       success = AllocateBlockedReg(current);
     }

     // (6) If the interval had a register allocated, add it to the list of active
     //     intervals.
     if (success) {
       active_.Add(current);
     }
   }
 }

 // Find a free register. If multiple are found, pick the register that
 // is free the longest.
 bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) {
   size_t* free_until = registers_array_;

   // First set all registers to be free.
   for (size_t i = 0; i < number_of_registers_; ++i) {
     free_until[i] = kMaxLifetimePosition;
   }

   // For each active interval, set its register to not free.
   for (size_t i = 0, e = active_.Size(); i < e; ++i) {
     LiveInterval* interval = active_.Get(i);
     DCHECK(interval->HasRegister());
     free_until[interval->GetRegister()] = 0;
   }

   // For each inactive interval, set its register to be free until
   // the next intersection with `current`.
   // Thanks to SSA, this should only be needed for intervals
   // that are the result of a split.
   for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
     LiveInterval* inactive = inactive_.Get(i);
     DCHECK(inactive->HasRegister());
     size_t next_intersection = inactive->FirstIntersectionWith(current);
     if (next_intersection != kNoLifetime) {
       free_until[inactive->GetRegister()] = next_intersection;
     }
   }

   // Pick the register that is free the longest.
   int reg = -1;
   for (size_t i = 0; i < number_of_registers_; ++i) {
     if (IsBlocked(i)) continue;
     if (reg == -1 || free_until[i] > free_until[reg]) {
       reg = i;
       if (free_until[i] == kMaxLifetimePosition) break;
     }
   }

   // If we could not find a register, we need to spill.
   if (reg == -1 || free_until[reg] == 0) {
     return false;
   }

   current->SetRegister(reg);
   if (!current->IsDeadAt(free_until[reg])) {
     // If the register is only available for a subset of live ranges
     // covered by `current`, split `current` at the position where
     // the register is not available anymore.
     LiveInterval* split = Split(current, free_until[reg]);
     DCHECK(split != nullptr);
     AddToUnhandled(split);
   }
   return true;
 }

 bool RegisterAllocator::IsBlocked(int reg) const {
   // TODO: This only works for core registers and needs to be adjusted for
   // floating point registers.
   DCHECK(processing_core_registers_);
   return blocked_registers_[reg];
 }

 // Find the register that is used the last, and spill the interval
 // that holds it. If the first use of `current` is after that register
 // we spill `current` instead.
 bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
   size_t first_register_use = current->FirstRegisterUse();
   if (current->FirstRegisterUse() == kNoLifetime) {
     // TODO: Allocate spill slot for `current`.
     return false;
   }

   // First set all registers as not being used.
   size_t* next_use = registers_array_;
   for (size_t i = 0; i < number_of_registers_; ++i) {
     next_use[i] = kMaxLifetimePosition;
   }

   // For each active interval, find the next use of its register after the
   // start of current.
   for (size_t i = 0, e = active_.Size(); i < e; ++i) {
     LiveInterval* active = active_.Get(i);
     DCHECK(active->HasRegister());
     size_t use = active->FirstRegisterUseAfter(current->GetStart());
     if (use != kNoLifetime) {
       next_use[active->GetRegister()] = use;
     }
   }

   // For each inactive interval, find the next use of its register after the
   // start of current.
   // Thanks to SSA, this should only be needed for intervals
   // that are the result of a split.
   for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
     LiveInterval* inactive = inactive_.Get(i);
     DCHECK(inactive->HasRegister());
     size_t use = inactive->FirstRegisterUseAfter(current->GetStart());
     if (use != kNoLifetime) {
       next_use[inactive->GetRegister()] = use;
     }
   }

   // Pick the register that is used the last.
   int reg = -1;
   for (size_t i = 0; i < number_of_registers_; ++i) {
     if (IsBlocked(i)) continue;
     if (reg == -1 || next_use[i] > next_use[reg]) {
       reg = i;
       if (next_use[i] == kMaxLifetimePosition) break;
     }
   }

   if (first_register_use >= next_use[reg]) {
     // If the first use of that instruction is after the last use of the found
     // register, we split this interval just before its first register use.
     LiveInterval* split = Split(current, first_register_use - 1);
     AddToUnhandled(split);
     return false;
   } else {
     // Use this register and spill the active and inactives interval that
     // have that register.
     current->SetRegister(reg);

     for (size_t i = 0, e = active_.Size(); i < e; ++i) {
       LiveInterval* active = active_.Get(i);
       if (active->GetRegister() == reg) {
         LiveInterval* split = Split(active, current->GetStart());
         active_.DeleteAt(i);
         handled_.Add(active);
         AddToUnhandled(split);
         break;
       }
     }

     for (size_t i = 0; i < inactive_.Size(); ++i) {
       LiveInterval* inactive = inactive_.Get(i);
       if (inactive->GetRegister() == reg) {
         LiveInterval* split = Split(inactive, current->GetStart());
         inactive_.DeleteAt(i);
         handled_.Add(inactive);
         AddToUnhandled(split);
         --i;
       }
     }

     return true;
   }
 }

 void RegisterAllocator::AddToUnhandled(LiveInterval* interval) {
   for (size_t i = unhandled_.Size(); i > 0; --i) {
     LiveInterval* current = unhandled_.Get(i - 1);
     if (current->StartsAfter(interval)) {
       unhandled_.InsertAt(i, interval);
       break;
     }
   }
 }

 LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) {
   DCHECK(position >= interval->GetStart());
   DCHECK(!interval->IsDeadAt(position));
   if (position == interval->GetStart()) {
     // Spill slot will be allocated when handling `interval` again.
     interval->ClearRegister();
     return interval;
   } else {
     LiveInterval* new_interval = interval->SplitAt(position);
     // TODO: Allocate spill slot for `interval`.
     return new_interval;
   }
 }

 }  // namespace art
	/*
	* Copyright (C) 2014 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "register_allocator.h"

	#include "code_generator.h"
	#include "ssa_liveness_analysis.h"

	namespace art {

	static constexpr size_t kMaxLifetimePosition = -1;

	RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, const CodeGenerator& codegen)
	: allocator_(allocator),
	codegen_(codegen),
	unhandled_(allocator, 0),
	handled_(allocator, 0),
	active_(allocator, 0),
	inactive_(allocator, 0),
	processing_core_registers_(false),
	number_of_registers_(-1),
	registers_array_(nullptr),
	blocked_registers_(allocator->AllocArray<bool>(codegen.GetNumberOfRegisters())) {
	codegen.SetupBlockedRegisters(blocked_registers_);
	}

	static bool ShouldProcess(bool processing_core_registers, HInstruction* instruction) {
	bool is_core_register = (instruction->GetType() != Primitive::kPrimDouble)
	&& (instruction->GetType() != Primitive::kPrimFloat);
	return processing_core_registers == is_core_register;
	}

	void RegisterAllocator::AllocateRegistersInternal(const SsaLivenessAnalysis& liveness) {
	number_of_registers_ = processing_core_registers_
	? codegen_.GetNumberOfCoreRegisters()
	: codegen_.GetNumberOfFloatingPointRegisters();

	registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_);

	// Iterate post-order, to ensure the list is sorted, and the last added interval
	// is the one with the lowest start position.
	for (size_t i = liveness.GetNumberOfSsaValues(); i > 0; --i) {
	HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i - 1);
	if (ShouldProcess(processing_core_registers_, instruction)) {
	LiveInterval* current = instruction->GetLiveInterval();
	DCHECK(unhandled_.IsEmpty() \|\| current->StartsBefore(unhandled_.Peek()));
	unhandled_.Add(current);
	}
	}

	LinearScan();
	if (kIsDebugBuild) {
	ValidateInternal(liveness, true);
	}
	}

	bool RegisterAllocator::ValidateInternal(const SsaLivenessAnalysis& liveness,
	bool log_fatal_on_failure) const {
	// To simplify unit testing, we eagerly create the array of intervals, and
	// call the helper method.
	GrowableArray<LiveInterval*> intervals(allocator_, 0);
	for (size_t i = 0; i < liveness.GetNumberOfSsaValues(); ++i) {
	HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i);
	if (ShouldProcess(processing_core_registers_, instruction)) {
	intervals.Add(instruction->GetLiveInterval());
	}
	}
	return ValidateIntervals(intervals, codegen_, allocator_, processing_core_registers_,
	log_fatal_on_failure);
	}

	bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& ranges,
	const CodeGenerator& codegen,
	ArenaAllocator* allocator,
	bool processing_core_registers,
	bool log_fatal_on_failure) {
	size_t number_of_registers = processing_core_registers
	? codegen.GetNumberOfCoreRegisters()
	: codegen.GetNumberOfFloatingPointRegisters();
	GrowableArray<ArenaBitVector*> bit_vectors(allocator, number_of_registers);

	// Allocate a bit vector per register. A live interval that has a register
	// allocated will populate the associated bit vector based on its live ranges.
	for (size_t i = 0; i < number_of_registers; i++) {
	bit_vectors.Add(new (allocator) ArenaBitVector(allocator, 0, true));
	}

	for (size_t i = 0, e = ranges.Size(); i < e; ++i) {
	LiveInterval* current = ranges.Get(i);
	do {
	if (!current->HasRegister()) {
	continue;
	}
	BitVector* vector = bit_vectors.Get(current->GetRegister());
	LiveRange* range = current->GetFirstRange();
	do {
	for (size_t j = range->GetStart(); j < range->GetEnd(); ++j) {
	if (vector->IsBitSet(j)) {
	if (log_fatal_on_failure) {
	std::ostringstream message;
	message << "Register conflict at " << j << " for ";
	if (processing_core_registers) {
	codegen.DumpCoreRegister(message, current->GetRegister());
	} else {
	codegen.DumpFloatingPointRegister(message, current->GetRegister());
	}
	LOG(FATAL) << message.str();
	} else {
	return false;
	}
	} else {
	vector->SetBit(j);
	}
	}
	} while ((range = range->GetNext()) != nullptr);
	} while ((current = current->GetNextSibling()) != nullptr);
	}
	return true;
	}

	void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) {
	interval->Dump(stream);
	stream << ": ";
	if (interval->HasRegister()) {
	if (processing_core_registers_) {
	codegen_.DumpCoreRegister(stream, interval->GetRegister());
	} else {
	codegen_.DumpFloatingPointRegister(stream, interval->GetRegister());
	}
	} else {
	stream << "spilled";
	}
	stream << std::endl;
	}

	// By the book implementation of a linear scan register allocator.
	void RegisterAllocator::LinearScan() {
	while (!unhandled_.IsEmpty()) {
	// (1) Remove interval with the lowest start position from unhandled.
	LiveInterval* current = unhandled_.Pop();
	size_t position = current->GetStart();

	// (2) Remove currently active intervals that are dead at this position.
	// Move active intervals that have a lifetime hole at this position
	// to inactive.
	for (size_t i = 0; i < active_.Size(); ++i) {
	LiveInterval* interval = active_.Get(i);
	if (interval->IsDeadAt(position)) {
	active_.Delete(interval);
	--i;
	handled_.Add(interval);
	} else if (!interval->Covers(position)) {
	active_.Delete(interval);
	--i;
	inactive_.Add(interval);
	}
	}

	// (3) Remove currently inactive intervals that are dead at this position.
	// Move inactive intervals that cover this position to active.
	for (size_t i = 0; i < inactive_.Size(); ++i) {
	LiveInterval* interval = inactive_.Get(i);
	if (interval->IsDeadAt(position)) {
	inactive_.Delete(interval);
	--i;
	handled_.Add(interval);
	} else if (interval->Covers(position)) {
	inactive_.Delete(interval);
	--i;
	active_.Add(interval);
	}
	}

	// (4) Try to find an available register.
	bool success = TryAllocateFreeReg(current);

	// (5) If no register could be found, we need to spill.
	if (!success) {
	success = AllocateBlockedReg(current);
	}

	// (6) If the interval had a register allocated, add it to the list of active
	// intervals.
	if (success) {
	active_.Add(current);
	}
	}
	}

	// Find a free register. If multiple are found, pick the register that
	// is free the longest.
	bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) {
	size_t* free_until = registers_array_;

	// First set all registers to be free.
	for (size_t i = 0; i < number_of_registers_; ++i) {
	free_until[i] = kMaxLifetimePosition;
	}

	// For each active interval, set its register to not free.
	for (size_t i = 0, e = active_.Size(); i < e; ++i) {
	LiveInterval* interval = active_.Get(i);
	DCHECK(interval->HasRegister());
	free_until[interval->GetRegister()] = 0;
	}

	// For each inactive interval, set its register to be free until
	// the next intersection with `current`.
	// Thanks to SSA, this should only be needed for intervals
	// that are the result of a split.
	for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
	LiveInterval* inactive = inactive_.Get(i);
	DCHECK(inactive->HasRegister());
	size_t next_intersection = inactive->FirstIntersectionWith(current);
	if (next_intersection != kNoLifetime) {
	free_until[inactive->GetRegister()] = next_intersection;
	}
	}

	// Pick the register that is free the longest.
	int reg = -1;
	for (size_t i = 0; i < number_of_registers_; ++i) {
	if (IsBlocked(i)) continue;
	if (reg == -1 \|\| free_until[i] > free_until[reg]) {
	reg = i;
	if (free_until[i] == kMaxLifetimePosition) break;
	}
	}

	// If we could not find a register, we need to spill.
	if (reg == -1 \|\| free_until[reg] == 0) {
	return false;
	}

	current->SetRegister(reg);
	if (!current->IsDeadAt(free_until[reg])) {
	// If the register is only available for a subset of live ranges
	// covered by `current`, split `current` at the position where
	// the register is not available anymore.
	LiveInterval* split = Split(current, free_until[reg]);
	DCHECK(split != nullptr);
	AddToUnhandled(split);
	}
	return true;
	}

	bool RegisterAllocator::IsBlocked(int reg) const {
	// TODO: This only works for core registers and needs to be adjusted for
	// floating point registers.
	DCHECK(processing_core_registers_);
	return blocked_registers_[reg];
	}

	// Find the register that is used the last, and spill the interval
	// that holds it. If the first use of `current` is after that register
	// we spill `current` instead.
	bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
	size_t first_register_use = current->FirstRegisterUse();
	if (current->FirstRegisterUse() == kNoLifetime) {
	// TODO: Allocate spill slot for `current`.
	return false;
	}

	// First set all registers as not being used.
	size_t* next_use = registers_array_;
	for (size_t i = 0; i < number_of_registers_; ++i) {
	next_use[i] = kMaxLifetimePosition;
	}

	// For each active interval, find the next use of its register after the
	// start of current.
	for (size_t i = 0, e = active_.Size(); i < e; ++i) {
	LiveInterval* active = active_.Get(i);
	DCHECK(active->HasRegister());
	size_t use = active->FirstRegisterUseAfter(current->GetStart());
	if (use != kNoLifetime) {
	next_use[active->GetRegister()] = use;
	}
	}

	// For each inactive interval, find the next use of its register after the
	// start of current.
	// Thanks to SSA, this should only be needed for intervals
	// that are the result of a split.
	for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
	LiveInterval* inactive = inactive_.Get(i);
	DCHECK(inactive->HasRegister());
	size_t use = inactive->FirstRegisterUseAfter(current->GetStart());
	if (use != kNoLifetime) {
	next_use[inactive->GetRegister()] = use;
	}
	}

	// Pick the register that is used the last.
	int reg = -1;
	for (size_t i = 0; i < number_of_registers_; ++i) {
	if (IsBlocked(i)) continue;
	if (reg == -1 \|\| next_use[i] > next_use[reg]) {
	reg = i;
	if (next_use[i] == kMaxLifetimePosition) break;
	}
	}

	if (first_register_use >= next_use[reg]) {
	// If the first use of that instruction is after the last use of the found
	// register, we split this interval just before its first register use.
	LiveInterval* split = Split(current, first_register_use - 1);
	AddToUnhandled(split);
	return false;
	} else {
	// Use this register and spill the active and inactives interval that
	// have that register.
	current->SetRegister(reg);

	for (size_t i = 0, e = active_.Size(); i < e; ++i) {
	LiveInterval* active = active_.Get(i);
	if (active->GetRegister() == reg) {
	LiveInterval* split = Split(active, current->GetStart());
	active_.DeleteAt(i);
	handled_.Add(active);
	AddToUnhandled(split);
	break;
	}
	}

	for (size_t i = 0; i < inactive_.Size(); ++i) {
	LiveInterval* inactive = inactive_.Get(i);
	if (inactive->GetRegister() == reg) {
	LiveInterval* split = Split(inactive, current->GetStart());
	inactive_.DeleteAt(i);
	handled_.Add(inactive);
	AddToUnhandled(split);
	--i;
	}
	}

	return true;
	}
	}

	void RegisterAllocator::AddToUnhandled(LiveInterval* interval) {
	for (size_t i = unhandled_.Size(); i > 0; --i) {
	LiveInterval* current = unhandled_.Get(i - 1);
	if (current->StartsAfter(interval)) {
	unhandled_.InsertAt(i, interval);
	break;
	}
	}
	}

	LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) {
	DCHECK(position >= interval->GetStart());
	DCHECK(!interval->IsDeadAt(position));
	if (position == interval->GetStart()) {
	// Spill slot will be allocated when handling `interval` again.
	interval->ClearRegister();
	return interval;
	} else {
	LiveInterval* new_interval = interval->SplitAt(position);
	// TODO: Allocate spill slot for `interval`.
	return new_interval;
	}
	}

	} // namespace art