RegisterScavenging.cpp revision 015f228861ef9b337366f92f637d4e8d624bb006
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 6206789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen if (!MBB) 63c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng return; 6406789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen 6506789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen // Live-in registers are in use. 6681bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 67c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng E = MBB->livein_end(); I != E; ++I) 68c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng setUsed(*I); 6906789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen 7006789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen // Pristine CSRs are also unavailable. 7106789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); 7206789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen for (int I = PR.find_first(); I>0; I = PR.find_next(I)) 7306789e23d1aa0bcd935a3fba3eff0ec8a35b9c01Jakob Stoklund Olesen setUsed(I); 74e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby} 75e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby 76a3756ee7fe384210eddcfd66e2934439960b13a1Evan Chengvoid RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 774542611bb9793e8376d7d5f33b4a1e2d11712894Dan Gohman MachineFunction &MF = *mbb->getParent(); 7896fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetMachine &TM = MF.getTarget(); 79b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng TII = TM.getInstrInfo(); 806130f66eaae89f8878590796977678afa8448926Evan Cheng TRI = TM.getRegisterInfo(); 811dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng MRI = &MF.getRegInfo(); 8296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 836130f66eaae89f8878590796977678afa8448926Evan Cheng assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 84898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng "Target changed?"); 85898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 86e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // Self-initialize. 87898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!MBB) { 886130f66eaae89f8878590796977678afa8448926Evan Cheng NumPhysRegs = TRI->getNumRegs(); 89c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable.resize(NumPhysRegs); 909f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen KillRegs.resize(NumPhysRegs); 919f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen DefRegs.resize(NumPhysRegs); 92898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 93a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng // Create reserved registers bitvector. 946130f66eaae89f8878590796977678afa8448926Evan Cheng ReservedRegs = TRI->getReservedRegs(MF); 95a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 96898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng // Create callee-saved registers bitvector. 97898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng CalleeSavedRegs.resize(NumPhysRegs); 98015f228861ef9b337366f92f637d4e8d624bb006Craig Topper const uint16_t *CSRegs = TRI->getCalleeSavedRegs(&MF); 99c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng if (CSRegs != NULL) 100c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng for (unsigned i = 0; CSRegs[i]; ++i) 101c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng CalleeSavedRegs.set(CSRegs[i]); 102898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 103898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 10460f90618203290f628f295510b8962c1bedd74daEvan Cheng MBB = mbb; 10560f90618203290f628f295510b8962c1bedd74daEvan Cheng initRegState(); 106a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 107a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng Tracking = false; 10896fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 10996fa612373e258120d351ed14361f964ad22f99dEvan Cheng 110dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesenvoid RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { 111dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BV.set(Reg); 112dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) 113dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BV.set(*R); 114dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen} 115dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen 11696fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::forward() { 117ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr forward. 118898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!Tracking) { 119898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng MBBI = MBB->begin(); 120898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng Tracking = true; 121898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } else { 122bdaa9dc4a45b8831c942437f726895eb24a956baBob Wilson assert(MBBI != MBB->end() && "Already past the end of the basic block!"); 1237896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MBBI = llvm::next(MBBI); 124898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 125bdaa9dc4a45b8831c942437f726895eb24a956baBob Wilson assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 126ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 12796fa612373e258120d351ed14361f964ad22f99dEvan Cheng MachineInstr *MI = MBBI; 128b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 129d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (MI == ScavengeRestore) { 130d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengedReg = 0; 131d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengedRC = NULL; 132d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengeRestore = NULL; 133d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 134b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 1355ef9d76f6f1afe5a07a9cffe7ce5780d07a25d9cJakob Stoklund Olesen if (MI->isDebugValue()) 1365ef9d76f6f1afe5a07a9cffe7ce5780d07a25d9cJakob Stoklund Olesen return; 1375ef9d76f6f1afe5a07a9cffe7ce5780d07a25d9cJakob Stoklund Olesen 138dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // Find out which registers are early clobbered, killed, defined, and marked 139dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // def-dead in this instruction. 14046df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // FIXME: The scavenger is not predication aware. If the instruction is 14146df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // predicated, conservatively assume "kill" markers do not actually kill the 14246df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // register. Similarly ignores "dead" markers. 14346df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng bool isPred = TII->isPredicated(MI); 1449f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen KillRegs.reset(); 1459f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen DefRegs.reset(); 14696fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 14796fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 148be2af7ee781cd0083124514f497b8cf3070776ecJakob Stoklund Olesen if (MO.isRegMask()) 149be2af7ee781cd0083124514f497b8cf3070776ecJakob Stoklund Olesen (isPred ? DefRegs : KillRegs).setBitsNotInMask(MO.getRegMask()); 1502048e4ab7fb4ed45bae2159bae600ddf610303b1Jakob Stoklund Olesen if (!MO.isReg()) 15196fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 15296fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 1534af0f5fecb42563ff3ca5bd7fddb2f4f111e2fefJakob Stoklund Olesen if (!Reg || isReserved(Reg)) 154dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen continue; 155a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 156dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen if (MO.isUse()) { 1572048e4ab7fb4ed45bae2159bae600ddf610303b1Jakob Stoklund Olesen // Ignore undef uses. 1582048e4ab7fb4ed45bae2159bae600ddf610303b1Jakob Stoklund Olesen if (MO.isUndef()) 1592048e4ab7fb4ed45bae2159bae600ddf610303b1Jakob Stoklund Olesen continue; 1609f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen if (!isPred && MO.isKill()) 161dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen addRegWithSubRegs(KillRegs, Reg); 162dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen } else { 163dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen assert(MO.isDef()); 16446df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng if (!isPred && MO.isDead()) 1659f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen addRegWithSubRegs(KillRegs, Reg); 166dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen else 167dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen addRegWithSubRegs(DefRegs, Reg); 168a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling } 16996fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 170a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 171dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // Verify uses and defs. 1729f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen#ifndef NDEBUG 173dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 174dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen const MachineOperand &MO = MI->getOperand(i); 175d61c40360c3acc847263c5e5184b715c17528b09Jakob Stoklund Olesen if (!MO.isReg()) 1762578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng continue; 177dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen unsigned Reg = MO.getReg(); 1784af0f5fecb42563ff3ca5bd7fddb2f4f111e2fefJakob Stoklund Olesen if (!Reg || isReserved(Reg)) 1795de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng continue; 180dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen if (MO.isUse()) { 181d61c40360c3acc847263c5e5184b715c17528b09Jakob Stoklund Olesen if (MO.isUndef()) 182d61c40360c3acc847263c5e5184b715c17528b09Jakob Stoklund Olesen continue; 183a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng if (!isUsed(Reg)) { 184a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // Check if it's partial live: e.g. 185a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // D0 = insert_subreg D0<undef>, S0 186a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // ... D0 187a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // The problem is the insert_subreg could be eliminated. The use of 188a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // D0 is using a partially undef value. This is not *incorrect* since 189a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // S1 is can be freely clobbered. 190a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // Ideally we would like a way to model this, but leaving the 191a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // insert_subreg around causes both correctness and performance issues. 192a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng bool SubUsed = false; 193a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 194a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng unsigned SubReg = *SubRegs; ++SubRegs) 195a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng if (isUsed(SubReg)) { 196a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng SubUsed = true; 197a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng break; 198a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng } 19963c66724235ace1860e60a11ce2756d577387b29Jakob Stoklund Olesen if (!SubUsed) { 20063c66724235ace1860e60a11ce2756d577387b29Jakob Stoklund Olesen MBB->getParent()->verify(NULL, "In Register Scavenger"); 20163c66724235ace1860e60a11ce2756d577387b29Jakob Stoklund Olesen llvm_unreachable("Using an undefined register!"); 20263c66724235ace1860e60a11ce2756d577387b29Jakob Stoklund Olesen } 2031f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)SubUsed; 204a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng } 205dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen } else { 206dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen assert(MO.isDef()); 207393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng#if 0 208393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng // FIXME: Enable this once we've figured out how to correctly transfer 209393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng // implicit kills during codegen passes like the coalescer. 2109390cd0e86cb3b79f6836acab2a27b275e5bde9eJakob Stoklund Olesen assert((KillRegs.test(Reg) || isUnused(Reg) || 211dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 212dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen "Re-defining a live register!"); 213393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng#endif 2145de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng } 21596fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 2169f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen#endif // NDEBUG 217dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen 218dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // Commit the changes. 219dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen setUnused(KillRegs); 220dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen setUsed(DefRegs); 22196fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 22296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 22369cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesenvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 224685c23e75842e64145fe319efd792abe72a827ddJakob Stoklund Olesen used = RegsAvailable; 225685c23e75842e64145fe319efd792abe72a827ddJakob Stoklund Olesen used.flip(); 226cf14613455bc32b6a17821808595263e061335bcJakob Stoklund Olesen if (includeReserved) 227cf14613455bc32b6a17821808595263e061335bcJakob Stoklund Olesen used |= ReservedRegs; 228cf14613455bc32b6a17821808595263e061335bcJakob Stoklund Olesen else 229cf14613455bc32b6a17821808595263e061335bcJakob Stoklund Olesen used.reset(ReservedRegs); 23069cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen} 23169cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 232c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesenunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 233c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 234c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen I != E; ++I) 235d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach if (!isAliasUsed(*I)) { 236d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << 237d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach "\n"); 238c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen return *I; 239d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach } 240c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen return 0; 24196fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 242b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 243d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach/// getRegsAvailable - Return all available registers in the register class 244d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach/// in Mask. 24527ea9999e84dfb1e6c2baf06ec27a92f12753917Jim GrosbachBitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { 24627ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach BitVector Mask(TRI->getNumRegs()); 247d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 248d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach I != E; ++I) 249d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach if (!isAliasUsed(*I)) 250d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach Mask.set(*I); 25127ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach return Mask; 252d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach} 253d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach 25466a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// findSurvivorReg - Return the candidate register that is unused for the 255d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach/// longest after StargMII. UseMI is set to the instruction where the search 25666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// stopped. 25766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// 25866a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// No more than InstrLimit instructions are inspected. 25966a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// 26007d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbachunsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 26166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen BitVector &Candidates, 26266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen unsigned InstrLimit, 26366a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen MachineBasicBlock::iterator &UseMI) { 26466a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen int Survivor = Candidates.find_first(); 26566a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen assert(Survivor > 0 && "No candidates for scavenging"); 26666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 26766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 26807d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach assert(StartMI != ME && "MI already at terminator"); 26907d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach MachineBasicBlock::iterator RestorePointMI = StartMI; 27007d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach MachineBasicBlock::iterator MI = StartMI; 27166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 27207d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach bool inVirtLiveRange = false; 27366a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 2741c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach if (MI->isDebugValue()) { 2751c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach ++InstrLimit; // Don't count debug instructions 2761c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach continue; 2771c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach } 27807d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach bool isVirtKillInsn = false; 27907d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach bool isVirtDefInsn = false; 28066a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // Remove any candidates touched by instruction. 28166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 28266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen const MachineOperand &MO = MI->getOperand(i); 283be2af7ee781cd0083124514f497b8cf3070776ecJakob Stoklund Olesen if (MO.isRegMask()) 284be2af7ee781cd0083124514f497b8cf3070776ecJakob Stoklund Olesen Candidates.clearBitsNotInMask(MO.getRegMask()); 28507d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 28666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen continue; 28707d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 28807d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (MO.isDef()) 28907d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach isVirtDefInsn = true; 29007d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach else if (MO.isKill()) 29107d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach isVirtKillInsn = true; 29207d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach continue; 29307d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach } 29466a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen Candidates.reset(MO.getReg()); 29566a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++) 29666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen Candidates.reset(*R); 29766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen } 29807d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // If we're not in a virtual reg's live range, this is a valid 29907d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // restore point. 30007d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (!inVirtLiveRange) RestorePointMI = MI; 30107d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach 30207d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // Update whether we're in the live range of a virtual register 30307d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (isVirtKillInsn) inVirtLiveRange = false; 30407d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (isVirtDefInsn) inVirtLiveRange = true; 3058c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen 30666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // Was our survivor untouched by this instruction? 30766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen if (Candidates.test(Survivor)) 3088c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen continue; 30966a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 31066a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // All candidates gone? 31166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen if (Candidates.none()) 31266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen break; 31366a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 31466a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen Survivor = Candidates.find_first(); 315b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 31607d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // If we ran off the end, that's where we want to restore. 31707d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (MI == ME) RestorePointMI = ME; 31807d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach assert (RestorePointMI != StartMI && 31907d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach "No available scavenger restore location!"); 32066a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 32166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // We ran out of candidates, so stop the search. 32207d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach UseMI = RestorePointMI; 32366a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen return Survivor; 324b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 325b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 326b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 3278e3347332120956538a6d882b02719e34b57f0cdEvan Cheng MachineBasicBlock::iterator I, 3288e3347332120956538a6d882b02719e34b57f0cdEvan Cheng int SPAdj) { 3299204ddad5c30216e48c5bba0528ba24d66a22e13Jim Grosbach // Consider all allocatable registers in the register class initially 3309204ddad5c30216e48c5bba0528ba24d66a22e13Jim Grosbach BitVector Candidates = 3319204ddad5c30216e48c5bba0528ba24d66a22e13Jim Grosbach TRI->getAllocatableSet(*I->getParent()->getParent(), RC); 332b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 333b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Exclude all the registers being used by the instruction. 334b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 335b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineOperand &MO = I->getOperand(i); 336366e021fb2cb0efb8e727ef5e40bd55cef974c7aJim Grosbach if (MO.isReg() && MO.getReg() != 0 && 337366e021fb2cb0efb8e727ef5e40bd55cef974c7aJim Grosbach !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 338b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates.reset(MO.getReg()); 339b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 340b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 341ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach // Try to find a register that's unused if there is one, as then we won't 34227ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach // have to spill. Search explicitly rather than masking out based on 34327ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach // RegsAvailable, as RegsAvailable does not take aliases into account. 34427ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach // That's what getRegsAvailable() is for. 34527ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach BitVector Available = getRegsAvailable(RC); 346685c23e75842e64145fe319efd792abe72a827ddJakob Stoklund Olesen Available &= Candidates; 347685c23e75842e64145fe319efd792abe72a827ddJakob Stoklund Olesen if (Available.any()) 348685c23e75842e64145fe319efd792abe72a827ddJakob Stoklund Olesen Candidates = Available; 349ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach 350527c250a9080a5b6cf0053a6215037c3769ff4a0Bill Wendling // Find the register whose use is furthest away. 35166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen MachineBasicBlock::iterator UseMI; 35266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 3538c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen 354ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach // If we found an unused register there is no reason to spill it. 355d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach if (!isAliasUsed(SReg)) { 356d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n"); 35766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen return SReg; 358d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach } 359b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 360b36eb9df205aa83cfdfc8ecebc93e1043d6253d9Jakob Stoklund Olesen assert(ScavengedReg == 0 && 361f36892335b4919b9120e48a792e6b3630b9de978Torok Edwin "Scavenger slot is live, unable to scavenge another register!"); 362b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 363e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // Avoid infinite regress 364e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby ScavengedReg = SReg; 365e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby 366540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // If the target knows how to save/restore the register, let it do so; 367540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // otherwise, use the emergency stack spill slot. 368d482f55af135081aee7f7ab972bb8973f189c88fJim Grosbach if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 369540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // Spill the scavenged register before I. 370540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach assert(ScavengingFrameIndex >= 0 && 3716e214805b1163c0e3cd218963c9e66ea244956b2Jim Grosbach "Cannot scavenge register without an emergency spill slot!"); 372746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC,TRI); 373540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach MachineBasicBlock::iterator II = prior(I); 374fcb4a8ead3cd8d9540d5eaa448af5d14a0ee341aJim Grosbach TRI->eliminateFrameIndex(II, SPAdj, this); 375540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach 376540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // Restore the scavenged register before its use (or first terminator). 377746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC, TRI); 37829bed1c8bb491a5fe609d58c5e560929117a859eJim Grosbach II = prior(UseMI); 379fcb4a8ead3cd8d9540d5eaa448af5d14a0ee341aJim Grosbach TRI->eliminateFrameIndex(II, SPAdj, this); 380d482f55af135081aee7f7ab972bb8973f189c88fJim Grosbach } 381d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng 38266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen ScavengeRestore = prior(UseMI); 383540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach 384c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng // Doing this here leads to infinite regress. 385e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // ScavengedReg = SReg; 386b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedRC = RC; 387b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 388d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << 389d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach "\n"); 390d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach 391b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return SReg; 392b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 393