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/RegisterClassInfo.h" 41 42 namespace llvm { 43 44 class LiveInterval; 45 class LiveIntervals; 46 class LiveRegMatrix; 47 class MachineInstr; 48 class MachineRegisterInfo; 49 template<typename T> class SmallVectorImpl; 50 class Spiller; 51 class TargetRegisterInfo; 52 class VirtRegMap; 53 54 /// RegAllocBase provides the register allocation driver and interface that can 55 /// be extended to add interesting heuristics. 56 /// 57 /// Register allocators must override the selectOrSplit() method to implement 58 /// live range splitting. They must also override enqueue/dequeue to provide an 59 /// assignment order. 60 class RegAllocBase { 61 virtual void anchor(); 62 63 protected: 64 const TargetRegisterInfo *TRI = nullptr; 65 MachineRegisterInfo *MRI = nullptr; 66 VirtRegMap *VRM = nullptr; 67 LiveIntervals *LIS = nullptr; 68 LiveRegMatrix *Matrix = nullptr; 69 RegisterClassInfo RegClassInfo; 70 71 /// Inst which is a def of an original reg and whose defs are already all 72 /// dead after remat is saved in DeadRemats. The deletion of such inst is 73 /// postponed till all the allocations are done, so its remat expr is 74 /// always available for the remat of all the siblings of the original reg. 75 SmallPtrSet<MachineInstr *, 32> DeadRemats; 76 77 RegAllocBase() = default; 78 virtual ~RegAllocBase() = default; 79 80 // A RegAlloc pass should call this before allocatePhysRegs. 81 void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat); 82 83 // The top-level driver. The output is a VirtRegMap that us updated with 84 // physical register assignments. 85 void allocatePhysRegs(); 86 87 // Include spiller post optimization and removing dead defs left because of 88 // rematerialization. 89 virtual void postOptimization(); 90 91 // Get a temporary reference to a Spiller instance. 92 virtual Spiller &spiller() = 0; 93 94 /// enqueue - Add VirtReg to the priority queue of unassigned registers. 95 virtual void enqueue(LiveInterval *LI) = 0; 96 97 /// dequeue - Return the next unassigned register, or NULL. 98 virtual LiveInterval *dequeue() = 0; 99 100 // A RegAlloc pass should override this to provide the allocation heuristics. 101 // Each call must guarantee forward progess by returning an available PhysReg 102 // or new set of split live virtual registers. It is up to the splitter to 103 // converge quickly toward fully spilled live ranges. 104 virtual Register selectOrSplit(LiveInterval &VirtReg, 105 SmallVectorImpl<Register> &splitLVRs) = 0; 106 107 // Use this group name for NamedRegionTimer. 108 static const char TimerGroupName[]; 109 static const char TimerGroupDescription[]; 110 111 /// Method called when the allocator is about to remove a LiveInterval. 112 virtual void aboutToRemoveInterval(LiveInterval &LI) {} 113 114 public: 115 /// VerifyEnabled - True when -verify-regalloc is given. 116 static bool VerifyEnabled; 117 118 private: 119 void seedLiveRegs(); 120 }; 121 122 } // end namespace llvm 123 124 #endif // LLVM_LIB_CODEGEN_REGALLOCBASE_H 125