1 //===-- RegisterPressure.cpp - Dynamic Register Pressure ------------------===//
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 // This file implements the RegisterPressure class which can be used to track
11 // MachineInstr level register pressure.
13 //===----------------------------------------------------------------------===//
15 #include "RegisterClassInfo.h"
16 #include "RegisterPressure.h"
17 #include "llvm/CodeGen/LiveInterval.h"
18 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
20 #include "llvm/Target/TargetMachine.h"
24 /// Increase register pressure for each set impacted by this register class.
25 static void increaseSetPressure(std::vector<unsigned> &CurrSetPressure,
26 std::vector<unsigned> &MaxSetPressure,
27 const TargetRegisterClass *RC,
28 const TargetRegisterInfo *TRI) {
29 unsigned Weight = TRI->getRegClassWeight(RC).RegWeight;
30 for (const int *PSet = TRI->getRegClassPressureSets(RC);
31 *PSet != -1; ++PSet) {
32 CurrSetPressure[*PSet] += Weight;
33 if (CurrSetPressure[*PSet] > MaxSetPressure[*PSet])
34 MaxSetPressure[*PSet] = CurrSetPressure[*PSet];
38 /// Decrease register pressure for each set impacted by this register class.
39 static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
40 const TargetRegisterClass *RC,
41 const TargetRegisterInfo *TRI) {
42 unsigned Weight = TRI->getRegClassWeight(RC).RegWeight;
43 for (const int *PSet = TRI->getRegClassPressureSets(RC);
44 *PSet != -1; ++PSet) {
45 assert(CurrSetPressure[*PSet] >= Weight && "register pressure underflow");
46 CurrSetPressure[*PSet] -= Weight;
50 /// Directly increase pressure only within this RegisterPressure result.
51 void RegisterPressure::increase(const TargetRegisterClass *RC,
52 const TargetRegisterInfo *TRI) {
53 increaseSetPressure(MaxSetPressure, MaxSetPressure, RC, TRI);
56 /// Directly decrease pressure only within this RegisterPressure result.
57 void RegisterPressure::decrease(const TargetRegisterClass *RC,
58 const TargetRegisterInfo *TRI) {
59 decreaseSetPressure(MaxSetPressure, RC, TRI);
62 /// Increase the current pressure as impacted by these physical registers and
63 /// bump the high water mark if needed.
64 void RegPressureTracker::increasePhysRegPressure(ArrayRef<unsigned> Regs) {
65 for (unsigned I = 0, E = Regs.size(); I != E; ++I)
66 increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
67 TRI->getMinimalPhysRegClass(Regs[I]), TRI);
70 /// Simply decrease the current pressure as impacted by these physcial
72 void RegPressureTracker::decreasePhysRegPressure(ArrayRef<unsigned> Regs) {
73 for (unsigned I = 0, E = Regs.size(); I != E; ++I)
74 decreaseSetPressure(CurrSetPressure, TRI->getMinimalPhysRegClass(Regs[I]),
78 /// Increase the current pressure as impacted by these virtual registers and
79 /// bump the high water mark if needed.
80 void RegPressureTracker::increaseVirtRegPressure(ArrayRef<unsigned> Regs) {
81 for (unsigned I = 0, E = Regs.size(); I != E; ++I)
82 increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
83 MRI->getRegClass(Regs[I]), TRI);
86 /// Simply decrease the current pressure as impacted by these virtual registers.
87 void RegPressureTracker::decreaseVirtRegPressure(ArrayRef<unsigned> Regs) {
88 for (unsigned I = 0, E = Regs.size(); I != E; ++I)
89 decreaseSetPressure(CurrSetPressure, MRI->getRegClass(Regs[I]), TRI);
92 /// Clear the result so it can be used for another round of pressure tracking.
93 void IntervalPressure::reset() {
94 TopIdx = BottomIdx = SlotIndex();
95 MaxSetPressure.clear();
100 /// Clear the result so it can be used for another round of pressure tracking.
101 void RegionPressure::reset() {
102 TopPos = BottomPos = MachineBasicBlock::const_iterator();
103 MaxSetPressure.clear();
108 /// If the current top is not less than or equal to the next index, open it.
109 /// We happen to need the SlotIndex for the next top for pressure update.
110 void IntervalPressure::openTop(SlotIndex NextTop) {
111 if (TopIdx <= NextTop)
113 TopIdx = SlotIndex();
117 /// If the current top is the previous instruction (before receding), open it.
118 void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
119 if (TopPos != PrevTop)
121 TopPos = MachineBasicBlock::const_iterator();
125 /// If the current bottom is not greater than the previous index, open it.
126 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
127 if (BottomIdx > PrevBottom)
129 BottomIdx = SlotIndex();
133 /// If the current bottom is the previous instr (before advancing), open it.
134 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
135 if (BottomPos != PrevBottom)
137 BottomPos = MachineBasicBlock::const_iterator();
141 /// Setup the RegPressureTracker.
143 /// TODO: Add support for pressure without LiveIntervals.
144 void RegPressureTracker::init(const MachineFunction *mf,
145 const RegisterClassInfo *rci,
146 const LiveIntervals *lis,
147 const MachineBasicBlock *mbb,
148 MachineBasicBlock::const_iterator pos)
151 TRI = MF->getTarget().getRegisterInfo();
153 MRI = &MF->getRegInfo();
156 if (RequireIntervals) {
157 assert(lis && "IntervalPressure requires LiveIntervals");
162 while (CurrPos != MBB->end() && CurrPos->isDebugValue())
165 CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
167 if (RequireIntervals)
168 static_cast<IntervalPressure&>(P).reset();
170 static_cast<RegionPressure&>(P).reset();
171 P.MaxSetPressure = CurrSetPressure;
173 LivePhysRegs.clear();
174 LivePhysRegs.setUniverse(TRI->getNumRegs());
175 LiveVirtRegs.clear();
176 LiveVirtRegs.setUniverse(MRI->getNumVirtRegs());
179 /// Does this pressure result have a valid top position and live ins.
180 bool RegPressureTracker::isTopClosed() const {
181 if (RequireIntervals)
182 return static_cast<IntervalPressure&>(P).TopIdx.isValid();
183 return (static_cast<RegionPressure&>(P).TopPos ==
184 MachineBasicBlock::const_iterator());
187 /// Does this pressure result have a valid bottom position and live outs.
188 bool RegPressureTracker::isBottomClosed() const {
189 if (RequireIntervals)
190 return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
191 return (static_cast<RegionPressure&>(P).BottomPos ==
192 MachineBasicBlock::const_iterator());
195 /// Set the boundary for the top of the region and summarize live ins.
196 void RegPressureTracker::closeTop() {
197 if (RequireIntervals)
198 static_cast<IntervalPressure&>(P).TopIdx =
199 LIS->getInstructionIndex(CurrPos).getRegSlot();
201 static_cast<RegionPressure&>(P).TopPos = CurrPos;
203 assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
204 P.LiveInRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
205 P.LiveInRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
206 for (SparseSet<unsigned>::const_iterator I =
207 LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
208 P.LiveInRegs.push_back(*I);
209 std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end());
210 P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()),
214 /// Set the boundary for the bottom of the region and summarize live outs.
215 void RegPressureTracker::closeBottom() {
216 if (RequireIntervals)
217 if (CurrPos == MBB->end())
218 static_cast<IntervalPressure&>(P).BottomIdx = LIS->getMBBEndIdx(MBB);
220 static_cast<IntervalPressure&>(P).BottomIdx =
221 LIS->getInstructionIndex(CurrPos).getRegSlot();
223 static_cast<RegionPressure&>(P).BottomPos = CurrPos;
225 assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
226 P.LiveOutRegs.reserve(LivePhysRegs.size() + LiveVirtRegs.size());
227 P.LiveOutRegs.append(LivePhysRegs.begin(), LivePhysRegs.end());
228 for (SparseSet<unsigned>::const_iterator I =
229 LiveVirtRegs.begin(), E = LiveVirtRegs.end(); I != E; ++I)
230 P.LiveOutRegs.push_back(*I);
231 std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end());
232 P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()),
233 P.LiveOutRegs.end());
236 /// Finalize the region boundaries and record live ins and live outs.
237 void RegPressureTracker::closeRegion() {
238 if (!isTopClosed() && !isBottomClosed()) {
239 assert(LivePhysRegs.empty() && LiveVirtRegs.empty() &&
240 "no region boundary");
243 if (!isBottomClosed())
245 else if (!isTopClosed())
247 // If both top and bottom are closed, do nothing.
250 /// Return true if Reg aliases a register in Regs SparseSet.
251 static bool hasRegAlias(unsigned Reg, SparseSet<unsigned> &Regs,
252 const TargetRegisterInfo *TRI) {
253 assert(!TargetRegisterInfo::isVirtualRegister(Reg) && "only for physregs");
254 for (const uint16_t *Alias = TRI->getOverlaps(Reg); *Alias; ++Alias) {
255 if (Regs.count(*Alias))
261 /// Return true if Reg aliases a register in unsorted Regs SmallVector.
262 /// This is only valid for physical registers.
263 static SmallVectorImpl<unsigned>::iterator
264 findRegAlias(unsigned Reg, SmallVectorImpl<unsigned> &Regs,
265 const TargetRegisterInfo *TRI) {
266 for (const uint16_t *Alias = TRI->getOverlaps(Reg); *Alias; ++Alias) {
267 SmallVectorImpl<unsigned>::iterator I =
268 std::find(Regs.begin(), Regs.end(), *Alias);
275 /// Return true if Reg can be inserted into Regs SmallVector. For virtual
276 /// register, do a linear search. For physical registers check for aliases.
277 static SmallVectorImpl<unsigned>::iterator
278 findReg(unsigned Reg, bool isVReg, SmallVectorImpl<unsigned> &Regs,
279 const TargetRegisterInfo *TRI) {
281 return std::find(Regs.begin(), Regs.end(), Reg);
282 return findRegAlias(Reg, Regs, TRI);
285 /// Collect this instruction's unique uses and defs into SmallVectors for
286 /// processing defs and uses in order.
287 template<bool isVReg>
288 struct RegisterOperands {
289 SmallVector<unsigned, 8> Uses;
290 SmallVector<unsigned, 8> Defs;
291 SmallVector<unsigned, 8> DeadDefs;
293 /// Push this operand's register onto the correct vector.
294 void collect(const MachineOperand &MO, const TargetRegisterInfo *TRI) {
296 if (findReg(MO.getReg(), isVReg, Uses, TRI) == Uses.end())
297 Uses.push_back(MO.getReg());
301 if (findReg(MO.getReg(), isVReg, DeadDefs, TRI) == DeadDefs.end())
302 DeadDefs.push_back(MO.getReg());
305 if (findReg(MO.getReg(), isVReg, Defs, TRI) == Defs.end())
306 Defs.push_back(MO.getReg());
311 typedef RegisterOperands<false> PhysRegOperands;
312 typedef RegisterOperands<true> VirtRegOperands;
314 /// Collect physical and virtual register operands.
315 static void collectOperands(const MachineInstr *MI,
316 PhysRegOperands &PhysRegOpers,
317 VirtRegOperands &VirtRegOpers,
318 const TargetRegisterInfo *TRI,
319 const RegisterClassInfo *RCI) {
320 for(ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI) {
321 const MachineOperand &MO = *OperI;
322 if (!MO.isReg() || !MO.getReg())
325 if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
326 VirtRegOpers.collect(MO, TRI);
327 else if (RCI->isAllocatable(MO.getReg()))
328 PhysRegOpers.collect(MO, TRI);
330 // Remove redundant physreg dead defs.
331 for (unsigned i = PhysRegOpers.DeadDefs.size(); i > 0; --i) {
332 unsigned Reg = PhysRegOpers.DeadDefs[i-1];
333 if (findRegAlias(Reg, PhysRegOpers.Defs, TRI) != PhysRegOpers.Defs.end())
334 PhysRegOpers.DeadDefs.erase(&PhysRegOpers.DeadDefs[i-1]);
338 /// Add PhysReg to the live in set and increase max pressure.
339 void RegPressureTracker::discoverPhysLiveIn(unsigned Reg) {
340 assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
341 if (findRegAlias(Reg, P.LiveInRegs, TRI) == P.LiveInRegs.end())
344 // At live in discovery, unconditionally increase the high water mark.
345 P.LiveInRegs.push_back(Reg);
346 P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
349 /// Add PhysReg to the live out set and increase max pressure.
350 void RegPressureTracker::discoverPhysLiveOut(unsigned Reg) {
351 assert(!LivePhysRegs.count(Reg) && "avoid bumping max pressure twice");
352 if (findRegAlias(Reg, P.LiveOutRegs, TRI) == P.LiveOutRegs.end())
355 // At live out discovery, unconditionally increase the high water mark.
356 P.LiveOutRegs.push_back(Reg);
357 P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
360 /// Add VirtReg to the live in set and increase max pressure.
361 void RegPressureTracker::discoverVirtLiveIn(unsigned Reg) {
362 assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
363 if (std::find(P.LiveInRegs.begin(), P.LiveInRegs.end(), Reg) !=
367 // At live in discovery, unconditionally increase the high water mark.
368 P.LiveInRegs.push_back(Reg);
369 P.increase(MRI->getRegClass(Reg), TRI);
372 /// Add VirtReg to the live out set and increase max pressure.
373 void RegPressureTracker::discoverVirtLiveOut(unsigned Reg) {
374 assert(!LiveVirtRegs.count(Reg) && "avoid bumping max pressure twice");
375 if (std::find(P.LiveOutRegs.begin(), P.LiveOutRegs.end(), Reg) !=
379 // At live out discovery, unconditionally increase the high water mark.
380 P.LiveOutRegs.push_back(Reg);
381 P.increase(MRI->getRegClass(Reg), TRI);
384 /// Recede across the previous instruction.
385 bool RegPressureTracker::recede() {
386 // Check for the top of the analyzable region.
387 if (CurrPos == MBB->begin()) {
391 if (!isBottomClosed())
394 // Open the top of the region using block iterators.
395 if (!RequireIntervals && isTopClosed())
396 static_cast<RegionPressure&>(P).openTop(CurrPos);
398 // Find the previous instruction.
401 while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
403 if (CurrPos->isDebugValue()) {
408 if (RequireIntervals)
409 SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
411 // Open the top of the region using slot indexes.
412 if (RequireIntervals && isTopClosed())
413 static_cast<IntervalPressure&>(P).openTop(SlotIdx);
415 PhysRegOperands PhysRegOpers;
416 VirtRegOperands VirtRegOpers;
417 collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
419 // Boost pressure for all dead defs together.
420 increasePhysRegPressure(PhysRegOpers.DeadDefs);
421 increaseVirtRegPressure(VirtRegOpers.DeadDefs);
422 decreasePhysRegPressure(PhysRegOpers.DeadDefs);
423 decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
425 // Kill liveness at live defs.
426 // TODO: consider earlyclobbers?
427 for (unsigned i = 0; i < PhysRegOpers.Defs.size(); ++i) {
428 unsigned Reg = PhysRegOpers.Defs[i];
429 if (LivePhysRegs.erase(Reg))
430 decreasePhysRegPressure(Reg);
432 discoverPhysLiveOut(Reg);
434 for (unsigned i = 0; i < VirtRegOpers.Defs.size(); ++i) {
435 unsigned Reg = VirtRegOpers.Defs[i];
436 if (LiveVirtRegs.erase(Reg))
437 decreaseVirtRegPressure(Reg);
439 discoverVirtLiveOut(Reg);
442 // Generate liveness for uses.
443 for (unsigned i = 0; i < PhysRegOpers.Uses.size(); ++i) {
444 unsigned Reg = PhysRegOpers.Uses[i];
445 if (!hasRegAlias(Reg, LivePhysRegs, TRI)) {
446 increasePhysRegPressure(Reg);
447 LivePhysRegs.insert(Reg);
450 for (unsigned i = 0; i < VirtRegOpers.Uses.size(); ++i) {
451 unsigned Reg = VirtRegOpers.Uses[i];
452 if (!LiveVirtRegs.count(Reg)) {
453 // Adjust liveouts if LiveIntervals are available.
454 if (RequireIntervals) {
455 const LiveInterval *LI = &LIS->getInterval(Reg);
456 if (!LI->killedAt(SlotIdx))
457 discoverVirtLiveOut(Reg);
459 increaseVirtRegPressure(Reg);
460 LiveVirtRegs.insert(Reg);
466 /// Advance across the current instruction.
467 bool RegPressureTracker::advance() {
468 // Check for the bottom of the analyzable region.
469 if (CurrPos == MBB->end()) {
477 if (RequireIntervals)
478 SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
480 // Open the bottom of the region using slot indexes.
481 if (isBottomClosed()) {
482 if (RequireIntervals)
483 static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
485 static_cast<RegionPressure&>(P).openBottom(CurrPos);
488 PhysRegOperands PhysRegOpers;
489 VirtRegOperands VirtRegOpers;
490 collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
492 // Kill liveness at last uses.
493 for (unsigned i = 0; i < PhysRegOpers.Uses.size(); ++i) {
494 unsigned Reg = PhysRegOpers.Uses[i];
495 if (!hasRegAlias(Reg, LivePhysRegs, TRI))
496 discoverPhysLiveIn(Reg);
498 // Allocatable physregs are always single-use before regalloc.
499 decreasePhysRegPressure(Reg);
500 LivePhysRegs.erase(Reg);
503 for (unsigned i = 0; i < VirtRegOpers.Uses.size(); ++i) {
504 unsigned Reg = VirtRegOpers.Uses[i];
505 if (RequireIntervals) {
506 const LiveInterval *LI = &LIS->getInterval(Reg);
507 if (LI->killedAt(SlotIdx)) {
508 if (LiveVirtRegs.erase(Reg))
509 decreaseVirtRegPressure(Reg);
511 discoverVirtLiveIn(Reg);
514 else if (!LiveVirtRegs.count(Reg)) {
515 discoverVirtLiveIn(Reg);
516 increaseVirtRegPressure(Reg);
520 // Generate liveness for defs.
521 for (unsigned i = 0; i < PhysRegOpers.Defs.size(); ++i) {
522 unsigned Reg = PhysRegOpers.Defs[i];
523 if (!hasRegAlias(Reg, LivePhysRegs, TRI)) {
524 increasePhysRegPressure(Reg);
525 LivePhysRegs.insert(Reg);
528 for (unsigned i = 0; i < VirtRegOpers.Defs.size(); ++i) {
529 unsigned Reg = VirtRegOpers.Defs[i];
530 if (LiveVirtRegs.insert(Reg).second)
531 increaseVirtRegPressure(Reg);
534 // Boost pressure for all dead defs together.
535 increasePhysRegPressure(PhysRegOpers.DeadDefs);
536 increaseVirtRegPressure(VirtRegOpers.DeadDefs);
537 decreasePhysRegPressure(PhysRegOpers.DeadDefs);
538 decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
540 // Find the next instruction.
543 while (CurrPos != MBB->end() && CurrPos->isDebugValue());