]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===-- RegAllocBase.h - basic regalloc interface and driver --*- C++ -*---===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // This file defines the RegAllocBase class, which is the skeleton of a basic | |
11 | // register allocation algorithm and interface for extending it. It provides the | |
12 | // building blocks on which to construct other experimental allocators and test | |
13 | // the validity of two principles: | |
14 | // | |
15 | // - If virtual and physical register liveness is modeled using intervals, then | |
16 | // on-the-fly interference checking is cheap. Furthermore, interferences can be | |
17 | // lazily cached and reused. | |
18 | // | |
19 | // - Register allocation complexity, and generated code performance is | |
20 | // determined by the effectiveness of live range splitting rather than optimal | |
21 | // coloring. | |
22 | // | |
23 | // Following the first principle, interfering checking revolves around the | |
24 | // LiveIntervalUnion data structure. | |
25 | // | |
26 | // To fulfill the second principle, the basic allocator provides a driver for | |
27 | // incremental splitting. It essentially punts on the problem of register | |
28 | // coloring, instead driving the assignment of virtual to physical registers by | |
29 | // the cost of splitting. The basic allocator allows for heuristic reassignment | |
30 | // of registers, if a more sophisticated allocator chooses to do that. | |
31 | // | |
32 | // This framework provides a way to engineer the compile time vs. code | |
33 | // quality trade-off without relying on a particular theoretical solver. | |
34 | // | |
35 | //===----------------------------------------------------------------------===// | |
36 | ||
1a4d82fc JJ |
37 | #ifndef LLVM_LIB_CODEGEN_REGALLOCBASE_H |
38 | #define LLVM_LIB_CODEGEN_REGALLOCBASE_H | |
223e47cc | 39 | |
1a4d82fc | 40 | #include "llvm/CodeGen/LiveInterval.h" |
970d7e83 | 41 | #include "llvm/CodeGen/RegisterClassInfo.h" |
223e47cc LB |
42 | |
43 | namespace llvm { | |
44 | ||
45 | template<typename T> class SmallVectorImpl; | |
46 | class TargetRegisterInfo; | |
47 | class VirtRegMap; | |
48 | class LiveIntervals; | |
49 | class LiveRegMatrix; | |
50 | class Spiller; | |
51 | ||
52 | /// RegAllocBase provides the register allocation driver and interface that can | |
53 | /// be extended to add interesting heuristics. | |
54 | /// | |
55 | /// Register allocators must override the selectOrSplit() method to implement | |
56 | /// live range splitting. They must also override enqueue/dequeue to provide an | |
57 | /// assignment order. | |
58 | class RegAllocBase { | |
1a4d82fc | 59 | virtual void anchor(); |
223e47cc LB |
60 | protected: |
61 | const TargetRegisterInfo *TRI; | |
62 | MachineRegisterInfo *MRI; | |
63 | VirtRegMap *VRM; | |
64 | LiveIntervals *LIS; | |
65 | LiveRegMatrix *Matrix; | |
66 | RegisterClassInfo RegClassInfo; | |
67 | ||
1a4d82fc JJ |
68 | RegAllocBase() |
69 | : TRI(nullptr), MRI(nullptr), VRM(nullptr), LIS(nullptr), Matrix(nullptr) {} | |
223e47cc LB |
70 | |
71 | virtual ~RegAllocBase() {} | |
72 | ||
73 | // A RegAlloc pass should call this before allocatePhysRegs. | |
74 | void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat); | |
75 | ||
76 | // The top-level driver. The output is a VirtRegMap that us updated with | |
77 | // physical register assignments. | |
78 | void allocatePhysRegs(); | |
79 | ||
80 | // Get a temporary reference to a Spiller instance. | |
81 | virtual Spiller &spiller() = 0; | |
82 | ||
83 | /// enqueue - Add VirtReg to the priority queue of unassigned registers. | |
84 | virtual void enqueue(LiveInterval *LI) = 0; | |
85 | ||
86 | /// dequeue - Return the next unassigned register, or NULL. | |
87 | virtual LiveInterval *dequeue() = 0; | |
88 | ||
89 | // A RegAlloc pass should override this to provide the allocation heuristics. | |
90 | // Each call must guarantee forward progess by returning an available PhysReg | |
91 | // or new set of split live virtual registers. It is up to the splitter to | |
92 | // converge quickly toward fully spilled live ranges. | |
93 | virtual unsigned selectOrSplit(LiveInterval &VirtReg, | |
1a4d82fc | 94 | SmallVectorImpl<unsigned> &splitLVRs) = 0; |
223e47cc LB |
95 | |
96 | // Use this group name for NamedRegionTimer. | |
1a4d82fc | 97 | static const char TimerGroupName[]; |
223e47cc | 98 | |
85aaf69f SL |
99 | /// Method called when the allocator is about to remove a LiveInterval. |
100 | virtual void aboutToRemoveInterval(LiveInterval &LI) {} | |
101 | ||
223e47cc LB |
102 | public: |
103 | /// VerifyEnabled - True when -verify-regalloc is given. | |
104 | static bool VerifyEnabled; | |
105 | ||
106 | private: | |
107 | void seedLiveRegs(); | |
108 | }; | |
109 | ||
110 | } // end namespace llvm | |
111 | ||
1a4d82fc | 112 | #endif |