RegisterScavenging.cpp revision 7d696d80409aad20bb5da0fc4eccab941dd371d4
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" 1996fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/MachineFunction.h" 2096fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/MachineBasicBlock.h" 2196fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/MachineInstr.h" 221dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 237d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 246f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 2596fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/Target/TargetInstrInfo.h" 2696fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/Target/TargetMachine.h" 271dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng#include "llvm/ADT/SmallPtrSet.h" 28d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman#include "llvm/ADT/SmallVector.h" 29ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng#include "llvm/ADT/STLExtras.h" 3096fa612373e258120d351ed14361f964ad22f99dEvan Chengusing namespace llvm; 3196fa612373e258120d351ed14361f964ad22f99dEvan Cheng 32ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling/// RedefinesSuperRegPart - Return true if the specified register is redefining 33ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling/// part of a super-register. 34ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendlingstatic bool RedefinesSuperRegPart(const MachineInstr *MI, unsigned SubReg, 35ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling const TargetRegisterInfo *TRI) { 36d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng bool SeenSuperUse = false; 37d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng bool SeenSuperDef = false; 38ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 39ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling const MachineOperand &MO = MI->getOperand(i); 404784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng if (!MO.isReg() || MO.isUndef()) 41ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling continue; 4243e2a035309f4e353a8bd5547d10125414597e74Duncan Sands if (TRI->isSuperRegister(SubReg, MO.getReg())) { 43d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng if (MO.isUse()) 44d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng SeenSuperUse = true; 45d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng else if (MO.isImplicit()) 46d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng SeenSuperDef = true; 4743e2a035309f4e353a8bd5547d10125414597e74Duncan Sands } 48ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling } 49ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling 50d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng return SeenSuperDef && SeenSuperUse; 51ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling} 52ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling 53ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendlingstatic bool RedefinesSuperRegPart(const MachineInstr *MI, 54ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling const MachineOperand &MO, 55ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling const TargetRegisterInfo *TRI) { 56d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman assert(MO.isReg() && MO.isDef() && "Not a register def!"); 57ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling return RedefinesSuperRegPart(MI, MO.getReg(), TRI); 58ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling} 59ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling 60a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling/// setUsed - Set the register and its sub-registers as being used. 61459a7c6b6ad9c4fcb9f119aa6eaaf2769b00d9b1Evan Chengvoid RegScavenger::setUsed(unsigned Reg) { 62a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling RegsAvailable.reset(Reg); 63a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 646130f66eaae89f8878590796977678afa8448926Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 65459a7c6b6ad9c4fcb9f119aa6eaaf2769b00d9b1Evan Cheng unsigned SubReg = *SubRegs; ++SubRegs) 66a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling RegsAvailable.reset(SubReg); 67a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling} 68a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 69a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling/// setUnused - Set the register and its sub-registers as being unused. 70ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendlingvoid RegScavenger::setUnused(unsigned Reg, const MachineInstr *MI) { 71a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling RegsAvailable.set(Reg); 72a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 736130f66eaae89f8878590796977678afa8448926Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 74a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling unsigned SubReg = *SubRegs; ++SubRegs) 75459a7c6b6ad9c4fcb9f119aa6eaaf2769b00d9b1Evan Cheng if (!RedefinesSuperRegPart(MI, Reg, TRI)) 76ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling RegsAvailable.set(SubReg); 77a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling} 78a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 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 89898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!MBB) { 906130f66eaae89f8878590796977678afa8448926Evan Cheng NumPhysRegs = TRI->getNumRegs(); 91c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable.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); 986130f66eaae89f8878590796977678afa8448926Evan Cheng const unsigned *CSRegs = TRI->getCalleeSavedRegs(); 99898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (CSRegs != NULL) 100898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng for (unsigned i = 0; CSRegs[i]; ++i) 101898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng CalleeSavedRegs.set(CSRegs[i]); 102898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 103898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 104898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng MBB = mbb; 105caddd590f72376aaac531c1004be0535b460992aEvan Cheng ScavengedReg = 0; 106caddd590f72376aaac531c1004be0535b460992aEvan Cheng ScavengedRC = NULL; 107d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengeRestore = NULL; 108d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng CurrDist = 0; 109d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DistanceMap.clear(); 110898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 111898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng // All registers started out unused. 112c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable.set(); 11396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 114a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng // Reserved registers are always used. 115c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable ^= ReservedRegs; 11696fa612373e258120d351ed14361f964ad22f99dEvan Cheng 117403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng // Live-in registers are in use. 118403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng if (!MBB->livein_empty()) 119403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 120403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng E = MBB->livein_end(); I != E; ++I) 121403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng setUsed(*I); 122a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 123a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng Tracking = false; 12496fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 12596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 126b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengvoid RegScavenger::restoreScavengedReg() { 127f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg, 1281dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng ScavengingFrameIndex, ScavengedRC); 129b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator II = prior(MBBI); 1306130f66eaae89f8878590796977678afa8448926Evan Cheng TRI->eliminateFrameIndex(II, 0, this); 131b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng setUsed(ScavengedReg); 132b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedReg = 0; 133b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedRC = NULL; 134b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 135b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 1362755896fd048d189bedc5e99e776b3eca010dd4eDevang Patel#ifndef NDEBUG 1371dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng/// isLiveInButUnusedBefore - Return true if register is livein the MBB not 1381dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng/// not used before it reaches the MI that defines register. 1391dc7869025d91906e8305e921ddb82dac780d70eEvan Chengstatic bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI, 1401dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng MachineBasicBlock *MBB, 1411dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng const TargetRegisterInfo *TRI, 1421dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng MachineRegisterInfo* MRI) { 1431dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng // First check if register is livein. 1441dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng bool isLiveIn = false; 1451dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 1461dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng E = MBB->livein_end(); I != E; ++I) 1471dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng if (Reg == *I || TRI->isSuperRegister(Reg, *I)) { 1481dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng isLiveIn = true; 1491dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng break; 1501dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng } 1511dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng if (!isLiveIn) 1521dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng return false; 1531dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng 1541dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng // Is there any use of it before the specified MI? 1551dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng SmallPtrSet<MachineInstr*, 4> UsesInMBB; 1561dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 1571dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng UE = MRI->use_end(); UI != UE; ++UI) { 1581dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng MachineInstr *UseMI = &*UI; 1591dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng if (UseMI->getParent() == MBB) 1601dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng UsesInMBB.insert(UseMI); 1611dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng } 1621dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng if (UsesInMBB.empty()) 1631dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng return true; 1641dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng 1651dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I) 1661dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng if (UsesInMBB.count(&*I)) 1671dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng return false; 1681dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng return true; 1691dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng} 1702755896fd048d189bedc5e99e776b3eca010dd4eDevang Patel#endif 1711dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng 17296fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::forward() { 173ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr forward. 174898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!Tracking) { 175898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng MBBI = MBB->begin(); 176898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng Tracking = true; 177898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } else { 178898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 179ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MBBI = next(MBBI); 180898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 181ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 18296fa612373e258120d351ed14361f964ad22f99dEvan Cheng MachineInstr *MI = MBBI; 183d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DistanceMap.insert(std::make_pair(MI, CurrDist++)); 184b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 185d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (MI == ScavengeRestore) { 186d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengedReg = 0; 187d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengedRC = NULL; 188d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengeRestore = NULL; 189d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 190b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 191459a7c6b6ad9c4fcb9f119aa6eaaf2769b00d9b1Evan Cheng#if 0 192459a7c6b6ad9c4fcb9f119aa6eaaf2769b00d9b1Evan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 193459a7c6b6ad9c4fcb9f119aa6eaaf2769b00d9b1Evan Cheng return; 194459a7c6b6ad9c4fcb9f119aa6eaaf2769b00d9b1Evan Cheng#endif 19550564ebc9e3d7ff806062023e6511e91065df0d2Evan Cheng 1969c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // Separate register operands into 3 classes: uses, defs, earlyclobbers. 19763a431c6704e711713b0258bd987cfb257767cf4Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs; 19863a431c6704e711713b0258bd987cfb257767cf4Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs; 19963a431c6704e711713b0258bd987cfb257767cf4Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs; 20096fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 20196fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 2024784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng if (!MO.isReg() || MO.getReg() == 0 || MO.isUndef()) 20396fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 2049c64bf3905ea338719800008c03d95a17cb26689Evan Cheng if (MO.isUse()) 20563a431c6704e711713b0258bd987cfb257767cf4Evan Cheng UseMOs.push_back(std::make_pair(&MO,i)); 2069c64bf3905ea338719800008c03d95a17cb26689Evan Cheng else if (MO.isEarlyClobber()) 20763a431c6704e711713b0258bd987cfb257767cf4Evan Cheng EarlyClobberMOs.push_back(std::make_pair(&MO,i)); 2089c64bf3905ea338719800008c03d95a17cb26689Evan Cheng else 20963a431c6704e711713b0258bd987cfb257767cf4Evan Cheng DefMOs.push_back(std::make_pair(&MO,i)); 2109c64bf3905ea338719800008c03d95a17cb26689Evan Cheng } 211a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2129c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // Process uses first. 2134a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng BitVector KillRegs(NumPhysRegs); 2149c64bf3905ea338719800008c03d95a17cb26689Evan Cheng for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { 21563a431c6704e711713b0258bd987cfb257767cf4Evan Cheng const MachineOperand MO = *UseMOs[i].first; 21696fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 217a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 218d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng assert(isUsed(Reg) && "Using an undefined register!"); 219a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 220459a7c6b6ad9c4fcb9f119aa6eaaf2769b00d9b1Evan Cheng if (MO.isKill() && !isReserved(Reg)) { 2214a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng KillRegs.set(Reg); 222a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2239c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // Mark sub-registers as used. 2246130f66eaae89f8878590796977678afa8448926Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 225a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling unsigned SubReg = *SubRegs; ++SubRegs) 2264a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng KillRegs.set(SubReg); 227a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling } 22896fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 229a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 23096fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Change states of all registers after all the uses are processed to guard 23196fa612373e258120d351ed14361f964ad22f99dEvan Cheng // against multiple uses. 2324a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng setUnused(KillRegs); 233a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2349c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // Process early clobber defs then process defs. We can have a early clobber 2359c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // that is dead, it should not conflict with a def that happens one "slot" 2369c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // (see InstrSlots in LiveIntervalAnalysis.h) later. 2379c64bf3905ea338719800008c03d95a17cb26689Evan Cheng unsigned NumECs = EarlyClobberMOs.size(); 2389c64bf3905ea338719800008c03d95a17cb26689Evan Cheng unsigned NumDefs = DefMOs.size(); 239a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2409c64bf3905ea338719800008c03d95a17cb26689Evan Cheng for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) { 2419c64bf3905ea338719800008c03d95a17cb26689Evan Cheng const MachineOperand &MO = (i < NumECs) 24263a431c6704e711713b0258bd987cfb257767cf4Evan Cheng ? *EarlyClobberMOs[i].first : *DefMOs[i-NumECs].first; 24363a431c6704e711713b0258bd987cfb257767cf4Evan Cheng unsigned Idx = (i < NumECs) 24463a431c6704e711713b0258bd987cfb257767cf4Evan Cheng ? EarlyClobberMOs[i].second : DefMOs[i-NumECs].second; 2450badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng unsigned Reg = MO.getReg(); 2462578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng if (MO.isUndef()) 2472578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng continue; 248a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2495de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng // If it's dead upon def, then it is now free. 2505de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng if (MO.isDead()) { 251ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling setUnused(Reg, MI); 2525de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng continue; 2535de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng } 254a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 25596fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 2562578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng unsigned UseIdx; 2572578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng if (MI->isRegTiedToUseOperand(Idx, &UseIdx) && 2582578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng !MI->getOperand(UseIdx).isUndef()) { 2595db322acefc3089c133b8f3a33fa0a3ce90e2001Evan Cheng assert(isUsed(Reg) && "Using an undefined register!"); 26096fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 2610badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng } 262a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 263d118342b25eb6a3a67792cda9fce9b4c1e45a867Dan Gohman // Skip if this is merely redefining part of a super-register. 264ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling if (RedefinesSuperRegPart(MI, MO, TRI)) 265ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling continue; 266ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling 2675d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng // Implicit def is allowed to "re-define" any register. Similarly, 2685d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng // implicitly defined registers can be clobbered. 2691dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng assert((isReserved(Reg) || isUnused(Reg) || 2701dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 2715db322acefc3089c133b8f3a33fa0a3ce90e2001Evan Cheng "Re-defining a live register!"); 272459a7c6b6ad9c4fcb9f119aa6eaaf2769b00d9b1Evan Cheng setUsed(Reg); 27396fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 27496fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 27596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 27696fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::backward() { 277898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert(Tracking && "Not tracking states!"); 278ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng assert(MBBI != MBB->begin() && "Already at start of basic block!"); 279ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr backward. 280ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MBBI = prior(MBBI); 281ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 282ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MachineInstr *MI = MBBI; 283d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DistanceMap.erase(MI); 284d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng --CurrDist; 2853a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 2863a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng // Separate register operands into 3 classes: uses, defs, earlyclobbers. 2873a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs; 2883a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs; 2893a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs; 29096fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 29196fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 2924784f1fc73abf6005b7b7262d395af71b57b1255Evan Cheng if (!MO.isReg() || MO.getReg() == 0 || MO.isUndef()) 29396fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 2943a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng if (MO.isUse()) 2953a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng UseMOs.push_back(std::make_pair(&MO,i)); 2963a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng else if (MO.isEarlyClobber()) 2973a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng EarlyClobberMOs.push_back(std::make_pair(&MO,i)); 2983a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng else 2993a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng DefMOs.push_back(std::make_pair(&MO,i)); 3003a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng } 3013a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 3023a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 3033a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng // Process defs first. 3043a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng unsigned NumECs = EarlyClobberMOs.size(); 3053a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng unsigned NumDefs = DefMOs.size(); 3063a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) { 3073a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng const MachineOperand &MO = (i < NumDefs) 3083a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng ? *DefMOs[i].first : *EarlyClobberMOs[i-NumDefs].first; 3093a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng unsigned Idx = (i < NumECs) 3103a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng ? DefMOs[i].second : EarlyClobberMOs[i-NumDefs].second; 3112578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng if (MO.isUndef()) 3122578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng continue; 3133a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 31496fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 315d9df5017040489303acb57bdd8697ef0f8bafc08Bob Wilson if (MI->isRegTiedToUseOperand(Idx)) 31696fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 3173a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 31896fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 31996fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUsed(Reg)); 32096fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!isReserved(Reg)) 321ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling setUnused(Reg, MI); 32296fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 32396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 32496fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process uses. 3259c64bf3905ea338719800008c03d95a17cb26689Evan Cheng BitVector UseRegs(NumPhysRegs); 3263a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { 3273a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng const MachineOperand MO = *UseMOs[i].first; 32896fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 32996fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUnused(Reg) || isReserved(Reg)); 3309c64bf3905ea338719800008c03d95a17cb26689Evan Cheng UseRegs.set(Reg); 331a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 332a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling // Set the sub-registers as "used". 3336130f66eaae89f8878590796977678afa8448926Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 334a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling unsigned SubReg = *SubRegs; ++SubRegs) 3359c64bf3905ea338719800008c03d95a17cb26689Evan Cheng UseRegs.set(SubReg); 33696fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 3379c64bf3905ea338719800008c03d95a17cb26689Evan Cheng setUsed(UseRegs); 33896fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 33996fa612373e258120d351ed14361f964ad22f99dEvan Cheng 34069cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesenvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 34169cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (includeReserved) 342c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen used = ~RegsAvailable; 34369cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen else 344c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen used = ~RegsAvailable & ~ReservedRegs; 34569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen} 34669cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 34796fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// CreateRegClassMask - Set the bits that represent the registers in the 34896fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// TargetRegisterClass. 34996fa612373e258120d351ed14361f964ad22f99dEvan Chengstatic void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 35096fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 35196fa612373e258120d351ed14361f964ad22f99dEvan Cheng ++I) 35296fa612373e258120d351ed14361f964ad22f99dEvan Cheng Mask.set(*I); 35396fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 35496fa612373e258120d351ed14361f964ad22f99dEvan Cheng 35596fa612373e258120d351ed14361f964ad22f99dEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 3565196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng const BitVector &Candidates) const { 3575196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 358c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen BitVector RegsAvailableCopy(NumPhysRegs, false); 359c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen CreateRegClassMask(RegClass, RegsAvailableCopy); 360c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= RegsAvailable; 3615196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 3625196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Restrict the search to candidates. 363c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= Candidates; 3645196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 3655196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 366c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen int Reg = RegsAvailableCopy.find_first(); 3675196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng return (Reg == -1) ? 0 : Reg; 3685196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng} 3695196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 3705196b3680cf8df32b6c763e3d97e963e45150e5aEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 37196fa612373e258120d351ed14361f964ad22f99dEvan Cheng bool ExCalleeSaved) const { 37296fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 373c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen BitVector RegsAvailableCopy(NumPhysRegs, false); 374c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen CreateRegClassMask(RegClass, RegsAvailableCopy); 375c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= RegsAvailable; 37696fa612373e258120d351ed14361f964ad22f99dEvan Cheng 37796fa612373e258120d351ed14361f964ad22f99dEvan Cheng // If looking for a non-callee-saved register, mask off all the callee-saved 37896fa612373e258120d351ed14361f964ad22f99dEvan Cheng // registers. 37996fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (ExCalleeSaved) 380c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= ~CalleeSavedRegs; 38196fa612373e258120d351ed14361f964ad22f99dEvan Cheng 38296fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 383c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen int Reg = RegsAvailableCopy.find_first(); 38496fa612373e258120d351ed14361f964ad22f99dEvan Cheng return (Reg == -1) ? 0 : Reg; 38596fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 386b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 387d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng/// findFirstUse - Calculate the distance to the first use of the 388b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng/// specified register. 389d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan ChengMachineInstr* 390d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan ChengRegScavenger::findFirstUse(MachineBasicBlock *MBB, 391d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineBasicBlock::iterator I, unsigned Reg, 392d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned &Dist) { 393d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *UseMI = 0; 394d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng Dist = ~0U; 395d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg), 396d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng RE = MRI->reg_end(); RI != RE; ++RI) { 397d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *UDMI = &*RI; 398d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (UDMI->getParent() != MBB) 399d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng continue; 400d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI); 401d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (DI == DistanceMap.end()) { 402d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng // If it's not in map, it's below current MI, let's initialize the 403d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng // map. 404d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng I = next(I); 405d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned Dist = CurrDist + 1; 406d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng while (I != MBB->end()) { 407d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DistanceMap.insert(std::make_pair(I, Dist++)); 408d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng I = next(I); 409d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 410d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 411d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DI = DistanceMap.find(UDMI); 412d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (DI->second > CurrDist && DI->second < Dist) { 413d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng Dist = DI->second; 414d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng UseMI = UDMI; 415d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 416b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 417d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng return UseMI; 418b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 419b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 420b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 4218e3347332120956538a6d882b02719e34b57f0cdEvan Cheng MachineBasicBlock::iterator I, 4228e3347332120956538a6d882b02719e34b57f0cdEvan Cheng int SPAdj) { 423b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng assert(ScavengingFrameIndex >= 0 && 424b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng "Cannot scavenge a register without an emergency spill slot!"); 425b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 426b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Mask off the registers which are not in the TargetRegisterClass. 427b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng BitVector Candidates(NumPhysRegs, false); 428b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng CreateRegClassMask(RC, Candidates); 429b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates ^= ReservedRegs; // Do not include reserved registers. 430b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 431b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Exclude all the registers being used by the instruction. 432b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 433b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineOperand &MO = I->getOperand(i); 434d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg()) 435b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates.reset(MO.getReg()); 436b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 437b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 438527c250a9080a5b6cf0053a6215037c3769ff4a0Bill Wendling // Find the register whose use is furthest away. 439b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned SReg = 0; 440b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned MaxDist = 0; 441d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *MaxUseMI = 0; 442b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng int Reg = Candidates.find_first(); 443b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng while (Reg != -1) { 444d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned Dist; 445d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist); 446d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 447d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned AsDist; 448d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist); 449d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (AsDist < Dist) { 450d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng Dist = AsDist; 451d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng UseMI = AsUseMI; 452d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 453d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 454b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (Dist >= MaxDist) { 455b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MaxDist = Dist; 456d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MaxUseMI = UseMI; 457b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng SReg = Reg; 458b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 459b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Reg = Candidates.find_next(Reg); 460b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 461b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 462b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (ScavengedReg != 0) { 4637d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin LLVM_UNREACHABLE("Scavenger slot is live, unable to scavenge another register!"); 464b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 465b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 466d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng // Spill the scavenged register before I. 467f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); 468b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator II = prior(I); 4696130f66eaae89f8878590796977678afa8448926Evan Cheng TRI->eliminateFrameIndex(II, SPAdj, this); 470d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng 471d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng // Restore the scavenged register before its use (or first terminator). 472d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng II = MaxUseMI 473d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator(); 474d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC); 475d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengeRestore = prior(II); 476b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedReg = SReg; 477b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedRC = RC; 478b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 479b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return SReg; 480b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 481