Line data Source code
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/CodeGen/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 0 : virtual ~Delegate() = default;
54 :
55 : /// Called immediately before erasing a dead machine instruction.
56 24270 : 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 30423 : virtual bool LRE_CanEraseVirtReg(unsigned) { return true; }
61 :
62 : /// Called before shrinking the live range of a virtual register.
63 31427 : 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 1 : 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 : /// 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 : /// Create a new empty interval based on OldReg.
125 : LiveInterval &createEmptyIntervalFrom(unsigned OldReg, bool createSubRanges);
126 :
127 : public:
128 : /// Create a LiveRangeEdit for breaking down parent into smaller pieces.
129 : /// @param parent The register being spilled or split.
130 : /// @param newRegs List to receive any new registers created. This needn't be
131 : /// empty initially, any existing registers are ignored.
132 : /// @param MF The MachineFunction the live range edit is taking place in.
133 : /// @param lis The collection of all live intervals in this function.
134 : /// @param vrm Map of virtual registers to physical registers for this
135 : /// function. If NULL, no virtual register map updates will
136 : /// be done. This could be the case if called before Regalloc.
137 : /// @param deadRemats The collection of all the instructions defining an
138 : /// original reg and are dead after remat.
139 : LiveRangeEdit(LiveInterval *parent, SmallVectorImpl<unsigned> &newRegs,
140 : MachineFunction &MF, LiveIntervals &lis, VirtRegMap *vrm,
141 : Delegate *delegate = nullptr,
142 : SmallPtrSet<MachineInstr *, 32> *deadRemats = nullptr)
143 546694 : : Parent(parent), NewRegs(newRegs), MRI(MF.getRegInfo()), LIS(lis),
144 273347 : VRM(vrm), TII(*MF.getSubtarget().getInstrInfo()), TheDelegate(delegate),
145 273347 : FirstNew(newRegs.size()), DeadRemats(deadRemats) {
146 273347 : MRI.setDelegate(this);
147 : }
148 :
149 298859 : ~LiveRangeEdit() override { MRI.resetDelegate(this); }
150 :
151 0 : LiveInterval &getParent() const {
152 : assert(Parent && "No parent LiveInterval");
153 0 : return *Parent;
154 : }
155 :
156 281959 : unsigned getReg() const { return getParent().reg; }
157 :
158 : /// Iterator for accessing the new registers added by this edit.
159 : using iterator = SmallVectorImpl<unsigned>::const_iterator;
160 68318 : iterator begin() const { return NewRegs.begin() + FirstNew; }
161 0 : iterator end() const { return NewRegs.end(); }
162 234036 : unsigned size() const { return NewRegs.size() - FirstNew; }
163 35095 : bool empty() const { return size() == 0; }
164 1919934 : unsigned get(unsigned idx) const { return NewRegs[idx + FirstNew]; }
165 :
166 : /// pop_back - It allows LiveRangeEdit users to drop new registers.
167 : /// The context is when an original def instruction of a register is
168 : /// dead after rematerialization, we still want to keep it for following
169 : /// rematerializations. We save the def instruction in DeadRemats,
170 : /// and replace the original dst register with a new dummy register so
171 : /// the live range of original dst register can be shrinked normally.
172 : /// We don't want to allocate phys register for the dummy register, so
173 : /// we want to drop it from the NewRegs set.
174 0 : void pop_back() { NewRegs.pop_back(); }
175 :
176 0 : ArrayRef<unsigned> regs() const {
177 18957 : return makeArrayRef(NewRegs).slice(FirstNew);
178 : }
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 : LiveInterval &createEmptyInterval() {
186 35095 : return createEmptyIntervalFrom(getReg(), true);
187 : }
188 :
189 : 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 93748 : 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 : void markRematerialized(const VNInfo *ParentVNI) {
228 2407 : Rematted.insert(ParentVNI);
229 : }
230 :
231 : /// didRematerialize - Return true if ParentVNI was rematerialized anywhere.
232 : bool didRematerialize(const VNInfo *ParentVNI) const {
233 74995 : return Rematted.count(ParentVNI);
234 : }
235 :
236 : /// eraseVirtReg - Notify the delegate that Reg is no longer in use, and try
237 : /// to erase it from LIS.
238 : void eraseVirtReg(unsigned Reg);
239 :
240 : /// eliminateDeadDefs - Try to delete machine instructions that are now dead
241 : /// (allDefsAreDead returns true). This may cause live intervals to be trimmed
242 : /// and further dead efs to be eliminated.
243 : /// RegsBeingSpilled lists registers currently being spilled by the register
244 : /// allocator. These registers should not be split into new intervals
245 : /// as currently those new intervals are not guaranteed to spill.
246 : void eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
247 : ArrayRef<unsigned> RegsBeingSpilled = None,
248 : AliasAnalysis *AA = nullptr);
249 :
250 : /// calculateRegClassAndHint - Recompute register class and hint for each new
251 : /// register.
252 : void calculateRegClassAndHint(MachineFunction &, const MachineLoopInfo &,
253 : const MachineBlockFrequencyInfo &);
254 : };
255 :
256 : } // end namespace llvm
257 :
258 : #endif // LLVM_CODEGEN_LIVERANGEEDIT_H
|
