RegisterScavenging.cpp revision d273a003b6ad27720b2f0bab1a0996150a3d6fbe
196fa612373e258120d351ed14361f964ad22f99dEvan Cheng//===-- RegisterScavenging.cpp - Machine register scavenging --------------===// 296fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 396fa612373e258120d351ed14361f964ad22f99dEvan Cheng// The LLVM Compiler Infrastructure 496fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 796fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 896fa612373e258120d351ed14361f964ad22f99dEvan Cheng//===----------------------------------------------------------------------===// 996fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 1096fa612373e258120d351ed14361f964ad22f99dEvan Cheng// This file implements the machine register scavenger. It can provide 11ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling// information, such as unused registers, at any point in a machine basic block. 12ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling// It also provides a mechanism to make registers available by evicting them to 13ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling// spill slots. 1496fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 1596fa612373e258120d351ed14361f964ad22f99dEvan Cheng//===----------------------------------------------------------------------===// 1696fa612373e258120d351ed14361f964ad22f99dEvan Cheng 1796fa612373e258120d351ed14361f964ad22f99dEvan Cheng#define DEBUG_TYPE "reg-scavenging" 1896fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/RegisterScavenging.h" 19e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby#include "llvm/CodeGen/MachineFrameInfo.h" 2096fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/MachineFunction.h" 2196fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/MachineBasicBlock.h" 2296fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/MachineInstr.h" 231dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 24d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach#include "llvm/Support/Debug.h" 257d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 26d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach#include "llvm/Support/raw_ostream.h" 276f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 2896fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/Target/TargetInstrInfo.h" 2996fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/Target/TargetMachine.h" 308c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 311dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng#include "llvm/ADT/SmallPtrSet.h" 32d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman#include "llvm/ADT/SmallVector.h" 33ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng#include "llvm/ADT/STLExtras.h" 3496fa612373e258120d351ed14361f964ad22f99dEvan Chengusing namespace llvm; 3596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 36a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling/// setUsed - Set the register and its sub-registers as being used. 37459a7c6b6ad9c4fcb9f119aa6eaaf2769b00d9b1Evan Chengvoid RegScavenger::setUsed(unsigned Reg) { 38a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling RegsAvailable.reset(Reg); 39a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 406130f66eaae89f8878590796977678afa8448926Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 41459a7c6b6ad9c4fcb9f119aa6eaaf2769b00d9b1Evan Cheng unsigned SubReg = *SubRegs; ++SubRegs) 42a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling RegsAvailable.reset(SubReg); 43a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling} 44a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 458c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesenbool RegScavenger::isAliasUsed(unsigned Reg) const { 468c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen if (isUsed(Reg)) 478c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen return true; 488c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R) 498c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen if (isUsed(*R)) 508c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen return true; 518c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen return false; 528c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen} 538c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen 54e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosbyvoid RegScavenger::initRegState() { 55e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby ScavengedReg = 0; 56e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby ScavengedRC = NULL; 57e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby ScavengeRestore = NULL; 58e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby 59e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // All registers started out unused. 60e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby RegsAvailable.set(); 61e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby 62e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // Reserved registers are always used. 63e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby RegsAvailable ^= ReservedRegs; 64e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby 6506789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen if (!MBB) 66c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng return; 6706789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen 6806789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen // Live-in registers are in use. 6981bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 70c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng E = MBB->livein_end(); I != E; ++I) 71c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng setUsed(*I); 7206789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen 7306789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen // Pristine CSRs are also unavailable. 7406789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); 7506789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen for (int I = PR.find_first(); I>0; I = PR.find_next(I)) 7606789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen setUsed(I); 77e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby} 78e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby 79a3756ee7fe384210eddcfd66e2934439960b13a1Evan Chengvoid RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 804542611bb9793e8376d7d5f33b4a1e2d11712894Dan Gohman MachineFunction &MF = *mbb->getParent(); 8196fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetMachine &TM = MF.getTarget(); 82b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng TII = TM.getInstrInfo(); 836130f66eaae89f8878590796977678afa8448926Evan Cheng TRI = TM.getRegisterInfo(); 841dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng MRI = &MF.getRegInfo(); 8596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 866130f66eaae89f8878590796977678afa8448926Evan Cheng assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 87898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng "Target changed?"); 88898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 89e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // Self-initialize. 90898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!MBB) { 916130f66eaae89f8878590796977678afa8448926Evan Cheng NumPhysRegs = TRI->getNumRegs(); 92c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable.resize(NumPhysRegs); 93898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 94a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng // Create reserved registers bitvector. 956130f66eaae89f8878590796977678afa8448926Evan Cheng ReservedRegs = TRI->getReservedRegs(MF); 96a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 97898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng // Create callee-saved registers bitvector. 98898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng CalleeSavedRegs.resize(NumPhysRegs); 996130f66eaae89f8878590796977678afa8448926Evan Cheng const unsigned *CSRegs = TRI->getCalleeSavedRegs(); 100c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng if (CSRegs != NULL) 101c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng for (unsigned i = 0; CSRegs[i]; ++i) 102c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng CalleeSavedRegs.set(CSRegs[i]); 103898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 104898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 10560f90618203290f628f295510b8962c1bedd74daEvan Cheng MBB = mbb; 10660f90618203290f628f295510b8962c1bedd74daEvan Cheng initRegState(); 107a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 108a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng Tracking = false; 10996fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 11096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 111dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesenvoid RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { 112dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BV.set(Reg); 113dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) 114dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BV.set(*R); 115dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen} 116dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen 117dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesenvoid RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) { 118dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BV.set(Reg); 119dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++) 120dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BV.set(*R); 121dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen} 122dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen 12396fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::forward() { 124ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr forward. 125898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!Tracking) { 126898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng MBBI = MBB->begin(); 127898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng Tracking = true; 128898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } else { 129898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 1307896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MBBI = llvm::next(MBBI); 131898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 132ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 13396fa612373e258120d351ed14361f964ad22f99dEvan Cheng MachineInstr *MI = MBBI; 134b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 135d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (MI == ScavengeRestore) { 136d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengedReg = 0; 137d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengedRC = NULL; 138d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengeRestore = NULL; 139d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 140b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 1415ef9d76f6f1afe5a07a9cffe7ce5780d07a25d9cJakob Stoklund Olesen if (MI->isDebugValue()) 1425ef9d76f6f1afe5a07a9cffe7ce5780d07a25d9cJakob Stoklund Olesen return; 1435ef9d76f6f1afe5a07a9cffe7ce5780d07a25d9cJakob Stoklund Olesen 144dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // Find out which registers are early clobbered, killed, defined, and marked 145dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // def-dead in this instruction. 14646df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // FIXME: The scavenger is not predication aware. If the instruction is 14746df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // predicated, conservatively assume "kill" markers do not actually kill the 14846df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // register. Similarly ignores "dead" markers. 14946df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng bool isPred = TII->isPredicated(MI); 150dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BitVector EarlyClobberRegs(NumPhysRegs); 151dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BitVector KillRegs(NumPhysRegs); 152dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BitVector DefRegs(NumPhysRegs); 153dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BitVector DeadRegs(NumPhysRegs); 15496fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 15596fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 156dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen if (!MO.isReg() || MO.isUndef()) 15796fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 15896fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 159dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen if (!Reg || isReserved(Reg)) 160dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen continue; 161a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 162dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen if (MO.isUse()) { 163dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // Two-address operands implicitly kill. 16446df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng if (!isPred && (MO.isKill() || MI->isRegTiedToDefOperand(i))) 165dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen addRegWithSubRegs(KillRegs, Reg); 166dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen } else { 167dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen assert(MO.isDef()); 16846df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng if (!isPred && MO.isDead()) 169dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen addRegWithSubRegs(DeadRegs, Reg); 170dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen else 171dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen addRegWithSubRegs(DefRegs, Reg); 172dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen if (MO.isEarlyClobber()) 173dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen addRegWithAliases(EarlyClobberRegs, Reg); 174a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling } 17596fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 176a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 177dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // Verify uses and defs. 178dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 179dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen const MachineOperand &MO = MI->getOperand(i); 180dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen if (!MO.isReg() || MO.isUndef()) 1812578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng continue; 182dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen unsigned Reg = MO.getReg(); 183dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen if (!Reg || isReserved(Reg)) 1845de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng continue; 185dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen if (MO.isUse()) { 186a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng if (!isUsed(Reg)) { 187a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // Check if it's partial live: e.g. 188a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // D0 = insert_subreg D0<undef>, S0 189a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // ... D0 190a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // The problem is the insert_subreg could be eliminated. The use of 191a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // D0 is using a partially undef value. This is not *incorrect* since 192a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // S1 is can be freely clobbered. 193a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // Ideally we would like a way to model this, but leaving the 194a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // insert_subreg around causes both correctness and performance issues. 195a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng bool SubUsed = false; 196a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 197a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng unsigned SubReg = *SubRegs; ++SubRegs) 198a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng if (isUsed(SubReg)) { 199a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng SubUsed = true; 200a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng break; 201a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng } 202a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng assert(SubUsed && "Using an undefined register!"); 203a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng } 20416b794d25accbc4c5db63bb4d172049f052f0a55Jakob Stoklund Olesen assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) && 205dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen "Using an early clobbered register!"); 206dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen } else { 207dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen assert(MO.isDef()); 208393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng#if 0 209393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng // FIXME: Enable this once we've figured out how to correctly transfer 210393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng // implicit kills during codegen passes like the coalescer. 2119390cd0e86cb3b79f6836acab2a27b275e5bde9eJakob Stoklund Olesen assert((KillRegs.test(Reg) || isUnused(Reg) || 212dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 213dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen "Re-defining a live register!"); 214393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng#endif 2155de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng } 21696fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 217dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen 218dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // Commit the changes. 219dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen setUnused(KillRegs); 220dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen setUnused(DeadRegs); 221dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen setUsed(DefRegs); 22296fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 22396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 22469cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesenvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 22569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (includeReserved) 226c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen used = ~RegsAvailable; 22769cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen else 228c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen used = ~RegsAvailable & ~ReservedRegs; 22969cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen} 23069cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 23196fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// CreateRegClassMask - Set the bits that represent the registers in the 23296fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// TargetRegisterClass. 23396fa612373e258120d351ed14361f964ad22f99dEvan Chengstatic void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 23496fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 23596fa612373e258120d351ed14361f964ad22f99dEvan Cheng ++I) 23696fa612373e258120d351ed14361f964ad22f99dEvan Cheng Mask.set(*I); 23796fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 23896fa612373e258120d351ed14361f964ad22f99dEvan Cheng 239c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesenunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 240c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 241c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen I != E; ++I) 242d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach if (!isAliasUsed(*I)) { 243d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << 244d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach "\n"); 245c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen return *I; 246d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach } 247c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen return 0; 24896fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 249b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 250d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach/// getRegsAvailable - Return all available registers in the register class 251d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach/// in Mask. 252d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbachvoid RegScavenger::getRegsAvailable(const TargetRegisterClass *RC, 253d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach BitVector &Mask) { 254d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 255d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach I != E; ++I) 256d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach if (!isAliasUsed(*I)) 257d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach Mask.set(*I); 258d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach} 259d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach 26066a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// findSurvivorReg - Return the candidate register that is unused for the 261d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach/// longest after StargMII. UseMI is set to the instruction where the search 26266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// stopped. 26366a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// 26466a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// No more than InstrLimit instructions are inspected. 26566a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// 26607d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbachunsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 26766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen BitVector &Candidates, 26866a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen unsigned InstrLimit, 26966a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen MachineBasicBlock::iterator &UseMI) { 27066a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen int Survivor = Candidates.find_first(); 27166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen assert(Survivor > 0 && "No candidates for scavenging"); 27266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 27366a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 27407d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach assert(StartMI != ME && "MI already at terminator"); 27507d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach MachineBasicBlock::iterator RestorePointMI = StartMI; 27607d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach MachineBasicBlock::iterator MI = StartMI; 27766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 27807d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach bool inVirtLiveRange = false; 27966a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 2801c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach if (MI->isDebugValue()) { 2811c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach ++InstrLimit; // Don't count debug instructions 2821c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach continue; 2831c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach } 28407d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach bool isVirtKillInsn = false; 28507d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach bool isVirtDefInsn = false; 28666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // Remove any candidates touched by instruction. 28766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 28866a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen const MachineOperand &MO = MI->getOperand(i); 28907d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 29066a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen continue; 29107d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 29207d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (MO.isDef()) 29307d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach isVirtDefInsn = true; 29407d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach else if (MO.isKill()) 29507d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach isVirtKillInsn = true; 29607d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach continue; 29707d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach } 29866a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen Candidates.reset(MO.getReg()); 29966a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++) 30066a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen Candidates.reset(*R); 30166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen } 30207d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // If we're not in a virtual reg's live range, this is a valid 30307d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // restore point. 30407d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (!inVirtLiveRange) RestorePointMI = MI; 30507d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach 30607d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // Update whether we're in the live range of a virtual register 30707d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (isVirtKillInsn) inVirtLiveRange = false; 30807d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (isVirtDefInsn) inVirtLiveRange = true; 3098c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen 31066a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // Was our survivor untouched by this instruction? 31166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen if (Candidates.test(Survivor)) 3128c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen continue; 31366a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 31466a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // All candidates gone? 31566a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen if (Candidates.none()) 31666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen break; 31766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 31866a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen Survivor = Candidates.find_first(); 319b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 32007d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // If we ran off the end, that's where we want to restore. 32107d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (MI == ME) RestorePointMI = ME; 32207d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach assert (RestorePointMI != StartMI && 32307d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach "No available scavenger restore location!"); 32466a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 32566a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // We ran out of candidates, so stop the search. 32607d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach UseMI = RestorePointMI; 32766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen return Survivor; 328b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 329b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 330b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 3318e3347332120956538a6d882b02719e34b57f0cdEvan Cheng MachineBasicBlock::iterator I, 3328e3347332120956538a6d882b02719e34b57f0cdEvan Cheng int SPAdj) { 333b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Mask off the registers which are not in the TargetRegisterClass. 334b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng BitVector Candidates(NumPhysRegs, false); 335b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng CreateRegClassMask(RC, Candidates); 336e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // Do not include reserved registers. 337e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby Candidates ^= ReservedRegs & Candidates; 338b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 339b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Exclude all the registers being used by the instruction. 340b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 341b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineOperand &MO = I->getOperand(i); 342366e021fb2cb0efb8e727ef5e40bd55cef974c7aJim Grosbach if (MO.isReg() && MO.getReg() != 0 && 343366e021fb2cb0efb8e727ef5e40bd55cef974c7aJim Grosbach !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 344b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates.reset(MO.getReg()); 345b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 346b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 347ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach // Try to find a register that's unused if there is one, as then we won't 348ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach // have to spill. 349ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach if ((Candidates & RegsAvailable).any()) 350ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach Candidates &= RegsAvailable; 351ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach 352527c250a9080a5b6cf0053a6215037c3769ff4a0Bill Wendling // Find the register whose use is furthest away. 35366a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen MachineBasicBlock::iterator UseMI; 35466a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 3558c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen 356ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach // If we found an unused register there is no reason to spill it. 357d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach if (!isAliasUsed(SReg)) { 358d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n"); 35966a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen return SReg; 360d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach } 361b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 362b36eb9df205aa83cfdfc8ecebc93e1043d6253d9Jakob Stoklund Olesen assert(ScavengedReg == 0 && 363f36892335b4919b9120e48a792e6b3630b9de978Torok Edwin "Scavenger slot is live, unable to scavenge another register!"); 364b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 365e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // Avoid infinite regress 366e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby ScavengedReg = SReg; 367e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby 368540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // If the target knows how to save/restore the register, let it do so; 369540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // otherwise, use the emergency stack spill slot. 370d482f55af135081aee7f7ab972bb8973f189c88fJim Grosbach if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 371540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // Spill the scavenged register before I. 372540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach assert(ScavengingFrameIndex >= 0 && 3736e214805b1163c0e3cd218963c9e66ea244956b2Jim Grosbach "Cannot scavenge register without an emergency spill slot!"); 374746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC,TRI); 375540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach MachineBasicBlock::iterator II = prior(I); 376fcb4a8ead3cd8d9540d5eaa448af5d14a0ee341aJim Grosbach TRI->eliminateFrameIndex(II, SPAdj, this); 377540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach 378540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // Restore the scavenged register before its use (or first terminator). 379746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC, TRI); 38029bed1c8bb491a5fe609d58c5e560929117a859eJim Grosbach II = prior(UseMI); 381fcb4a8ead3cd8d9540d5eaa448af5d14a0ee341aJim Grosbach TRI->eliminateFrameIndex(II, SPAdj, this); 382d482f55af135081aee7f7ab972bb8973f189c88fJim Grosbach } 383d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng 38466a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen ScavengeRestore = prior(UseMI); 385540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach 386c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng // Doing this here leads to infinite regress. 387e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // ScavengedReg = SReg; 388b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedRC = RC; 389b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 390d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << 391d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach "\n"); 392d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach 393b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return SReg; 394b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 395