diff options
author | Nicolas Geoffray <ngeoffray@google.com> | 2014-05-22 12:50:17 +0100 |
---|---|---|
committer | Nicolas Geoffray <ngeoffray@google.com> | 2014-05-26 11:31:38 +0100 |
commit | a7062e05e6048c7f817d784a5b94e3122e25b1ec (patch) | |
tree | a5d6b64ae6d5352f761fc2547bda863281adbe40 /compiler/optimizing/register_allocator.h | |
parent | 8b5b1e5593ffa77c393e4172b71a3d5a821d2ed8 (diff) | |
download | art-a7062e05e6048c7f817d784a5b94e3122e25b1ec.zip art-a7062e05e6048c7f817d784a5b94e3122e25b1ec.tar.gz art-a7062e05e6048c7f817d784a5b94e3122e25b1ec.tar.bz2 |
Add a linear scan register allocator to the optimizing compiler.
This is a "by-the-book" implementation. It currently only deals
with allocating registers, with no hint optimizations.
The changes remaining to make it functional are:
- Allocate spill slots.
- Resolution and placements of Move instructions.
- Connect it to the code generator.
Change-Id: Ie0b2f6ba1b98da85425be721ce4afecd6b4012a4
Diffstat (limited to 'compiler/optimizing/register_allocator.h')
-rw-r--r-- | compiler/optimizing/register_allocator.h | 119 |
1 files changed, 119 insertions, 0 deletions
diff --git a/compiler/optimizing/register_allocator.h b/compiler/optimizing/register_allocator.h new file mode 100644 index 0000000..e575b96 --- /dev/null +++ b/compiler/optimizing/register_allocator.h @@ -0,0 +1,119 @@ +/* + * 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. + */ + +#ifndef ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ +#define ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ + +#include "base/macros.h" +#include "utils/growable_array.h" + +namespace art { + +class CodeGenerator; +class LiveInterval; +class SsaLivenessAnalysis; + +/** + * An implementation of a linear scan register allocator on an `HGraph` with SSA form. + */ +class RegisterAllocator { + public: + RegisterAllocator(ArenaAllocator* allocator, const CodeGenerator& codegen); + + // Main entry point for the register allocator. Given the liveness analysis, + // allocates registers to live intervals. + void AllocateRegisters(const SsaLivenessAnalysis& liveness) { + processing_core_registers_ = true; + AllocateRegistersInternal(liveness); + processing_core_registers_ = false; + AllocateRegistersInternal(liveness); + } + + // Validate that the register allocator did not allocate the same register to + // intervals that intersect each other. Returns false if it did not. + bool Validate(const SsaLivenessAnalysis& liveness, bool log_fatal_on_failure) { + processing_core_registers_ = true; + if (!ValidateInternal(liveness, log_fatal_on_failure)) { + return false; + } + processing_core_registers_ = false; + return ValidateInternal(liveness, log_fatal_on_failure); + } + + // Helper method for validation. Used by unit testing. + static bool ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, + const CodeGenerator& codegen, + ArenaAllocator* allocator, + bool processing_core_registers, + bool log_fatal_on_failure); + + private: + // Main methods of the allocator. + void LinearScan(); + bool TryAllocateFreeReg(LiveInterval* interval); + bool AllocateBlockedReg(LiveInterval* interval); + + // Add `interval` in the sorted list of unhandled intervals. + void AddToUnhandled(LiveInterval* interval); + + // Split `interval` at the position `at`. The new interval starts at `at`. + LiveInterval* Split(LiveInterval* interval, size_t at); + + // Returns whether `reg` is blocked by the code generator. + bool IsBlocked(int reg) const; + + // Helper methods. + void AllocateRegistersInternal(const SsaLivenessAnalysis& liveness); + bool ValidateInternal(const SsaLivenessAnalysis& liveness, bool log_fatal_on_failure) const; + void DumpInterval(std::ostream& stream, LiveInterval* interval); + + ArenaAllocator* const allocator_; + const CodeGenerator& codegen_; + + // List of intervals that must be processed, ordered by start position. Last entry + // is the interval that has the lowest start position. + GrowableArray<LiveInterval*> unhandled_; + + // List of intervals that have been processed. + GrowableArray<LiveInterval*> handled_; + + // List of intervals that are currently active when processing a new live interval. + // That is, they have a live range that spans the start of the new interval. + GrowableArray<LiveInterval*> active_; + + // List of intervals that are currently inactive when processing a new live interval. + // That is, they have a lifetime hole that spans the start of the new interval. + GrowableArray<LiveInterval*> inactive_; + + // True if processing core registers. False if processing floating + // point registers. + bool processing_core_registers_; + + // Number of registers for the current register kind (core or floating point). + size_t number_of_registers_; + + // Temporary array, allocated ahead of time for simplicity. + size_t* registers_array_; + + // Blocked registers, as decided by the code generator. + bool* const blocked_registers_; + + DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ |