1a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray/* 2a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 3a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * 4a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 5a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * you may not use this file except in compliance with the License. 6a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * You may obtain a copy of the License at 7a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * 8a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 9a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * 10a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * Unless required by applicable law or agreed to in writing, software 11a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 12a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * See the License for the specific language governing permissions and 14a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * limitations under the License. 15a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray */ 16a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 17a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#ifndef ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ 18a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#define ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ 19a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 20a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "base/macros.h" 21e63db27db913f1a88e2095a1ee8239b2bb9124e8Ian Rogers#include "primitive.h" 22a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "utils/growable_array.h" 23a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 24a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraynamespace art { 25a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 26a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayclass CodeGenerator; 2786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayclass HBasicBlock; 2886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayclass HGraph; 2986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayclass HInstruction; 3086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayclass HParallelMove; 31a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayclass LiveInterval; 3286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayclass Location; 33a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayclass SsaLivenessAnalysis; 34a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 35a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray/** 36a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * An implementation of a linear scan register allocator on an `HGraph` with SSA form. 37a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray */ 38a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayclass RegisterAllocator { 39a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray public: 4086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray RegisterAllocator(ArenaAllocator* allocator, 4186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray CodeGenerator* codegen, 4286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray const SsaLivenessAnalysis& analysis); 43a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 44a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Main entry point for the register allocator. Given the liveness analysis, 45a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // allocates registers to live intervals. 4686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void AllocateRegisters(); 47a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 48a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Validate that the register allocator did not allocate the same register to 49a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // intervals that intersect each other. Returns false if it did not. 5086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray bool Validate(bool log_fatal_on_failure) { 51a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray processing_core_registers_ = true; 5286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!ValidateInternal(log_fatal_on_failure)) { 53a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 54a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 55a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray processing_core_registers_ = false; 5686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return ValidateInternal(log_fatal_on_failure); 57a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 58a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 59a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Helper method for validation. Used by unit testing. 60a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray static bool ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, 6131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t number_of_spill_slots, 62a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray const CodeGenerator& codegen, 63a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ArenaAllocator* allocator, 64a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool processing_core_registers, 65a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool log_fatal_on_failure); 66a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 6786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray static bool CanAllocateRegistersFor(const HGraph& graph, InstructionSet instruction_set); 6886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray static bool Supports(InstructionSet instruction_set) { 6993bedb7a96c8e6f9b6caa66689bf4f3c520bc234Nicolas Geoffray return instruction_set == kX86 7093bedb7a96c8e6f9b6caa66689bf4f3c520bc234Nicolas Geoffray || instruction_set == kArm 7193bedb7a96c8e6f9b6caa66689bf4f3c520bc234Nicolas Geoffray || instruction_set == kX86_64 7293bedb7a96c8e6f9b6caa66689bf4f3c520bc234Nicolas Geoffray || instruction_set == kThumb2; 7386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 7486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 7586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t GetNumberOfSpillSlots() const { 7686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return spill_slots_.Size(); 7786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 7886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 79a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray private: 80a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Main methods of the allocator. 81a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray void LinearScan(); 82a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool TryAllocateFreeReg(LiveInterval* interval); 83a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool AllocateBlockedReg(LiveInterval* interval); 8486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void Resolve(); 85a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 86a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Add `interval` in the sorted list of unhandled intervals. 87a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray void AddToUnhandled(LiveInterval* interval); 88a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 89a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Split `interval` at the position `at`. The new interval starts at `at`. 90a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* Split(LiveInterval* interval, size_t at); 91a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 92a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Returns whether `reg` is blocked by the code generator. 93a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool IsBlocked(int reg) const; 94a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 9586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Update the interval for the register in `location` to cover [start, end). 9686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void BlockRegister(Location location, size_t start, size_t end, Primitive::Type type); 9786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 9831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // Allocate a spill slot for the given interval. 9931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray void AllocateSpillSlotFor(LiveInterval* interval); 100412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray void AllocateOneSpillSlot(LiveInterval* interval, size_t end); 101412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray void AllocateTwoSpillSlots(LiveInterval* interval, size_t end); 10231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 10386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Connect adjacent siblings within blocks. 10486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void ConnectSiblings(LiveInterval* interval); 10586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 10686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Connect siblings between block entries and exits. 10786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void ConnectSplitSiblings(LiveInterval* interval, HBasicBlock* from, HBasicBlock* to) const; 10886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 10986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Helper methods to insert parallel moves in the graph. 11086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void InsertParallelMoveAtExitOf(HBasicBlock* block, Location source, Location destination) const; 11186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void InsertParallelMoveAtEntryOf(HBasicBlock* block, Location source, Location destination) const; 11286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void InsertMoveAfter(HInstruction* instruction, Location source, Location destination) const; 11386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void AddInputMoveFor(HInstruction* instruction, Location source, Location destination) const; 11486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void InsertParallelMoveAt(size_t position, Location source, Location destination) const; 11586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 116a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Helper methods. 11786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void AllocateRegistersInternal(); 11886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray bool ValidateInternal(bool log_fatal_on_failure) const; 11986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray void DumpInterval(std::ostream& stream, LiveInterval* interval) const; 120a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 121a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ArenaAllocator* const allocator_; 12286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray CodeGenerator* const codegen_; 12386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray const SsaLivenessAnalysis& liveness_; 124a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 125a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // List of intervals that must be processed, ordered by start position. Last entry 126a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // is the interval that has the lowest start position. 127a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray GrowableArray<LiveInterval*> unhandled_; 128a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 129a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // List of intervals that have been processed. 130a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray GrowableArray<LiveInterval*> handled_; 131a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 132a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // List of intervals that are currently active when processing a new live interval. 133a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // That is, they have a live range that spans the start of the new interval. 134a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray GrowableArray<LiveInterval*> active_; 135a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 136a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // List of intervals that are currently inactive when processing a new live interval. 137a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // That is, they have a lifetime hole that spans the start of the new interval. 138a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray GrowableArray<LiveInterval*> inactive_; 139a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 14086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Fixed intervals for physical registers. Such an interval covers the positions 14186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // where an instruction requires a specific register. 14286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray GrowableArray<LiveInterval*> physical_register_intervals_; 14386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 14431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // The spill slots allocated for live intervals. 14531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray GrowableArray<size_t> spill_slots_; 14631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 147a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // True if processing core registers. False if processing floating 148a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // point registers. 149a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool processing_core_registers_; 150a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 151a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Number of registers for the current register kind (core or floating point). 152a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t number_of_registers_; 153a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 154a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Temporary array, allocated ahead of time for simplicity. 155a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* registers_array_; 156a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 157a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Blocked registers, as decided by the code generator. 158a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool* const blocked_registers_; 159a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 160a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); 161a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray}; 162a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 163a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} // namespace art 164a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 165a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ 166