1 /* 2 * Copyright (c) 2021-2024 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 "optimizer/optimizations/regalloc/working_ranges.h" 25 #include "reg_map.h" 26 #include "utils/arena_containers.h" 27 #include "utils/small_vector.h" 28 29 namespace ark::compiler { 30 class RegAllocGraphColoring : public RegAllocBase { 31 public: 32 explicit RegAllocGraphColoring(Graph *graph); 33 PANDA_PUBLIC_API RegAllocGraphColoring(Graph *graph, size_t regsCount); 34 PANDA_PUBLIC_API RegAllocGraphColoring(Graph *graph, LocationMask mask); 35 GetPassName()36 const char *GetPassName() const override 37 { 38 return "RegAllocGraphColoring"; 39 } 40 AbortIfFailed()41 bool AbortIfFailed() const override 42 { 43 return true; 44 } 45 46 static const size_t DEFAULT_VECTOR_SIZE = 64; 47 using IndexVector = SmallVector<unsigned, DEFAULT_VECTOR_SIZE>; 48 using IndexVectorPair = std::pair<IndexVector, IndexVector>; 49 50 protected: 51 bool Allocate() override; 52 53 private: 54 void InitWorkingRanges(WorkingRanges *generalRanges, WorkingRanges *fpRanges); 55 void FillPhysicalNodes(InterferenceGraph *ig, WorkingRanges *ranges, ArenaVector<ColorNode *> &physicalNodes); 56 void BuildIG(InterferenceGraph *ig, WorkingRanges *ranges, bool rematConstants = false); 57 IndexVector PrecolorIG(InterferenceGraph *ig); 58 IndexVector PrecolorIG(InterferenceGraph *ig, const RegisterMap &map); 59 void BuildBias(InterferenceGraph *ig, const IndexVector &affinityNodes); 60 void WalkNodes(IndexVectorPair &&vectors, NodeVector &nodes, ColorNode node, InterferenceGraph *ig, 61 const IndexVector &affinityNodes); 62 void AddAffinityEdgesToPhi(InterferenceGraph *ig, const ColorNode &node, IndexVector *affinityNodes); 63 void AddAffinityEdgesToSiblings(InterferenceGraph *ig, const ColorNode &node, IndexVector *affinityNodes); 64 void AddAffinityEdgesToPhysicalNodes(InterferenceGraph *ig, IndexVector *affinityNodes); 65 void AddAffinityEdge(InterferenceGraph *ig, IndexVector *affinityNodes, const ColorNode &node, LifeIntervals *li); 66 bool AllocateRegisters(InterferenceGraph *ig, WorkingRanges *ranges, WorkingRanges *stackRanges, 67 const RegisterMap &map); 68 bool AllocateSlots(InterferenceGraph *ig, WorkingRanges *stackRanges); 69 void Remap(const InterferenceGraph &ig, const RegisterMap &map); 70 bool MapSlots(const InterferenceGraph &ig); 71 void InitMap(RegisterMap *map, bool isVector); 72 void Presplit(WorkingRanges *ranges); 73 void SparseIG(InterferenceGraph *ig, unsigned regsCount, WorkingRanges *ranges, WorkingRanges *stackRanges); 74 void SpillInterval(LifeIntervals *interval, WorkingRanges *ranges, WorkingRanges *stackRanges); 75 }; 76 } // namespace ark::compiler 77 78 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_REG_ALLOC_GRAPH_COLORING_H 79