1 /* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ 18 #define ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ 19 20 #include "arch/instruction_set.h" 21 #include "base/arena_containers.h" 22 #include "base/arena_object.h" 23 #include "base/macros.h" 24 #include "primitive.h" 25 26 namespace art { 27 28 class CodeGenerator; 29 class HBasicBlock; 30 class HGraph; 31 class HInstruction; 32 class HParallelMove; 33 class LiveInterval; 34 class Location; 35 class SsaLivenessAnalysis; 36 37 /** 38 * Base class for any register allocator. 39 */ 40 class RegisterAllocator : public ArenaObject<kArenaAllocRegisterAllocator> { 41 public: 42 enum Strategy { 43 kRegisterAllocatorLinearScan, 44 kRegisterAllocatorGraphColor 45 }; 46 47 static constexpr Strategy kRegisterAllocatorDefault = kRegisterAllocatorLinearScan; 48 49 static RegisterAllocator* Create(ArenaAllocator* allocator, 50 CodeGenerator* codegen, 51 const SsaLivenessAnalysis& analysis, 52 Strategy strategy = kRegisterAllocatorDefault); 53 54 virtual ~RegisterAllocator() = default; 55 56 // Main entry point for the register allocator. Given the liveness analysis, 57 // allocates registers to live intervals. 58 virtual void AllocateRegisters() = 0; 59 60 // Validate that the register allocator did not allocate the same register to 61 // intervals that intersect each other. Returns false if it failed. 62 virtual bool Validate(bool log_fatal_on_failure) = 0; 63 64 static bool CanAllocateRegistersFor(const HGraph& graph, 65 InstructionSet instruction_set); 66 67 // Verifies that live intervals do not conflict. Used by unit testing. 68 static bool ValidateIntervals(const ArenaVector<LiveInterval*>& intervals, 69 size_t number_of_spill_slots, 70 size_t number_of_out_slots, 71 const CodeGenerator& codegen, 72 ArenaAllocator* allocator, 73 bool processing_core_registers, 74 bool log_fatal_on_failure); 75 76 static constexpr const char* kRegisterAllocatorPassName = "register"; 77 78 protected: 79 RegisterAllocator(ArenaAllocator* allocator, 80 CodeGenerator* codegen, 81 const SsaLivenessAnalysis& analysis); 82 83 // Split `interval` at the position `position`. The new interval starts at `position`. 84 // If `position` is at the start of `interval`, returns `interval` with its 85 // register location(s) cleared. 86 static LiveInterval* Split(LiveInterval* interval, size_t position); 87 88 // Split `interval` at a position between `from` and `to`. The method will try 89 // to find an optimal split position. 90 LiveInterval* SplitBetween(LiveInterval* interval, size_t from, size_t to); 91 92 ArenaAllocator* const allocator_; 93 CodeGenerator* const codegen_; 94 const SsaLivenessAnalysis& liveness_; 95 }; 96 97 } // namespace art 98 99 #endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ 100