1 //===-- llvm/CodeGen/Spiller.h - Spiller -*- C++ -*------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_CODEGEN_SPILLER_H
11 #define LLVM_CODEGEN_SPILLER_H
13 #include "llvm/Target/TargetRegisterInfo.h"
14 #include "llvm/ADT/BitVector.h"
15 #include "llvm/ADT/IndexedMap.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/Support/Streams.h"
19 #include "llvm/Function.h"
20 #include "llvm/CodeGen/MachineFrameInfo.h"
21 #include "llvm/CodeGen/MachineFunction.h"
22 #include "llvm/CodeGen/MachineInstrBuilder.h"
23 #include "llvm/CodeGen/MachineRegisterInfo.h"
24 #include "llvm/Target/TargetMachine.h"
25 #include "llvm/Target/TargetInstrInfo.h"
26 #include "llvm/Support/CommandLine.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/ADT/BitVector.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/SmallSet.h"
31 #include "VirtRegMap.h"
36 /// Spiller interface: Implementations of this interface assign spilled
37 /// virtual registers to stack slots, rewriting the code.
40 virtual bool runOnMachineFunction(MachineFunction &MF,
44 /// createSpiller - Create an return a spiller object, as specified on the
46 Spiller* createSpiller();
48 // ************************************************************************ //
50 // Simple Spiller Implementation
51 struct VISIBILITY_HIDDEN SimpleSpiller : public Spiller {
52 bool runOnMachineFunction(MachineFunction& mf, VirtRegMap &VRM);
55 // ************************************************************************ //
57 /// AvailableSpills - As the local spiller is scanning and rewriting an MBB
58 /// from top down, keep track of which spills slots or remat are available in
61 /// Note that not all physregs are created equal here. In particular, some
62 /// physregs are reloads that we are allowed to clobber or ignore at any time.
63 /// Other physregs are values that the register allocated program is using
64 /// that we cannot CHANGE, but we can read if we like. We keep track of this
65 /// on a per-stack-slot / remat id basis as the low bit in the value of the
66 /// SpillSlotsAvailable entries. The predicate 'canClobberPhysReg()' checks
67 /// this bit and addAvailable sets it if.
68 class VISIBILITY_HIDDEN AvailableSpills {
69 const TargetRegisterInfo *TRI;
70 const TargetInstrInfo *TII;
72 // SpillSlotsOrReMatsAvailable - This map keeps track of all of the spilled
73 // or remat'ed virtual register values that are still available, due to
74 // being loaded or stored to, but not invalidated yet.
75 std::map<int, unsigned> SpillSlotsOrReMatsAvailable;
77 // PhysRegsAvailable - This is the inverse of SpillSlotsOrReMatsAvailable,
78 // indicating which stack slot values are currently held by a physreg. This
79 // is used to invalidate entries in SpillSlotsOrReMatsAvailable when a
80 // physreg is modified.
81 std::multimap<unsigned, int> PhysRegsAvailable;
83 void disallowClobberPhysRegOnly(unsigned PhysReg);
85 void ClobberPhysRegOnly(unsigned PhysReg);
87 AvailableSpills(const TargetRegisterInfo *tri, const TargetInstrInfo *tii)
88 : TRI(tri), TII(tii) {
91 /// clear - Reset the state.
93 SpillSlotsOrReMatsAvailable.clear();
94 PhysRegsAvailable.clear();
97 const TargetRegisterInfo *getRegInfo() const { return TRI; }
99 /// getSpillSlotOrReMatPhysReg - If the specified stack slot or remat is
100 /// available in a physical register, return that PhysReg, otherwise
102 unsigned getSpillSlotOrReMatPhysReg(int Slot) const {
103 std::map<int, unsigned>::const_iterator I =
104 SpillSlotsOrReMatsAvailable.find(Slot);
105 if (I != SpillSlotsOrReMatsAvailable.end()) {
106 return I->second >> 1; // Remove the CanClobber bit.
111 /// addAvailable - Mark that the specified stack slot / remat is available
112 /// in the specified physreg. If CanClobber is true, the physreg can be
113 /// modified at any time without changing the semantics of the program.
114 void addAvailable(int SlotOrReMat, unsigned Reg, bool CanClobber = true) {
115 // If this stack slot is thought to be available in some other physreg,
116 // remove its record.
117 ModifyStackSlotOrReMat(SlotOrReMat);
119 PhysRegsAvailable.insert(std::make_pair(Reg, SlotOrReMat));
120 SpillSlotsOrReMatsAvailable[SlotOrReMat]= (Reg << 1) |
121 (unsigned)CanClobber;
123 if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT)
124 DOUT << "Remembering RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1;
126 DOUT << "Remembering SS#" << SlotOrReMat;
127 DOUT << " in physreg " << TRI->getName(Reg) << "\n";
130 /// canClobberPhysRegForSS - Return true if the spiller is allowed to change
131 /// the value of the specified stackslot register if it desires. The
132 /// specified stack slot must be available in a physreg for this query to
134 bool canClobberPhysRegForSS(int SlotOrReMat) const {
135 assert(SpillSlotsOrReMatsAvailable.count(SlotOrReMat) &&
136 "Value not available!");
137 return SpillSlotsOrReMatsAvailable.find(SlotOrReMat)->second & 1;
140 /// canClobberPhysReg - Return true if the spiller is allowed to clobber the
141 /// physical register where values for some stack slot(s) might be
143 bool canClobberPhysReg(unsigned PhysReg) const {
144 std::multimap<unsigned, int>::const_iterator I =
145 PhysRegsAvailable.lower_bound(PhysReg);
146 while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
147 int SlotOrReMat = I->second;
149 if (!canClobberPhysRegForSS(SlotOrReMat))
155 /// disallowClobberPhysReg - Unset the CanClobber bit of the specified
156 /// stackslot register. The register is still available but is no longer
157 /// allowed to be modifed.
158 void disallowClobberPhysReg(unsigned PhysReg);
160 /// ClobberPhysReg - This is called when the specified physreg changes
161 /// value. We use this to invalidate any info about stuff that lives in
162 /// it and any of its aliases.
163 void ClobberPhysReg(unsigned PhysReg);
165 /// ModifyStackSlotOrReMat - This method is called when the value in a stack
166 /// slot changes. This removes information about which register the
167 /// previous value for this slot lives in (as the previous value is dead
169 void ModifyStackSlotOrReMat(int SlotOrReMat);
171 /// AddAvailableRegsToLiveIn - Availability information is being kept coming
172 /// into the specified MBB. Add available physical registers as potential
173 /// live-in's. If they are reused in the MBB, they will be added to the
174 /// live-in set to make register scavenger and post-allocation scheduler.
175 void AddAvailableRegsToLiveIn(MachineBasicBlock &MBB, BitVector &RegKills,
176 std::vector<MachineOperand*> &KillOps);
179 // ************************************************************************ //
181 // ReusedOp - For each reused operand, we keep track of a bit of information,
182 // in case we need to rollback upon processing a new operand. See comments
185 // The MachineInstr operand that reused an available value.
188 // StackSlotOrReMat - The spill slot or remat id of the value being reused.
189 unsigned StackSlotOrReMat;
191 // PhysRegReused - The physical register the value was available in.
192 unsigned PhysRegReused;
194 // AssignedPhysReg - The physreg that was assigned for use by the reload.
195 unsigned AssignedPhysReg;
197 // VirtReg - The virtual register itself.
200 ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr,
202 : Operand(o), StackSlotOrReMat(ss), PhysRegReused(prr),
203 AssignedPhysReg(apr), VirtReg(vreg) {}
206 /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that
207 /// is reused instead of reloaded.
208 class VISIBILITY_HIDDEN ReuseInfo {
210 std::vector<ReusedOp> Reuses;
211 BitVector PhysRegsClobbered;
213 ReuseInfo(MachineInstr &mi, const TargetRegisterInfo *tri) : MI(mi) {
214 PhysRegsClobbered.resize(tri->getNumRegs());
217 bool hasReuses() const {
218 return !Reuses.empty();
221 /// addReuse - If we choose to reuse a virtual register that is already
222 /// available instead of reloading it, remember that we did so.
223 void addReuse(unsigned OpNo, unsigned StackSlotOrReMat,
224 unsigned PhysRegReused, unsigned AssignedPhysReg,
226 // If the reload is to the assigned register anyway, no undo will be
228 if (PhysRegReused == AssignedPhysReg) return;
230 // Otherwise, remember this.
231 Reuses.push_back(ReusedOp(OpNo, StackSlotOrReMat, PhysRegReused,
232 AssignedPhysReg, VirtReg));
235 void markClobbered(unsigned PhysReg) {
236 PhysRegsClobbered.set(PhysReg);
239 bool isClobbered(unsigned PhysReg) const {
240 return PhysRegsClobbered.test(PhysReg);
243 /// GetRegForReload - We are about to emit a reload into PhysReg. If there
244 /// is some other operand that is using the specified register, either pick
245 /// a new register to use, or evict the previous reload and use this reg.
246 unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
247 AvailableSpills &Spills,
248 std::vector<MachineInstr*> &MaybeDeadStores,
249 SmallSet<unsigned, 8> &Rejected,
251 std::vector<MachineOperand*> &KillOps,
254 /// GetRegForReload - Helper for the above GetRegForReload(). Add a
255 /// 'Rejected' set to remember which registers have been considered and
256 /// rejected for the reload. This avoids infinite looping in case like
259 /// t2 <- assigned r0 for use by the reload but ended up reuse r1
260 /// t3 <- assigned r1 for use by the reload but ended up reuse r0
262 /// sees r1 is taken by t2, tries t2's reload register r0
263 /// sees r0 is taken by t3, tries t3's reload register r1
264 /// sees r1 is taken by t2, tries t2's reload register r0 ...
265 unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
266 AvailableSpills &Spills,
267 std::vector<MachineInstr*> &MaybeDeadStores,
269 std::vector<MachineOperand*> &KillOps,
271 SmallSet<unsigned, 8> Rejected;
272 return GetRegForReload(PhysReg, MI, Spills, MaybeDeadStores, Rejected,
273 RegKills, KillOps, VRM);
277 // ************************************************************************ //
279 /// LocalSpiller - This spiller does a simple pass over the machine basic
280 /// block to attempt to keep spills in registers as much as possible for
281 /// blocks that have low register pressure (the vreg may be spilled due to
282 /// register pressure in other blocks).
283 class VISIBILITY_HIDDEN LocalSpiller : public Spiller {
284 MachineRegisterInfo *RegInfo;
285 const TargetRegisterInfo *TRI;
286 const TargetInstrInfo *TII;
287 DenseMap<MachineInstr*, unsigned> DistanceMap;
289 bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM);
291 void TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist,
292 unsigned Reg, BitVector &RegKills,
293 std::vector<MachineOperand*> &KillOps);
294 bool PrepForUnfoldOpti(MachineBasicBlock &MBB,
295 MachineBasicBlock::iterator &MII,
296 std::vector<MachineInstr*> &MaybeDeadStores,
297 AvailableSpills &Spills, BitVector &RegKills,
298 std::vector<MachineOperand*> &KillOps,
300 bool CommuteToFoldReload(MachineBasicBlock &MBB,
301 MachineBasicBlock::iterator &MII,
302 unsigned VirtReg, unsigned SrcReg, int SS,
303 AvailableSpills &Spills,
305 std::vector<MachineOperand*> &KillOps,
306 const TargetRegisterInfo *TRI,
308 void SpillRegToStackSlot(MachineBasicBlock &MBB,
309 MachineBasicBlock::iterator &MII,
310 int Idx, unsigned PhysReg, int StackSlot,
311 const TargetRegisterClass *RC,
312 bool isAvailable, MachineInstr *&LastStore,
313 AvailableSpills &Spills,
314 SmallSet<MachineInstr*, 4> &ReMatDefs,
316 std::vector<MachineOperand*> &KillOps,
318 void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
319 AvailableSpills &Spills,
320 BitVector &RegKills, std::vector<MachineOperand*> &KillOps);