RegisterScavenging.cpp revision 403c45dfcc74585b02339b5f55f739672e3d141a
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" 2596fa612373e258120d351ed14361f964ad22f99dEvan Chengusing namespace llvm; 2696fa612373e258120d351ed14361f964ad22f99dEvan Cheng 2796fa612373e258120d351ed14361f964ad22f99dEvan ChengRegScavenger::RegScavenger(MachineBasicBlock *mbb) 2896fa612373e258120d351ed14361f964ad22f99dEvan Cheng : MBB(mbb), MBBI(mbb->begin()) { 2996fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineFunction &MF = *MBB->getParent(); 3096fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetMachine &TM = MF.getTarget(); 3196fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MRegisterInfo *RegInfo = TM.getRegisterInfo(); 3296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 3396fa612373e258120d351ed14361f964ad22f99dEvan Cheng NumPhysRegs = RegInfo->getNumRegs(); 3496fa612373e258120d351ed14361f964ad22f99dEvan Cheng RegStates.resize(NumPhysRegs, true); 3596fa612373e258120d351ed14361f964ad22f99dEvan Cheng 3696fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Create reserved registers bitvector. 3796fa612373e258120d351ed14361f964ad22f99dEvan Cheng ReservedRegs = RegInfo->getReservedRegs(MF); 3896fa612373e258120d351ed14361f964ad22f99dEvan Cheng RegStates ^= ReservedRegs; 3996fa612373e258120d351ed14361f964ad22f99dEvan Cheng 4096fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Create callee-saved registers bitvector. 4196fa612373e258120d351ed14361f964ad22f99dEvan Cheng CalleeSavedRegs.resize(NumPhysRegs); 4296fa612373e258120d351ed14361f964ad22f99dEvan Cheng const unsigned *CSRegs = RegInfo->getCalleeSavedRegs(); 4396fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (CSRegs != NULL) 4496fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0; CSRegs[i]; ++i) 4596fa612373e258120d351ed14361f964ad22f99dEvan Cheng CalleeSavedRegs.set(CSRegs[i]); 46403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng 47403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng // Live-in registers are in use. 48403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng if (!MBB->livein_empty()) 49403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 50403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng E = MBB->livein_end(); I != E; ++I) 51403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng setUsed(*I); 5296fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 5396fa612373e258120d351ed14361f964ad22f99dEvan Cheng 5496fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::forward() { 5596fa612373e258120d351ed14361f964ad22f99dEvan Cheng MachineInstr *MI = MBBI; 5696fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process uses first. 5796fa612373e258120d351ed14361f964ad22f99dEvan Cheng BitVector ChangedRegs(NumPhysRegs); 5896fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 5996fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 6096fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isUse()) 6196fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 6296fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 6396fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (Reg == 0) 6496fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 6596fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUsed(Reg)); 6696fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (MO.isKill() && !isReserved(Reg)) 6796fa612373e258120d351ed14361f964ad22f99dEvan Cheng ChangedRegs.set(Reg); 6896fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 6996fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Change states of all registers after all the uses are processed to guard 7096fa612373e258120d351ed14361f964ad22f99dEvan Cheng // against multiple uses. 7196fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUnused(ChangedRegs); 7296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 7396fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process defs. 7496fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); 7596fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 7696fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 7796fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isDef()) 7896fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 7996fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 8096fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (TID->findTiedToSrcOperand(i) != -1) 8196fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 8296fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 8396fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUnused(Reg) || isReserved(Reg)); 8496fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isDead()) 8596fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUsed(Reg); 8696fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 8796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 8896fa612373e258120d351ed14361f964ad22f99dEvan Cheng ++MBBI; 8996fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 9096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 9196fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::backward() { 9296fa612373e258120d351ed14361f964ad22f99dEvan Cheng MachineInstr *MI = --MBBI; 9396fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process defs first. 9496fa612373e258120d351ed14361f964ad22f99dEvan Cheng const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); 9596fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 9696fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 9796fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isDef()) 9896fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 9996fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Skip two-address destination operand. 10096fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (TID->findTiedToSrcOperand(i) != -1) 10196fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 10296fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 10396fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUsed(Reg)); 10496fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!isReserved(Reg)) 10596fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUnused(Reg); 10696fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 10796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 10896fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Process uses. 10996fa612373e258120d351ed14361f964ad22f99dEvan Cheng BitVector ChangedRegs(NumPhysRegs); 11096fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 11196fa612373e258120d351ed14361f964ad22f99dEvan Cheng const MachineOperand &MO = MI->getOperand(i); 11296fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (!MO.isReg() || !MO.isUse()) 11396fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 11496fa612373e258120d351ed14361f964ad22f99dEvan Cheng unsigned Reg = MO.getReg(); 11596fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (Reg == 0) 11696fa612373e258120d351ed14361f964ad22f99dEvan Cheng continue; 11796fa612373e258120d351ed14361f964ad22f99dEvan Cheng assert(isUnused(Reg) || isReserved(Reg)); 11896fa612373e258120d351ed14361f964ad22f99dEvan Cheng ChangedRegs.set(Reg); 11996fa612373e258120d351ed14361f964ad22f99dEvan Cheng } 12096fa612373e258120d351ed14361f964ad22f99dEvan Cheng setUsed(ChangedRegs); 12196fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 12296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 12396fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// CreateRegClassMask - Set the bits that represent the registers in the 12496fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// TargetRegisterClass. 12596fa612373e258120d351ed14361f964ad22f99dEvan Chengstatic void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 12696fa612373e258120d351ed14361f964ad22f99dEvan Cheng for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 12796fa612373e258120d351ed14361f964ad22f99dEvan Cheng ++I) 12896fa612373e258120d351ed14361f964ad22f99dEvan Cheng Mask.set(*I); 12996fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 13096fa612373e258120d351ed14361f964ad22f99dEvan Cheng 13196fa612373e258120d351ed14361f964ad22f99dEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 13296fa612373e258120d351ed14361f964ad22f99dEvan Cheng bool ExCalleeSaved) const { 13396fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Mask off the registers which are not in the TargetRegisterClass. 13496fa612373e258120d351ed14361f964ad22f99dEvan Cheng BitVector RegStatesCopy(NumPhysRegs, false); 13596fa612373e258120d351ed14361f964ad22f99dEvan Cheng CreateRegClassMask(RegClass, RegStatesCopy); 13696fa612373e258120d351ed14361f964ad22f99dEvan Cheng RegStatesCopy &= RegStates; 13796fa612373e258120d351ed14361f964ad22f99dEvan Cheng 13896fa612373e258120d351ed14361f964ad22f99dEvan Cheng // If looking for a non-callee-saved register, mask off all the callee-saved 13996fa612373e258120d351ed14361f964ad22f99dEvan Cheng // registers. 14096fa612373e258120d351ed14361f964ad22f99dEvan Cheng if (ExCalleeSaved) 14196fa612373e258120d351ed14361f964ad22f99dEvan Cheng RegStatesCopy &= ~CalleeSavedRegs; 14296fa612373e258120d351ed14361f964ad22f99dEvan Cheng 14396fa612373e258120d351ed14361f964ad22f99dEvan Cheng // Returns the first unused (bit is set) register, or 0 is none is found. 14496fa612373e258120d351ed14361f964ad22f99dEvan Cheng int Reg = RegStatesCopy.find_first(); 14596fa612373e258120d351ed14361f964ad22f99dEvan Cheng return (Reg == -1) ? 0 : Reg; 14696fa612373e258120d351ed14361f964ad22f99dEvan Cheng} 147