From a7aca370a7d62ca04a1e24423d90e8020d6f1a58 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Mon, 28 Apr 2014 17:47:12 +0100 Subject: Setup policies for register allocation. Change-Id: I857e77530fca3e2fb872fc142a916af1b48400dc --- compiler/optimizing/code_generator.cc | 100 +++++++++++++- compiler/optimizing/code_generator.h | 112 +++++++++++++--- compiler/optimizing/code_generator_arm.cc | 153 ++++++++++++++++----- compiler/optimizing/code_generator_arm.h | 11 +- compiler/optimizing/code_generator_x86.cc | 216 +++++++++++++++++++++++------- compiler/optimizing/code_generator_x86.h | 11 +- 6 files changed, 496 insertions(+), 107 deletions(-) (limited to 'compiler') diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc index babb1f5628..ff316e5b04 100644 --- a/compiler/optimizing/code_generator.cc +++ b/compiler/optimizing/code_generator.cc @@ -55,9 +55,105 @@ void CodeGenerator::CompileBlock(HBasicBlock* block) { } } +size_t CodeGenerator::AllocateFreeRegisterInternal( + bool* blocked_registers, size_t number_of_registers) const { + for (size_t regno = 0; regno < number_of_registers; regno++) { + if (!blocked_registers[regno]) { + blocked_registers[regno] = true; + return regno; + } + } + LOG(FATAL) << "Unreachable"; + return -1; +} + + +void CodeGenerator::AllocateRegistersLocally(HInstruction* instruction) const { + LocationSummary* locations = instruction->GetLocations(); + if (locations == nullptr) return; + + for (size_t i = 0, e = GetNumberOfRegisters(); i < e; ++i) { + blocked_registers_[i] = false; + } + + // Mark all fixed input, temp and output registers as used. + for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) { + Location loc = locations->InAt(i); + if (loc.IsRegister()) { + // Check that a register is not specified twice in the summary. + DCHECK(!blocked_registers_[loc.GetEncoding()]); + blocked_registers_[loc.GetEncoding()] = true; + } + } + + for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) { + Location loc = locations->GetTemp(i); + if (loc.IsRegister()) { + // Check that a register is not specified twice in the summary. + DCHECK(!blocked_registers_[loc.GetEncoding()]); + blocked_registers_[loc.GetEncoding()] = true; + } + } + + SetupBlockedRegisters(blocked_registers_); + + // Allocate all unallocated input locations. + for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) { + Location loc = locations->InAt(i); + HInstruction* input = instruction->InputAt(i); + if (loc.IsUnallocated()) { + if (loc.GetPolicy() == Location::kRequiresRegister) { + loc = Location::RegisterLocation( + AllocateFreeRegister(input->GetType(), blocked_registers_)); + } else { + DCHECK_EQ(loc.GetPolicy(), Location::kAny); + HLoadLocal* load = input->AsLoadLocal(); + if (load != nullptr) { + loc = GetStackLocation(load); + } else { + loc = Location::RegisterLocation( + AllocateFreeRegister(input->GetType(), blocked_registers_)); + } + } + locations->SetInAt(i, loc); + } + } + + // Allocate all unallocated temp locations. + for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) { + Location loc = locations->GetTemp(i); + if (loc.IsUnallocated()) { + DCHECK_EQ(loc.GetPolicy(), Location::kRequiresRegister); + // TODO: Adjust handling of temps. We currently consider temps to use + // core registers. They may also use floating point registers at some point. + loc = Location::RegisterLocation(static_cast( + AllocateFreeRegister(Primitive::kPrimInt, blocked_registers_))); + locations->SetTempAt(i, loc); + } + } + + Location result_location = locations->Out(); + if (result_location.IsUnallocated()) { + switch (result_location.GetPolicy()) { + case Location::kAny: + case Location::kRequiresRegister: + result_location = Location::RegisterLocation( + AllocateFreeRegister(instruction->GetType(), blocked_registers_)); + break; + case Location::kSameAsFirstInput: + result_location = locations->InAt(0); + break; + } + locations->SetOut(result_location); + } +} + void CodeGenerator::InitLocations(HInstruction* instruction) { - if (instruction->GetLocations() == nullptr) return; - for (size_t i = 0; i < instruction->InputCount(); i++) { + if (instruction->GetLocations() == nullptr) { + return; + } + AllocateRegistersLocally(instruction); + for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) { Location location = instruction->GetLocations()->InAt(i); if (location.IsValid()) { // Move the input to the desired location. diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h index 54f9e70695..74cbccc4b8 100644 --- a/compiler/optimizing/code_generator.h +++ b/compiler/optimizing/code_generator.h @@ -62,6 +62,12 @@ class Location : public ValueObject { // bits are in a stack slot. The kQuickParameter kind is for // handling this special case. kQuickParameter = 4, + + // Unallocated location represents a location that is not fixed and can be + // allocated by a register allocator. Each unallocated location has + // a policy that specifies what kind of location is suitable. Payload + // contains register allocation policy. + kUnallocated = 5, }; Location() : value_(kInvalid) { @@ -166,10 +172,50 @@ class Location : public ValueObject { case kStackSlot: return "S"; case kDoubleStackSlot: return "DS"; case kQuickParameter: return "Q"; + case kUnallocated: return "U"; } return "?"; } + // Unallocated locations. + enum Policy { + kAny, + kRequiresRegister, + kSameAsFirstInput, + }; + + bool IsUnallocated() const { + return GetKind() == kUnallocated; + } + + static Location UnallocatedLocation(Policy policy) { + return Location(kUnallocated, PolicyField::Encode(policy)); + } + + // Any free register is suitable to replace this unallocated location. + static Location Any() { + return UnallocatedLocation(kAny); + } + + static Location RequiresRegister() { + return UnallocatedLocation(kRequiresRegister); + } + + // The location of the first input to the instruction will be + // used to replace this unallocated location. + static Location SameAsFirstInput() { + return UnallocatedLocation(kSameAsFirstInput); + } + + Policy GetPolicy() const { + DCHECK(IsUnallocated()); + return PolicyField::Decode(GetPayload()); + } + + uword GetEncoding() const { + return GetPayload(); + } + private: // Number of bits required to encode Kind value. static constexpr uint32_t kBitsForKind = 4; @@ -187,6 +233,9 @@ class Location : public ValueObject { typedef BitField KindField; typedef BitField PayloadField; + // Layout for kUnallocated locations payload. + typedef BitField PolicyField; + // Layout for stack slots. static const intptr_t kStackIndexBias = static_cast(1) << (kBitsForPayload - 1); @@ -208,40 +257,52 @@ class Location : public ValueObject { class LocationSummary : public ArenaObject { public: explicit LocationSummary(HInstruction* instruction) - : inputs(instruction->GetBlock()->GetGraph()->GetArena(), instruction->InputCount()), - temps(instruction->GetBlock()->GetGraph()->GetArena(), 0) { - inputs.SetSize(instruction->InputCount()); + : inputs_(instruction->GetBlock()->GetGraph()->GetArena(), instruction->InputCount()), + temps_(instruction->GetBlock()->GetGraph()->GetArena(), 0) { + inputs_.SetSize(instruction->InputCount()); for (size_t i = 0; i < instruction->InputCount(); i++) { - inputs.Put(i, Location()); + inputs_.Put(i, Location()); } } void SetInAt(uint32_t at, Location location) { - inputs.Put(at, location); + inputs_.Put(at, location); } Location InAt(uint32_t at) const { - return inputs.Get(at); + return inputs_.Get(at); + } + + size_t GetInputCount() const { + return inputs_.Size(); } void SetOut(Location location) { - output = Location(location); + output_ = Location(location); } void AddTemp(Location location) { - temps.Add(location); + temps_.Add(location); } Location GetTemp(uint32_t at) const { - return temps.Get(at); + return temps_.Get(at); + } + + void SetTempAt(uint32_t at, Location location) { + temps_.Put(at, location); } - Location Out() const { return output; } + size_t GetTempCount() const { + return temps_.Size(); + } + + Location Out() const { return output_; } private: - GrowableArray inputs; - GrowableArray temps; - Location output; + GrowableArray inputs_; + GrowableArray temps_; + Location output_; DISALLOW_COPY_AND_ASSIGN(LocationSummary); }; @@ -286,15 +347,33 @@ class CodeGenerator : public ArenaObject { std::vector* vector, const DexCompilationUnit& dex_compilation_unit) const; protected: - explicit CodeGenerator(HGraph* graph) + CodeGenerator(HGraph* graph, size_t number_of_registers) : frame_size_(0), graph_(graph), block_labels_(graph->GetArena(), 0), - pc_infos_(graph->GetArena(), 32) { + pc_infos_(graph->GetArena(), 32), + blocked_registers_(static_cast( + graph->GetArena()->Alloc(number_of_registers * sizeof(bool), kArenaAllocData))) { block_labels_.SetSize(graph->GetBlocks()->Size()); } ~CodeGenerator() { } + // Register allocation logic. + void AllocateRegistersLocally(HInstruction* instruction) const; + + // Backend specific implementation for allocating a register. + virtual ManagedRegister AllocateFreeRegister(Primitive::Type type, + bool* blocked_registers) const = 0; + + // Raw implementation of allocating a register: loops over blocked_registers to find + // the first available register. + size_t AllocateFreeRegisterInternal(bool* blocked_registers, size_t number_of_registers) const; + + virtual void SetupBlockedRegisters(bool* blocked_registers) const = 0; + virtual size_t GetNumberOfRegisters() const = 0; + + virtual Location GetStackLocation(HLoadLocal* load) const = 0; + // Frame size required for this method. uint32_t frame_size_; uint32_t core_spill_mask_; @@ -309,6 +388,9 @@ class CodeGenerator : public ArenaObject { GrowableArray