1 //===- RegAllocBase.h - basic regalloc interface and driver -----*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the RegAllocBase class, which is the skeleton of a basic 10 // register allocation algorithm and interface for extending it. It provides the 11 // building blocks on which to construct other experimental allocators and test 12 // the validity of two principles: 13 // 14 // - If virtual and physical register liveness is modeled using intervals, then 15 // on-the-fly interference checking is cheap. Furthermore, interferences can be 16 // lazily cached and reused. 17 // 18 // - Register allocation complexity, and generated code performance is 19 // determined by the effectiveness of live range splitting rather than optimal 20 // coloring. 21 // 22 // Following the first principle, interfering checking revolves around the 23 // LiveIntervalUnion data structure. 24 // 25 // To fulfill the second principle, the basic allocator provides a driver for 26 // incremental splitting. It essentially punts on the problem of register 27 // coloring, instead driving the assignment of virtual to physical registers by 28 // the cost of splitting. The basic allocator allows for heuristic reassignment 29 // of registers, if a more sophisticated allocator chooses to do that. 30 // 31 // This framework provides a way to engineer the compile time vs. code 32 // quality trade-off without relying on a particular theoretical solver. 33 // 34 //===----------------------------------------------------------------------===// 35 36 #ifndef LLVM_LIB_CODEGEN_REGALLOCBASE_H 37 #define LLVM_LIB_CODEGEN_REGALLOCBASE_H 38 39 #include "llvm/ADT/SmallPtrSet.h" 40 #include "llvm/CodeGen/RegAllocCommon.h" 41 #include "llvm/CodeGen/RegisterClassInfo.h" 42 43 namespace llvm { 44 45 class LiveInterval; 46 class LiveIntervals; 47 class LiveRegMatrix; 48 class MachineInstr; 49 class MachineRegisterInfo; 50 template<typename T> class SmallVectorImpl; 51 class Spiller; 52 class TargetRegisterInfo; 53 class VirtRegMap; 54 55 /// RegAllocBase provides the register allocation driver and interface that can 56 /// be extended to add interesting heuristics. 57 /// 58 /// Register allocators must override the selectOrSplit() method to implement 59 /// live range splitting. They must also override enqueue/dequeue to provide an 60 /// assignment order. 61 class RegAllocBase { 62 virtual void anchor(); 63 64 protected: 65 const TargetRegisterInfo *TRI = nullptr; 66 MachineRegisterInfo *MRI = nullptr; 67 VirtRegMap *VRM = nullptr; 68 LiveIntervals *LIS = nullptr; 69 LiveRegMatrix *Matrix = nullptr; 70 RegisterClassInfo RegClassInfo; 71 const RegClassFilterFunc ShouldAllocateClass; 72 73 /// Inst which is a def of an original reg and whose defs are already all 74 /// dead after remat is saved in DeadRemats. The deletion of such inst is 75 /// postponed till all the allocations are done, so its remat expr is 76 /// always available for the remat of all the siblings of the original reg. 77 SmallPtrSet<MachineInstr *, 32> DeadRemats; 78 79 RegAllocBase(const RegClassFilterFunc F = allocateAllRegClasses) : 80 ShouldAllocateClass(F) {} 81 82 virtual ~RegAllocBase() = default; 83 84 // A RegAlloc pass should call this before allocatePhysRegs. 85 void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat); 86 87 // The top-level driver. The output is a VirtRegMap that us updated with 88 // physical register assignments. 89 void allocatePhysRegs(); 90 91 // Include spiller post optimization and removing dead defs left because of 92 // rematerialization. 93 virtual void postOptimization(); 94 95 // Get a temporary reference to a Spiller instance. 96 virtual Spiller &spiller() = 0; 97 98 /// enqueue - Add VirtReg to the priority queue of unassigned registers. 99 virtual void enqueueImpl(LiveInterval *LI) = 0; 100 101 /// enqueue - Add VirtReg to the priority queue of unassigned registers. 102 void enqueue(LiveInterval *LI); 103 104 /// dequeue - Return the next unassigned register, or NULL. 105 virtual LiveInterval *dequeue() = 0; 106 107 // A RegAlloc pass should override this to provide the allocation heuristics. 108 // Each call must guarantee forward progess by returning an available PhysReg 109 // or new set of split live virtual registers. It is up to the splitter to 110 // converge quickly toward fully spilled live ranges. 111 virtual MCRegister selectOrSplit(LiveInterval &VirtReg, 112 SmallVectorImpl<Register> &splitLVRs) = 0; 113 114 // Use this group name for NamedRegionTimer. 115 static const char TimerGroupName[]; 116 static const char TimerGroupDescription[]; 117 118 /// Method called when the allocator is about to remove a LiveInterval. 119 virtual void aboutToRemoveInterval(LiveInterval &LI) {} 120 121 public: 122 /// VerifyEnabled - True when -verify-regalloc is given. 123 static bool VerifyEnabled; 124 125 private: 126 void seedLiveRegs(); 127 }; 128 129 } // end namespace llvm 130 131 #endif // LLVM_LIB_CODEGEN_REGALLOCBASE_H 132