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