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 409ebfbf8b9fd5f982e0db9293808bd32168615ba9Craig Topper for (const uint16_t *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; 48e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *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 86aba6559370c3d453588103fb667ffa3b11b76652Jakob Stoklund Olesen // It is not possible to use the register scavenger after late optimization 87aba6559370c3d453588103fb667ffa3b11b76652Jakob Stoklund Olesen // passes that don't preserve accurate liveness information. 88aba6559370c3d453588103fb667ffa3b11b76652Jakob Stoklund Olesen assert(MRI->tracksLiveness() && 89aba6559370c3d453588103fb667ffa3b11b76652Jakob Stoklund Olesen "Cannot use register scavenger with inaccurate liveness"); 90aba6559370c3d453588103fb667ffa3b11b76652Jakob Stoklund Olesen 91e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // Self-initialize. 92898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!MBB) { 936130f66eaae89f8878590796977678afa8448926Evan Cheng NumPhysRegs = TRI->getNumRegs(); 94c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable.resize(NumPhysRegs); 959f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen KillRegs.resize(NumPhysRegs); 969f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen DefRegs.resize(NumPhysRegs); 97898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 98a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng // Create reserved registers bitvector. 996130f66eaae89f8878590796977678afa8448926Evan Cheng ReservedRegs = TRI->getReservedRegs(MF); 100a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 101898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng // Create callee-saved registers bitvector. 102898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng CalleeSavedRegs.resize(NumPhysRegs); 103015f228861ef9b337366f92f637d4e8d624bb006Craig Topper const uint16_t *CSRegs = TRI->getCalleeSavedRegs(&MF); 104c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng if (CSRegs != NULL) 105c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng for (unsigned i = 0; CSRegs[i]; ++i) 106c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng CalleeSavedRegs.set(CSRegs[i]); 107898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 108898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 10960f90618203290f628f295510b8962c1bedd74daEvan Cheng MBB = mbb; 11060f90618203290f628f295510b8962c1bedd74daEvan Cheng initRegState(); 111a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 112a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng Tracking = false; 11396fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 11496fa612373e258120d351ed14361f964ad22f99dEvan Cheng 115dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesenvoid RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { 116dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BV.set(Reg); 1179ebfbf8b9fd5f982e0db9293808bd32168615ba9Craig Topper for (const uint16_t *R = TRI->getSubRegisters(Reg); *R; R++) 118dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen BV.set(*R); 119dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen} 120dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen 12196fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::forward() { 122ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr forward. 123898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!Tracking) { 124898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng MBBI = MBB->begin(); 125898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng Tracking = true; 126898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } else { 127bdaa9dc4a45b8831c942437f726895eb24a956baBob Wilson assert(MBBI != MBB->end() && "Already past the end of the basic block!"); 1287896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MBBI = llvm::next(MBBI); 129898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 130bdaa9dc4a45b8831c942437f726895eb24a956baBob Wilson assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 131ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 13296fa612373e258120d351ed14361f964ad22f99dEvan Cheng MachineInstr *MI = MBBI; 133b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 134d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (MI == ScavengeRestore) { 135d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengedReg = 0; 136d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengedRC = NULL; 137d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengeRestore = NULL; 138d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 139b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 1405ef9d76f6f1afe5a07a9cffe7ce5780d07a25d9cJakob Stoklund Olesen if (MI->isDebugValue()) 1415ef9d76f6f1afe5a07a9cffe7ce5780d07a25d9cJakob Stoklund Olesen return; 1425ef9d76f6f1afe5a07a9cffe7ce5780d07a25d9cJakob Stoklund Olesen 143dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // Find out which registers are early clobbered, killed, defined, and marked 144dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // def-dead in this instruction. 14546df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // FIXME: The scavenger is not predication aware. If the instruction is 14646df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // predicated, conservatively assume "kill" markers do not actually kill the 14746df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // register. Similarly ignores "dead" markers. 14846df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng bool isPred = TII->isPredicated(MI); 1499f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen KillRegs.reset(); 1509f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen DefRegs.reset(); 15196fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 15296fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 153be2af7ee781cd0083124514f497b8cf3070776ecJakob Stoklund Olesen if (MO.isRegMask()) 154be2af7ee781cd0083124514f497b8cf3070776ecJakob Stoklund Olesen (isPred ? DefRegs : KillRegs).setBitsNotInMask(MO.getRegMask()); 1552048e4ab7fb4ed45bae2159bae600ddf610303b1Jakob Stoklund Olesen if (!MO.isReg()) 15696fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 15796fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 1584af0f5fecb42563ff3ca5bd7fddb2f4f111e2fefJakob Stoklund Olesen if (!Reg || isReserved(Reg)) 159dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen continue; 160a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 161dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen if (MO.isUse()) { 1622048e4ab7fb4ed45bae2159bae600ddf610303b1Jakob Stoklund Olesen // Ignore undef uses. 1632048e4ab7fb4ed45bae2159bae600ddf610303b1Jakob Stoklund Olesen if (MO.isUndef()) 1642048e4ab7fb4ed45bae2159bae600ddf610303b1Jakob Stoklund Olesen continue; 1659f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen if (!isPred && MO.isKill()) 166dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen addRegWithSubRegs(KillRegs, Reg); 167dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen } else { 168dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen assert(MO.isDef()); 16946df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng if (!isPred && MO.isDead()) 1709f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen addRegWithSubRegs(KillRegs, Reg); 171dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen else 172dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen addRegWithSubRegs(DefRegs, Reg); 173a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling } 17496fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 175a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 176dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // Verify uses and defs. 1779f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen#ifndef NDEBUG 178dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 179dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen const MachineOperand &MO = MI->getOperand(i); 180d61c40360c3acc847263c5e5184b715c17528b09Jakob Stoklund Olesen if (!MO.isReg()) 1812578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng continue; 182dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen unsigned Reg = MO.getReg(); 1834af0f5fecb42563ff3ca5bd7fddb2f4f111e2fefJakob Stoklund Olesen if (!Reg || isReserved(Reg)) 1845de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng continue; 185dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen if (MO.isUse()) { 186d61c40360c3acc847263c5e5184b715c17528b09Jakob Stoklund Olesen if (MO.isUndef()) 187d61c40360c3acc847263c5e5184b715c17528b09Jakob Stoklund Olesen continue; 188a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng if (!isUsed(Reg)) { 189a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // Check if it's partial live: e.g. 190a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // D0 = insert_subreg D0<undef>, S0 191a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // ... D0 192a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // The problem is the insert_subreg could be eliminated. The use of 193a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // D0 is using a partially undef value. This is not *incorrect* since 194a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // S1 is can be freely clobbered. 195a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // Ideally we would like a way to model this, but leaving the 196a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng // insert_subreg around causes both correctness and performance issues. 197a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng bool SubUsed = false; 1989ebfbf8b9fd5f982e0db9293808bd32168615ba9Craig Topper for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); 199a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng unsigned SubReg = *SubRegs; ++SubRegs) 200a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng if (isUsed(SubReg)) { 201a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng SubUsed = true; 202a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng break; 203a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng } 20463c66724235ace1860e60a11ce2756d577387b29Jakob Stoklund Olesen if (!SubUsed) { 20563c66724235ace1860e60a11ce2756d577387b29Jakob Stoklund Olesen MBB->getParent()->verify(NULL, "In Register Scavenger"); 20663c66724235ace1860e60a11ce2756d577387b29Jakob Stoklund Olesen llvm_unreachable("Using an undefined register!"); 20763c66724235ace1860e60a11ce2756d577387b29Jakob Stoklund Olesen } 2081f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)SubUsed; 209a5dc45e3c8fa26e62b187284a240adf3879b56e2Evan Cheng } 210dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen } else { 211dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen assert(MO.isDef()); 212393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng#if 0 213393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng // FIXME: Enable this once we've figured out how to correctly transfer 214393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng // implicit kills during codegen passes like the coalescer. 2159390cd0e86cb3b79f6836acab2a27b275e5bde9eJakob Stoklund Olesen assert((KillRegs.test(Reg) || isUnused(Reg) || 216dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 217dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen "Re-defining a live register!"); 218393e277ecd02f52443633f6bfacdd1d4c6981212Evan Cheng#endif 2195de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng } 22096fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 2219f946a24d9e69559d1e0aeb6d128c2fa19846c92Jakob Stoklund Olesen#endif // NDEBUG 222dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen 223dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen // Commit the changes. 224dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen setUnused(KillRegs); 225dffb051c21d32209c601ca0ca6baae75b6c6463fJakob Stoklund Olesen setUsed(DefRegs); 22696fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 22796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 22869cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesenvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 229685c23e75842e64145fe319efd792abe72a827ddJakob Stoklund Olesen used = RegsAvailable; 230685c23e75842e64145fe319efd792abe72a827ddJakob Stoklund Olesen used.flip(); 231cf14613455bc32b6a17821808595263e061335bcJakob Stoklund Olesen if (includeReserved) 232cf14613455bc32b6a17821808595263e061335bcJakob Stoklund Olesen used |= ReservedRegs; 233cf14613455bc32b6a17821808595263e061335bcJakob Stoklund Olesen else 234cf14613455bc32b6a17821808595263e061335bcJakob Stoklund Olesen used.reset(ReservedRegs); 23569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen} 23669cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 237c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesenunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 238c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 239c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen I != E; ++I) 240d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach if (!isAliasUsed(*I)) { 241d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << 242d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach "\n"); 243c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen return *I; 244d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach } 245c0823fe7c679ca8f7d1667a310c2fca97b9402d5Jakob Stoklund Olesen return 0; 24696fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 247b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 248d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach/// getRegsAvailable - Return all available registers in the register class 249d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach/// in Mask. 25027ea9999e84dfb1e6c2baf06ec27a92f12753917Jim GrosbachBitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { 25127ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach BitVector Mask(TRI->getNumRegs()); 252d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 253d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach I != E; ++I) 254d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach if (!isAliasUsed(*I)) 255d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach Mask.set(*I); 25627ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach return Mask; 257d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach} 258d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach 25966a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// findSurvivorReg - Return the candidate register that is unused for the 260d9642faf7c66273eb3a8d99e5fa6b542da5374ddJim Grosbach/// longest after StargMII. UseMI is set to the instruction where the search 26166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// stopped. 26266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// 26366a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// No more than InstrLimit instructions are inspected. 26466a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen/// 26507d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbachunsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 26666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen BitVector &Candidates, 26766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen unsigned InstrLimit, 26866a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen MachineBasicBlock::iterator &UseMI) { 26966a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen int Survivor = Candidates.find_first(); 27066a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen assert(Survivor > 0 && "No candidates for scavenging"); 27166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 27266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 27307d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach assert(StartMI != ME && "MI already at terminator"); 27407d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach MachineBasicBlock::iterator RestorePointMI = StartMI; 27507d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach MachineBasicBlock::iterator MI = StartMI; 27666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 27707d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach bool inVirtLiveRange = false; 27866a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 2791c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach if (MI->isDebugValue()) { 2801c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach ++InstrLimit; // Don't count debug instructions 2811c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach continue; 2821c8ab781d5b24bc473b4baa8f3fb6e9b55597aa3Jim Grosbach } 28307d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach bool isVirtKillInsn = false; 28407d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach bool isVirtDefInsn = false; 28566a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // Remove any candidates touched by instruction. 28666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 28766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen const MachineOperand &MO = MI->getOperand(i); 288be2af7ee781cd0083124514f497b8cf3070776ecJakob Stoklund Olesen if (MO.isRegMask()) 289be2af7ee781cd0083124514f497b8cf3070776ecJakob Stoklund Olesen Candidates.clearBitsNotInMask(MO.getRegMask()); 29007d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 29166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen continue; 29207d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 29307d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (MO.isDef()) 29407d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach isVirtDefInsn = true; 29507d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach else if (MO.isKill()) 29607d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach isVirtKillInsn = true; 29707d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach continue; 29807d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach } 29966a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen Candidates.reset(MO.getReg()); 300e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *R = TRI->getAliasSet(MO.getReg()); *R; R++) 30166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen Candidates.reset(*R); 30266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen } 30307d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // If we're not in a virtual reg's live range, this is a valid 30407d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // restore point. 30507d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (!inVirtLiveRange) RestorePointMI = MI; 30607d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach 30707d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // Update whether we're in the live range of a virtual register 30807d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (isVirtKillInsn) inVirtLiveRange = false; 30907d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (isVirtDefInsn) inVirtLiveRange = true; 3108c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen 31166a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // Was our survivor untouched by this instruction? 31266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen if (Candidates.test(Survivor)) 3138c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen continue; 31466a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 31566a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // All candidates gone? 31666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen if (Candidates.none()) 31766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen break; 31866a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 31966a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen Survivor = Candidates.find_first(); 320b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 32107d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach // If we ran off the end, that's where we want to restore. 32207d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach if (MI == ME) RestorePointMI = ME; 32307d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach assert (RestorePointMI != StartMI && 32407d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach "No available scavenger restore location!"); 32566a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen 32666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen // We ran out of candidates, so stop the search. 32707d4964d1fc10a404f9bafd7c30b46322fe9293fJim Grosbach UseMI = RestorePointMI; 32866a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen return Survivor; 329b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 330b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 331b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 3328e3347332120956538a6d882b02719e34b57f0cdEvan Cheng MachineBasicBlock::iterator I, 3338e3347332120956538a6d882b02719e34b57f0cdEvan Cheng int SPAdj) { 3349204ddad5c30216e48c5bba0528ba24d66a22e13Jim Grosbach // Consider all allocatable registers in the register class initially 3359204ddad5c30216e48c5bba0528ba24d66a22e13Jim Grosbach BitVector Candidates = 3369204ddad5c30216e48c5bba0528ba24d66a22e13Jim Grosbach TRI->getAllocatableSet(*I->getParent()->getParent(), RC); 337b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 338b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Exclude all the registers being used by the instruction. 339b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 340b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineOperand &MO = I->getOperand(i); 341366e021fb2cb0efb8e727ef5e40bd55cef974c7aJim Grosbach if (MO.isReg() && MO.getReg() != 0 && 342366e021fb2cb0efb8e727ef5e40bd55cef974c7aJim Grosbach !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 343b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates.reset(MO.getReg()); 344b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 345b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 346ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach // Try to find a register that's unused if there is one, as then we won't 34727ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach // have to spill. Search explicitly rather than masking out based on 34827ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach // RegsAvailable, as RegsAvailable does not take aliases into account. 34927ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach // That's what getRegsAvailable() is for. 35027ea9999e84dfb1e6c2baf06ec27a92f12753917Jim Grosbach BitVector Available = getRegsAvailable(RC); 351685c23e75842e64145fe319efd792abe72a827ddJakob Stoklund Olesen Available &= Candidates; 352685c23e75842e64145fe319efd792abe72a827ddJakob Stoklund Olesen if (Available.any()) 353685c23e75842e64145fe319efd792abe72a827ddJakob Stoklund Olesen Candidates = Available; 354ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach 355527c250a9080a5b6cf0053a6215037c3769ff4a0Bill Wendling // Find the register whose use is furthest away. 35666a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen MachineBasicBlock::iterator UseMI; 35766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 3588c54a620618a77f18af4bb5a0fb48dc741044b91Jakob Stoklund Olesen 359ed903d746d96d071305b8182680595ba281b3f12Jim Grosbach // If we found an unused register there is no reason to spill it. 360d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach if (!isAliasUsed(SReg)) { 361d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n"); 36266a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen return SReg; 363d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach } 364b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 365b36eb9df205aa83cfdfc8ecebc93e1043d6253d9Jakob Stoklund Olesen assert(ScavengedReg == 0 && 366f36892335b4919b9120e48a792e6b3630b9de978Torok Edwin "Scavenger slot is live, unable to scavenge another register!"); 367b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 368e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // Avoid infinite regress 369e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby ScavengedReg = SReg; 370e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby 371540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // If the target knows how to save/restore the register, let it do so; 372540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // otherwise, use the emergency stack spill slot. 373d482f55af135081aee7f7ab972bb8973f189c88fJim Grosbach if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 374540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // Spill the scavenged register before I. 375540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach assert(ScavengingFrameIndex >= 0 && 3766e214805b1163c0e3cd218963c9e66ea244956b2Jim Grosbach "Cannot scavenge register without an emergency spill slot!"); 377746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC,TRI); 378540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach MachineBasicBlock::iterator II = prior(I); 379fcb4a8ead3cd8d9540d5eaa448af5d14a0ee341aJim Grosbach TRI->eliminateFrameIndex(II, SPAdj, this); 380540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach 381540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach // Restore the scavenged register before its use (or first terminator). 382746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC, TRI); 38329bed1c8bb491a5fe609d58c5e560929117a859eJim Grosbach II = prior(UseMI); 384fcb4a8ead3cd8d9540d5eaa448af5d14a0ee341aJim Grosbach TRI->eliminateFrameIndex(II, SPAdj, this); 385d482f55af135081aee7f7ab972bb8973f189c88fJim Grosbach } 386d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng 38766a39699fb6b862e674415b32d307263812e996eJakob Stoklund Olesen ScavengeRestore = prior(UseMI); 388540b05d227a79443b2a7b07d5152a35cb6392abfJim Grosbach 389c40f6130344c53d5f0833838eddca1f94670ea1dEvan Cheng // Doing this here leads to infinite regress. 390e0161ea1050fd4107f3307b1e25b3aac02c2ba16John Mosby // ScavengedReg = SReg; 391b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedRC = RC; 392b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 393d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << 394d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach "\n"); 395d273a003b6ad27720b2f0bab1a0996150a3d6fbeJim Grosbach 396b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return SReg; 397b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 398