RegisterScavenging.cpp revision 5db322acefc3089c133b8f3a33fa0a3ce90e2001
196fa612373e258120d351ed14361f964ad22f99dEvan Cheng//===-- RegisterScavenging.cpp - Machine register scavenging --------------===// 296fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 396fa612373e258120d351ed14361f964ad22f99dEvan Cheng// The LLVM Compiler Infrastructure 496fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 596fa612373e258120d351ed14361f964ad22f99dEvan Cheng// This file was developed by the Evan Cheng and is distributed under the 696fa612373e258120d351ed14361f964ad22f99dEvan Cheng// University of Illinois Open Source License. See LICENSE.TXT for details. 796fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 896fa612373e258120d351ed14361f964ad22f99dEvan Cheng//===----------------------------------------------------------------------===// 996fa612373e258120d351ed14361f964ad22f99dEvan Cheng// 1096fa612373e258120d351ed14361f964ad22f99dEvan Cheng// This file implements the machine register scavenger. It can provide 1196fa612373e258120d351ed14361f964ad22f99dEvan Cheng// information such as unused register at any point in a machine basic block. 1296fa612373e258120d351ed14361f964ad22f99dEvan Cheng// It also provides a mechanism to make registers availbale by evicting them 1396fa612373e258120d351ed14361f964ad22f99dEvan Cheng// to 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" 2296fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/Target/MRegisterInfo.h" 2396fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/Target/TargetInstrInfo.h" 2496fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/Target/TargetMachine.h" 25ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng#include "llvm/ADT/STLExtras.h" 2696fa612373e258120d351ed14361f964ad22f99dEvan Chengusing namespace llvm; 2796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 28a3756ee7fe384210eddcfd66e2934439960b13a1Evan Chengvoid RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 29898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng const MachineFunction &MF = *mbb->getParent(); 3096fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetMachine &TM = MF.getTarget(); 31b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng TII = TM.getInstrInfo(); 32b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng RegInfo = TM.getRegisterInfo(); 3396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 34898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert((NumPhysRegs == 0 || NumPhysRegs == RegInfo->getNumRegs()) && 35898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng "Target changed?"); 36898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 37898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!MBB) { 38898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng NumPhysRegs = RegInfo->getNumRegs(); 39c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable.resize(NumPhysRegs); 40898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 41a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng // Create reserved registers bitvector. 42a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng ReservedRegs = RegInfo->getReservedRegs(MF); 43a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 44898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng // Create callee-saved registers bitvector. 45898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng CalleeSavedRegs.resize(NumPhysRegs); 46898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng const unsigned *CSRegs = RegInfo->getCalleeSavedRegs(); 47898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (CSRegs != NULL) 48898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng for (unsigned i = 0; CSRegs[i]; ++i) 49898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng CalleeSavedRegs.set(CSRegs[i]); 50898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 51898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 52898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng MBB = mbb; 53caddd590f72376aaac531c1004be0535b460992aEvan Cheng ScavengedReg = 0; 54caddd590f72376aaac531c1004be0535b460992aEvan Cheng ScavengedRC = NULL; 55898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 56898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng // All registers started out unused. 57c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable.set(); 5896fa612373e258120d351ed14361f964ad22f99dEvan Cheng 59a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng // Reserved registers are always used. 60c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailable ^= ReservedRegs; 6196fa612373e258120d351ed14361f964ad22f99dEvan Cheng 62403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng // Live-in registers are in use. 63403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng if (!MBB->livein_empty()) 64403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 65403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng E = MBB->livein_end(); I != E; ++I) 66403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng setUsed(*I); 67a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 68a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng Tracking = false; 6996fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 7096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 71b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengvoid RegScavenger::restoreScavengedReg() { 72b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (!ScavengedReg) 73b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return; 74b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 75b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng RegInfo->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg, 76b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengingFrameIndex, ScavengedRC); 77b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator II = prior(MBBI); 788e3347332120956538a6d882b02719e34b57f0cdEvan Cheng RegInfo->eliminateFrameIndex(II, 0, this); 79b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng setUsed(ScavengedReg); 80b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedReg = 0; 81b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedRC = NULL; 82b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 83b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 8496fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::forward() { 85ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr forward. 86898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!Tracking) { 87898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng MBBI = MBB->begin(); 88898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng Tracking = true; 89898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } else { 90898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 91ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MBBI = next(MBBI); 92898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 93ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 9496fa612373e258120d351ed14361f964ad22f99dEvan Cheng MachineInstr *MI = MBBI; 95b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 96b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Reaching a terminator instruction. Restore a scavenged register (which 97b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // must be life out. 98b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (TII->isTerminatorInstr(MI->getOpcode())) 99b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng restoreScavengedReg(); 100b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 10196fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process uses first. 10296fa612373e258120d351ed14361f964ad22f99dEvan Cheng BitVector ChangedRegs(NumPhysRegs); 10396fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 10496fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 10596fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isUse()) 10696fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 10796fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 10896fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (Reg == 0) 10996fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 110b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (!isUsed(Reg)) { 111b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Register has been scavenged. Restore it! 112b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (Reg != ScavengedReg) 1135db322acefc3089c133b8f3a33fa0a3ce90e2001Evan Cheng assert(false && "Using an undefined register!"); 114b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng else 115b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng restoreScavengedReg(); 116b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 11796fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (MO.isKill() && !isReserved(Reg)) 11896fa612373e258120d351ed14361f964ad22f99dEvan Cheng ChangedRegs.set(Reg); 11996fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 12096fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Change states of all registers after all the uses are processed to guard 12196fa612373e258120d351ed14361f964ad22f99dEvan Cheng // against multiple uses. 12296fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUnused(ChangedRegs); 12396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 12496fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process defs. 12596fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); 12696fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 12796fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 12896fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isDef()) 12996fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 1300badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng unsigned Reg = MO.getReg(); 1315de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng // If it's dead upon def, then it is now free. 1325de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng if (MO.isDead()) { 1335de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng setUnused(Reg); 1345de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng continue; 1355de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng } 13696fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 1370badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng if (TID->findTiedToSrcOperand(i) != -1) { 1385db322acefc3089c133b8f3a33fa0a3ce90e2001Evan Cheng assert(isUsed(Reg) && "Using an undefined register!"); 13996fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 1400badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng } 1415db322acefc3089c133b8f3a33fa0a3ce90e2001Evan Cheng assert((isUnused(Reg) || isReserved(Reg)) && 1425db322acefc3089c133b8f3a33fa0a3ce90e2001Evan Cheng "Re-defining a live register!"); 1435de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng setUsed(Reg); 14496fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 14596fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 14696fa612373e258120d351ed14361f964ad22f99dEvan Cheng 14796fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::backward() { 148898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert(Tracking && "Not tracking states!"); 149ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng assert(MBBI != MBB->begin() && "Already at start of basic block!"); 150ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr backward. 151ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MBBI = prior(MBBI); 152ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 153ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MachineInstr *MI = MBBI; 15496fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process defs first. 15596fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); 15696fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 15796fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 15896fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isDef()) 15996fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 16096fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 16196fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (TID->findTiedToSrcOperand(i) != -1) 16296fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 16396fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 16496fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUsed(Reg)); 16596fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!isReserved(Reg)) 16696fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUnused(Reg); 16796fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 16896fa612373e258120d351ed14361f964ad22f99dEvan Cheng 16996fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process uses. 17096fa612373e258120d351ed14361f964ad22f99dEvan Cheng BitVector ChangedRegs(NumPhysRegs); 17196fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 17296fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 17396fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isUse()) 17496fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 17596fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 17696fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (Reg == 0) 17796fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 17896fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUnused(Reg) || isReserved(Reg)); 17996fa612373e258120d351ed14361f964ad22f99dEvan Cheng ChangedRegs.set(Reg); 18096fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 18196fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUsed(ChangedRegs); 18296fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 18396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 18469cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesenvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 18569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen if (includeReserved) 186c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen used = ~RegsAvailable; 18769cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen else 188c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen used = ~RegsAvailable & ~ReservedRegs; 18969cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen} 19069cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen 19196fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// CreateRegClassMask - Set the bits that represent the registers in the 19296fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// TargetRegisterClass. 19396fa612373e258120d351ed14361f964ad22f99dEvan Chengstatic void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 19496fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 19596fa612373e258120d351ed14361f964ad22f99dEvan Cheng ++I) 19696fa612373e258120d351ed14361f964ad22f99dEvan Cheng Mask.set(*I); 19796fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 19896fa612373e258120d351ed14361f964ad22f99dEvan Cheng 19996fa612373e258120d351ed14361f964ad22f99dEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 2005196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng const BitVector &Candidates) const { 2015196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 202c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen BitVector RegsAvailableCopy(NumPhysRegs, false); 203c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen CreateRegClassMask(RegClass, RegsAvailableCopy); 204c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= RegsAvailable; 2055196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 2065196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Restrict the search to candidates. 207c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= Candidates; 2085196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 2095196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 210c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen int Reg = RegsAvailableCopy.find_first(); 2115196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng return (Reg == -1) ? 0 : Reg; 2125196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng} 2135196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 2145196b3680cf8df32b6c763e3d97e963e45150e5aEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 21596fa612373e258120d351ed14361f964ad22f99dEvan Cheng bool ExCalleeSaved) const { 21696fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 217c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen BitVector RegsAvailableCopy(NumPhysRegs, false); 218c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen CreateRegClassMask(RegClass, RegsAvailableCopy); 219c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= RegsAvailable; 22096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 22196fa612373e258120d351ed14361f964ad22f99dEvan Cheng // If looking for a non-callee-saved register, mask off all the callee-saved 22296fa612373e258120d351ed14361f964ad22f99dEvan Cheng // registers. 22396fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (ExCalleeSaved) 224c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen RegsAvailableCopy &= ~CalleeSavedRegs; 22596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 22696fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 227c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen int Reg = RegsAvailableCopy.find_first(); 22896fa612373e258120d351ed14361f964ad22f99dEvan Cheng return (Reg == -1) ? 0 : Reg; 22996fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 230b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 231b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng/// calcDistanceToUse - Calculate the distance to the first use of the 232b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng/// specified register. 233b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengstatic unsigned calcDistanceToUse(MachineBasicBlock *MBB, 234b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator I, unsigned Reg) { 235b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned Dist = 0; 236b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng I = next(I); 237b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng while (I != MBB->end()) { 238b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Dist++; 239faa510726f4b40aa4495e60e4d341c6467e3fb01Evan Cheng if (I->findRegisterUseOperandIdx(Reg) != -1) 240b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return Dist; 241b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng I = next(I); 242b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 243b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return Dist + 1; 244b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 245b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 246b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 2478e3347332120956538a6d882b02719e34b57f0cdEvan Cheng MachineBasicBlock::iterator I, 2488e3347332120956538a6d882b02719e34b57f0cdEvan Cheng int SPAdj) { 249b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng assert(ScavengingFrameIndex >= 0 && 250b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng "Cannot scavenge a register without an emergency spill slot!"); 251b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 252b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Mask off the registers which are not in the TargetRegisterClass. 253b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng BitVector Candidates(NumPhysRegs, false); 254b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng CreateRegClassMask(RC, Candidates); 255b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates ^= ReservedRegs; // Do not include reserved registers. 256b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 257b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Exclude all the registers being used by the instruction. 258b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 259b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineOperand &MO = I->getOperand(i); 260b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (MO.isReg()) 261b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates.reset(MO.getReg()); 262b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 263b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 264b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Find the register whose use is furtherest aaway. 265b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned SReg = 0; 266b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned MaxDist = 0; 267b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng int Reg = Candidates.find_first(); 268b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng while (Reg != -1) { 269b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned Dist = calcDistanceToUse(MBB, I, Reg); 270b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (Dist >= MaxDist) { 271b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MaxDist = Dist; 272b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng SReg = Reg; 273b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 274b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Reg = Candidates.find_next(Reg); 275b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 276b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 277b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (ScavengedReg != 0) { 278b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // First restore previously scavenged register. 279b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng RegInfo->loadRegFromStackSlot(*MBB, I, ScavengedReg, 280b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengingFrameIndex, ScavengedRC); 281b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator II = prior(I); 2828e3347332120956538a6d882b02719e34b57f0cdEvan Cheng RegInfo->eliminateFrameIndex(II, SPAdj, this); 283b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 284b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 285b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng RegInfo->storeRegToStackSlot(*MBB, I, SReg, ScavengingFrameIndex, RC); 286b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator II = prior(I); 2878e3347332120956538a6d882b02719e34b57f0cdEvan Cheng RegInfo->eliminateFrameIndex(II, SPAdj, this); 288b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedReg = SReg; 289b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedRC = RC; 290b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 291b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return SReg; 292b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 293