RegisterScavenging.cpp revision d9df5017040489303acb57bdd8697ef0f8bafc08
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" 236f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 2496fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/Target/TargetInstrInfo.h" 2596fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/Target/TargetMachine.h" 261dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng#include "llvm/ADT/SmallPtrSet.h" 27d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman#include "llvm/ADT/SmallVector.h" 28ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng#include "llvm/ADT/STLExtras.h" 2996fa612373e258120d351ed14361f964ad22f99dEvan Chengusing namespace llvm; 3096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 31ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling/// RedefinesSuperRegPart - Return true if the specified register is redefining 32ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling/// part of a super-register. 33ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendlingstatic bool RedefinesSuperRegPart(const MachineInstr *MI, unsigned SubReg, 34ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling const TargetRegisterInfo *TRI) { 35d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng bool SeenSuperUse = false; 36d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng bool SeenSuperDef = false; 37ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 38ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling const MachineOperand &MO = MI->getOperand(i); 39d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 40ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling continue; 4143e2a035309f4e353a8bd5547d10125414597e74Duncan Sands if (TRI->isSuperRegister(SubReg, MO.getReg())) { 42d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng if (MO.isUse()) 43d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng SeenSuperUse = true; 44d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng else if (MO.isImplicit()) 45d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng SeenSuperDef = true; 4643e2a035309f4e353a8bd5547d10125414597e74Duncan Sands } 47ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling } 48ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling 49d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng return SeenSuperDef && SeenSuperUse; 50ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling} 51ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling 52ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendlingstatic bool RedefinesSuperRegPart(const MachineInstr *MI, 53ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling const MachineOperand &MO, 54ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling const TargetRegisterInfo *TRI) { 55d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman assert(MO.isReg() && MO.isDef() && "Not a register def!"); 56ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling return RedefinesSuperRegPart(MI, MO.getReg(), TRI); 57ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling} 58ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling 59a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling/// setUsed - Set the register and its sub-registers as being used. 605d3600f5766e93cb459ef6108fba00c052aa6388Evan Chengvoid RegScavenger::setUsed(unsigned Reg, bool ImpDef) { 61a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling RegsAvailable.reset(Reg); 625d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng ImplicitDefed[Reg] = ImpDef; 63a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 646130f66eaae89f8878590796977678afa8448926Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 655d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng unsigned SubReg = *SubRegs; ++SubRegs) { 66a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling RegsAvailable.reset(SubReg); 675d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng ImplicitDefed[SubReg] = ImpDef; 685d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng } 69a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling} 70a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 71a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling/// setUnused - Set the register and its sub-registers as being unused. 72ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendlingvoid RegScavenger::setUnused(unsigned Reg, const MachineInstr *MI) { 73a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling RegsAvailable.set(Reg); 745d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng ImplicitDefed.reset(Reg); 75a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 766130f66eaae89f8878590796977678afa8448926Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 77a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling unsigned SubReg = *SubRegs; ++SubRegs) 785d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng if (!RedefinesSuperRegPart(MI, Reg, TRI)) { 79ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling RegsAvailable.set(SubReg); 805d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng ImplicitDefed.reset(SubReg); 815d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng } 82a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling} 83a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 84a3756ee7fe384210eddcfd66e2934439960b13a1Evan Chengvoid RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 854542611bb9793e8376d7d5f33b4a1e2d11712894Dan Gohman MachineFunction &MF = *mbb->getParent(); 8696fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetMachine &TM = MF.getTarget(); 87b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng TII = TM.getInstrInfo(); 886130f66eaae89f8878590796977678afa8448926Evan Cheng TRI = TM.getRegisterInfo(); 891dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng MRI = &MF.getRegInfo(); 9096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 916130f66eaae89f8878590796977678afa8448926Evan Cheng assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 92898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng "Target changed?"); 93898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 94898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!MBB) { 956130f66eaae89f8878590796977678afa8448926Evan Cheng NumPhysRegs = TRI->getNumRegs(); 96c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable.resize(NumPhysRegs); 975d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng ImplicitDefed.resize(NumPhysRegs); 98898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 99a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng // Create reserved registers bitvector. 1006130f66eaae89f8878590796977678afa8448926Evan Cheng ReservedRegs = TRI->getReservedRegs(MF); 101a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 102898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng // Create callee-saved registers bitvector. 103898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng CalleeSavedRegs.resize(NumPhysRegs); 1046130f66eaae89f8878590796977678afa8448926Evan Cheng const unsigned *CSRegs = TRI->getCalleeSavedRegs(); 105898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (CSRegs != NULL) 106898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng for (unsigned i = 0; CSRegs[i]; ++i) 107898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng CalleeSavedRegs.set(CSRegs[i]); 108898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 109898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 110898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng MBB = mbb; 111caddd590f72376aaac531c1004be0535b460992aEvan Cheng ScavengedReg = 0; 112caddd590f72376aaac531c1004be0535b460992aEvan Cheng ScavengedRC = NULL; 113d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengeRestore = NULL; 114d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng CurrDist = 0; 115d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DistanceMap.clear(); 1161385758215bb31ba042a3d42e40d28e521616a0cDan Gohman ImplicitDefed.reset(); 117898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 118898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng // All registers started out unused. 119c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable.set(); 12096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 121a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng // Reserved registers are always used. 122c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable ^= ReservedRegs; 12396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 124403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng // Live-in registers are in use. 125403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng if (!MBB->livein_empty()) 126403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 127403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng E = MBB->livein_end(); I != E; ++I) 128403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng setUsed(*I); 129a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 130a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng Tracking = false; 13196fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 13296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 133b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengvoid RegScavenger::restoreScavengedReg() { 134f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg, 1351dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng ScavengingFrameIndex, ScavengedRC); 136b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator II = prior(MBBI); 1376130f66eaae89f8878590796977678afa8448926Evan Cheng TRI->eliminateFrameIndex(II, 0, this); 138b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng setUsed(ScavengedReg); 139b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedReg = 0; 140b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedRC = NULL; 141b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 142b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 1432755896fd048d189bedc5e99e776b3eca010dd4eDevang Patel#ifndef NDEBUG 1441dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng/// isLiveInButUnusedBefore - Return true if register is livein the MBB not 1451dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng/// not used before it reaches the MI that defines register. 1461dc7869025d91906e8305e921ddb82dac780d70eEvan Chengstatic bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI, 1471dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng MachineBasicBlock *MBB, 1481dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng const TargetRegisterInfo *TRI, 1491dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng MachineRegisterInfo* MRI) { 1501dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng // First check if register is livein. 1511dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng bool isLiveIn = false; 1521dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 1531dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng E = MBB->livein_end(); I != E; ++I) 1541dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng if (Reg == *I || TRI->isSuperRegister(Reg, *I)) { 1551dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng isLiveIn = true; 1561dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng break; 1571dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng } 1581dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng if (!isLiveIn) 1591dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng return false; 1601dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng 1611dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng // Is there any use of it before the specified MI? 1621dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng SmallPtrSet<MachineInstr*, 4> UsesInMBB; 1631dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 1641dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng UE = MRI->use_end(); UI != UE; ++UI) { 1651dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng MachineInstr *UseMI = &*UI; 1661dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng if (UseMI->getParent() == MBB) 1671dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng UsesInMBB.insert(UseMI); 1681dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng } 1691dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng if (UsesInMBB.empty()) 1701dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng return true; 1711dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng 1721dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I) 1731dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng if (UsesInMBB.count(&*I)) 1741dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng return false; 1751dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng return true; 1761dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng} 1772755896fd048d189bedc5e99e776b3eca010dd4eDevang Patel#endif 1781dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng 17996fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::forward() { 180ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr forward. 181898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!Tracking) { 182898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng MBBI = MBB->begin(); 183898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng Tracking = true; 184898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } else { 185898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 186ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MBBI = next(MBBI); 187898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 188ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 18996fa612373e258120d351ed14361f964ad22f99dEvan Cheng MachineInstr *MI = MBBI; 190d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DistanceMap.insert(std::make_pair(MI, CurrDist++)); 191b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 192d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (MI == ScavengeRestore) { 193d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengedReg = 0; 194d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengedRC = NULL; 195d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengeRestore = NULL; 196d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 197b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 1989c64bf3905ea338719800008c03d95a17cb26689Evan Cheng bool IsImpDef = MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF; 1999c64bf3905ea338719800008c03d95a17cb26689Evan Cheng 2009c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // Separate register operands into 3 classes: uses, defs, earlyclobbers. 20163a431c6704e711713b0258bd987cfb257767cf4Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs; 20263a431c6704e711713b0258bd987cfb257767cf4Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs; 20363a431c6704e711713b0258bd987cfb257767cf4Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs; 20496fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 20596fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 2069c64bf3905ea338719800008c03d95a17cb26689Evan Cheng if (!MO.isReg() || MO.getReg() == 0) 20796fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 2089c64bf3905ea338719800008c03d95a17cb26689Evan Cheng if (MO.isUse()) 20963a431c6704e711713b0258bd987cfb257767cf4Evan Cheng UseMOs.push_back(std::make_pair(&MO,i)); 2109c64bf3905ea338719800008c03d95a17cb26689Evan Cheng else if (MO.isEarlyClobber()) 21163a431c6704e711713b0258bd987cfb257767cf4Evan Cheng EarlyClobberMOs.push_back(std::make_pair(&MO,i)); 2129c64bf3905ea338719800008c03d95a17cb26689Evan Cheng else 21363a431c6704e711713b0258bd987cfb257767cf4Evan Cheng DefMOs.push_back(std::make_pair(&MO,i)); 2149c64bf3905ea338719800008c03d95a17cb26689Evan Cheng } 215a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2169c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // Process uses first. 2179c64bf3905ea338719800008c03d95a17cb26689Evan Cheng BitVector UseRegs(NumPhysRegs); 2189c64bf3905ea338719800008c03d95a17cb26689Evan Cheng for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { 21963a431c6704e711713b0258bd987cfb257767cf4Evan Cheng const MachineOperand MO = *UseMOs[i].first; 22096fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 221a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 222d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng assert(isUsed(Reg) && "Using an undefined register!"); 223a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 224a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling if (MO.isKill() && !isReserved(Reg)) { 2259c64bf3905ea338719800008c03d95a17cb26689Evan Cheng UseRegs.set(Reg); 226a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2279c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // Mark sub-registers as used. 2286130f66eaae89f8878590796977678afa8448926Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 229a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling unsigned SubReg = *SubRegs; ++SubRegs) 2309c64bf3905ea338719800008c03d95a17cb26689Evan Cheng UseRegs.set(SubReg); 231a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling } 23296fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 233a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 23496fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Change states of all registers after all the uses are processed to guard 23596fa612373e258120d351ed14361f964ad22f99dEvan Cheng // against multiple uses. 2369c64bf3905ea338719800008c03d95a17cb26689Evan Cheng setUnused(UseRegs); 237a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2389c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // Process early clobber defs then process defs. We can have a early clobber 2399c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // that is dead, it should not conflict with a def that happens one "slot" 2409c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // (see InstrSlots in LiveIntervalAnalysis.h) later. 2419c64bf3905ea338719800008c03d95a17cb26689Evan Cheng unsigned NumECs = EarlyClobberMOs.size(); 2429c64bf3905ea338719800008c03d95a17cb26689Evan Cheng unsigned NumDefs = DefMOs.size(); 243a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2449c64bf3905ea338719800008c03d95a17cb26689Evan Cheng for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) { 2459c64bf3905ea338719800008c03d95a17cb26689Evan Cheng const MachineOperand &MO = (i < NumECs) 24663a431c6704e711713b0258bd987cfb257767cf4Evan Cheng ? *EarlyClobberMOs[i].first : *DefMOs[i-NumECs].first; 24763a431c6704e711713b0258bd987cfb257767cf4Evan Cheng unsigned Idx = (i < NumECs) 24863a431c6704e711713b0258bd987cfb257767cf4Evan Cheng ? EarlyClobberMOs[i].second : DefMOs[i-NumECs].second; 2490badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng unsigned Reg = MO.getReg(); 250a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2515de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng // If it's dead upon def, then it is now free. 2525de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng if (MO.isDead()) { 253ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling setUnused(Reg, MI); 2545de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng continue; 2555de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng } 256a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 25796fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 258d9df5017040489303acb57bdd8697ef0f8bafc08Bob Wilson if (MI->isRegTiedToUseOperand(Idx)) { 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) || 2705d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng IsImpDef || isImplicitlyDefined(Reg) || 2711dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 2725db322acefc3089c133b8f3a33fa0a3ce90e2001Evan Cheng "Re-defining a live register!"); 2735d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng setUsed(Reg, IsImpDef); 27496fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 27596fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 27696fa612373e258120d351ed14361f964ad22f99dEvan Cheng 27796fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::backward() { 278898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert(Tracking && "Not tracking states!"); 279ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng assert(MBBI != MBB->begin() && "Already at start of basic block!"); 280ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr backward. 281ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MBBI = prior(MBBI); 282ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 283ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MachineInstr *MI = MBBI; 284d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DistanceMap.erase(MI); 285d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng --CurrDist; 2863a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 2873a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng // Separate register operands into 3 classes: uses, defs, earlyclobbers. 2883a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs; 2893a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs; 2903a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs; 29196fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 29296fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 2933a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng if (!MO.isReg() || MO.getReg() == 0) 29496fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 2953a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng if (MO.isUse()) 2963a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng UseMOs.push_back(std::make_pair(&MO,i)); 2973a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng else if (MO.isEarlyClobber()) 2983a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng EarlyClobberMOs.push_back(std::make_pair(&MO,i)); 2993a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng else 3003a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng DefMOs.push_back(std::make_pair(&MO,i)); 3013a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng } 3023a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 3033a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 3043a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng // Process defs first. 3053a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng unsigned NumECs = EarlyClobberMOs.size(); 3063a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng unsigned NumDefs = DefMOs.size(); 3073a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) { 3083a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng const MachineOperand &MO = (i < NumDefs) 3093a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng ? *DefMOs[i].first : *EarlyClobberMOs[i-NumDefs].first; 3103a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng unsigned Idx = (i < NumECs) 3113a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng ? DefMOs[i].second : EarlyClobberMOs[i-NumDefs].second; 3123a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 31396fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 314d9df5017040489303acb57bdd8697ef0f8bafc08Bob Wilson if (MI->isRegTiedToUseOperand(Idx)) 31596fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 3163a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 31796fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 31896fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUsed(Reg)); 31996fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!isReserved(Reg)) 320ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling setUnused(Reg, MI); 32196fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 32296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 32396fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process uses. 3249c64bf3905ea338719800008c03d95a17cb26689Evan Cheng BitVector UseRegs(NumPhysRegs); 3253a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { 3263a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng const MachineOperand MO = *UseMOs[i].first; 32796fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 32896fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUnused(Reg) || isReserved(Reg)); 3299c64bf3905ea338719800008c03d95a17cb26689Evan Cheng UseRegs.set(Reg); 330a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 331a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling // Set the sub-registers as "used". 3326130f66eaae89f8878590796977678afa8448926Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 333a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling unsigned SubReg = *SubRegs; ++SubRegs) 3349c64bf3905ea338719800008c03d95a17cb26689Evan Cheng UseRegs.set(SubReg); 33596fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 3369c64bf3905ea338719800008c03d95a17cb26689Evan Cheng setUsed(UseRegs); 33796fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 33896fa612373e258120d351ed14361f964ad22f99dEvan Cheng 33969cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesenvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 34069cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (includeReserved) 341c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen used = ~RegsAvailable; 34269cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen else 343c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen used = ~RegsAvailable & ~ReservedRegs; 34469cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen} 34569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 34696fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// CreateRegClassMask - Set the bits that represent the registers in the 34796fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// TargetRegisterClass. 34896fa612373e258120d351ed14361f964ad22f99dEvan Chengstatic void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 34996fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 35096fa612373e258120d351ed14361f964ad22f99dEvan Cheng ++I) 35196fa612373e258120d351ed14361f964ad22f99dEvan Cheng Mask.set(*I); 35296fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 35396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 35496fa612373e258120d351ed14361f964ad22f99dEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 3555196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng const BitVector &Candidates) const { 3565196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 357c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen BitVector RegsAvailableCopy(NumPhysRegs, false); 358c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen CreateRegClassMask(RegClass, RegsAvailableCopy); 359c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= RegsAvailable; 3605196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 3615196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Restrict the search to candidates. 362c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= Candidates; 3635196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 3645196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 365c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen int Reg = RegsAvailableCopy.find_first(); 3665196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng return (Reg == -1) ? 0 : Reg; 3675196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng} 3685196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 3695196b3680cf8df32b6c763e3d97e963e45150e5aEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 37096fa612373e258120d351ed14361f964ad22f99dEvan Cheng bool ExCalleeSaved) const { 37196fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 372c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen BitVector RegsAvailableCopy(NumPhysRegs, false); 373c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen CreateRegClassMask(RegClass, RegsAvailableCopy); 374c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= RegsAvailable; 37596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 37696fa612373e258120d351ed14361f964ad22f99dEvan Cheng // If looking for a non-callee-saved register, mask off all the callee-saved 37796fa612373e258120d351ed14361f964ad22f99dEvan Cheng // registers. 37896fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (ExCalleeSaved) 379c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= ~CalleeSavedRegs; 38096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 38196fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 382c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen int Reg = RegsAvailableCopy.find_first(); 38396fa612373e258120d351ed14361f964ad22f99dEvan Cheng return (Reg == -1) ? 0 : Reg; 38496fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 385b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 386d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng/// findFirstUse - Calculate the distance to the first use of the 387b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng/// specified register. 388d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan ChengMachineInstr* 389d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan ChengRegScavenger::findFirstUse(MachineBasicBlock *MBB, 390d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineBasicBlock::iterator I, unsigned Reg, 391d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned &Dist) { 392d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *UseMI = 0; 393d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng Dist = ~0U; 394d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg), 395d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng RE = MRI->reg_end(); RI != RE; ++RI) { 396d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *UDMI = &*RI; 397d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (UDMI->getParent() != MBB) 398d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng continue; 399d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI); 400d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (DI == DistanceMap.end()) { 401d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng // If it's not in map, it's below current MI, let's initialize the 402d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng // map. 403d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng I = next(I); 404d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned Dist = CurrDist + 1; 405d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng while (I != MBB->end()) { 406d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DistanceMap.insert(std::make_pair(I, Dist++)); 407d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng I = next(I); 408d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 409d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 410d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DI = DistanceMap.find(UDMI); 411d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (DI->second > CurrDist && DI->second < Dist) { 412d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng Dist = DI->second; 413d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng UseMI = UDMI; 414d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 415b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 416d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng return UseMI; 417b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 418b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 419b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 4208e3347332120956538a6d882b02719e34b57f0cdEvan Cheng MachineBasicBlock::iterator I, 4218e3347332120956538a6d882b02719e34b57f0cdEvan Cheng int SPAdj) { 422b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng assert(ScavengingFrameIndex >= 0 && 423b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng "Cannot scavenge a register without an emergency spill slot!"); 424b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 425b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Mask off the registers which are not in the TargetRegisterClass. 426b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng BitVector Candidates(NumPhysRegs, false); 427b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng CreateRegClassMask(RC, Candidates); 428b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates ^= ReservedRegs; // Do not include reserved registers. 429b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 430b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Exclude all the registers being used by the instruction. 431b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 432b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineOperand &MO = I->getOperand(i); 433d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg()) 434b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates.reset(MO.getReg()); 435b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 436b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 437527c250a9080a5b6cf0053a6215037c3769ff4a0Bill Wendling // Find the register whose use is furthest away. 438b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned SReg = 0; 439b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned MaxDist = 0; 440d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *MaxUseMI = 0; 441b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng int Reg = Candidates.find_first(); 442b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng while (Reg != -1) { 443d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned Dist; 444d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist); 445d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 446d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned AsDist; 447d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist); 448d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (AsDist < Dist) { 449d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng Dist = AsDist; 450d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng UseMI = AsUseMI; 451d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 452d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 453b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (Dist >= MaxDist) { 454b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MaxDist = Dist; 455d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MaxUseMI = UseMI; 456b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng SReg = Reg; 457b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 458b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Reg = Candidates.find_next(Reg); 459b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 460b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 461b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (ScavengedReg != 0) { 462d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng assert(0 && "Scavenger slot is live, unable to scavenge another register!"); 463d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng abort(); 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