RegisterScavenging.cpp revision a3756ee7fe384210eddcfd66e2934439960b13a1
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(); 3196fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MRegisterInfo *RegInfo = TM.getRegisterInfo(); 3296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 33898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert((NumPhysRegs == 0 || NumPhysRegs == RegInfo->getNumRegs()) && 34898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng "Target changed?"); 35898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 36898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!MBB) { 37898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng NumPhysRegs = RegInfo->getNumRegs(); 38898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng RegStates.resize(NumPhysRegs); 39898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 40a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng // Create reserved registers bitvector. 41a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng ReservedRegs = RegInfo->getReservedRegs(MF); 42a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 43898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng // Create callee-saved registers bitvector. 44898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng CalleeSavedRegs.resize(NumPhysRegs); 45898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng const unsigned *CSRegs = RegInfo->getCalleeSavedRegs(); 46898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (CSRegs != NULL) 47898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng for (unsigned i = 0; CSRegs[i]; ++i) 48898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng CalleeSavedRegs.set(CSRegs[i]); 49898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 50898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 51898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng MBB = mbb; 52898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng 53898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng // All registers started out unused. 54898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng RegStates.set(); 5596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 56a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng // Reserved registers are always used. 5796fa612373e258120d351ed14361f964ad22f99dEvan Cheng RegStates ^= ReservedRegs; 5896fa612373e258120d351ed14361f964ad22f99dEvan Cheng 59403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng // Live-in registers are in use. 60403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng if (!MBB->livein_empty()) 61403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 62403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng E = MBB->livein_end(); I != E; ++I) 63403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng setUsed(*I); 64a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng 65a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng Tracking = false; 6696fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 6796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 6896fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::forward() { 69ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr forward. 70898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng if (!Tracking) { 71898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng MBBI = MBB->begin(); 72898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng Tracking = true; 73898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } else { 74898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 75ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MBBI = next(MBBI); 76898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng } 77ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 7896fa612373e258120d351ed14361f964ad22f99dEvan Cheng MachineInstr *MI = MBBI; 7996fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process uses first. 8096fa612373e258120d351ed14361f964ad22f99dEvan Cheng BitVector ChangedRegs(NumPhysRegs); 8196fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 8296fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 8396fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isUse()) 8496fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 8596fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 8696fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (Reg == 0) 8796fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 8896fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUsed(Reg)); 8996fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (MO.isKill() && !isReserved(Reg)) 9096fa612373e258120d351ed14361f964ad22f99dEvan Cheng ChangedRegs.set(Reg); 9196fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 9296fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Change states of all registers after all the uses are processed to guard 9396fa612373e258120d351ed14361f964ad22f99dEvan Cheng // against multiple uses. 9496fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUnused(ChangedRegs); 9596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 9696fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process defs. 9796fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); 9896fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 9996fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 10096fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isDef()) 10196fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 1020badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng unsigned Reg = MO.getReg(); 10396fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 1040badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng if (TID->findTiedToSrcOperand(i) != -1) { 1050badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng assert(isUsed(Reg)); 10696fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 1070badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng } 10896fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUnused(Reg) || isReserved(Reg)); 10996fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isDead()) 11096fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUsed(Reg); 11196fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 11296fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 11396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 11496fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::backward() { 115898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng assert(Tracking && "Not tracking states!"); 116ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng assert(MBBI != MBB->begin() && "Already at start of basic block!"); 117ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng // Move ptr backward. 118ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MBBI = prior(MBBI); 119ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng 120ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng MachineInstr *MI = MBBI; 12196fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process defs first. 12296fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); 12396fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 12496fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 12596fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isDef()) 12696fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 12796fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 12896fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (TID->findTiedToSrcOperand(i) != -1) 12996fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 13096fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 13196fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUsed(Reg)); 13296fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!isReserved(Reg)) 13396fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUnused(Reg); 13496fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 13596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 13696fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process uses. 13796fa612373e258120d351ed14361f964ad22f99dEvan Cheng BitVector ChangedRegs(NumPhysRegs); 13896fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 13996fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 14096fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isUse()) 14196fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 14296fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 14396fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (Reg == 0) 14496fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 14596fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUnused(Reg) || isReserved(Reg)); 14696fa612373e258120d351ed14361f964ad22f99dEvan Cheng ChangedRegs.set(Reg); 14796fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 14896fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUsed(ChangedRegs); 14996fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 15096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 15196fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// CreateRegClassMask - Set the bits that represent the registers in the 15296fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// TargetRegisterClass. 15396fa612373e258120d351ed14361f964ad22f99dEvan Chengstatic void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 15496fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 15596fa612373e258120d351ed14361f964ad22f99dEvan Cheng ++I) 15696fa612373e258120d351ed14361f964ad22f99dEvan Cheng Mask.set(*I); 15796fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 15896fa612373e258120d351ed14361f964ad22f99dEvan Cheng 15996fa612373e258120d351ed14361f964ad22f99dEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 16096fa612373e258120d351ed14361f964ad22f99dEvan Cheng bool ExCalleeSaved) const { 16196fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 16296fa612373e258120d351ed14361f964ad22f99dEvan Cheng BitVector RegStatesCopy(NumPhysRegs, false); 16396fa612373e258120d351ed14361f964ad22f99dEvan Cheng CreateRegClassMask(RegClass, RegStatesCopy); 16496fa612373e258120d351ed14361f964ad22f99dEvan Cheng RegStatesCopy &= RegStates; 16596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 16696fa612373e258120d351ed14361f964ad22f99dEvan Cheng // If looking for a non-callee-saved register, mask off all the callee-saved 16796fa612373e258120d351ed14361f964ad22f99dEvan Cheng // registers. 16896fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (ExCalleeSaved) 16996fa612373e258120d351ed14361f964ad22f99dEvan Cheng RegStatesCopy &= ~CalleeSavedRegs; 17096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 17196fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 17296fa612373e258120d351ed14361f964ad22f99dEvan Cheng int Reg = RegStatesCopy.find_first(); 17396fa612373e258120d351ed14361f964ad22f99dEvan Cheng return (Reg == -1) ? 0 : Reg; 17496fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 175