Lang Hames | a937f22 | 2009-12-14 06:49:42 +0000 | [diff] [blame] | 1 | //===------------------------ CalcSpillWeights.cpp ------------------------===// |
| 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 | #define DEBUG_TYPE "calcspillweights" |
| 11 | |
Lang Hames | a937f22 | 2009-12-14 06:49:42 +0000 | [diff] [blame] | 12 | #include "llvm/CodeGen/CalcSpillWeights.h" |
| 13 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
Benjamin Kramer | 4eed756 | 2013-06-17 19:00:36 +0000 | [diff] [blame] | 14 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
Lang Hames | a937f22 | 2009-12-14 06:49:42 +0000 | [diff] [blame] | 15 | #include "llvm/CodeGen/MachineFunction.h" |
| 16 | #include "llvm/CodeGen/MachineLoopInfo.h" |
| 17 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Lang Hames | a937f22 | 2009-12-14 06:49:42 +0000 | [diff] [blame] | 18 | #include "llvm/Support/Debug.h" |
| 19 | #include "llvm/Support/raw_ostream.h" |
| 20 | #include "llvm/Target/TargetInstrInfo.h" |
Evan Cheng | 8112b53 | 2010-02-10 01:21:02 +0000 | [diff] [blame] | 21 | #include "llvm/Target/TargetMachine.h" |
Lang Hames | a937f22 | 2009-12-14 06:49:42 +0000 | [diff] [blame] | 22 | #include "llvm/Target/TargetRegisterInfo.h" |
Lang Hames | a937f22 | 2009-12-14 06:49:42 +0000 | [diff] [blame] | 23 | using namespace llvm; |
| 24 | |
Arnaud A. de Grandmaison | 095f994 | 2013-11-11 19:04:45 +0000 | [diff] [blame^] | 25 | void llvm::calculateSpillWeightsAndHints(LiveIntervals &LIS, |
Arnaud A. de Grandmaison | a77da05 | 2013-11-10 17:46:31 +0000 | [diff] [blame] | 26 | MachineFunction &MF, |
| 27 | const MachineLoopInfo &MLI, |
| 28 | const MachineBlockFrequencyInfo &MBFI) { |
David Greene | 7ed6dd6 | 2009-12-24 00:39:02 +0000 | [diff] [blame] | 29 | DEBUG(dbgs() << "********** Compute Spill Weights **********\n" |
David Blaikie | 986d76d | 2012-08-22 17:18:53 +0000 | [diff] [blame] | 30 | << "********** Function: " << MF.getName() << '\n'); |
Lang Hames | a937f22 | 2009-12-14 06:49:42 +0000 | [diff] [blame] | 31 | |
Jakob Stoklund Olesen | d67582e | 2012-06-20 21:25:05 +0000 | [diff] [blame] | 32 | MachineRegisterInfo &MRI = MF.getRegInfo(); |
Arnaud A. de Grandmaison | a77da05 | 2013-11-10 17:46:31 +0000 | [diff] [blame] | 33 | VirtRegAuxInfo VRAI(MF, LIS, MLI, MBFI); |
Jakob Stoklund Olesen | d67582e | 2012-06-20 21:25:05 +0000 | [diff] [blame] | 34 | for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) { |
| 35 | unsigned Reg = TargetRegisterInfo::index2VirtReg(i); |
| 36 | if (MRI.reg_nodbg_empty(Reg)) |
| 37 | continue; |
Arnaud A. de Grandmaison | 095f994 | 2013-11-11 19:04:45 +0000 | [diff] [blame^] | 38 | VRAI.calculateSpillWeightAndHint(LIS.getInterval(Reg)); |
Lang Hames | a937f22 | 2009-12-14 06:49:42 +0000 | [diff] [blame] | 39 | } |
Lang Hames | a937f22 | 2009-12-14 06:49:42 +0000 | [diff] [blame] | 40 | } |
| 41 | |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 42 | // Return the preferred allocation register for reg, given a COPY instruction. |
| 43 | static unsigned copyHint(const MachineInstr *mi, unsigned reg, |
| 44 | const TargetRegisterInfo &tri, |
| 45 | const MachineRegisterInfo &mri) { |
| 46 | unsigned sub, hreg, hsub; |
| 47 | if (mi->getOperand(0).getReg() == reg) { |
| 48 | sub = mi->getOperand(0).getSubReg(); |
| 49 | hreg = mi->getOperand(1).getReg(); |
| 50 | hsub = mi->getOperand(1).getSubReg(); |
| 51 | } else { |
| 52 | sub = mi->getOperand(1).getSubReg(); |
| 53 | hreg = mi->getOperand(0).getReg(); |
| 54 | hsub = mi->getOperand(0).getSubReg(); |
| 55 | } |
| 56 | |
| 57 | if (!hreg) |
| 58 | return 0; |
| 59 | |
| 60 | if (TargetRegisterInfo::isVirtualRegister(hreg)) |
| 61 | return sub == hsub ? hreg : 0; |
| 62 | |
| 63 | const TargetRegisterClass *rc = mri.getRegClass(reg); |
| 64 | |
| 65 | // Only allow physreg hints in rc. |
| 66 | if (sub == 0) |
| 67 | return rc->contains(hreg) ? hreg : 0; |
| 68 | |
| 69 | // reg:sub should match the physreg hreg. |
| 70 | return tri.getMatchingSuperReg(hreg, sub, rc); |
Lang Hames | a937f22 | 2009-12-14 06:49:42 +0000 | [diff] [blame] | 71 | } |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 72 | |
Jakob Stoklund Olesen | 3dfd59b | 2012-06-05 01:06:12 +0000 | [diff] [blame] | 73 | // Check if all values in LI are rematerializable |
| 74 | static bool isRematerializable(const LiveInterval &LI, |
| 75 | const LiveIntervals &LIS, |
| 76 | const TargetInstrInfo &TII) { |
| 77 | for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); |
| 78 | I != E; ++I) { |
| 79 | const VNInfo *VNI = *I; |
| 80 | if (VNI->isUnused()) |
| 81 | continue; |
| 82 | if (VNI->isPHIDef()) |
| 83 | return false; |
| 84 | |
| 85 | MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); |
| 86 | assert(MI && "Dead valno in interval"); |
| 87 | |
| 88 | if (!TII.isTriviallyReMaterializable(MI, LIS.getAliasAnalysis())) |
| 89 | return false; |
| 90 | } |
| 91 | return true; |
| 92 | } |
| 93 | |
Benjamin Kramer | 4eed756 | 2013-06-17 19:00:36 +0000 | [diff] [blame] | 94 | void |
Arnaud A. de Grandmaison | 095f994 | 2013-11-11 19:04:45 +0000 | [diff] [blame^] | 95 | VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &li) { |
Jakob Stoklund Olesen | 1394e6d | 2011-04-26 18:52:36 +0000 | [diff] [blame] | 96 | MachineRegisterInfo &mri = MF.getRegInfo(); |
| 97 | const TargetRegisterInfo &tri = *MF.getTarget().getRegisterInfo(); |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 98 | MachineBasicBlock *mbb = 0; |
| 99 | MachineLoop *loop = 0; |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 100 | bool isExiting = false; |
| 101 | float totalWeight = 0; |
| 102 | SmallPtrSet<MachineInstr*, 8> visited; |
| 103 | |
Nadav Rotem | 6e01dcb | 2013-04-06 04:24:12 +0000 | [diff] [blame] | 104 | // Find the best physreg hint and the best virtreg hint. |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 105 | float bestPhys = 0, bestVirt = 0; |
| 106 | unsigned hintPhys = 0, hintVirt = 0; |
| 107 | |
| 108 | // Don't recompute a target specific hint. |
| 109 | bool noHint = mri.getRegAllocationHint(li.reg).first != 0; |
| 110 | |
Jakob Stoklund Olesen | 6094bd8 | 2011-03-29 21:20:19 +0000 | [diff] [blame] | 111 | // Don't recompute spill weight for an unspillable register. |
| 112 | bool Spillable = li.isSpillable(); |
| 113 | |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 114 | for (MachineRegisterInfo::reg_iterator I = mri.reg_begin(li.reg); |
| 115 | MachineInstr *mi = I.skipInstruction();) { |
| 116 | if (mi->isIdentityCopy() || mi->isImplicitDef() || mi->isDebugValue()) |
| 117 | continue; |
| 118 | if (!visited.insert(mi)) |
| 119 | continue; |
| 120 | |
Jakob Stoklund Olesen | 6094bd8 | 2011-03-29 21:20:19 +0000 | [diff] [blame] | 121 | float weight = 1.0f; |
| 122 | if (Spillable) { |
| 123 | // Get loop info for mi. |
| 124 | if (mi->getParent() != mbb) { |
| 125 | mbb = mi->getParent(); |
Jakob Stoklund Olesen | 1394e6d | 2011-04-26 18:52:36 +0000 | [diff] [blame] | 126 | loop = Loops.getLoopFor(mbb); |
Jakob Stoklund Olesen | 6094bd8 | 2011-03-29 21:20:19 +0000 | [diff] [blame] | 127 | isExiting = loop ? loop->isLoopExiting(mbb) : false; |
| 128 | } |
| 129 | |
| 130 | // Calculate instr weight. |
| 131 | bool reads, writes; |
| 132 | tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg); |
Benjamin Kramer | 4eed756 | 2013-06-17 19:00:36 +0000 | [diff] [blame] | 133 | weight = LiveIntervals::getSpillWeight( |
| 134 | writes, reads, MBFI.getBlockFreq(mi->getParent())); |
Jakob Stoklund Olesen | 6094bd8 | 2011-03-29 21:20:19 +0000 | [diff] [blame] | 135 | |
| 136 | // Give extra weight to what looks like a loop induction variable update. |
Jakob Stoklund Olesen | 1394e6d | 2011-04-26 18:52:36 +0000 | [diff] [blame] | 137 | if (writes && isExiting && LIS.isLiveOutOfMBB(li, mbb)) |
Jakob Stoklund Olesen | 6094bd8 | 2011-03-29 21:20:19 +0000 | [diff] [blame] | 138 | weight *= 3; |
| 139 | |
| 140 | totalWeight += weight; |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 141 | } |
| 142 | |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 143 | // Get allocation hints from copies. |
| 144 | if (noHint || !mi->isCopy()) |
| 145 | continue; |
| 146 | unsigned hint = copyHint(mi, li.reg, tri, mri); |
| 147 | if (!hint) |
| 148 | continue; |
Jakob Stoklund Olesen | 1394e6d | 2011-04-26 18:52:36 +0000 | [diff] [blame] | 149 | float hweight = Hint[hint] += weight; |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 150 | if (TargetRegisterInfo::isPhysicalRegister(hint)) { |
Jakob Stoklund Olesen | 7900476 | 2012-10-15 22:14:34 +0000 | [diff] [blame] | 151 | if (hweight > bestPhys && mri.isAllocatable(hint)) |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 152 | bestPhys = hweight, hintPhys = hint; |
| 153 | } else { |
| 154 | if (hweight > bestVirt) |
| 155 | bestVirt = hweight, hintVirt = hint; |
| 156 | } |
| 157 | } |
| 158 | |
Jakob Stoklund Olesen | 1394e6d | 2011-04-26 18:52:36 +0000 | [diff] [blame] | 159 | Hint.clear(); |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 160 | |
| 161 | // Always prefer the physreg hint. |
| 162 | if (unsigned hint = hintPhys ? hintPhys : hintVirt) { |
| 163 | mri.setRegAllocationHint(li.reg, 0, hint); |
Jakob Stoklund Olesen | 6094bd8 | 2011-03-29 21:20:19 +0000 | [diff] [blame] | 164 | // Weakly boost the spill weight of hinted registers. |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 165 | totalWeight *= 1.01F; |
| 166 | } |
| 167 | |
Jakob Stoklund Olesen | 6094bd8 | 2011-03-29 21:20:19 +0000 | [diff] [blame] | 168 | // If the live interval was already unspillable, leave it that way. |
| 169 | if (!Spillable) |
| 170 | return; |
| 171 | |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 172 | // Mark li as unspillable if all live ranges are tiny. |
Jakob Stoklund Olesen | f5497fb | 2011-05-16 23:50:05 +0000 | [diff] [blame] | 173 | if (li.isZeroLength(LIS.getSlotIndexes())) { |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 174 | li.markNotSpillable(); |
| 175 | return; |
| 176 | } |
| 177 | |
| 178 | // If all of the definitions of the interval are re-materializable, |
Jakob Stoklund Olesen | 3dfd59b | 2012-06-05 01:06:12 +0000 | [diff] [blame] | 179 | // it is a preferred candidate for spilling. |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 180 | // FIXME: this gets much more complicated once we support non-trivial |
| 181 | // re-materialization. |
Jakob Stoklund Olesen | 3dfd59b | 2012-06-05 01:06:12 +0000 | [diff] [blame] | 182 | if (isRematerializable(li, LIS, *MF.getTarget().getInstrInfo())) |
| 183 | totalWeight *= 0.5F; |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 184 | |
Jakob Stoklund Olesen | eb9f040 | 2011-02-14 23:15:38 +0000 | [diff] [blame] | 185 | li.weight = normalizeSpillWeight(totalWeight, li.getSize()); |
Jakob Stoklund Olesen | df30cf9 | 2010-08-10 00:02:26 +0000 | [diff] [blame] | 186 | } |