1 | //===- LiveRangeEdit.h - Basic tools for split and spill --------*- 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 LiveRangeEdit class represents changes done to a virtual register when it |
10 | // is spilled or split. |
11 | // |
12 | // The parent register is never changed. Instead, a number of new virtual |
13 | // registers are created and added to the newRegs vector. |
14 | // |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #ifndef LLVM_CODEGEN_LIVERANGEEDIT_H |
18 | #define LLVM_CODEGEN_LIVERANGEEDIT_H |
19 | |
20 | #include "llvm/ADT/ArrayRef.h" |
21 | #include "llvm/ADT/SetVector.h" |
22 | #include "llvm/ADT/SmallPtrSet.h" |
23 | #include "llvm/ADT/SmallVector.h" |
24 | #include "llvm/CodeGen/LiveInterval.h" |
25 | #include "llvm/CodeGen/MachineBasicBlock.h" |
26 | #include "llvm/CodeGen/MachineFunction.h" |
27 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
28 | #include "llvm/CodeGen/SlotIndexes.h" |
29 | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
30 | #include <cassert> |
31 | |
32 | namespace llvm { |
33 | |
34 | class LiveIntervals; |
35 | class MachineInstr; |
36 | class MachineOperand; |
37 | class TargetInstrInfo; |
38 | class TargetRegisterInfo; |
39 | class VirtRegMap; |
40 | class VirtRegAuxInfo; |
41 | |
42 | class LiveRangeEdit : private MachineRegisterInfo::Delegate { |
43 | public: |
44 | /// Callback methods for LiveRangeEdit owners. |
45 | class Delegate { |
46 | virtual void anchor(); |
47 | |
48 | public: |
49 | virtual ~Delegate() = default; |
50 | |
51 | /// Called immediately before erasing a dead machine instruction. |
52 | virtual void LRE_WillEraseInstruction(MachineInstr *MI) {} |
53 | |
54 | /// Called when a virtual register is no longer used. Return false to defer |
55 | /// its deletion from LiveIntervals. |
56 | virtual bool LRE_CanEraseVirtReg(Register) { return true; } |
57 | |
58 | /// Called before shrinking the live range of a virtual register. |
59 | virtual void LRE_WillShrinkVirtReg(Register) {} |
60 | |
61 | /// Called after cloning a virtual register. |
62 | /// This is used for new registers representing connected components of Old. |
63 | virtual void LRE_DidCloneVirtReg(Register New, Register Old) {} |
64 | }; |
65 | |
66 | private: |
67 | const LiveInterval *const Parent; |
68 | SmallVectorImpl<Register> &NewRegs; |
69 | MachineRegisterInfo &MRI; |
70 | LiveIntervals &LIS; |
71 | VirtRegMap *VRM; |
72 | const TargetInstrInfo &TII; |
73 | Delegate *const TheDelegate; |
74 | |
75 | /// FirstNew - Index of the first register added to NewRegs. |
76 | const unsigned FirstNew; |
77 | |
78 | /// ScannedRemattable - true when remattable values have been identified. |
79 | bool ScannedRemattable = false; |
80 | |
81 | /// DeadRemats - The saved instructions which have already been dead after |
82 | /// rematerialization but not deleted yet -- to be done in postOptimization. |
83 | SmallPtrSet<MachineInstr *, 32> *DeadRemats; |
84 | |
85 | /// Remattable - Values defined by remattable instructions as identified by |
86 | /// tii.isTriviallyReMaterializable(). |
87 | SmallPtrSet<const VNInfo *, 4> Remattable; |
88 | |
89 | /// Rematted - Values that were actually rematted, and so need to have their |
90 | /// live range trimmed or entirely removed. |
91 | SmallPtrSet<const VNInfo *, 4> Rematted; |
92 | |
93 | /// scanRemattable - Identify the Parent values that may rematerialize. |
94 | void scanRemattable(); |
95 | |
96 | /// foldAsLoad - If LI has a single use and a single def that can be folded as |
97 | /// a load, eliminate the register by folding the def into the use. |
98 | bool foldAsLoad(LiveInterval *LI, SmallVectorImpl<MachineInstr *> &Dead); |
99 | |
100 | using ToShrinkSet = SmallSetVector<LiveInterval *, 8>; |
101 | |
102 | /// Helper for eliminateDeadDefs. |
103 | void eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink); |
104 | |
105 | /// MachineRegisterInfo callback to notify when new virtual |
106 | /// registers are created. |
107 | void MRI_NoteNewVirtualRegister(Register VReg) override; |
108 | |
109 | /// Check if MachineOperand \p MO is a last use/kill either in the |
110 | /// main live range of \p LI or in one of the matching subregister ranges. |
111 | bool useIsKill(const LiveInterval &LI, const MachineOperand &MO) const; |
112 | |
113 | /// Create a new empty interval based on OldReg. |
114 | LiveInterval &createEmptyIntervalFrom(Register OldReg, bool createSubRanges); |
115 | |
116 | public: |
117 | /// Create a LiveRangeEdit for breaking down parent into smaller pieces. |
118 | /// @param parent The register being spilled or split. |
119 | /// @param newRegs List to receive any new registers created. This needn't be |
120 | /// empty initially, any existing registers are ignored. |
121 | /// @param MF The MachineFunction the live range edit is taking place in. |
122 | /// @param lis The collection of all live intervals in this function. |
123 | /// @param vrm Map of virtual registers to physical registers for this |
124 | /// function. If NULL, no virtual register map updates will |
125 | /// be done. This could be the case if called before Regalloc. |
126 | /// @param deadRemats The collection of all the instructions defining an |
127 | /// original reg and are dead after remat. |
128 | LiveRangeEdit(const LiveInterval *parent, SmallVectorImpl<Register> &newRegs, |
129 | MachineFunction &MF, LiveIntervals &lis, VirtRegMap *vrm, |
130 | Delegate *delegate = nullptr, |
131 | SmallPtrSet<MachineInstr *, 32> *deadRemats = nullptr) |
132 | : Parent(parent), NewRegs(newRegs), MRI(MF.getRegInfo()), LIS(lis), |
133 | VRM(vrm), TII(*MF.getSubtarget().getInstrInfo()), TheDelegate(delegate), |
134 | FirstNew(newRegs.size()), DeadRemats(deadRemats) { |
135 | MRI.addDelegate(delegate: this); |
136 | } |
137 | |
138 | ~LiveRangeEdit() override { MRI.resetDelegate(delegate: this); } |
139 | |
140 | const LiveInterval &getParent() const { |
141 | assert(Parent && "No parent LiveInterval" ); |
142 | return *Parent; |
143 | } |
144 | |
145 | Register getReg() const { return getParent().reg(); } |
146 | |
147 | /// Iterator for accessing the new registers added by this edit. |
148 | using iterator = SmallVectorImpl<Register>::const_iterator; |
149 | iterator begin() const { return NewRegs.begin() + FirstNew; } |
150 | iterator end() const { return NewRegs.end(); } |
151 | unsigned size() const { return NewRegs.size() - FirstNew; } |
152 | bool empty() const { return size() == 0; } |
153 | Register get(unsigned idx) const { return NewRegs[idx + FirstNew]; } |
154 | |
155 | /// pop_back - It allows LiveRangeEdit users to drop new registers. |
156 | /// The context is when an original def instruction of a register is |
157 | /// dead after rematerialization, we still want to keep it for following |
158 | /// rematerializations. We save the def instruction in DeadRemats, |
159 | /// and replace the original dst register with a new dummy register so |
160 | /// the live range of original dst register can be shrinked normally. |
161 | /// We don't want to allocate phys register for the dummy register, so |
162 | /// we want to drop it from the NewRegs set. |
163 | void pop_back() { NewRegs.pop_back(); } |
164 | |
165 | ArrayRef<Register> regs() const { return ArrayRef(NewRegs).slice(N: FirstNew); } |
166 | |
167 | /// createFrom - Create a new virtual register based on OldReg. |
168 | Register createFrom(Register OldReg); |
169 | |
170 | /// create - Create a new register with the same class and original slot as |
171 | /// parent. |
172 | LiveInterval &createEmptyInterval() { |
173 | return createEmptyIntervalFrom(OldReg: getReg(), createSubRanges: true); |
174 | } |
175 | |
176 | Register create() { return createFrom(OldReg: getReg()); } |
177 | |
178 | /// anyRematerializable - Return true if any parent values may be |
179 | /// rematerializable. |
180 | /// This function must be called before any rematerialization is attempted. |
181 | bool anyRematerializable(); |
182 | |
183 | /// checkRematerializable - Manually add VNI to the list of rematerializable |
184 | /// values if DefMI may be rematerializable. |
185 | bool checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI); |
186 | |
187 | /// Remat - Information needed to rematerialize at a specific location. |
188 | struct Remat { |
189 | const VNInfo *const ParentVNI; // parent_'s value at the remat location. |
190 | MachineInstr *OrigMI = nullptr; // Instruction defining OrigVNI. It contains |
191 | // the real expr for remat. |
192 | |
193 | explicit Remat(const VNInfo *ParentVNI) : ParentVNI(ParentVNI) {} |
194 | }; |
195 | |
196 | /// allUsesAvailableAt - Return true if all registers used by OrigMI at |
197 | /// OrigIdx are also available with the same value at UseIdx. |
198 | bool allUsesAvailableAt(const MachineInstr *OrigMI, SlotIndex OrigIdx, |
199 | SlotIndex UseIdx) const; |
200 | |
201 | /// canRematerializeAt - Determine if ParentVNI can be rematerialized at |
202 | /// UseIdx. It is assumed that parent_.getVNINfoAt(UseIdx) == ParentVNI. |
203 | /// When cheapAsAMove is set, only cheap remats are allowed. |
204 | bool canRematerializeAt(Remat &RM, VNInfo *OrigVNI, SlotIndex UseIdx, |
205 | bool cheapAsAMove); |
206 | |
207 | /// rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an |
208 | /// instruction into MBB before MI. The new instruction is mapped, but |
209 | /// liveness is not updated. If ReplaceIndexMI is not null it will be replaced |
210 | /// by new MI in the index map. |
211 | /// Return the SlotIndex of the new instruction. |
212 | SlotIndex rematerializeAt(MachineBasicBlock &MBB, |
213 | MachineBasicBlock::iterator MI, Register DestReg, |
214 | const Remat &RM, const TargetRegisterInfo &, |
215 | bool Late = false, unsigned SubIdx = 0, |
216 | MachineInstr *ReplaceIndexMI = nullptr); |
217 | |
218 | /// markRematerialized - explicitly mark a value as rematerialized after doing |
219 | /// it manually. |
220 | void markRematerialized(const VNInfo *ParentVNI) { |
221 | Rematted.insert(Ptr: ParentVNI); |
222 | } |
223 | |
224 | /// didRematerialize - Return true if ParentVNI was rematerialized anywhere. |
225 | bool didRematerialize(const VNInfo *ParentVNI) const { |
226 | return Rematted.count(Ptr: ParentVNI); |
227 | } |
228 | |
229 | /// eraseVirtReg - Notify the delegate that Reg is no longer in use, and try |
230 | /// to erase it from LIS. |
231 | void eraseVirtReg(Register Reg); |
232 | |
233 | /// eliminateDeadDefs - Try to delete machine instructions that are now dead |
234 | /// (allDefsAreDead returns true). This may cause live intervals to be trimmed |
235 | /// and further dead efs to be eliminated. |
236 | /// RegsBeingSpilled lists registers currently being spilled by the register |
237 | /// allocator. These registers should not be split into new intervals |
238 | /// as currently those new intervals are not guaranteed to spill. |
239 | void eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead, |
240 | ArrayRef<Register> RegsBeingSpilled = std::nullopt); |
241 | |
242 | /// calculateRegClassAndHint - Recompute register class and hint for each new |
243 | /// register. |
244 | void calculateRegClassAndHint(MachineFunction &, VirtRegAuxInfo &); |
245 | }; |
246 | |
247 | } // end namespace llvm |
248 | |
249 | #endif // LLVM_CODEGEN_LIVERANGEEDIT_H |
250 | |