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