1 | //===- LiveRegMatrix.h - Track register interference ----------*- 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 | // The LiveRegMatrix analysis pass keeps track of virtual register interference |
10 | // along two dimensions: Slot indexes and register units. The matrix is used by |
11 | // register allocators to ensure that no interfering virtual registers get |
12 | // assigned to overlapping physical registers. |
13 | // |
14 | // Register units are defined in MCRegisterInfo.h, they represent the smallest |
15 | // unit of interference when dealing with overlapping physical registers. The |
16 | // LiveRegMatrix is represented as a LiveIntervalUnion per register unit. When |
17 | // a virtual register is assigned to a physical register, the live range for |
18 | // the virtual register is inserted into the LiveIntervalUnion for each regunit |
19 | // in the physreg. |
20 | // |
21 | //===----------------------------------------------------------------------===// |
22 | |
23 | #ifndef LLVM_CODEGEN_LIVEREGMATRIX_H |
24 | #define LLVM_CODEGEN_LIVEREGMATRIX_H |
25 | |
26 | #include "llvm/ADT/BitVector.h" |
27 | #include "llvm/CodeGen/LiveIntervalUnion.h" |
28 | #include "llvm/CodeGen/MachineFunctionPass.h" |
29 | #include <memory> |
30 | |
31 | namespace llvm { |
32 | |
33 | class AnalysisUsage; |
34 | class LiveInterval; |
35 | class LiveIntervals; |
36 | class MachineFunction; |
37 | class TargetRegisterInfo; |
38 | class VirtRegMap; |
39 | |
40 | class LiveRegMatrix : public MachineFunctionPass { |
41 | const TargetRegisterInfo *TRI = nullptr; |
42 | LiveIntervals *LIS = nullptr; |
43 | VirtRegMap *VRM = nullptr; |
44 | |
45 | // UserTag changes whenever virtual registers have been modified. |
46 | unsigned UserTag = 0; |
47 | |
48 | // The matrix is represented as a LiveIntervalUnion per register unit. |
49 | LiveIntervalUnion::Allocator LIUAlloc; |
50 | LiveIntervalUnion::Array Matrix; |
51 | |
52 | // Cached queries per register unit. |
53 | std::unique_ptr<LiveIntervalUnion::Query[]> Queries; |
54 | |
55 | // Cached register mask interference info. |
56 | unsigned RegMaskTag = 0; |
57 | unsigned RegMaskVirtReg = 0; |
58 | BitVector RegMaskUsable; |
59 | |
60 | // MachineFunctionPass boilerplate. |
61 | void getAnalysisUsage(AnalysisUsage &) const override; |
62 | bool runOnMachineFunction(MachineFunction &) override; |
63 | void releaseMemory() override; |
64 | |
65 | public: |
66 | static char ID; |
67 | |
68 | LiveRegMatrix(); |
69 | |
70 | //===--------------------------------------------------------------------===// |
71 | // High-level interface. |
72 | //===--------------------------------------------------------------------===// |
73 | // |
74 | // Check for interference before assigning virtual registers to physical |
75 | // registers. |
76 | // |
77 | |
78 | /// Invalidate cached interference queries after modifying virtual register |
79 | /// live ranges. Interference checks may return stale information unless |
80 | /// caches are invalidated. |
81 | void invalidateVirtRegs() { ++UserTag; } |
82 | |
83 | enum InterferenceKind { |
84 | /// No interference, go ahead and assign. |
85 | IK_Free = 0, |
86 | |
87 | /// Virtual register interference. There are interfering virtual registers |
88 | /// assigned to PhysReg or its aliases. This interference could be resolved |
89 | /// by unassigning those other virtual registers. |
90 | IK_VirtReg, |
91 | |
92 | /// Register unit interference. A fixed live range is in the way, typically |
93 | /// argument registers for a call. This can't be resolved by unassigning |
94 | /// other virtual registers. |
95 | IK_RegUnit, |
96 | |
97 | /// RegMask interference. The live range is crossing an instruction with a |
98 | /// regmask operand that doesn't preserve PhysReg. This typically means |
99 | /// VirtReg is live across a call, and PhysReg isn't call-preserved. |
100 | IK_RegMask |
101 | }; |
102 | |
103 | /// Check for interference before assigning VirtReg to PhysReg. |
104 | /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg). |
105 | /// When there is more than one kind of interference, the InterferenceKind |
106 | /// with the highest enum value is returned. |
107 | InterferenceKind checkInterference(const LiveInterval &VirtReg, |
108 | MCRegister PhysReg); |
109 | |
110 | /// Check for interference in the segment [Start, End) that may prevent |
111 | /// assignment to PhysReg. If this function returns true, there is |
112 | /// interference in the segment [Start, End) of some other interval already |
113 | /// assigned to PhysReg. If this function returns false, PhysReg is free at |
114 | /// the segment [Start, End). |
115 | bool checkInterference(SlotIndex Start, SlotIndex End, MCRegister PhysReg); |
116 | |
117 | /// Assign VirtReg to PhysReg. |
118 | /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and |
119 | /// update VirtRegMap. The live range is expected to be available in PhysReg. |
120 | void assign(const LiveInterval &VirtReg, MCRegister PhysReg); |
121 | |
122 | /// Unassign VirtReg from its PhysReg. |
123 | /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes |
124 | /// the assignment and updates VirtRegMap accordingly. |
125 | void unassign(const LiveInterval &VirtReg); |
126 | |
127 | /// Returns true if the given \p PhysReg has any live intervals assigned. |
128 | bool isPhysRegUsed(MCRegister PhysReg) const; |
129 | |
130 | //===--------------------------------------------------------------------===// |
131 | // Low-level interface. |
132 | //===--------------------------------------------------------------------===// |
133 | // |
134 | // Provide access to the underlying LiveIntervalUnions. |
135 | // |
136 | |
137 | /// Check for regmask interference only. |
138 | /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg. |
139 | /// If PhysReg is null, check if VirtReg crosses any regmask operands. |
140 | bool checkRegMaskInterference(const LiveInterval &VirtReg, |
141 | MCRegister PhysReg = MCRegister::NoRegister); |
142 | |
143 | /// Check for regunit interference only. |
144 | /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's |
145 | /// register units. |
146 | bool checkRegUnitInterference(const LiveInterval &VirtReg, |
147 | MCRegister PhysReg); |
148 | |
149 | /// Query a line of the assigned virtual register matrix directly. |
150 | /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg. |
151 | /// This returns a reference to an internal Query data structure that is only |
152 | /// valid until the next query() call. |
153 | LiveIntervalUnion::Query &query(const LiveRange &LR, MCRegister RegUnit); |
154 | |
155 | /// Directly access the live interval unions per regunit. |
156 | /// This returns an array indexed by the regunit number. |
157 | LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; } |
158 | |
159 | Register getOneVReg(unsigned PhysReg) const; |
160 | }; |
161 | |
162 | } // end namespace llvm |
163 | |
164 | #endif // LLVM_CODEGEN_LIVEREGMATRIX_H |
165 | |