Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 1 | //===-- RegisterScavenging.cpp - Machine register scavenging --------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements the machine register scavenger. It can provide |
| 11 | // information such as unused register at any point in a machine basic block. |
| 12 | // It also provides a mechanism to make registers availbale by evicting them |
| 13 | // to spill slots. |
| 14 | // |
| 15 | //===----------------------------------------------------------------------===// |
| 16 | |
| 17 | #define DEBUG_TYPE "reg-scavenging" |
| 18 | #include "llvm/CodeGen/RegisterScavenging.h" |
| 19 | #include "llvm/CodeGen/MachineFunction.h" |
| 20 | #include "llvm/CodeGen/MachineBasicBlock.h" |
| 21 | #include "llvm/CodeGen/MachineInstr.h" |
| 22 | #include "llvm/Target/MRegisterInfo.h" |
| 23 | #include "llvm/Target/TargetInstrInfo.h" |
| 24 | #include "llvm/Target/TargetMachine.h" |
Evan Cheng | ed570de | 2007-02-27 01:58:48 +0000 | [diff] [blame] | 25 | #include "llvm/ADT/STLExtras.h" |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 26 | using namespace llvm; |
| 27 | |
Evan Cheng | a3756ee | 2007-03-01 02:19:39 +0000 | [diff] [blame] | 28 | void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { |
Evan Cheng | 898218c | 2007-02-27 22:58:43 +0000 | [diff] [blame] | 29 | const MachineFunction &MF = *mbb->getParent(); |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 30 | const TargetMachine &TM = MF.getTarget(); |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 31 | TII = TM.getInstrInfo(); |
| 32 | RegInfo = TM.getRegisterInfo(); |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 33 | |
Evan Cheng | 898218c | 2007-02-27 22:58:43 +0000 | [diff] [blame] | 34 | assert((NumPhysRegs == 0 || NumPhysRegs == RegInfo->getNumRegs()) && |
| 35 | "Target changed?"); |
| 36 | |
| 37 | if (!MBB) { |
| 38 | NumPhysRegs = RegInfo->getNumRegs(); |
Dale Johannesen | c6b9ef8 | 2007-03-26 22:23:54 +0000 | [diff] [blame] | 39 | RegsAvailable.resize(NumPhysRegs); |
Evan Cheng | 898218c | 2007-02-27 22:58:43 +0000 | [diff] [blame] | 40 | |
Evan Cheng | a3756ee | 2007-03-01 02:19:39 +0000 | [diff] [blame] | 41 | // Create reserved registers bitvector. |
| 42 | ReservedRegs = RegInfo->getReservedRegs(MF); |
| 43 | |
Evan Cheng | 898218c | 2007-02-27 22:58:43 +0000 | [diff] [blame] | 44 | // Create callee-saved registers bitvector. |
| 45 | CalleeSavedRegs.resize(NumPhysRegs); |
| 46 | const unsigned *CSRegs = RegInfo->getCalleeSavedRegs(); |
| 47 | if (CSRegs != NULL) |
| 48 | for (unsigned i = 0; CSRegs[i]; ++i) |
| 49 | CalleeSavedRegs.set(CSRegs[i]); |
| 50 | } |
| 51 | |
| 52 | MBB = mbb; |
Evan Cheng | caddd59 | 2007-03-06 21:58:15 +0000 | [diff] [blame] | 53 | ScavengedReg = 0; |
| 54 | ScavengedRC = NULL; |
Evan Cheng | 898218c | 2007-02-27 22:58:43 +0000 | [diff] [blame] | 55 | |
| 56 | // All registers started out unused. |
Dale Johannesen | c6b9ef8 | 2007-03-26 22:23:54 +0000 | [diff] [blame] | 57 | RegsAvailable.set(); |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 58 | |
Evan Cheng | a3756ee | 2007-03-01 02:19:39 +0000 | [diff] [blame] | 59 | // Reserved registers are always used. |
Dale Johannesen | c6b9ef8 | 2007-03-26 22:23:54 +0000 | [diff] [blame] | 60 | RegsAvailable ^= ReservedRegs; |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 61 | |
Evan Cheng | 403c45d | 2007-02-23 08:41:19 +0000 | [diff] [blame] | 62 | // Live-in registers are in use. |
| 63 | if (!MBB->livein_empty()) |
| 64 | for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), |
| 65 | E = MBB->livein_end(); I != E; ++I) |
| 66 | setUsed(*I); |
Evan Cheng | a3756ee | 2007-03-01 02:19:39 +0000 | [diff] [blame] | 67 | |
| 68 | Tracking = false; |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 69 | } |
| 70 | |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 71 | void RegScavenger::restoreScavengedReg() { |
| 72 | if (!ScavengedReg) |
| 73 | return; |
| 74 | |
| 75 | RegInfo->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg, |
| 76 | ScavengingFrameIndex, ScavengedRC); |
| 77 | MachineBasicBlock::iterator II = prior(MBBI); |
Evan Cheng | 8e33473 | 2007-05-01 09:01:42 +0000 | [diff] [blame] | 78 | RegInfo->eliminateFrameIndex(II, 0, this); |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 79 | setUsed(ScavengedReg); |
| 80 | ScavengedReg = 0; |
| 81 | ScavengedRC = NULL; |
| 82 | } |
| 83 | |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 84 | void RegScavenger::forward() { |
Evan Cheng | ed570de | 2007-02-27 01:58:48 +0000 | [diff] [blame] | 85 | // Move ptr forward. |
Evan Cheng | 898218c | 2007-02-27 22:58:43 +0000 | [diff] [blame] | 86 | if (!Tracking) { |
| 87 | MBBI = MBB->begin(); |
| 88 | Tracking = true; |
| 89 | } else { |
| 90 | assert(MBBI != MBB->end() && "Already at the end of the basic block!"); |
Evan Cheng | ed570de | 2007-02-27 01:58:48 +0000 | [diff] [blame] | 91 | MBBI = next(MBBI); |
Evan Cheng | 898218c | 2007-02-27 22:58:43 +0000 | [diff] [blame] | 92 | } |
Evan Cheng | ed570de | 2007-02-27 01:58:48 +0000 | [diff] [blame] | 93 | |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 94 | MachineInstr *MI = MBBI; |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 95 | |
| 96 | // Reaching a terminator instruction. Restore a scavenged register (which |
| 97 | // must be life out. |
| 98 | if (TII->isTerminatorInstr(MI->getOpcode())) |
| 99 | restoreScavengedReg(); |
| 100 | |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 101 | // Process uses first. |
| 102 | BitVector ChangedRegs(NumPhysRegs); |
| 103 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 104 | const MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | 92dfe20 | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 105 | if (!MO.isRegister() || !MO.isUse()) |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 106 | continue; |
| 107 | unsigned Reg = MO.getReg(); |
| 108 | if (Reg == 0) |
| 109 | continue; |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 110 | if (!isUsed(Reg)) { |
| 111 | // Register has been scavenged. Restore it! |
| 112 | if (Reg != ScavengedReg) |
Evan Cheng | 5db322a | 2007-07-05 07:05:38 +0000 | [diff] [blame] | 113 | assert(false && "Using an undefined register!"); |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 114 | else |
| 115 | restoreScavengedReg(); |
| 116 | } |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 117 | if (MO.isKill() && !isReserved(Reg)) |
| 118 | ChangedRegs.set(Reg); |
| 119 | } |
| 120 | // Change states of all registers after all the uses are processed to guard |
| 121 | // against multiple uses. |
| 122 | setUnused(ChangedRegs); |
| 123 | |
| 124 | // Process defs. |
| 125 | const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); |
| 126 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 127 | const MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | 92dfe20 | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 128 | if (!MO.isRegister() || !MO.isDef()) |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 129 | continue; |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 130 | unsigned Reg = MO.getReg(); |
Evan Cheng | 5de3b7f | 2007-03-02 10:43:16 +0000 | [diff] [blame] | 131 | // If it's dead upon def, then it is now free. |
| 132 | if (MO.isDead()) { |
| 133 | setUnused(Reg); |
| 134 | continue; |
| 135 | } |
Evan Cheng | 0badfea | 2007-02-25 09:47:31 +0000 | [diff] [blame] | 136 | // Skip two-address destination operand. |
| 137 | if (TID->findTiedToSrcOperand(i) != -1) { |
Evan Cheng | 5db322a | 2007-07-05 07:05:38 +0000 | [diff] [blame] | 138 | assert(isUsed(Reg) && "Using an undefined register!"); |
Evan Cheng | 0badfea | 2007-02-25 09:47:31 +0000 | [diff] [blame] | 139 | continue; |
| 140 | } |
Evan Cheng | 5db322a | 2007-07-05 07:05:38 +0000 | [diff] [blame] | 141 | assert((isUnused(Reg) || isReserved(Reg)) && |
| 142 | "Re-defining a live register!"); |
Evan Cheng | 5de3b7f | 2007-03-02 10:43:16 +0000 | [diff] [blame] | 143 | setUsed(Reg); |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 144 | } |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 145 | } |
| 146 | |
| 147 | void RegScavenger::backward() { |
Evan Cheng | 898218c | 2007-02-27 22:58:43 +0000 | [diff] [blame] | 148 | assert(Tracking && "Not tracking states!"); |
Evan Cheng | ed570de | 2007-02-27 01:58:48 +0000 | [diff] [blame] | 149 | assert(MBBI != MBB->begin() && "Already at start of basic block!"); |
| 150 | // Move ptr backward. |
| 151 | MBBI = prior(MBBI); |
| 152 | |
| 153 | MachineInstr *MI = MBBI; |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 154 | // Process defs first. |
| 155 | const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); |
| 156 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 157 | const MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | 92dfe20 | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 158 | if (!MO.isRegister() || !MO.isDef()) |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 159 | continue; |
| 160 | // Skip two-address destination operand. |
| 161 | if (TID->findTiedToSrcOperand(i) != -1) |
| 162 | continue; |
| 163 | unsigned Reg = MO.getReg(); |
| 164 | assert(isUsed(Reg)); |
| 165 | if (!isReserved(Reg)) |
| 166 | setUnused(Reg); |
| 167 | } |
| 168 | |
| 169 | // Process uses. |
| 170 | BitVector ChangedRegs(NumPhysRegs); |
| 171 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 172 | const MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | 92dfe20 | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 173 | if (!MO.isRegister() || !MO.isUse()) |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 174 | continue; |
| 175 | unsigned Reg = MO.getReg(); |
| 176 | if (Reg == 0) |
| 177 | continue; |
| 178 | assert(isUnused(Reg) || isReserved(Reg)); |
| 179 | ChangedRegs.set(Reg); |
| 180 | } |
| 181 | setUsed(ChangedRegs); |
| 182 | } |
| 183 | |
Dale Johannesen | 69cb9b7 | 2007-03-20 21:35:06 +0000 | [diff] [blame] | 184 | void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { |
| 185 | if (includeReserved) |
Dale Johannesen | c6b9ef8 | 2007-03-26 22:23:54 +0000 | [diff] [blame] | 186 | used = ~RegsAvailable; |
Dale Johannesen | 69cb9b7 | 2007-03-20 21:35:06 +0000 | [diff] [blame] | 187 | else |
Dale Johannesen | c6b9ef8 | 2007-03-26 22:23:54 +0000 | [diff] [blame] | 188 | used = ~RegsAvailable & ~ReservedRegs; |
Dale Johannesen | 69cb9b7 | 2007-03-20 21:35:06 +0000 | [diff] [blame] | 189 | } |
| 190 | |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 191 | /// CreateRegClassMask - Set the bits that represent the registers in the |
| 192 | /// TargetRegisterClass. |
| 193 | static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { |
| 194 | for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; |
| 195 | ++I) |
| 196 | Mask.set(*I); |
| 197 | } |
| 198 | |
| 199 | unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, |
Evan Cheng | 5196b36 | 2007-03-01 08:56:24 +0000 | [diff] [blame] | 200 | const BitVector &Candidates) const { |
| 201 | // Mask off the registers which are not in the TargetRegisterClass. |
Dale Johannesen | c6b9ef8 | 2007-03-26 22:23:54 +0000 | [diff] [blame] | 202 | BitVector RegsAvailableCopy(NumPhysRegs, false); |
| 203 | CreateRegClassMask(RegClass, RegsAvailableCopy); |
| 204 | RegsAvailableCopy &= RegsAvailable; |
Evan Cheng | 5196b36 | 2007-03-01 08:56:24 +0000 | [diff] [blame] | 205 | |
| 206 | // Restrict the search to candidates. |
Dale Johannesen | c6b9ef8 | 2007-03-26 22:23:54 +0000 | [diff] [blame] | 207 | RegsAvailableCopy &= Candidates; |
Evan Cheng | 5196b36 | 2007-03-01 08:56:24 +0000 | [diff] [blame] | 208 | |
| 209 | // Returns the first unused (bit is set) register, or 0 is none is found. |
Dale Johannesen | c6b9ef8 | 2007-03-26 22:23:54 +0000 | [diff] [blame] | 210 | int Reg = RegsAvailableCopy.find_first(); |
Evan Cheng | 5196b36 | 2007-03-01 08:56:24 +0000 | [diff] [blame] | 211 | return (Reg == -1) ? 0 : Reg; |
| 212 | } |
| 213 | |
| 214 | unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 215 | bool ExCalleeSaved) const { |
| 216 | // Mask off the registers which are not in the TargetRegisterClass. |
Dale Johannesen | c6b9ef8 | 2007-03-26 22:23:54 +0000 | [diff] [blame] | 217 | BitVector RegsAvailableCopy(NumPhysRegs, false); |
| 218 | CreateRegClassMask(RegClass, RegsAvailableCopy); |
| 219 | RegsAvailableCopy &= RegsAvailable; |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 220 | |
| 221 | // If looking for a non-callee-saved register, mask off all the callee-saved |
| 222 | // registers. |
| 223 | if (ExCalleeSaved) |
Dale Johannesen | c6b9ef8 | 2007-03-26 22:23:54 +0000 | [diff] [blame] | 224 | RegsAvailableCopy &= ~CalleeSavedRegs; |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 225 | |
| 226 | // Returns the first unused (bit is set) register, or 0 is none is found. |
Dale Johannesen | c6b9ef8 | 2007-03-26 22:23:54 +0000 | [diff] [blame] | 227 | int Reg = RegsAvailableCopy.find_first(); |
Evan Cheng | 96fa612 | 2007-02-23 01:01:19 +0000 | [diff] [blame] | 228 | return (Reg == -1) ? 0 : Reg; |
| 229 | } |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 230 | |
| 231 | /// calcDistanceToUse - Calculate the distance to the first use of the |
| 232 | /// specified register. |
| 233 | static unsigned calcDistanceToUse(MachineBasicBlock *MBB, |
| 234 | MachineBasicBlock::iterator I, unsigned Reg) { |
| 235 | unsigned Dist = 0; |
| 236 | I = next(I); |
| 237 | while (I != MBB->end()) { |
| 238 | Dist++; |
Evan Cheng | faa5107 | 2007-04-26 19:00:32 +0000 | [diff] [blame] | 239 | if (I->findRegisterUseOperandIdx(Reg) != -1) |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 240 | return Dist; |
| 241 | I = next(I); |
| 242 | } |
| 243 | return Dist + 1; |
| 244 | } |
| 245 | |
| 246 | unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, |
Evan Cheng | 8e33473 | 2007-05-01 09:01:42 +0000 | [diff] [blame] | 247 | MachineBasicBlock::iterator I, |
| 248 | int SPAdj) { |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 249 | assert(ScavengingFrameIndex >= 0 && |
| 250 | "Cannot scavenge a register without an emergency spill slot!"); |
| 251 | |
| 252 | // Mask off the registers which are not in the TargetRegisterClass. |
| 253 | BitVector Candidates(NumPhysRegs, false); |
| 254 | CreateRegClassMask(RC, Candidates); |
| 255 | Candidates ^= ReservedRegs; // Do not include reserved registers. |
| 256 | |
| 257 | // Exclude all the registers being used by the instruction. |
| 258 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { |
| 259 | MachineOperand &MO = I->getOperand(i); |
Dan Gohman | 92dfe20 | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 260 | if (MO.isRegister()) |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 261 | Candidates.reset(MO.getReg()); |
| 262 | } |
| 263 | |
| 264 | // Find the register whose use is furtherest aaway. |
| 265 | unsigned SReg = 0; |
| 266 | unsigned MaxDist = 0; |
| 267 | int Reg = Candidates.find_first(); |
| 268 | while (Reg != -1) { |
| 269 | unsigned Dist = calcDistanceToUse(MBB, I, Reg); |
| 270 | if (Dist >= MaxDist) { |
| 271 | MaxDist = Dist; |
| 272 | SReg = Reg; |
| 273 | } |
| 274 | Reg = Candidates.find_next(Reg); |
| 275 | } |
| 276 | |
| 277 | if (ScavengedReg != 0) { |
| 278 | // First restore previously scavenged register. |
| 279 | RegInfo->loadRegFromStackSlot(*MBB, I, ScavengedReg, |
| 280 | ScavengingFrameIndex, ScavengedRC); |
| 281 | MachineBasicBlock::iterator II = prior(I); |
Evan Cheng | 8e33473 | 2007-05-01 09:01:42 +0000 | [diff] [blame] | 282 | RegInfo->eliminateFrameIndex(II, SPAdj, this); |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 283 | } |
| 284 | |
Evan Cheng | d64b5c8 | 2007-12-05 03:14:33 +0000 | [diff] [blame] | 285 | RegInfo->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 286 | MachineBasicBlock::iterator II = prior(I); |
Evan Cheng | 8e33473 | 2007-05-01 09:01:42 +0000 | [diff] [blame] | 287 | RegInfo->eliminateFrameIndex(II, SPAdj, this); |
Evan Cheng | b74a3e6 | 2007-03-06 10:01:25 +0000 | [diff] [blame] | 288 | ScavengedReg = SReg; |
| 289 | ScavengedRC = RC; |
| 290 | |
| 291 | return SReg; |
| 292 | } |