1327952Sdim//===- RegAllocBase.h - basic regalloc interface and driver -----*- C++ -*-===// 2218885Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6218885Sdim// 7218885Sdim//===----------------------------------------------------------------------===// 8218885Sdim// 9218885Sdim// This file defines the RegAllocBase class, which is the skeleton of a basic 10218885Sdim// register allocation algorithm and interface for extending it. It provides the 11218885Sdim// building blocks on which to construct other experimental allocators and test 12218885Sdim// the validity of two principles: 13218885Sdim// 14218885Sdim// - If virtual and physical register liveness is modeled using intervals, then 15218885Sdim// on-the-fly interference checking is cheap. Furthermore, interferences can be 16218885Sdim// lazily cached and reused. 17218885Sdim// 18218885Sdim// - Register allocation complexity, and generated code performance is 19218885Sdim// determined by the effectiveness of live range splitting rather than optimal 20218885Sdim// coloring. 21218885Sdim// 22218885Sdim// Following the first principle, interfering checking revolves around the 23218885Sdim// LiveIntervalUnion data structure. 24218885Sdim// 25218885Sdim// To fulfill the second principle, the basic allocator provides a driver for 26218885Sdim// incremental splitting. It essentially punts on the problem of register 27218885Sdim// coloring, instead driving the assignment of virtual to physical registers by 28218885Sdim// the cost of splitting. The basic allocator allows for heuristic reassignment 29218885Sdim// of registers, if a more sophisticated allocator chooses to do that. 30218885Sdim// 31218885Sdim// This framework provides a way to engineer the compile time vs. code 32218885Sdim// quality trade-off without relying on a particular theoretical solver. 33218885Sdim// 34218885Sdim//===----------------------------------------------------------------------===// 35218885Sdim 36280031Sdim#ifndef LLVM_LIB_CODEGEN_REGALLOCBASE_H 37280031Sdim#define LLVM_LIB_CODEGEN_REGALLOCBASE_H 38218885Sdim 39327952Sdim#include "llvm/ADT/SmallPtrSet.h" 40239462Sdim#include "llvm/CodeGen/RegisterClassInfo.h" 41218885Sdim 42218885Sdimnamespace llvm { 43218885Sdim 44327952Sdimclass LiveInterval; 45327952Sdimclass LiveIntervals; 46327952Sdimclass LiveRegMatrix; 47327952Sdimclass MachineInstr; 48327952Sdimclass MachineRegisterInfo; 49218885Sdimtemplate<typename T> class SmallVectorImpl; 50327952Sdimclass Spiller; 51218885Sdimclass TargetRegisterInfo; 52218885Sdimclass VirtRegMap; 53218885Sdim 54218885Sdim/// RegAllocBase provides the register allocation driver and interface that can 55218885Sdim/// be extended to add interesting heuristics. 56218885Sdim/// 57218885Sdim/// Register allocators must override the selectOrSplit() method to implement 58219077Sdim/// live range splitting. They must also override enqueue/dequeue to provide an 59219077Sdim/// assignment order. 60218885Sdimclass RegAllocBase { 61261991Sdim virtual void anchor(); 62327952Sdim 63234353Sdimprotected: 64327952Sdim const TargetRegisterInfo *TRI = nullptr; 65327952Sdim MachineRegisterInfo *MRI = nullptr; 66327952Sdim VirtRegMap *VRM = nullptr; 67327952Sdim LiveIntervals *LIS = nullptr; 68327952Sdim LiveRegMatrix *Matrix = nullptr; 69223017Sdim RegisterClassInfo RegClassInfo; 70218885Sdim 71309124Sdim /// Inst which is a def of an original reg and whose defs are already all 72309124Sdim /// dead after remat is saved in DeadRemats. The deletion of such inst is 73309124Sdim /// postponed till all the allocations are done, so its remat expr is 74309124Sdim /// always available for the remat of all the siblings of the original reg. 75309124Sdim SmallPtrSet<MachineInstr *, 32> DeadRemats; 76309124Sdim 77327952Sdim RegAllocBase() = default; 78327952Sdim virtual ~RegAllocBase() = default; 79218885Sdim 80218885Sdim // A RegAlloc pass should call this before allocatePhysRegs. 81239462Sdim void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat); 82218885Sdim 83218885Sdim // The top-level driver. The output is a VirtRegMap that us updated with 84218885Sdim // physical register assignments. 85218885Sdim void allocatePhysRegs(); 86218885Sdim 87309124Sdim // Include spiller post optimization and removing dead defs left because of 88309124Sdim // rematerialization. 89309124Sdim virtual void postOptimization(); 90309124Sdim 91218885Sdim // Get a temporary reference to a Spiller instance. 92218885Sdim virtual Spiller &spiller() = 0; 93218885Sdim 94219077Sdim /// enqueue - Add VirtReg to the priority queue of unassigned registers. 95219077Sdim virtual void enqueue(LiveInterval *LI) = 0; 96218885Sdim 97219077Sdim /// dequeue - Return the next unassigned register, or NULL. 98219077Sdim virtual LiveInterval *dequeue() = 0; 99219077Sdim 100218885Sdim // A RegAlloc pass should override this to provide the allocation heuristics. 101218885Sdim // Each call must guarantee forward progess by returning an available PhysReg 102218885Sdim // or new set of split live virtual registers. It is up to the splitter to 103218885Sdim // converge quickly toward fully spilled live ranges. 104218885Sdim virtual unsigned selectOrSplit(LiveInterval &VirtReg, 105261991Sdim SmallVectorImpl<unsigned> &splitLVRs) = 0; 106218885Sdim 107218885Sdim // Use this group name for NamedRegionTimer. 108261991Sdim static const char TimerGroupName[]; 109314564Sdim static const char TimerGroupDescription[]; 110218885Sdim 111280031Sdim /// Method called when the allocator is about to remove a LiveInterval. 112280031Sdim virtual void aboutToRemoveInterval(LiveInterval &LI) {} 113280031Sdim 114218885Sdimpublic: 115218885Sdim /// VerifyEnabled - True when -verify-regalloc is given. 116218885Sdim static bool VerifyEnabled; 117218885Sdim 118218885Sdimprivate: 119219077Sdim void seedLiveRegs(); 120218885Sdim}; 121218885Sdim 122218885Sdim} // end namespace llvm 123218885Sdim 124327952Sdim#endif // LLVM_LIB_CODEGEN_REGALLOCBASE_H 125