RegisterPressure: ArrayRefize some functions for better readability. No functionality...
[oota-llvm.git] / lib / CodeGen / RegisterPressure.cpp
1 //===-- RegisterPressure.cpp - Dynamic Register Pressure ------------------===//
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 // This file implements the RegisterPressure class which can be used to track
11 // MachineInstr level register pressure.
12 //
13 //===----------------------------------------------------------------------===//
14
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"
21
22 using namespace llvm;
23
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];
35   }
36 }
37
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;
47   }
48 }
49
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);
54 }
55
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);
60 }
61
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);
68 }
69
70 /// Simply decrease the current pressure as impacted by these physcial
71 /// registers.
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]),
75                         TRI);
76 }
77
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);
84 }
85
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);
90 }
91
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();
96   LiveInRegs.clear();
97   LiveOutRegs.clear();
98 }
99
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();
104   LiveInRegs.clear();
105   LiveOutRegs.clear();
106 }
107
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)
112     return;
113   TopIdx = SlotIndex();
114   LiveInRegs.clear();
115 }
116
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)
120     return;
121   TopPos = MachineBasicBlock::const_iterator();
122   LiveInRegs.clear();
123 }
124
125 /// If the current bottom is not greater than the previous index, open it.
126 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
127   if (BottomIdx > PrevBottom)
128     return;
129   BottomIdx = SlotIndex();
130   LiveInRegs.clear();
131 }
132
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)
136     return;
137   BottomPos = MachineBasicBlock::const_iterator();
138   LiveInRegs.clear();
139 }
140
141 /// Setup the RegPressureTracker.
142 ///
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)
149 {
150   MF = mf;
151   TRI = MF->getTarget().getRegisterInfo();
152   RCI = rci;
153   MRI = &MF->getRegInfo();
154   MBB = mbb;
155
156   if (RequireIntervals) {
157     assert(lis && "IntervalPressure requires LiveIntervals");
158     LIS = lis;
159   }
160
161   CurrPos = pos;
162   while (CurrPos != MBB->end() && CurrPos->isDebugValue())
163     ++CurrPos;
164
165   CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
166
167   if (RequireIntervals)
168     static_cast<IntervalPressure&>(P).reset();
169   else
170     static_cast<RegionPressure&>(P).reset();
171   P.MaxSetPressure = CurrSetPressure;
172
173   LivePhysRegs.clear();
174   LivePhysRegs.setUniverse(TRI->getNumRegs());
175   LiveVirtRegs.clear();
176   LiveVirtRegs.setUniverse(MRI->getNumVirtRegs());
177 }
178
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());
185 }
186
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());
193 }
194
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();
200   else
201     static_cast<RegionPressure&>(P).TopPos = CurrPos;
202
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()),
211                      P.LiveInRegs.end());
212 }
213
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);
219     else
220       static_cast<IntervalPressure&>(P).BottomIdx =
221         LIS->getInstructionIndex(CurrPos).getRegSlot();
222   else
223     static_cast<RegionPressure&>(P).BottomPos = CurrPos;
224
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());
234 }
235
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");
241     return;
242   }
243   if (!isBottomClosed())
244     closeBottom();
245   else if (!isTopClosed())
246     closeTop();
247   // If both top and bottom are closed, do nothing.
248 }
249
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))
256       return true;
257   }
258   return false;
259 }
260
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);
269     if (I != Regs.end())
270       return I;
271   }
272   return Regs.end();
273 }
274
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) {
280   if(isVReg)
281     return std::find(Regs.begin(), Regs.end(), Reg);
282   return findRegAlias(Reg, Regs, TRI);
283 }
284
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;
292
293   /// Push this operand's register onto the correct vector.
294   void collect(const MachineOperand &MO, const TargetRegisterInfo *TRI) {
295     if (MO.readsReg()) {
296       if (findReg(MO.getReg(), isVReg, Uses, TRI) == Uses.end())
297       Uses.push_back(MO.getReg());
298     }
299     if (MO.isDef()) {
300       if (MO.isDead()) {
301         if (findReg(MO.getReg(), isVReg, DeadDefs, TRI) == DeadDefs.end())
302           DeadDefs.push_back(MO.getReg());
303       }
304       else {
305         if (findReg(MO.getReg(), isVReg, Defs, TRI) == Defs.end())
306           Defs.push_back(MO.getReg());
307       }
308     }
309   }
310 };
311 typedef RegisterOperands<false> PhysRegOperands;
312 typedef RegisterOperands<true> VirtRegOperands;
313
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())
323       continue;
324
325     if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
326       VirtRegOpers.collect(MO, TRI);
327     else if (RCI->isAllocatable(MO.getReg()))
328       PhysRegOpers.collect(MO, TRI);
329   }
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]);
335   }
336 }
337
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())
342     return;
343
344   // At live in discovery, unconditionally increase the high water mark.
345   P.LiveInRegs.push_back(Reg);
346   P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
347 }
348
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())
353     return;
354
355   // At live out discovery, unconditionally increase the high water mark.
356   P.LiveOutRegs.push_back(Reg);
357   P.increase(TRI->getMinimalPhysRegClass(Reg), TRI);
358 }
359
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) !=
364       P.LiveInRegs.end())
365     return;
366
367   // At live in discovery, unconditionally increase the high water mark.
368   P.LiveInRegs.push_back(Reg);
369   P.increase(MRI->getRegClass(Reg), TRI);
370 }
371
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) !=
376       P.LiveOutRegs.end())
377     return;
378
379   // At live out discovery, unconditionally increase the high water mark.
380   P.LiveOutRegs.push_back(Reg);
381   P.increase(MRI->getRegClass(Reg), TRI);
382 }
383
384 /// Recede across the previous instruction.
385 bool RegPressureTracker::recede() {
386   // Check for the top of the analyzable region.
387   if (CurrPos == MBB->begin()) {
388     closeRegion();
389     return false;
390   }
391   if (!isBottomClosed())
392     closeBottom();
393
394   // Open the top of the region using block iterators.
395   if (!RequireIntervals && isTopClosed())
396     static_cast<RegionPressure&>(P).openTop(CurrPos);
397
398   // Find the previous instruction.
399   do
400     --CurrPos;
401   while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
402
403   if (CurrPos->isDebugValue()) {
404     closeRegion();
405     return false;
406   }
407   SlotIndex SlotIdx;
408   if (RequireIntervals)
409     SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
410
411   // Open the top of the region using slot indexes.
412   if (RequireIntervals && isTopClosed())
413     static_cast<IntervalPressure&>(P).openTop(SlotIdx);
414
415   PhysRegOperands PhysRegOpers;
416   VirtRegOperands VirtRegOpers;
417   collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
418
419   // Boost pressure for all dead defs together.
420   increasePhysRegPressure(PhysRegOpers.DeadDefs);
421   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
422   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
423   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
424
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);
431     else
432       discoverPhysLiveOut(Reg);
433   }
434   for (unsigned i = 0; i < VirtRegOpers.Defs.size(); ++i) {
435     unsigned Reg = VirtRegOpers.Defs[i];
436     if (LiveVirtRegs.erase(Reg))
437       decreaseVirtRegPressure(Reg);
438     else
439       discoverVirtLiveOut(Reg);
440   }
441
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);
448     }
449   }
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);
458       }
459       increaseVirtRegPressure(Reg);
460       LiveVirtRegs.insert(Reg);
461     }
462   }
463   return true;
464 }
465
466 /// Advance across the current instruction.
467 bool RegPressureTracker::advance() {
468   // Check for the bottom of the analyzable region.
469   if (CurrPos == MBB->end()) {
470     closeRegion();
471     return false;
472   }
473   if (!isTopClosed())
474     closeTop();
475
476   SlotIndex SlotIdx;
477   if (RequireIntervals)
478     SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
479
480   // Open the bottom of the region using slot indexes.
481   if (isBottomClosed()) {
482     if (RequireIntervals)
483       static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
484     else
485       static_cast<RegionPressure&>(P).openBottom(CurrPos);
486   }
487
488   PhysRegOperands PhysRegOpers;
489   VirtRegOperands VirtRegOpers;
490   collectOperands(CurrPos, PhysRegOpers, VirtRegOpers, TRI, RCI);
491
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);
497     else {
498       // Allocatable physregs are always single-use before regalloc.
499       decreasePhysRegPressure(Reg);
500       LivePhysRegs.erase(Reg);
501     }
502   }
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);
510         else
511           discoverVirtLiveIn(Reg);
512       }
513     }
514     else if (!LiveVirtRegs.count(Reg)) {
515       discoverVirtLiveIn(Reg);
516       increaseVirtRegPressure(Reg);
517     }
518   }
519
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);
526     }
527   }
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);
532   }
533
534   // Boost pressure for all dead defs together.
535   increasePhysRegPressure(PhysRegOpers.DeadDefs);
536   increaseVirtRegPressure(VirtRegOpers.DeadDefs);
537   decreasePhysRegPressure(PhysRegOpers.DeadDefs);
538   decreaseVirtRegPressure(VirtRegOpers.DeadDefs);
539
540   // Find the next instruction.
541   do
542     ++CurrPos;
543   while (CurrPos != MBB->end() && CurrPos->isDebugValue());
544   return true;
545 }