1 /** 2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef COMPILER_OPTIMIZER_OPTIMIZATIONS_REG_ALLOC_GRAPH_COLORING_H 17 #define COMPILER_OPTIMIZER_OPTIMIZATIONS_REG_ALLOC_GRAPH_COLORING_H 18 19 #include "reg_alloc_base.h" 20 #include "compiler_logger.h" 21 #include "interference_graph.h" 22 #include "optimizer/analysis/liveness_analyzer.h" 23 #include "optimizer/code_generator/registers_description.h" 24 #include "reg_map.h" 25 #include "utils/arena_containers.h" 26 #include "utils/small_vector.h" 27 28 namespace panda::compiler { 29 using InstructionsRanges = ArenaDeque<LifeIntervals *>; 30 31 class RegAllocGraphColoring : public RegAllocBase { 32 struct WorkingRanges { WorkingRangesWorkingRanges33 explicit WorkingRanges(ArenaAllocator *allocator) 34 : regular(allocator->Adapter()), physical(allocator->Adapter()) 35 { 36 } 37 38 InstructionsRanges regular; // NOLINT(misc-non-private-member-variables-in-classes) 39 InstructionsRanges physical; // NOLINT(misc-non-private-member-variables-in-classes) 40 }; 41 42 public: 43 explicit RegAllocGraphColoring(Graph *graph); 44 RegAllocGraphColoring(Graph *graph, size_t regs_count); 45 GetPassName()46 const char *GetPassName() const override 47 { 48 return "RegAllocGraphColoring"; 49 } 50 AbortIfFailed()51 bool AbortIfFailed() const override 52 { 53 return true; 54 } 55 56 static const size_t DEFAULT_VECTOR_SIZE = 64; 57 using IndexVector = SmallVector<unsigned, DEFAULT_VECTOR_SIZE>; 58 59 protected: 60 bool Allocate() override; 61 62 private: 63 void InitWorkingRanges(WorkingRanges *general_ranges, WorkingRanges *fp_ranges); 64 void BuildIG(InterferenceGraph *ig, WorkingRanges *ranges); 65 IndexVector PrecolorIG(InterferenceGraph *ig, const RegisterMap &map); 66 void BuildBias(InterferenceGraph *ig, const IndexVector &affinity_nodes); 67 void AddAffinityEdges(InterferenceGraph *ig, ColorNode *node, IndexVector *affinity_nodes); 68 void AddAffinityEdgeToSibling(InterferenceGraph *ig, ColorNode *node, IndexVector *affinity_nodes); 69 Register AllocateRegisters(InterferenceGraph *ig, WorkingRanges *ranges, const RegisterMap &map); 70 void Remap(const InterferenceGraph &ig, const RegisterMap &map); 71 void InitMap(RegisterMap *map, bool is_vector); 72 void Presplit(WorkingRanges *ranges); 73 }; 74 } // namespace panda::compiler 75 76 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_REG_ALLOC_GRAPH_COLORING_H