From 96fa612373e258120d351ed14361f964ad22f99d Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Fri, 23 Feb 2007 01:01:19 +0000 Subject: [PATCH] Initial check in of register scavenger. Its only current functionality is tracking live registers per MBB. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34511 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/RegisterScavenging.h | 75 ++++++++++++++++ lib/CodeGen/RegisterScavenging.cpp | 140 ++++++++++++++++++++++++++++++ 2 files changed, 215 insertions(+) create mode 100644 include/llvm/CodeGen/RegisterScavenging.h create mode 100644 lib/CodeGen/RegisterScavenging.cpp diff --git a/include/llvm/CodeGen/RegisterScavenging.h b/include/llvm/CodeGen/RegisterScavenging.h new file mode 100644 index 00000000000..117539a498e --- /dev/null +++ b/include/llvm/CodeGen/RegisterScavenging.h @@ -0,0 +1,75 @@ +//===-- RegisterScavenging.h - Machine register scavenging ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the Evan Cheng and is distributed under the +// University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares the machine register scavenger class. It can provide +// information such as unused register at any point in a machine basic block. +// It also provides a mechanism to make registers availbale by evicting them +// to spill slots. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_REGISTER_SCAVENGING_H +#define LLVM_CODEGEN_REGISTER_SCAVENGING_H + +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/ADT/BitVector.h" + +namespace llvm { + +class TargetRegisterClass; + +class RegScavenger { + MachineBasicBlock *MBB; + MachineBasicBlock::iterator MBBI; + unsigned NumPhysRegs; + + /// RegStates - The current state of all the physical registers immediately + /// before MBBI. One bit per physical register. If bit is set that means it's + /// available, unset means the register is currently being used. + BitVector RegStates; + +public: + RegScavenger(MachineBasicBlock *mbb); + + /// forward / backward - Move the internal MBB iterator and update register + /// states. + void forward(); + void backward(); + + /// isReserved - Returns true if a register is reserved. It is never "unused". + bool isReserved(unsigned Reg) const { return ReservedRegs[Reg]; } + + /// isUsed / isUsed - Test if a register is currently being used. + /// + bool isUsed(unsigned Reg) const { return !RegStates[Reg]; } + bool isUnused(unsigned Reg) const { return RegStates[Reg]; } + + /// setUsed / setUnused - Mark the state of one or a number of registers. + /// + void setUsed(unsigned Reg) { RegStates.reset(Reg); } + void setUsed(BitVector Regs) { RegStates &= ~Regs; } + void setUnused(unsigned Reg) { RegStates.set(Reg); } + void setUnused(BitVector Regs) { RegStates |= Regs; } + + /// FindUnusedReg - Find a unused register of the specified register class. + /// Exclude callee saved registers if directed. It return 0 is none is found. + unsigned FindUnusedReg(const TargetRegisterClass *RegClass, + bool ExCalleeSaved = false) const; + +private: + /// CalleeSavedrRegs - A bitvector of callee saved registers for the target. + BitVector CalleeSavedRegs; + + /// ReservedRegs - A bitvector of reserved registers. + BitVector ReservedRegs; +}; + +} // End llvm namespace + +#endif diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp new file mode 100644 index 00000000000..5aa2ca3ede3 --- /dev/null +++ b/lib/CodeGen/RegisterScavenging.cpp @@ -0,0 +1,140 @@ +//===-- RegisterScavenging.cpp - Machine register scavenging --------------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the Evan Cheng and is distributed under the +// University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the machine register scavenger. It can provide +// information such as unused register at any point in a machine basic block. +// It also provides a mechanism to make registers availbale by evicting them +// to spill slots. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "reg-scavenging" +#include "llvm/CodeGen/RegisterScavenging.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Target/MRegisterInfo.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +using namespace llvm; + +RegScavenger::RegScavenger(MachineBasicBlock *mbb) + : MBB(mbb), MBBI(mbb->begin()) { + const MachineFunction &MF = *MBB->getParent(); + const TargetMachine &TM = MF.getTarget(); + const MRegisterInfo *RegInfo = TM.getRegisterInfo(); + + NumPhysRegs = RegInfo->getNumRegs(); + RegStates.resize(NumPhysRegs, true); + + // Create reserved registers bitvector. + ReservedRegs = RegInfo->getReservedRegs(MF); + RegStates ^= ReservedRegs; + + // Create callee-saved registers bitvector. + CalleeSavedRegs.resize(NumPhysRegs); + const unsigned *CSRegs = RegInfo->getCalleeSavedRegs(); + if (CSRegs != NULL) + for (unsigned i = 0; CSRegs[i]; ++i) + CalleeSavedRegs.set(CSRegs[i]); +} + +void RegScavenger::forward() { + MachineInstr *MI = MBBI; + // Process uses first. + BitVector ChangedRegs(NumPhysRegs); + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !MO.isUse()) + continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) + continue; + assert(isUsed(Reg)); + if (MO.isKill() && !isReserved(Reg)) + ChangedRegs.set(Reg); + } + // Change states of all registers after all the uses are processed to guard + // against multiple uses. + setUnused(ChangedRegs); + + // Process defs. + const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !MO.isDef()) + continue; + // Skip two-address destination operand. + if (TID->findTiedToSrcOperand(i) != -1) + continue; + unsigned Reg = MO.getReg(); + assert(isUnused(Reg) || isReserved(Reg)); + if (!MO.isDead()) + setUsed(Reg); + } + + ++MBBI; +} + +void RegScavenger::backward() { + MachineInstr *MI = --MBBI; + // Process defs first. + const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !MO.isDef()) + continue; + // Skip two-address destination operand. + if (TID->findTiedToSrcOperand(i) != -1) + continue; + unsigned Reg = MO.getReg(); + assert(isUsed(Reg)); + if (!isReserved(Reg)) + setUnused(Reg); + } + + // Process uses. + BitVector ChangedRegs(NumPhysRegs); + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !MO.isUse()) + continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) + continue; + assert(isUnused(Reg) || isReserved(Reg)); + ChangedRegs.set(Reg); + } + setUsed(ChangedRegs); +} + +/// CreateRegClassMask - Set the bits that represent the registers in the +/// TargetRegisterClass. +static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { + for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; + ++I) + Mask.set(*I); +} + +unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, + bool ExCalleeSaved) const { + // Mask off the registers which are not in the TargetRegisterClass. + BitVector RegStatesCopy(NumPhysRegs, false); + CreateRegClassMask(RegClass, RegStatesCopy); + RegStatesCopy &= RegStates; + + // If looking for a non-callee-saved register, mask off all the callee-saved + // registers. + if (ExCalleeSaved) + RegStatesCopy &= ~CalleeSavedRegs; + + // Returns the first unused (bit is set) register, or 0 is none is found. + int Reg = RegStatesCopy.find_first(); + return (Reg == -1) ? 0 : Reg; +} -- 2.11.0