Home | History | Annotate | Download | only in optimizing 
      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