RegisterScavenging.cpp revision 4a274e573dbbd4a6085de0d3c738c801b9d000c5
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. 2174a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng BitVector KillRegs(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 2244a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng // Kill of implicit_def defined registers are ignored. e.g. 2254a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng // entry: 0x2029ab8, LLVM BB @0x1b06080, ID#0: 2264a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng // Live Ins: %R0 2274a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng // %R0<def> = IMPLICIT_DEF 2284a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng // %R0<def> = IMPLICIT_DEF 2294a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng // STR %R0<kill>, %R0, %reg0, 0, 14, %reg0, Mem:ST(4,4) [0x1b06510 + 0] 2304a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng // %R1<def> = LDR %R0, %reg0, 24, 14, %reg0, Mem:LD(4,4) [0x1b065bc + 0] 2314a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng if (MO.isKill() && !isReserved(Reg) && !isImplicitlyDefined(Reg)) { 2324a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng KillRegs.set(Reg); 233a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2349c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // Mark sub-registers as used. 2356130f66eaae89f8878590796977678afa8448926Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 236a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling unsigned SubReg = *SubRegs; ++SubRegs) 2374a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng KillRegs.set(SubReg); 238a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling } 23996fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 240a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 24196fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Change states of all registers after all the uses are processed to guard 24296fa612373e258120d351ed14361f964ad22f99dEvan Cheng // against multiple uses. 2434a274e573dbbd4a6085de0d3c738c801b9d000c5Evan Cheng setUnused(KillRegs); 244a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2459c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // Process early clobber defs then process defs. We can have a early clobber 2469c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // that is dead, it should not conflict with a def that happens one "slot" 2479c64bf3905ea338719800008c03d95a17cb26689Evan Cheng // (see InstrSlots in LiveIntervalAnalysis.h) later. 2489c64bf3905ea338719800008c03d95a17cb26689Evan Cheng unsigned NumECs = EarlyClobberMOs.size(); 2499c64bf3905ea338719800008c03d95a17cb26689Evan Cheng unsigned NumDefs = DefMOs.size(); 250a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2519c64bf3905ea338719800008c03d95a17cb26689Evan Cheng for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) { 2529c64bf3905ea338719800008c03d95a17cb26689Evan Cheng const MachineOperand &MO = (i < NumECs) 25363a431c6704e711713b0258bd987cfb257767cf4Evan Cheng ? *EarlyClobberMOs[i].first : *DefMOs[i-NumECs].first; 25463a431c6704e711713b0258bd987cfb257767cf4Evan Cheng unsigned Idx = (i < NumECs) 25563a431c6704e711713b0258bd987cfb257767cf4Evan Cheng ? EarlyClobberMOs[i].second : DefMOs[i-NumECs].second; 2560badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng unsigned Reg = MO.getReg(); 257a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 2585de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng // If it's dead upon def, then it is now free. 2595de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng if (MO.isDead()) { 260ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling setUnused(Reg, MI); 2615de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng continue; 2625de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng } 263a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 26496fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 265d9df5017040489303acb57bdd8697ef0f8bafc08Bob Wilson if (MI->isRegTiedToUseOperand(Idx)) { 2665db322acefc3089c133b8f3a33fa0a3ce90e2001Evan Cheng assert(isUsed(Reg) && "Using an undefined register!"); 26796fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 2680badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng } 269a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 270d118342b25eb6a3a67792cda9fce9b4c1e45a867Dan Gohman // Skip if this is merely redefining part of a super-register. 271ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling if (RedefinesSuperRegPart(MI, MO, TRI)) 272ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling continue; 273ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling 2745d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng // Implicit def is allowed to "re-define" any register. Similarly, 2755d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng // implicitly defined registers can be clobbered. 2761dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng assert((isReserved(Reg) || isUnused(Reg) || 2775d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng IsImpDef || isImplicitlyDefined(Reg) || 2781dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 2795db322acefc3089c133b8f3a33fa0a3ce90e2001Evan Cheng "Re-defining a live register!"); 2805d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng setUsed(Reg, IsImpDef); 28196fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 28296fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 28396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 28496fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::backward() { 285898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert(Tracking && "Not tracking states!"); 286ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng assert(MBBI != MBB->begin() && "Already at start of basic block!"); 287ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr backward. 288ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MBBI = prior(MBBI); 289ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 290ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MachineInstr *MI = MBBI; 291d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DistanceMap.erase(MI); 292d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng --CurrDist; 2933a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 2943a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng // Separate register operands into 3 classes: uses, defs, earlyclobbers. 2953a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs; 2963a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs; 2973a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs; 29896fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 29996fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 3003a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng if (!MO.isReg() || MO.getReg() == 0) 30196fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 3023a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng if (MO.isUse()) 3033a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng UseMOs.push_back(std::make_pair(&MO,i)); 3043a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng else if (MO.isEarlyClobber()) 3053a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng EarlyClobberMOs.push_back(std::make_pair(&MO,i)); 3063a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng else 3073a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng DefMOs.push_back(std::make_pair(&MO,i)); 3083a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng } 3093a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 3103a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 3113a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng // Process defs first. 3123a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng unsigned NumECs = EarlyClobberMOs.size(); 3133a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng unsigned NumDefs = DefMOs.size(); 3143a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) { 3153a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng const MachineOperand &MO = (i < NumDefs) 3163a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng ? *DefMOs[i].first : *EarlyClobberMOs[i-NumDefs].first; 3173a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng unsigned Idx = (i < NumECs) 3183a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng ? DefMOs[i].second : EarlyClobberMOs[i-NumDefs].second; 3193a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 32096fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 321d9df5017040489303acb57bdd8697ef0f8bafc08Bob Wilson if (MI->isRegTiedToUseOperand(Idx)) 32296fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 3233a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng 32496fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 32596fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUsed(Reg)); 32696fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!isReserved(Reg)) 327ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling setUnused(Reg, MI); 32896fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 32996fa612373e258120d351ed14361f964ad22f99dEvan Cheng 33096fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process uses. 3319c64bf3905ea338719800008c03d95a17cb26689Evan Cheng BitVector UseRegs(NumPhysRegs); 3323a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { 3333a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng const MachineOperand MO = *UseMOs[i].first; 33496fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 33596fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUnused(Reg) || isReserved(Reg)); 3369c64bf3905ea338719800008c03d95a17cb26689Evan Cheng UseRegs.set(Reg); 337a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling 338a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling // Set the sub-registers as "used". 3396130f66eaae89f8878590796977678afa8448926Evan Cheng for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 340a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling unsigned SubReg = *SubRegs; ++SubRegs) 3419c64bf3905ea338719800008c03d95a17cb26689Evan Cheng UseRegs.set(SubReg); 34296fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 3439c64bf3905ea338719800008c03d95a17cb26689Evan Cheng setUsed(UseRegs); 34496fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 34596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 34669cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesenvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 34769cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (includeReserved) 348c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen used = ~RegsAvailable; 34969cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen else 350c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen used = ~RegsAvailable & ~ReservedRegs; 35169cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen} 35269cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 35396fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// CreateRegClassMask - Set the bits that represent the registers in the 35496fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// TargetRegisterClass. 35596fa612373e258120d351ed14361f964ad22f99dEvan Chengstatic void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 35696fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 35796fa612373e258120d351ed14361f964ad22f99dEvan Cheng ++I) 35896fa612373e258120d351ed14361f964ad22f99dEvan Cheng Mask.set(*I); 35996fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 36096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 36196fa612373e258120d351ed14361f964ad22f99dEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 3625196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng const BitVector &Candidates) const { 3635196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 364c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen BitVector RegsAvailableCopy(NumPhysRegs, false); 365c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen CreateRegClassMask(RegClass, RegsAvailableCopy); 366c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= RegsAvailable; 3675196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 3685196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Restrict the search to candidates. 369c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= Candidates; 3705196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 3715196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 372c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen int Reg = RegsAvailableCopy.find_first(); 3735196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng return (Reg == -1) ? 0 : Reg; 3745196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng} 3755196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 3765196b3680cf8df32b6c763e3d97e963e45150e5aEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 37796fa612373e258120d351ed14361f964ad22f99dEvan Cheng bool ExCalleeSaved) const { 37896fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 379c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen BitVector RegsAvailableCopy(NumPhysRegs, false); 380c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen CreateRegClassMask(RegClass, RegsAvailableCopy); 381c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= RegsAvailable; 38296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 38396fa612373e258120d351ed14361f964ad22f99dEvan Cheng // If looking for a non-callee-saved register, mask off all the callee-saved 38496fa612373e258120d351ed14361f964ad22f99dEvan Cheng // registers. 38596fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (ExCalleeSaved) 386c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= ~CalleeSavedRegs; 38796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 38896fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 389c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen int Reg = RegsAvailableCopy.find_first(); 39096fa612373e258120d351ed14361f964ad22f99dEvan Cheng return (Reg == -1) ? 0 : Reg; 39196fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 392b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 393d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng/// findFirstUse - Calculate the distance to the first use of the 394b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng/// specified register. 395d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan ChengMachineInstr* 396d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan ChengRegScavenger::findFirstUse(MachineBasicBlock *MBB, 397d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineBasicBlock::iterator I, unsigned Reg, 398d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned &Dist) { 399d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *UseMI = 0; 400d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng Dist = ~0U; 401d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg), 402d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng RE = MRI->reg_end(); RI != RE; ++RI) { 403d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *UDMI = &*RI; 404d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (UDMI->getParent() != MBB) 405d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng continue; 406d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI); 407d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (DI == DistanceMap.end()) { 408d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng // If it's not in map, it's below current MI, let's initialize the 409d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng // map. 410d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng I = next(I); 411d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned Dist = CurrDist + 1; 412d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng while (I != MBB->end()) { 413d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DistanceMap.insert(std::make_pair(I, Dist++)); 414d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng I = next(I); 415d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 416d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 417d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng DI = DistanceMap.find(UDMI); 418d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (DI->second > CurrDist && DI->second < Dist) { 419d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng Dist = DI->second; 420d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng UseMI = UDMI; 421d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 422b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 423d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng return UseMI; 424b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 425b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 426b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 4278e3347332120956538a6d882b02719e34b57f0cdEvan Cheng MachineBasicBlock::iterator I, 4288e3347332120956538a6d882b02719e34b57f0cdEvan Cheng int SPAdj) { 429b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng assert(ScavengingFrameIndex >= 0 && 430b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng "Cannot scavenge a register without an emergency spill slot!"); 431b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 432b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Mask off the registers which are not in the TargetRegisterClass. 433b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng BitVector Candidates(NumPhysRegs, false); 434b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng CreateRegClassMask(RC, Candidates); 435b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates ^= ReservedRegs; // Do not include reserved registers. 436b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 437b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Exclude all the registers being used by the instruction. 438b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 439b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineOperand &MO = I->getOperand(i); 440d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg()) 441b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates.reset(MO.getReg()); 442b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 443b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 444527c250a9080a5b6cf0053a6215037c3769ff4a0Bill Wendling // Find the register whose use is furthest away. 445b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned SReg = 0; 446b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned MaxDist = 0; 447d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *MaxUseMI = 0; 448b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng int Reg = Candidates.find_first(); 449b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng while (Reg != -1) { 450d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned Dist; 451d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist); 452d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 453d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng unsigned AsDist; 454d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist); 455d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng if (AsDist < Dist) { 456d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng Dist = AsDist; 457d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng UseMI = AsUseMI; 458d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 459d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng } 460b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (Dist >= MaxDist) { 461b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MaxDist = Dist; 462d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng MaxUseMI = UseMI; 463b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng SReg = Reg; 464b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 465b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Reg = Candidates.find_next(Reg); 466b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 467b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 468b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (ScavengedReg != 0) { 469d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng assert(0 && "Scavenger slot is live, unable to scavenge another register!"); 470d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng abort(); 471b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 472b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 473d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng // Spill the scavenged register before I. 474f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); 475b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator II = prior(I); 4766130f66eaae89f8878590796977678afa8448926Evan Cheng TRI->eliminateFrameIndex(II, SPAdj, this); 477d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng 478d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng // Restore the scavenged register before its use (or first terminator). 479d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng II = MaxUseMI 480d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator(); 481d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC); 482d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng ScavengeRestore = prior(II); 483b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedReg = SReg; 484b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedRC = RC; 485b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 486b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return SReg; 487b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 488