RegisterScavenging.cpp revision caddd590f72376aaac531c1004be0535b460992a
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(); 39898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng RegStates.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. 57898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng RegStates.set(); 5896fa612373e258120d351ed14361f964ad22f99dEvan Cheng 59a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng // Reserved registers are always used. 6096fa612373e258120d351ed14361f964ad22f99dEvan Cheng RegStates ^= 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); 78b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng RegInfo->eliminateFrameIndex(II, 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) 113b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng assert(false); 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) { 1380badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng assert(isUsed(Reg)); 13996fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 1400badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng } 14196fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUnused(Reg) || isReserved(Reg)); 1425de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng setUsed(Reg); 14396fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 14496fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 14596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 14696fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::backward() { 147898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert(Tracking && "Not tracking states!"); 148ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng assert(MBBI != MBB->begin() && "Already at start of basic block!"); 149ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr backward. 150ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MBBI = prior(MBBI); 151ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 152ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MachineInstr *MI = MBBI; 15396fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process defs first. 15496fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); 15596fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 15696fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 15796fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isDef()) 15896fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 15996fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 16096fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (TID->findTiedToSrcOperand(i) != -1) 16196fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 16296fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 16396fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUsed(Reg)); 16496fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!isReserved(Reg)) 16596fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUnused(Reg); 16696fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 16796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 16896fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process uses. 16996fa612373e258120d351ed14361f964ad22f99dEvan Cheng BitVector ChangedRegs(NumPhysRegs); 17096fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 17196fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 17296fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isUse()) 17396fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 17496fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 17596fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (Reg == 0) 17696fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 17796fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUnused(Reg) || isReserved(Reg)); 17896fa612373e258120d351ed14361f964ad22f99dEvan Cheng ChangedRegs.set(Reg); 17996fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 18096fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUsed(ChangedRegs); 18196fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 18296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 18396fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// CreateRegClassMask - Set the bits that represent the registers in the 18496fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// TargetRegisterClass. 18596fa612373e258120d351ed14361f964ad22f99dEvan Chengstatic void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 18696fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 18796fa612373e258120d351ed14361f964ad22f99dEvan Cheng ++I) 18896fa612373e258120d351ed14361f964ad22f99dEvan Cheng Mask.set(*I); 18996fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 19096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 19196fa612373e258120d351ed14361f964ad22f99dEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 1925196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng const BitVector &Candidates) const { 1935196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 1945196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng BitVector RegStatesCopy(NumPhysRegs, false); 1955196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng CreateRegClassMask(RegClass, RegStatesCopy); 1965196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng RegStatesCopy &= RegStates; 1975196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 1985196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Restrict the search to candidates. 1995196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng RegStatesCopy &= Candidates; 2005196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 2015196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 2025196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng int Reg = RegStatesCopy.find_first(); 2035196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng return (Reg == -1) ? 0 : Reg; 2045196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng} 2055196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng 2065196b3680cf8df32b6c763e3d97e963e45150e5aEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 20796fa612373e258120d351ed14361f964ad22f99dEvan Cheng bool ExCalleeSaved) const { 20896fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 20996fa612373e258120d351ed14361f964ad22f99dEvan Cheng BitVector RegStatesCopy(NumPhysRegs, false); 21096fa612373e258120d351ed14361f964ad22f99dEvan Cheng CreateRegClassMask(RegClass, RegStatesCopy); 21196fa612373e258120d351ed14361f964ad22f99dEvan Cheng RegStatesCopy &= RegStates; 21296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 21396fa612373e258120d351ed14361f964ad22f99dEvan Cheng // If looking for a non-callee-saved register, mask off all the callee-saved 21496fa612373e258120d351ed14361f964ad22f99dEvan Cheng // registers. 21596fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (ExCalleeSaved) 21696fa612373e258120d351ed14361f964ad22f99dEvan Cheng RegStatesCopy &= ~CalleeSavedRegs; 21796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 21896fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 21996fa612373e258120d351ed14361f964ad22f99dEvan Cheng int Reg = RegStatesCopy.find_first(); 22096fa612373e258120d351ed14361f964ad22f99dEvan Cheng return (Reg == -1) ? 0 : Reg; 22196fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 222b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 223b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng/// calcDistanceToUse - Calculate the distance to the first use of the 224b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng/// specified register. 225b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengstatic unsigned calcDistanceToUse(MachineBasicBlock *MBB, 226b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator I, unsigned Reg) { 227b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned Dist = 0; 228b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng I = next(I); 229b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng while (I != MBB->end()) { 230b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Dist++; 231b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (I->findRegisterUseOperand(Reg)) 232b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return Dist; 233b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng I = next(I); 234b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 235b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return Dist + 1; 236b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 237b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 238b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 239b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator I) { 240b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng assert(ScavengingFrameIndex >= 0 && 241b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng "Cannot scavenge a register without an emergency spill slot!"); 242b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 243b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Mask off the registers which are not in the TargetRegisterClass. 244b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng BitVector Candidates(NumPhysRegs, false); 245b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng CreateRegClassMask(RC, Candidates); 246b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates ^= ReservedRegs; // Do not include reserved registers. 247b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 248b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Exclude all the registers being used by the instruction. 249b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 250b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineOperand &MO = I->getOperand(i); 251b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (MO.isReg()) 252b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Candidates.reset(MO.getReg()); 253b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 254b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 255b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // Find the register whose use is furtherest aaway. 256b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned SReg = 0; 257b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned MaxDist = 0; 258b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng int Reg = Candidates.find_first(); 259b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng while (Reg != -1) { 260b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng unsigned Dist = calcDistanceToUse(MBB, I, Reg); 261b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (Dist >= MaxDist) { 262b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MaxDist = Dist; 263b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng SReg = Reg; 264b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 265b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng Reg = Candidates.find_next(Reg); 266b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 267b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 268b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng if (ScavengedReg != 0) { 269b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng // First restore previously scavenged register. 270b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng RegInfo->loadRegFromStackSlot(*MBB, I, ScavengedReg, 271b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengingFrameIndex, ScavengedRC); 272b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator II = prior(I); 273b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng RegInfo->eliminateFrameIndex(II, this); 274b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng } 275b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 276b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng RegInfo->storeRegToStackSlot(*MBB, I, SReg, ScavengingFrameIndex, RC); 277b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng MachineBasicBlock::iterator II = prior(I); 278b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng RegInfo->eliminateFrameIndex(II, this); 279b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedReg = SReg; 280b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng ScavengedRC = RC; 281b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng 282b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng return SReg; 283b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng} 284