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/array_ref.h" 22 #include "base/arena_object.h" 23 #include "base/macros.h" 24 25 namespace art HIDDEN { 26 27 class CodeGenerator; 28 class HBasicBlock; 29 class HGraph; 30 class HInstruction; 31 class HParallelMove; 32 class LiveInterval; 33 class Location; 34 class SsaLivenessAnalysis; 35 36 /** 37 * Base class for any register allocator. 38 */ 39 class RegisterAllocator : public DeletableArenaObject<kArenaAllocRegisterAllocator> { 40 public: 41 enum class RegisterType { 42 kCoreRegister, 43 kFpRegister 44 }; 45 46 static std::unique_ptr<RegisterAllocator> Create(ScopedArenaAllocator* allocator, 47 CodeGenerator* codegen, 48 const SsaLivenessAnalysis& analysis); 49 50 virtual ~RegisterAllocator(); 51 52 // Main entry point for the register allocator. Given the liveness analysis, 53 // allocates registers to live intervals. 54 virtual void AllocateRegisters() = 0; 55 56 // Validate that the register allocator did not allocate the same register to 57 // intervals that intersect each other. Returns false if it failed. 58 virtual bool Validate(bool log_fatal_on_failure) = 0; 59 60 // Verifies that live intervals do not conflict. Used by unit testing. 61 static bool ValidateIntervals(ArrayRef<LiveInterval* const> intervals, 62 size_t number_of_spill_slots, 63 size_t number_of_out_slots, 64 const CodeGenerator& codegen, 65 const SsaLivenessAnalysis* liveness, // Can be null in tests. 66 RegisterType register_type, 67 bool log_fatal_on_failure); 68 69 static constexpr const char* kRegisterAllocatorPassName = "register"; 70 71 protected: 72 RegisterAllocator(ScopedArenaAllocator* allocator, 73 CodeGenerator* codegen, 74 const SsaLivenessAnalysis& analysis); 75 76 // Split `interval` at the position `position`. The new interval starts at `position`. 77 // If `position` is at the start of `interval`, returns `interval` with its 78 // register location(s) cleared. 79 static LiveInterval* Split(LiveInterval* interval, size_t position); 80 81 // Split `interval` at a position between `from` and `to`. The method will try 82 // to find an optimal split position. 83 LiveInterval* SplitBetween(LiveInterval* interval, size_t from, size_t to); 84 85 // Helper for calling the right typed codegen function for dumping a register. DumpRegister(std::ostream & stream,int reg,RegisterType register_type)86 void DumpRegister(std::ostream& stream, int reg, RegisterType register_type) const { 87 DumpRegister(stream, reg, register_type, codegen_); 88 } 89 static void DumpRegister( 90 std::ostream& stream, int reg, RegisterType register_type, const CodeGenerator* codegen); 91 92 // Get a mask of all registers for an interval. 93 // Most intervals either have or do not have a register, but we're using special fixed 94 // intervals with type `Void` to mark large sets of blocked registers for calls, catch 95 // blocks and irreducible loop headers to save memory and improve performance. 96 uint32_t GetRegisterMask(LiveInterval* interval, RegisterType register_type) const; 97 98 ScopedArenaAllocator* const allocator_; 99 CodeGenerator* const codegen_; 100 const SsaLivenessAnalysis& liveness_; 101 102 // Cached values calculated from codegen data. 103 const size_t num_core_registers_; 104 const size_t num_fp_registers_; 105 const uint32_t core_registers_blocked_for_call_; 106 const uint32_t fp_registers_blocked_for_call_; 107 }; 108 109 } // namespace art 110 111 #endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ 112