114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick//===-- RegAllocBase.h - basic regalloc interface and driver --*- C++ -*---===// 214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// The LLVM Compiler Infrastructure 414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// This file is distributed under the University of Illinois Open Source 614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// License. See LICENSE.TXT for details. 714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick//===----------------------------------------------------------------------===// 914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 1014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// This file defines the RegAllocBase class, which is the skeleton of a basic 1114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// register allocation algorithm and interface for extending it. It provides the 1214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// building blocks on which to construct other experimental allocators and test 1314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// the validity of two principles: 1418c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick// 1514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// - If virtual and physical register liveness is modeled using intervals, then 1614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// on-the-fly interference checking is cheap. Furthermore, interferences can be 1714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// lazily cached and reused. 1818c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick// 1914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// - Register allocation complexity, and generated code performance is 2014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// determined by the effectiveness of live range splitting rather than optimal 2114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// coloring. 2214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 2314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// Following the first principle, interfering checking revolves around the 2414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// LiveIntervalUnion data structure. 2514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 2614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// To fulfill the second principle, the basic allocator provides a driver for 2714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// incremental splitting. It essentially punts on the problem of register 2814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// coloring, instead driving the assignment of virtual to physical registers by 2914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// the cost of splitting. The basic allocator allows for heuristic reassignment 3014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// of registers, if a more sophisticated allocator chooses to do that. 3114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 3214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// This framework provides a way to engineer the compile time vs. code 337fb95d4235ad588d4105544b2ae3fa1aa0eba3b1Cameron Zwarich// quality trade-off without relying on a particular theoretical solver. 3414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 3514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick//===----------------------------------------------------------------------===// 3614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 3714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#ifndef LLVM_CODEGEN_REGALLOCBASE 3814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#define LLVM_CODEGEN_REGALLOCBASE 3914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 40be6a376b95d03e4e58f10ed50c3eee2f593c9cccJakob Stoklund Olesen#include "llvm/CodeGen/LiveInterval.h" 41a1514e24cc24b050f53a12650e047799358833a1Chandler Carruth#include "llvm/CodeGen/RegisterClassInfo.h" 4214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 4314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Tricknamespace llvm { 4414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 45e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Tricktemplate<typename T> class SmallVectorImpl; 46e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Trickclass TargetRegisterInfo; 4714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickclass VirtRegMap; 48e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Trickclass LiveIntervals; 49812cda9a5cc26b1f8dda6f909bf5062c215b65d7Jakob Stoklund Olesenclass LiveRegMatrix; 50f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickclass Spiller; 51e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Trick 5214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// RegAllocBase provides the register allocation driver and interface that can 5314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// be extended to add interesting heuristics. 5414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// 5518c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick/// Register allocators must override the selectOrSplit() method to implement 5698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen/// live range splitting. They must also override enqueue/dequeue to provide an 5798d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen/// assignment order. 5855c06ae7afa3f862a6bb4a4441fe485c135f5b5eBenjamin Kramerclass RegAllocBase { 59354362524a72b3fa43a6c09380b7ae3b2380cbbaJuergen Ributzka virtual void anchor(); 609384111e90cb840e7eb867098f19910cf4c4a11dJakob Stoklund Olesenprotected: 619384111e90cb840e7eb867098f19910cf4c4a11dJakob Stoklund Olesen const TargetRegisterInfo *TRI; 629384111e90cb840e7eb867098f19910cf4c4a11dJakob Stoklund Olesen MachineRegisterInfo *MRI; 639384111e90cb840e7eb867098f19910cf4c4a11dJakob Stoklund Olesen VirtRegMap *VRM; 649384111e90cb840e7eb867098f19910cf4c4a11dJakob Stoklund Olesen LiveIntervals *LIS; 65812cda9a5cc26b1f8dda6f909bf5062c215b65d7Jakob Stoklund Olesen LiveRegMatrix *Matrix; 669384111e90cb840e7eb867098f19910cf4c4a11dJakob Stoklund Olesen RegisterClassInfo RegClassInfo; 679384111e90cb840e7eb867098f19910cf4c4a11dJakob Stoklund Olesen 68dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RegAllocBase() 69dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : TRI(nullptr), MRI(nullptr), VRM(nullptr), LIS(nullptr), Matrix(nullptr) {} 7014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 71f4331060548004471f5bb10e330ba4ce4de28ad2Andrew Trick virtual ~RegAllocBase() {} 72f4331060548004471f5bb10e330ba4ce4de28ad2Andrew Trick 7314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // A RegAlloc pass should call this before allocatePhysRegs. 74d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat); 75bdda37d7fbafe6876f248341837423a4100f95a5Jakob Stoklund Olesen 76e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Trick // The top-level driver. The output is a VirtRegMap that us updated with 77e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Trick // physical register assignments. 78e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Trick void allocatePhysRegs(); 7914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 80f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick // Get a temporary reference to a Spiller instance. 81f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick virtual Spiller &spiller() = 0; 8218c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick 8398d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen /// enqueue - Add VirtReg to the priority queue of unassigned registers. 8498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual void enqueue(LiveInterval *LI) = 0; 8598d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen 8698d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen /// dequeue - Return the next unassigned register, or NULL. 8798d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen virtual LiveInterval *dequeue() = 0; 88d0bec3e62c98b1f0ef3a41db8f95599b2014c131Jakob Stoklund Olesen 8914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // A RegAlloc pass should override this to provide the allocation heuristics. 90e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Trick // Each call must guarantee forward progess by returning an available PhysReg 91e16eecc323879744dcff4f359ba9ccdb25bd6909Andrew Trick // or new set of split live virtual registers. It is up to the splitter to 9214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // converge quickly toward fully spilled live ranges. 9318c57a8a09a7c79fbcf4348b0ad8135246ab984fAndrew Trick virtual unsigned selectOrSplit(LiveInterval &VirtReg, 941feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVectorImpl<unsigned> &splitLVRs) = 0; 9514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 96533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen // Use this group name for NamedRegionTimer. 978de25f031d8a8c63e0107f7fd0ac4af6b8ab600cCraig Topper static const char TimerGroupName[]; 98533f58ecdd8a4732c2f0e149387c4d8d8d4142deJakob Stoklund Olesen 99af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesenpublic: 100af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen /// VerifyEnabled - True when -verify-regalloc is given. 101af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen static bool VerifyEnabled; 102af24964251e27c2dd863239ba66ffd967b593be5Jakob Stoklund Olesen 10314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickprivate: 10498d9648de7d571b2e6d139b65961a70d1833b0d7Jakob Stoklund Olesen void seedLiveRegs(); 10514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick}; 10614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 10714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick} // end namespace llvm 10814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 10914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#endif // !defined(LLVM_CODEGEN_REGALLOCBASE) 110