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