Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 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" |
Vladimir Marko | e764d2e | 2017-10-05 14:35:55 +0100 | [diff] [blame] | 21 | #include "base/array_ref.h" |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 22 | #include "base/arena_object.h" |
| 23 | #include "base/macros.h" |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 24 | |
| 25 | namespace art { |
| 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 | */ |
Vladimir Marko | e764d2e | 2017-10-05 14:35:55 +0100 | [diff] [blame] | 39 | class RegisterAllocator : public DeletableArenaObject<kArenaAllocRegisterAllocator> { |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 40 | public: |
| 41 | enum Strategy { |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 42 | kRegisterAllocatorLinearScan, |
| 43 | kRegisterAllocatorGraphColor |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 44 | }; |
| 45 | |
| 46 | static constexpr Strategy kRegisterAllocatorDefault = kRegisterAllocatorLinearScan; |
| 47 | |
Vladimir Marko | e764d2e | 2017-10-05 14:35:55 +0100 | [diff] [blame] | 48 | static std::unique_ptr<RegisterAllocator> Create(ScopedArenaAllocator* allocator, |
| 49 | CodeGenerator* codegen, |
| 50 | const SsaLivenessAnalysis& analysis, |
| 51 | Strategy strategy = kRegisterAllocatorDefault); |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 52 | |
Vladimir Marko | bea75ff | 2017-10-11 20:39:54 +0100 | [diff] [blame] | 53 | virtual ~RegisterAllocator(); |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 54 | |
| 55 | // Main entry point for the register allocator. Given the liveness analysis, |
| 56 | // allocates registers to live intervals. |
| 57 | virtual void AllocateRegisters() = 0; |
| 58 | |
| 59 | // Validate that the register allocator did not allocate the same register to |
| 60 | // intervals that intersect each other. Returns false if it failed. |
| 61 | virtual bool Validate(bool log_fatal_on_failure) = 0; |
| 62 | |
| 63 | static bool CanAllocateRegistersFor(const HGraph& graph, |
| 64 | InstructionSet instruction_set); |
| 65 | |
| 66 | // Verifies that live intervals do not conflict. Used by unit testing. |
Vladimir Marko | e764d2e | 2017-10-05 14:35:55 +0100 | [diff] [blame] | 67 | static bool ValidateIntervals(ArrayRef<LiveInterval* const> intervals, |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 68 | size_t number_of_spill_slots, |
| 69 | size_t number_of_out_slots, |
| 70 | const CodeGenerator& codegen, |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 71 | bool processing_core_registers, |
| 72 | bool log_fatal_on_failure); |
| 73 | |
| 74 | static constexpr const char* kRegisterAllocatorPassName = "register"; |
| 75 | |
| 76 | protected: |
Vladimir Marko | e764d2e | 2017-10-05 14:35:55 +0100 | [diff] [blame] | 77 | RegisterAllocator(ScopedArenaAllocator* allocator, |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 78 | CodeGenerator* codegen, |
| 79 | const SsaLivenessAnalysis& analysis); |
| 80 | |
| 81 | // Split `interval` at the position `position`. The new interval starts at `position`. |
| 82 | // If `position` is at the start of `interval`, returns `interval` with its |
| 83 | // register location(s) cleared. |
| 84 | static LiveInterval* Split(LiveInterval* interval, size_t position); |
| 85 | |
| 86 | // Split `interval` at a position between `from` and `to`. The method will try |
| 87 | // to find an optimal split position. |
| 88 | LiveInterval* SplitBetween(LiveInterval* interval, size_t from, size_t to); |
| 89 | |
Vladimir Marko | 69d310e | 2017-10-09 14:12:23 +0100 | [diff] [blame] | 90 | ScopedArenaAllocator* const allocator_; |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 91 | CodeGenerator* const codegen_; |
| 92 | const SsaLivenessAnalysis& liveness_; |
| 93 | }; |
| 94 | |
| 95 | } // namespace art |
| 96 | |
| 97 | #endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ |