Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 1 | //===-- RegAllocLocal.cpp - A BasicBlock generic register allocator -------===// |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 9 | // |
| 10 | // This register allocator allocates registers to a basic block at a time, |
| 11 | // attempting to keep values in registers and reusing registers as appropriate. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
Chris Lattner | 4cc662b | 2003-08-03 21:47:31 +0000 | [diff] [blame] | 15 | #define DEBUG_TYPE "regalloc" |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 16 | #include "llvm/CodeGen/Passes.h" |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 17 | #include "llvm/CodeGen/MachineFunctionPass.h" |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 18 | #include "llvm/CodeGen/MachineInstr.h" |
Chris Lattner | ff863ba | 2002-12-25 05:05:46 +0000 | [diff] [blame] | 19 | #include "llvm/CodeGen/SSARegMap.h" |
Chris Lattner | eb24db9 | 2002-12-28 21:08:26 +0000 | [diff] [blame] | 20 | #include "llvm/CodeGen/MachineFrameInfo.h" |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 21 | #include "llvm/CodeGen/LiveVariables.h" |
Alkis Evlogimenos | 9af9dbd | 2003-12-18 13:08:52 +0000 | [diff] [blame^] | 22 | #include "llvm/CodeGen/TwoAddressInstructionPass.h" |
Chris Lattner | 3501fea | 2003-01-14 22:00:31 +0000 | [diff] [blame] | 23 | #include "llvm/Target/TargetInstrInfo.h" |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 24 | #include "llvm/Target/TargetMachine.h" |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 25 | #include "Support/CommandLine.h" |
Chris Lattner | a11136b | 2003-08-01 22:21:34 +0000 | [diff] [blame] | 26 | #include "Support/Debug.h" |
| 27 | #include "Support/Statistic.h" |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 28 | #include <iostream> |
| 29 | |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 30 | namespace llvm { |
| 31 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 32 | namespace { |
| 33 | Statistic<> NumSpilled ("ra-local", "Number of registers spilled"); |
| 34 | Statistic<> NumReloaded("ra-local", "Number of registers reloaded"); |
Chris Lattner | 3e43026 | 2003-10-24 20:05:58 +0000 | [diff] [blame] | 35 | cl::opt<bool> DisableKill("disable-kill", cl::Hidden, |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 36 | cl::desc("Disable register kill in local-ra")); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 37 | |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 38 | class RA : public MachineFunctionPass { |
| 39 | const TargetMachine *TM; |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 40 | MachineFunction *MF; |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 41 | const MRegisterInfo *RegInfo; |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 42 | LiveVariables *LV; |
Chris Lattner | ff863ba | 2002-12-25 05:05:46 +0000 | [diff] [blame] | 43 | |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 44 | // StackSlotForVirtReg - Maps virtual regs to the frame index where these |
| 45 | // values are spilled. |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 46 | std::map<unsigned, int> StackSlotForVirtReg; |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 47 | |
| 48 | // Virt2PhysRegMap - This map contains entries for each virtual register |
| 49 | // that is currently available in a physical register. |
| 50 | // |
| 51 | std::map<unsigned, unsigned> Virt2PhysRegMap; |
| 52 | |
| 53 | // PhysRegsUsed - This map contains entries for each physical register that |
| 54 | // currently has a value (ie, it is in Virt2PhysRegMap). The value mapped |
| 55 | // to is the virtual register corresponding to the physical register (the |
| 56 | // inverse of the Virt2PhysRegMap), or 0. The value is set to 0 if this |
| 57 | // register is pinned because it is used by a future instruction. |
| 58 | // |
| 59 | std::map<unsigned, unsigned> PhysRegsUsed; |
| 60 | |
| 61 | // PhysRegsUseOrder - This contains a list of the physical registers that |
| 62 | // currently have a virtual register value in them. This list provides an |
| 63 | // ordering of registers, imposing a reallocation order. This list is only |
| 64 | // used if all registers are allocated and we have to spill one, in which |
| 65 | // case we spill the least recently used register. Entries at the front of |
| 66 | // the list are the least recently used registers, entries at the back are |
| 67 | // the most recently used. |
| 68 | // |
| 69 | std::vector<unsigned> PhysRegsUseOrder; |
| 70 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 71 | // VirtRegModified - This bitset contains information about which virtual |
| 72 | // registers need to be spilled back to memory when their registers are |
| 73 | // scavenged. If a virtual register has simply been rematerialized, there |
| 74 | // is no reason to spill it to memory when we need the register back. |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 75 | // |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 76 | std::vector<bool> VirtRegModified; |
| 77 | |
| 78 | void markVirtRegModified(unsigned Reg, bool Val = true) { |
| 79 | assert(Reg >= MRegisterInfo::FirstVirtualRegister && "Illegal VirtReg!"); |
| 80 | Reg -= MRegisterInfo::FirstVirtualRegister; |
| 81 | if (VirtRegModified.size() <= Reg) VirtRegModified.resize(Reg+1); |
| 82 | VirtRegModified[Reg] = Val; |
| 83 | } |
| 84 | |
| 85 | bool isVirtRegModified(unsigned Reg) const { |
| 86 | assert(Reg >= MRegisterInfo::FirstVirtualRegister && "Illegal VirtReg!"); |
| 87 | assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size() |
| 88 | && "Illegal virtual register!"); |
| 89 | return VirtRegModified[Reg - MRegisterInfo::FirstVirtualRegister]; |
| 90 | } |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 91 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 92 | void MarkPhysRegRecentlyUsed(unsigned Reg) { |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 93 | assert(!PhysRegsUseOrder.empty() && "No registers used!"); |
Chris Lattner | 0eb172c | 2002-12-24 00:04:55 +0000 | [diff] [blame] | 94 | if (PhysRegsUseOrder.back() == Reg) return; // Already most recently used |
| 95 | |
| 96 | for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i) |
| 97 | if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) { |
| 98 | unsigned RegMatch = PhysRegsUseOrder[i-1]; // remove from middle |
| 99 | PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1); |
| 100 | // Add it to the end of the list |
| 101 | PhysRegsUseOrder.push_back(RegMatch); |
| 102 | if (RegMatch == Reg) |
| 103 | return; // Found an exact match, exit early |
| 104 | } |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 105 | } |
| 106 | |
| 107 | public: |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 108 | virtual const char *getPassName() const { |
| 109 | return "Local Register Allocator"; |
| 110 | } |
| 111 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 112 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 113 | if (!DisableKill) |
| 114 | AU.addRequired<LiveVariables>(); |
| 115 | AU.addRequiredID(PHIEliminationID); |
Alkis Evlogimenos | 9af9dbd | 2003-12-18 13:08:52 +0000 | [diff] [blame^] | 116 | AU.addRequired<TwoAddressInstructionPass>(); |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 117 | MachineFunctionPass::getAnalysisUsage(AU); |
| 118 | } |
| 119 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 120 | private: |
| 121 | /// runOnMachineFunction - Register allocate the whole function |
| 122 | bool runOnMachineFunction(MachineFunction &Fn); |
| 123 | |
| 124 | /// AllocateBasicBlock - Register allocate the specified basic block. |
| 125 | void AllocateBasicBlock(MachineBasicBlock &MBB); |
| 126 | |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 127 | |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 128 | /// areRegsEqual - This method returns true if the specified registers are |
| 129 | /// related to each other. To do this, it checks to see if they are equal |
| 130 | /// or if the first register is in the alias set of the second register. |
| 131 | /// |
| 132 | bool areRegsEqual(unsigned R1, unsigned R2) const { |
| 133 | if (R1 == R2) return true; |
Alkis Evlogimenos | 73ff512 | 2003-10-08 05:20:08 +0000 | [diff] [blame] | 134 | for (const unsigned *AliasSet = RegInfo->getAliasSet(R2); |
| 135 | *AliasSet; ++AliasSet) { |
| 136 | if (*AliasSet == R1) return true; |
| 137 | } |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 138 | return false; |
| 139 | } |
| 140 | |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 141 | /// getStackSpaceFor - This returns the frame index of the specified virtual |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 142 | /// register on the stack, allocating space if necessary. |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 143 | int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 144 | |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 145 | /// removePhysReg - This method marks the specified physical register as no |
| 146 | /// longer being in use. |
| 147 | /// |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 148 | void removePhysReg(unsigned PhysReg); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 149 | |
| 150 | /// spillVirtReg - This method spills the value specified by PhysReg into |
| 151 | /// the virtual register slot specified by VirtReg. It then updates the RA |
| 152 | /// data structures to indicate the fact that PhysReg is now available. |
| 153 | /// |
| 154 | void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, |
| 155 | unsigned VirtReg, unsigned PhysReg); |
| 156 | |
Chris Lattner | c21be92 | 2002-12-16 17:44:42 +0000 | [diff] [blame] | 157 | /// spillPhysReg - This method spills the specified physical register into |
Chris Lattner | 128c2aa | 2003-08-17 18:01:15 +0000 | [diff] [blame] | 158 | /// the virtual register slot associated with it. If OnlyVirtRegs is set to |
| 159 | /// true, then the request is ignored if the physical register does not |
| 160 | /// contain a virtual register. |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 161 | /// |
Chris Lattner | c21be92 | 2002-12-16 17:44:42 +0000 | [diff] [blame] | 162 | void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, |
Chris Lattner | 128c2aa | 2003-08-17 18:01:15 +0000 | [diff] [blame] | 163 | unsigned PhysReg, bool OnlyVirtRegs = false); |
Chris Lattner | c21be92 | 2002-12-16 17:44:42 +0000 | [diff] [blame] | 164 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 165 | /// assignVirtToPhysReg - This method updates local state so that we know |
| 166 | /// that PhysReg is the proper container for VirtReg now. The physical |
| 167 | /// register must not be used for anything else when this is called. |
| 168 | /// |
| 169 | void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg); |
| 170 | |
| 171 | /// liberatePhysReg - Make sure the specified physical register is available |
| 172 | /// for use. If there is currently a value in it, it is either moved out of |
| 173 | /// the way or spilled to memory. |
| 174 | /// |
| 175 | void liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, |
| 176 | unsigned PhysReg); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 177 | |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 178 | /// isPhysRegAvailable - Return true if the specified physical register is |
| 179 | /// free and available for use. This also includes checking to see if |
| 180 | /// aliased registers are all free... |
| 181 | /// |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 182 | bool isPhysRegAvailable(unsigned PhysReg) const; |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 183 | |
| 184 | /// getFreeReg - Look to see if there is a free register available in the |
| 185 | /// specified register class. If not, return 0. |
| 186 | /// |
| 187 | unsigned getFreeReg(const TargetRegisterClass *RC); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 188 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 189 | /// getReg - Find a physical register to hold the specified virtual |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 190 | /// register. If all compatible physical registers are used, this method |
| 191 | /// spills the last used virtual register to the stack, and uses that |
| 192 | /// register. |
| 193 | /// |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 194 | unsigned getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, |
| 195 | unsigned VirtReg); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 196 | |
| 197 | /// reloadVirtReg - This method loads the specified virtual register into a |
| 198 | /// physical register, returning the physical register chosen. This updates |
| 199 | /// the regalloc data structures to reflect the fact that the virtual reg is |
| 200 | /// now alive in a physical register, and the previous one isn't. |
| 201 | /// |
| 202 | unsigned reloadVirtReg(MachineBasicBlock &MBB, |
| 203 | MachineBasicBlock::iterator &I, unsigned VirtReg); |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 204 | |
| 205 | void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, |
| 206 | unsigned PhysReg); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 207 | }; |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 208 | } |
| 209 | |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 210 | /// getStackSpaceFor - This allocates space for the specified virtual register |
| 211 | /// to be held on the stack. |
| 212 | int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { |
| 213 | // Find the location Reg would belong... |
| 214 | std::map<unsigned, int>::iterator I =StackSlotForVirtReg.lower_bound(VirtReg); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 215 | |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 216 | if (I != StackSlotForVirtReg.end() && I->first == VirtReg) |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 217 | return I->second; // Already has space allocated? |
| 218 | |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 219 | // Allocate a new stack object for this spill location... |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 220 | int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 221 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 222 | // Assign the slot... |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 223 | StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx)); |
| 224 | return FrameIdx; |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 225 | } |
| 226 | |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 227 | |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 228 | /// removePhysReg - This method marks the specified physical register as no |
| 229 | /// longer being in use. |
| 230 | /// |
| 231 | void RA::removePhysReg(unsigned PhysReg) { |
| 232 | PhysRegsUsed.erase(PhysReg); // PhyReg no longer used |
| 233 | |
| 234 | std::vector<unsigned>::iterator It = |
| 235 | std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg); |
| 236 | assert(It != PhysRegsUseOrder.end() && |
| 237 | "Spilled a physical register, but it was not in use list!"); |
| 238 | PhysRegsUseOrder.erase(It); |
| 239 | } |
| 240 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 241 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 242 | /// spillVirtReg - This method spills the value specified by PhysReg into the |
| 243 | /// virtual register slot specified by VirtReg. It then updates the RA data |
| 244 | /// structures to indicate the fact that PhysReg is now available. |
| 245 | /// |
| 246 | void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, |
| 247 | unsigned VirtReg, unsigned PhysReg) { |
Chris Lattner | 8c81945 | 2003-08-05 04:13:58 +0000 | [diff] [blame] | 248 | if (!VirtReg && DisableKill) return; |
| 249 | assert(VirtReg && "Spilling a physical register is illegal!" |
Chris Lattner | d9ac6a7 | 2003-08-05 00:49:09 +0000 | [diff] [blame] | 250 | " Must not have appropriate kill for the register or use exists beyond" |
| 251 | " the intended one."); |
| 252 | DEBUG(std::cerr << " Spilling register " << RegInfo->getName(PhysReg); |
| 253 | std::cerr << " containing %reg" << VirtReg; |
| 254 | if (!isVirtRegModified(VirtReg)) |
| 255 | std::cerr << " which has not been modified, so no store necessary!"); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 256 | |
Chris Lattner | d9ac6a7 | 2003-08-05 00:49:09 +0000 | [diff] [blame] | 257 | // Otherwise, there is a virtual register corresponding to this physical |
| 258 | // register. We only need to spill it into its stack slot if it has been |
| 259 | // modified. |
| 260 | if (isVirtRegModified(VirtReg)) { |
| 261 | const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); |
| 262 | int FrameIndex = getStackSpaceFor(VirtReg, RC); |
| 263 | DEBUG(std::cerr << " to stack slot #" << FrameIndex); |
| 264 | RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC); |
| 265 | ++NumSpilled; // Update statistics |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 266 | } |
Chris Lattner | d9ac6a7 | 2003-08-05 00:49:09 +0000 | [diff] [blame] | 267 | Virt2PhysRegMap.erase(VirtReg); // VirtReg no longer available |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 268 | |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 269 | DEBUG(std::cerr << "\n"); |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 270 | removePhysReg(PhysReg); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 271 | } |
| 272 | |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 273 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 274 | /// spillPhysReg - This method spills the specified physical register into the |
Chris Lattner | 128c2aa | 2003-08-17 18:01:15 +0000 | [diff] [blame] | 275 | /// virtual register slot associated with it. If OnlyVirtRegs is set to true, |
| 276 | /// then the request is ignored if the physical register does not contain a |
| 277 | /// virtual register. |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 278 | /// |
| 279 | void RA::spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, |
Chris Lattner | 128c2aa | 2003-08-17 18:01:15 +0000 | [diff] [blame] | 280 | unsigned PhysReg, bool OnlyVirtRegs) { |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 281 | std::map<unsigned, unsigned>::iterator PI = PhysRegsUsed.find(PhysReg); |
| 282 | if (PI != PhysRegsUsed.end()) { // Only spill it if it's used! |
Chris Lattner | 128c2aa | 2003-08-17 18:01:15 +0000 | [diff] [blame] | 283 | if (PI->second || !OnlyVirtRegs) |
| 284 | spillVirtReg(MBB, I, PI->second, PhysReg); |
Alkis Evlogimenos | 73ff512 | 2003-10-08 05:20:08 +0000 | [diff] [blame] | 285 | } else { |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 286 | // If the selected register aliases any other registers, we must make |
| 287 | // sure that one of the aliases isn't alive... |
Alkis Evlogimenos | 73ff512 | 2003-10-08 05:20:08 +0000 | [diff] [blame] | 288 | for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); |
| 289 | *AliasSet; ++AliasSet) { |
| 290 | PI = PhysRegsUsed.find(*AliasSet); |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 291 | if (PI != PhysRegsUsed.end()) // Spill aliased register... |
Chris Lattner | 128c2aa | 2003-08-17 18:01:15 +0000 | [diff] [blame] | 292 | if (PI->second || !OnlyVirtRegs) |
Alkis Evlogimenos | 73ff512 | 2003-10-08 05:20:08 +0000 | [diff] [blame] | 293 | spillVirtReg(MBB, I, PI->second, *AliasSet); |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 294 | } |
| 295 | } |
| 296 | } |
| 297 | |
| 298 | |
| 299 | /// assignVirtToPhysReg - This method updates local state so that we know |
| 300 | /// that PhysReg is the proper container for VirtReg now. The physical |
| 301 | /// register must not be used for anything else when this is called. |
| 302 | /// |
| 303 | void RA::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { |
| 304 | assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() && |
| 305 | "Phys reg already assigned!"); |
| 306 | // Update information to note the fact that this register was just used, and |
| 307 | // it holds VirtReg. |
| 308 | PhysRegsUsed[PhysReg] = VirtReg; |
| 309 | Virt2PhysRegMap[VirtReg] = PhysReg; |
| 310 | PhysRegsUseOrder.push_back(PhysReg); // New use of PhysReg |
| 311 | } |
| 312 | |
| 313 | |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 314 | /// isPhysRegAvailable - Return true if the specified physical register is free |
| 315 | /// and available for use. This also includes checking to see if aliased |
| 316 | /// registers are all free... |
| 317 | /// |
| 318 | bool RA::isPhysRegAvailable(unsigned PhysReg) const { |
| 319 | if (PhysRegsUsed.count(PhysReg)) return false; |
| 320 | |
| 321 | // If the selected register aliases any other allocated registers, it is |
| 322 | // not free! |
Alkis Evlogimenos | 73ff512 | 2003-10-08 05:20:08 +0000 | [diff] [blame] | 323 | for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); |
| 324 | *AliasSet; ++AliasSet) |
| 325 | if (PhysRegsUsed.count(*AliasSet)) // Aliased register in use? |
| 326 | return false; // Can't use this reg then. |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 327 | return true; |
| 328 | } |
| 329 | |
| 330 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 331 | /// getFreeReg - Look to see if there is a free register available in the |
| 332 | /// specified register class. If not, return 0. |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 333 | /// |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 334 | unsigned RA::getFreeReg(const TargetRegisterClass *RC) { |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 335 | // Get iterators defining the range of registers that are valid to allocate in |
| 336 | // this class, which also specifies the preferred allocation order. |
| 337 | TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF); |
| 338 | TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF); |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 339 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 340 | for (; RI != RE; ++RI) |
| 341 | if (isPhysRegAvailable(*RI)) { // Is reg unused? |
| 342 | assert(*RI != 0 && "Cannot use register!"); |
| 343 | return *RI; // Found an unused register! |
| 344 | } |
| 345 | return 0; |
| 346 | } |
| 347 | |
| 348 | |
| 349 | /// liberatePhysReg - Make sure the specified physical register is available for |
| 350 | /// use. If there is currently a value in it, it is either moved out of the way |
| 351 | /// or spilled to memory. |
| 352 | /// |
| 353 | void RA::liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, |
| 354 | unsigned PhysReg) { |
| 355 | // FIXME: This code checks to see if a register is available, but it really |
| 356 | // wants to know if a reg is available BEFORE the instruction executes. If |
| 357 | // called after killed operands are freed, it runs the risk of reallocating a |
| 358 | // used operand... |
| 359 | #if 0 |
| 360 | if (isPhysRegAvailable(PhysReg)) return; // Already available... |
| 361 | |
| 362 | // Check to see if the register is directly used, not indirectly used through |
| 363 | // aliases. If aliased registers are the ones actually used, we cannot be |
| 364 | // sure that we will be able to save the whole thing if we do a reg-reg copy. |
| 365 | std::map<unsigned, unsigned>::iterator PRUI = PhysRegsUsed.find(PhysReg); |
| 366 | if (PRUI != PhysRegsUsed.end()) { |
| 367 | unsigned VirtReg = PRUI->second; // The virtual register held... |
| 368 | |
| 369 | // Check to see if there is a compatible register available. If so, we can |
| 370 | // move the value into the new register... |
| 371 | // |
| 372 | const TargetRegisterClass *RC = RegInfo->getRegClass(PhysReg); |
| 373 | if (unsigned NewReg = getFreeReg(RC)) { |
| 374 | // Emit the code to copy the value... |
| 375 | RegInfo->copyRegToReg(MBB, I, NewReg, PhysReg, RC); |
| 376 | |
| 377 | // Update our internal state to indicate that PhysReg is available and Reg |
| 378 | // isn't. |
| 379 | Virt2PhysRegMap.erase(VirtReg); |
| 380 | removePhysReg(PhysReg); // Free the physreg |
| 381 | |
| 382 | // Move reference over to new register... |
| 383 | assignVirtToPhysReg(VirtReg, NewReg); |
| 384 | return; |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 385 | } |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 386 | } |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 387 | #endif |
| 388 | spillPhysReg(MBB, I, PhysReg); |
| 389 | } |
| 390 | |
| 391 | |
| 392 | /// getReg - Find a physical register to hold the specified virtual |
| 393 | /// register. If all compatible physical registers are used, this method spills |
| 394 | /// the last used virtual register to the stack, and uses that register. |
| 395 | /// |
| 396 | unsigned RA::getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, |
| 397 | unsigned VirtReg) { |
| 398 | const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); |
| 399 | |
| 400 | // First check to see if we have a free register of the requested type... |
| 401 | unsigned PhysReg = getFreeReg(RC); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 402 | |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 403 | // If we didn't find an unused register, scavenge one now! |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 404 | if (PhysReg == 0) { |
Chris Lattner | c21be92 | 2002-12-16 17:44:42 +0000 | [diff] [blame] | 405 | assert(!PhysRegsUseOrder.empty() && "No allocated registers??"); |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 406 | |
| 407 | // Loop over all of the preallocated registers from the least recently used |
| 408 | // to the most recently used. When we find one that is capable of holding |
| 409 | // our register, use it. |
| 410 | for (unsigned i = 0; PhysReg == 0; ++i) { |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 411 | assert(i != PhysRegsUseOrder.size() && |
| 412 | "Couldn't find a register of the appropriate class!"); |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 413 | |
| 414 | unsigned R = PhysRegsUseOrder[i]; |
Chris Lattner | 41822c7 | 2003-08-23 23:49:42 +0000 | [diff] [blame] | 415 | |
| 416 | // We can only use this register if it holds a virtual register (ie, it |
| 417 | // can be spilled). Do not use it if it is an explicitly allocated |
| 418 | // physical register! |
| 419 | assert(PhysRegsUsed.count(R) && |
| 420 | "PhysReg in PhysRegsUseOrder, but is not allocated?"); |
| 421 | if (PhysRegsUsed[R]) { |
| 422 | // If the current register is compatible, use it. |
| 423 | if (RegInfo->getRegClass(R) == RC) { |
| 424 | PhysReg = R; |
| 425 | break; |
| 426 | } else { |
| 427 | // If one of the registers aliased to the current register is |
| 428 | // compatible, use it. |
Alkis Evlogimenos | 73ff512 | 2003-10-08 05:20:08 +0000 | [diff] [blame] | 429 | for (const unsigned *AliasSet = RegInfo->getAliasSet(R); |
| 430 | *AliasSet; ++AliasSet) { |
| 431 | if (RegInfo->getRegClass(*AliasSet) == RC) { |
| 432 | PhysReg = *AliasSet; // Take an aliased register |
| 433 | break; |
| 434 | } |
| 435 | } |
Chris Lattner | 41822c7 | 2003-08-23 23:49:42 +0000 | [diff] [blame] | 436 | } |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 437 | } |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 438 | } |
| 439 | |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 440 | assert(PhysReg && "Physical register not assigned!?!?"); |
| 441 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 442 | // At this point PhysRegsUseOrder[i] is the least recently used register of |
| 443 | // compatible register class. Spill it to memory and reap its remains. |
Chris Lattner | c21be92 | 2002-12-16 17:44:42 +0000 | [diff] [blame] | 444 | spillPhysReg(MBB, I, PhysReg); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 445 | } |
| 446 | |
| 447 | // Now that we know which register we need to assign this to, do it now! |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 448 | assignVirtToPhysReg(VirtReg, PhysReg); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 449 | return PhysReg; |
| 450 | } |
| 451 | |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 452 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 453 | /// reloadVirtReg - This method loads the specified virtual register into a |
| 454 | /// physical register, returning the physical register chosen. This updates the |
| 455 | /// regalloc data structures to reflect the fact that the virtual reg is now |
| 456 | /// alive in a physical register, and the previous one isn't. |
| 457 | /// |
| 458 | unsigned RA::reloadVirtReg(MachineBasicBlock &MBB, |
| 459 | MachineBasicBlock::iterator &I, |
| 460 | unsigned VirtReg) { |
| 461 | std::map<unsigned, unsigned>::iterator It = Virt2PhysRegMap.find(VirtReg); |
| 462 | if (It != Virt2PhysRegMap.end()) { |
| 463 | MarkPhysRegRecentlyUsed(It->second); |
| 464 | return It->second; // Already have this value available! |
| 465 | } |
| 466 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 467 | unsigned PhysReg = getReg(MBB, I, VirtReg); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 468 | |
Chris Lattner | ff863ba | 2002-12-25 05:05:46 +0000 | [diff] [blame] | 469 | const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 470 | int FrameIndex = getStackSpaceFor(VirtReg, RC); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 471 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 472 | markVirtRegModified(VirtReg, false); // Note that this reg was just reloaded |
| 473 | |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 474 | DEBUG(std::cerr << " Reloading %reg" << VirtReg << " into " |
| 475 | << RegInfo->getName(PhysReg) << "\n"); |
| 476 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 477 | // Add move instruction(s) |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 478 | RegInfo->loadRegFromStackSlot(MBB, I, PhysReg, FrameIndex, RC); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 479 | ++NumReloaded; // Update statistics |
| 480 | return PhysReg; |
| 481 | } |
| 482 | |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 483 | |
| 484 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 485 | void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { |
| 486 | // loop over each instruction |
| 487 | MachineBasicBlock::iterator I = MBB.begin(); |
| 488 | for (; I != MBB.end(); ++I) { |
| 489 | MachineInstr *MI = *I; |
Chris Lattner | 3501fea | 2003-01-14 22:00:31 +0000 | [diff] [blame] | 490 | const TargetInstrDescriptor &TID = TM->getInstrInfo().get(MI->getOpcode()); |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 491 | DEBUG(std::cerr << "\nStarting RegAlloc of: " << *MI; |
| 492 | std::cerr << " Regs have values: "; |
| 493 | for (std::map<unsigned, unsigned>::const_iterator |
| 494 | I = PhysRegsUsed.begin(), E = PhysRegsUsed.end(); I != E; ++I) |
| 495 | std::cerr << "[" << RegInfo->getName(I->first) |
| 496 | << ",%reg" << I->second << "] "; |
| 497 | std::cerr << "\n"); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 498 | |
Chris Lattner | ae64043 | 2002-12-17 02:50:10 +0000 | [diff] [blame] | 499 | // Loop over the implicit uses, making sure that they are at the head of the |
| 500 | // use order list, so they don't get reallocated. |
Alkis Evlogimenos | 73ff512 | 2003-10-08 05:20:08 +0000 | [diff] [blame] | 501 | for (const unsigned *ImplicitUses = TID.ImplicitUses; |
| 502 | *ImplicitUses; ++ImplicitUses) |
| 503 | MarkPhysRegRecentlyUsed(*ImplicitUses); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 504 | |
Brian Gaeke | 53b99a0 | 2003-08-15 21:19:25 +0000 | [diff] [blame] | 505 | // Get the used operands into registers. This has the potential to spill |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 506 | // incoming values if we are out of registers. Note that we completely |
| 507 | // ignore physical register uses here. We assume that if an explicit |
| 508 | // physical register is referenced by the instruction, that it is guaranteed |
| 509 | // to be live-in, or the input is badly hosed. |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 510 | // |
| 511 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) |
Alkis Evlogimenos | 4d7af65 | 2003-12-14 13:24:17 +0000 | [diff] [blame] | 512 | if (MI->getOperand(i).isUse() && |
| 513 | !MI->getOperand(i).isDef() && |
| 514 | MI->getOperand(i).isVirtualRegister()){ |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 515 | unsigned VirtSrcReg = MI->getOperand(i).getAllocatedRegNum(); |
| 516 | unsigned PhysSrcReg = reloadVirtReg(MBB, I, VirtSrcReg); |
| 517 | MI->SetMachineOperandReg(i, PhysSrcReg); // Assign the input register |
| 518 | } |
| 519 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 520 | if (!DisableKill) { |
| 521 | // If this instruction is the last user of anything in registers, kill the |
| 522 | // value, freeing the register being used, so it doesn't need to be |
| 523 | // spilled to memory. |
| 524 | // |
| 525 | for (LiveVariables::killed_iterator KI = LV->killed_begin(MI), |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 526 | KE = LV->killed_end(MI); KI != KE; ++KI) { |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 527 | unsigned VirtReg = KI->second; |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 528 | unsigned PhysReg = VirtReg; |
| 529 | if (VirtReg >= MRegisterInfo::FirstVirtualRegister) { |
| 530 | std::map<unsigned, unsigned>::iterator I = |
| 531 | Virt2PhysRegMap.find(VirtReg); |
| 532 | assert(I != Virt2PhysRegMap.end()); |
| 533 | PhysReg = I->second; |
| 534 | Virt2PhysRegMap.erase(I); |
| 535 | } |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 536 | |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 537 | if (PhysReg) { |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 538 | DEBUG(std::cerr << " Last use of " << RegInfo->getName(PhysReg) |
| 539 | << "[%reg" << VirtReg <<"], removing it from live set\n"); |
Chris Lattner | d9ac6a7 | 2003-08-05 00:49:09 +0000 | [diff] [blame] | 540 | removePhysReg(PhysReg); |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 541 | } |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 542 | } |
| 543 | } |
| 544 | |
| 545 | // Loop over all of the operands of the instruction, spilling registers that |
| 546 | // are defined, and marking explicit destinations in the PhysRegsUsed map. |
| 547 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) |
Alkis Evlogimenos | 4d7af65 | 2003-12-14 13:24:17 +0000 | [diff] [blame] | 548 | if (MI->getOperand(i).isDef() && |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 549 | MI->getOperand(i).isPhysicalRegister()) { |
| 550 | unsigned Reg = MI->getOperand(i).getAllocatedRegNum(); |
Chris Lattner | 128c2aa | 2003-08-17 18:01:15 +0000 | [diff] [blame] | 551 | spillPhysReg(MBB, I, Reg, true); // Spill any existing value in the reg |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 552 | PhysRegsUsed[Reg] = 0; // It is free and reserved now |
| 553 | PhysRegsUseOrder.push_back(Reg); |
| 554 | } |
| 555 | |
| 556 | // Loop over the implicit defs, spilling them as well. |
Alkis Evlogimenos | efe995a | 2003-12-13 01:20:58 +0000 | [diff] [blame] | 557 | for (const unsigned *ImplicitDefs = TID.ImplicitDefs; |
| 558 | *ImplicitDefs; ++ImplicitDefs) { |
| 559 | unsigned Reg = *ImplicitDefs; |
| 560 | spillPhysReg(MBB, I, Reg); |
| 561 | PhysRegsUseOrder.push_back(Reg); |
| 562 | PhysRegsUsed[Reg] = 0; // It is free and reserved now |
| 563 | } |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 564 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 565 | // Okay, we have allocated all of the source operands and spilled any values |
| 566 | // that would be destroyed by defs of this instruction. Loop over the |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 567 | // implicit defs and assign them to a register, spilling incoming values if |
| 568 | // we need to scavenge a register. |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 569 | // |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 570 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) |
Alkis Evlogimenos | 4d7af65 | 2003-12-14 13:24:17 +0000 | [diff] [blame] | 571 | if (MI->getOperand(i).isDef() && |
| 572 | MI->getOperand(i).isVirtualRegister()) { |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 573 | unsigned DestVirtReg = MI->getOperand(i).getAllocatedRegNum(); |
| 574 | unsigned DestPhysReg; |
| 575 | |
Alkis Evlogimenos | 9af9dbd | 2003-12-18 13:08:52 +0000 | [diff] [blame^] | 576 | // If DestVirtReg already has a value, use it. |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 577 | std::map<unsigned, unsigned>::iterator DestI = |
| 578 | Virt2PhysRegMap.find(DestVirtReg); |
| 579 | if (DestI != Virt2PhysRegMap.end()) { |
Alkis Evlogimenos | 9af9dbd | 2003-12-18 13:08:52 +0000 | [diff] [blame^] | 580 | DestPhysReg = DestI->second; |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 581 | } |
Alkis Evlogimenos | 9af9dbd | 2003-12-18 13:08:52 +0000 | [diff] [blame^] | 582 | else { |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 583 | DestPhysReg = getReg(MBB, I, DestVirtReg); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 584 | } |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 585 | markVirtRegModified(DestVirtReg); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 586 | MI->SetMachineOperandReg(i, DestPhysReg); // Assign the output register |
| 587 | } |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 588 | |
| 589 | if (!DisableKill) { |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 590 | // If this instruction defines any registers that are immediately dead, |
| 591 | // kill them now. |
| 592 | // |
| 593 | for (LiveVariables::killed_iterator KI = LV->dead_begin(MI), |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 594 | KE = LV->dead_end(MI); KI != KE; ++KI) { |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 595 | unsigned VirtReg = KI->second; |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 596 | unsigned PhysReg = VirtReg; |
| 597 | if (VirtReg >= MRegisterInfo::FirstVirtualRegister) { |
| 598 | std::map<unsigned, unsigned>::iterator I = |
| 599 | Virt2PhysRegMap.find(VirtReg); |
| 600 | assert(I != Virt2PhysRegMap.end()); |
| 601 | PhysReg = I->second; |
| 602 | Virt2PhysRegMap.erase(I); |
| 603 | } |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 604 | |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 605 | if (PhysReg) { |
Chris Lattner | b8822ad | 2003-08-04 23:36:39 +0000 | [diff] [blame] | 606 | DEBUG(std::cerr << " Register " << RegInfo->getName(PhysReg) |
| 607 | << " [%reg" << VirtReg |
| 608 | << "] is never used, removing it frame live list\n"); |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 609 | removePhysReg(PhysReg); |
| 610 | } |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 611 | } |
| 612 | } |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 613 | } |
| 614 | |
| 615 | // Rewind the iterator to point to the first flow control instruction... |
Chris Lattner | 3501fea | 2003-01-14 22:00:31 +0000 | [diff] [blame] | 616 | const TargetInstrInfo &TII = TM->getInstrInfo(); |
Chris Lattner | 0416d2a | 2003-01-16 18:06:43 +0000 | [diff] [blame] | 617 | I = MBB.end(); |
Chris Lattner | 3501fea | 2003-01-14 22:00:31 +0000 | [diff] [blame] | 618 | while (I != MBB.begin() && TII.isTerminatorInstr((*(I-1))->getOpcode())) |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 619 | --I; |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 620 | |
| 621 | // Spill all physical registers holding virtual registers now. |
| 622 | while (!PhysRegsUsed.empty()) |
Chris Lattner | 8c81945 | 2003-08-05 04:13:58 +0000 | [diff] [blame] | 623 | if (unsigned VirtReg = PhysRegsUsed.begin()->second) |
| 624 | spillVirtReg(MBB, I, VirtReg, PhysRegsUsed.begin()->first); |
| 625 | else |
| 626 | removePhysReg(PhysRegsUsed.begin()->first); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 627 | |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 628 | for (std::map<unsigned, unsigned>::iterator I = Virt2PhysRegMap.begin(), |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 629 | E = Virt2PhysRegMap.end(); I != E; ++I) |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 630 | std::cerr << "Register still mapped: " << I->first << " -> " |
Chris Lattner | d572563 | 2003-05-12 03:54:14 +0000 | [diff] [blame] | 631 | << I->second << "\n"; |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 632 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 633 | assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?"); |
Chris Lattner | 128c2aa | 2003-08-17 18:01:15 +0000 | [diff] [blame] | 634 | |
| 635 | // Clear any physical register which appear live at the end of the basic |
| 636 | // block, but which do not hold any virtual registers. e.g., the stack |
| 637 | // pointer. |
| 638 | PhysRegsUseOrder.clear(); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 639 | } |
| 640 | |
Chris Lattner | 86c69a6 | 2002-12-17 03:16:10 +0000 | [diff] [blame] | 641 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 642 | /// runOnMachineFunction - Register allocate the whole function |
| 643 | /// |
| 644 | bool RA::runOnMachineFunction(MachineFunction &Fn) { |
| 645 | DEBUG(std::cerr << "Machine Function " << "\n"); |
| 646 | MF = &Fn; |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 647 | TM = &Fn.getTarget(); |
| 648 | RegInfo = TM->getRegisterInfo(); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 649 | |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 650 | if (!DisableKill) |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 651 | LV = &getAnalysis<LiveVariables>(); |
Chris Lattner | 82bee0f | 2002-12-18 08:14:26 +0000 | [diff] [blame] | 652 | |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 653 | // Loop over all of the basic blocks, eliminating virtual register references |
| 654 | for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); |
| 655 | MBB != MBBe; ++MBB) |
| 656 | AllocateBasicBlock(*MBB); |
| 657 | |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 658 | StackSlotForVirtReg.clear(); |
Chris Lattner | 91a452b | 2003-01-13 00:25:40 +0000 | [diff] [blame] | 659 | VirtRegModified.clear(); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 660 | return true; |
| 661 | } |
| 662 | |
Brian Gaeke | 19df387 | 2003-08-13 18:18:15 +0000 | [diff] [blame] | 663 | FunctionPass *createLocalRegisterAllocator() { |
Chris Lattner | 580f9be | 2002-12-28 20:40:43 +0000 | [diff] [blame] | 664 | return new RA(); |
Chris Lattner | b74e83c | 2002-12-16 16:15:28 +0000 | [diff] [blame] | 665 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 666 | |
| 667 | } // End llvm namespace |