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 42namespace llvm { 43 44class LiveInterval; 45class LiveIntervals; 46class LiveRegMatrix; 47class MachineInstr; 48class MachineRegisterInfo; 49template<typename T> class SmallVectorImpl; 50class Spiller; 51class TargetRegisterInfo; 52class 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. 60class RegAllocBase { 61 virtual void anchor(); 62 63protected: 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 114public: 115 /// VerifyEnabled - True when -verify-regalloc is given. 116 static bool VerifyEnabled; 117 118private: 119 void seedLiveRegs(); 120}; 121 122} // end namespace llvm 123 124#endif // LLVM_LIB_CODEGEN_REGALLOCBASE_H 125