//
// The LLVM Compiler Infrastructure
//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "spiller"
+#define DEBUG_TYPE "virtregmap"
#include "VirtRegMap.h"
#include "llvm/Function.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/SSARegMap.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallSet.h"
#include <algorithm>
-#include <iostream>
using namespace llvm;
-namespace {
- Statistic<> NumSpills("spiller", "Number of register spills");
- Statistic<> NumStores("spiller", "Number of stores added");
- Statistic<> NumLoads ("spiller", "Number of loads added");
- Statistic<> NumReused("spiller", "Number of values reused");
- Statistic<> NumDSE ("spiller", "Number of dead stores elided");
- Statistic<> NumDCE ("spiller", "Number of copies elided");
-
- enum SpillerName { simple, local };
-
- cl::opt<SpillerName>
- SpillerOpt("spiller",
- cl::desc("Spiller to use: (default: local)"),
- cl::Prefix,
- cl::values(clEnumVal(simple, " simple spiller"),
- clEnumVal(local, " local spiller"),
- clEnumValEnd),
- cl::init(local));
-}
+STATISTIC(NumSpills , "Number of register spills");
//===----------------------------------------------------------------------===//
// VirtRegMap implementation
//===----------------------------------------------------------------------===//
+char VirtRegMap::ID = 0;
+
+static RegisterPass<VirtRegMap>
+X("virtregmap", "Virtual Register Map");
+
+bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
+ MRI = &mf.getRegInfo();
+ TII = mf.getTarget().getInstrInfo();
+ TRI = mf.getTarget().getRegisterInfo();
+ MF = &mf;
+
+ ReMatId = MAX_STACK_SLOT+1;
+ LowSpillSlot = HighSpillSlot = NO_STACK_SLOT;
+
+ Virt2PhysMap.clear();
+ Virt2StackSlotMap.clear();
+ Virt2ReMatIdMap.clear();
+ Virt2SplitMap.clear();
+ Virt2SplitKillMap.clear();
+ ReMatMap.clear();
+ ImplicitDefed.clear();
+ SpillSlotToUsesMap.clear();
+ MI2VirtMap.clear();
+ SpillPt2VirtMap.clear();
+ RestorePt2VirtMap.clear();
+ EmergencySpillMap.clear();
+ EmergencySpillSlots.clear();
+
+ SpillSlotToUsesMap.resize(8);
+ ImplicitDefed.resize(MF->getRegInfo().getLastVirtReg()+1-
+ TargetRegisterInfo::FirstVirtualRegister);
+
+ allocatableRCRegs.clear();
+ for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(),
+ E = TRI->regclass_end(); I != E; ++I)
+ allocatableRCRegs.insert(std::make_pair(*I,
+ TRI->getAllocatableSet(mf, *I)));
+
+ grow();
+
+ return false;
+}
+
void VirtRegMap::grow() {
- Virt2PhysMap.grow(MF.getSSARegMap()->getLastVirtReg());
- Virt2StackSlotMap.grow(MF.getSSARegMap()->getLastVirtReg());
+ unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg();
+ Virt2PhysMap.grow(LastVirtReg);
+ Virt2StackSlotMap.grow(LastVirtReg);
+ Virt2ReMatIdMap.grow(LastVirtReg);
+ Virt2SplitMap.grow(LastVirtReg);
+ Virt2SplitKillMap.grow(LastVirtReg);
+ ReMatMap.grow(LastVirtReg);
+ ImplicitDefed.resize(LastVirtReg-TargetRegisterInfo::FirstVirtualRegister+1);
+}
+
+unsigned VirtRegMap::getRegAllocPref(unsigned virtReg) {
+ std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(virtReg);
+ unsigned physReg = Hint.second;
+ if (physReg &&
+ TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg))
+ physReg = getPhys(physReg);
+ if (Hint.first == 0)
+ return (physReg && TargetRegisterInfo::isPhysicalRegister(physReg))
+ ? physReg : 0;
+ return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF);
}
int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
- assert(MRegisterInfo::isVirtualRegister(virtReg));
+ assert(TargetRegisterInfo::isVirtualRegister(virtReg));
assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
"attempt to assign stack slot to already spilled register");
- const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(virtReg);
- int frameIndex = MF.getFrameInfo()->CreateStackObject(RC->getSize(),
- RC->getAlignment());
- Virt2StackSlotMap[virtReg] = frameIndex;
+ const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg);
+ int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
+ RC->getAlignment());
+ if (LowSpillSlot == NO_STACK_SLOT)
+ LowSpillSlot = SS;
+ if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
+ HighSpillSlot = SS;
+ unsigned Idx = SS-LowSpillSlot;
+ while (Idx >= SpillSlotToUsesMap.size())
+ SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2);
+ Virt2StackSlotMap[virtReg] = SS;
++NumSpills;
- return frameIndex;
+ return SS;
}
-void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) {
- assert(MRegisterInfo::isVirtualRegister(virtReg));
+void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
+ assert(TargetRegisterInfo::isVirtualRegister(virtReg));
assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
"attempt to assign stack slot to already spilled register");
- Virt2StackSlotMap[virtReg] = frameIndex;
+ assert((SS >= 0 ||
+ (SS >= MF->getFrameInfo()->getObjectIndexBegin())) &&
+ "illegal fixed frame index");
+ Virt2StackSlotMap[virtReg] = SS;
}
-void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
- unsigned OpNo, MachineInstr *NewMI) {
- // Move previous memory references folded to new instruction.
- MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI);
- for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI),
- E = MI2VirtMap.end(); I != E && I->first == OldMI; ) {
- MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second));
- MI2VirtMap.erase(I++);
- }
-
- ModRef MRInfo;
- if (!OldMI->getOperand(OpNo).isDef()) {
- assert(OldMI->getOperand(OpNo).isUse() && "Operand is not use or def?");
- MRInfo = isRef;
- } else {
- MRInfo = OldMI->getOperand(OpNo).isUse() ? isModRef : isMod;
- }
-
- // add new memory reference
- MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo)));
+int VirtRegMap::assignVirtReMatId(unsigned virtReg) {
+ assert(TargetRegisterInfo::isVirtualRegister(virtReg));
+ assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
+ "attempt to assign re-mat id to already spilled register");
+ Virt2ReMatIdMap[virtReg] = ReMatId;
+ return ReMatId++;
}
-void VirtRegMap::print(std::ostream &OS) const {
- const MRegisterInfo* MRI = MF.getTarget().getRegisterInfo();
-
- OS << "********** REGISTER MAP **********\n";
- for (unsigned i = MRegisterInfo::FirstVirtualRegister,
- e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
- if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
- OS << "[reg" << i << " -> " << MRI->getName(Virt2PhysMap[i]) << "]\n";
-
- }
-
- for (unsigned i = MRegisterInfo::FirstVirtualRegister,
- e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i)
- if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT)
- OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n";
- OS << '\n';
+void VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) {
+ assert(TargetRegisterInfo::isVirtualRegister(virtReg));
+ assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
+ "attempt to assign re-mat id to already spilled register");
+ Virt2ReMatIdMap[virtReg] = id;
}
-void VirtRegMap::dump() const { print(std::cerr); }
-
-
-//===----------------------------------------------------------------------===//
-// Simple Spiller Implementation
-//===----------------------------------------------------------------------===//
-
-Spiller::~Spiller() {}
-
-namespace {
- struct SimpleSpiller : public Spiller {
- bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap &VRM);
- };
+int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass *RC) {
+ std::map<const TargetRegisterClass*, int>::iterator I =
+ EmergencySpillSlots.find(RC);
+ if (I != EmergencySpillSlots.end())
+ return I->second;
+ int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
+ RC->getAlignment());
+ if (LowSpillSlot == NO_STACK_SLOT)
+ LowSpillSlot = SS;
+ if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
+ HighSpillSlot = SS;
+ EmergencySpillSlots[RC] = SS;
+ return SS;
}
-bool SimpleSpiller::runOnMachineFunction(MachineFunction &MF,
- const VirtRegMap &VRM) {
- DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
- DEBUG(std::cerr << "********** Function: "
- << MF.getFunction()->getName() << '\n');
- const TargetMachine &TM = MF.getTarget();
- const MRegisterInfo &MRI = *TM.getRegisterInfo();
- bool *PhysRegsUsed = MF.getUsedPhysregs();
-
- // LoadedRegs - Keep track of which vregs are loaded, so that we only load
- // each vreg once (in the case where a spilled vreg is used by multiple
- // operands). This is always smaller than the number of operands to the
- // current machine instr, so it should be small.
- std::vector<unsigned> LoadedRegs;
-
- for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
- MBBI != E; ++MBBI) {
- DEBUG(std::cerr << MBBI->getBasicBlock()->getName() << ":\n");
- MachineBasicBlock &MBB = *MBBI;
- for (MachineBasicBlock::iterator MII = MBB.begin(),
- E = MBB.end(); MII != E; ++MII) {
- MachineInstr &MI = *MII;
- for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI.getOperand(i);
- if (MO.isRegister() && MO.getReg())
- if (MRegisterInfo::isVirtualRegister(MO.getReg())) {
- unsigned VirtReg = MO.getReg();
- unsigned PhysReg = VRM.getPhys(VirtReg);
- if (VRM.hasStackSlot(VirtReg)) {
- int StackSlot = VRM.getStackSlot(VirtReg);
- const TargetRegisterClass* RC =
- MF.getSSARegMap()->getRegClass(VirtReg);
-
- if (MO.isUse() &&
- std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg)
- == LoadedRegs.end()) {
- MRI.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
- LoadedRegs.push_back(VirtReg);
- ++NumLoads;
- DEBUG(std::cerr << '\t' << *prior(MII));
- }
-
- if (MO.isDef()) {
- MRI.storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot, RC);
- ++NumStores;
- }
- }
- PhysRegsUsed[PhysReg] = true;
- MI.SetMachineOperandReg(i, PhysReg);
- } else {
- PhysRegsUsed[MO.getReg()] = true;
- }
- }
-
- DEBUG(std::cerr << '\t' << MI);
- LoadedRegs.clear();
+void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) {
+ if (!MF->getFrameInfo()->isFixedObjectIndex(FI)) {
+ // If FI < LowSpillSlot, this stack reference was produced by
+ // instruction selection and is not a spill
+ if (FI >= LowSpillSlot) {
+ assert(FI >= 0 && "Spill slot index should not be negative!");
+ assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
+ && "Invalid spill slot");
+ SpillSlotToUsesMap[FI-LowSpillSlot].insert(MI);
}
}
- return true;
-}
-
-//===----------------------------------------------------------------------===//
-// Local Spiller Implementation
-//===----------------------------------------------------------------------===//
-
-namespace {
- /// LocalSpiller - This spiller does a simple pass over the machine basic
- /// block to attempt to keep spills in registers as much as possible for
- /// blocks that have low register pressure (the vreg may be spilled due to
- /// register pressure in other blocks).
- class LocalSpiller : public Spiller {
- const MRegisterInfo *MRI;
- const TargetInstrInfo *TII;
- public:
- bool runOnMachineFunction(MachineFunction &MF, const VirtRegMap &VRM) {
- MRI = MF.getTarget().getRegisterInfo();
- TII = MF.getTarget().getInstrInfo();
- DEBUG(std::cerr << "\n**** Local spiller rewriting function '"
- << MF.getFunction()->getName() << "':\n");
-
- for (MachineFunction::iterator MBB = MF.begin(), E = MF.end();
- MBB != E; ++MBB)
- RewriteMBB(*MBB, VRM);
- return true;
- }
- private:
- void RewriteMBB(MachineBasicBlock &MBB, const VirtRegMap &VRM);
- void ClobberPhysReg(unsigned PR, std::map<int, unsigned> &SpillSlots,
- std::multimap<unsigned, int> &PhysRegs);
- void ClobberPhysRegOnly(unsigned PR, std::map<int, unsigned> &SpillSlots,
- std::multimap<unsigned, int> &PhysRegs);
- void ModifyStackSlot(int Slot, std::map<int, unsigned> &SpillSlots,
- std::multimap<unsigned, int> &PhysRegs);
- };
}
-/// AvailableSpills - As the local spiller is scanning and rewriting an MBB from
-/// top down, keep track of which spills slots are available in each register.
-///
-/// Note that not all physregs are created equal here. In particular, some
-/// physregs are reloads that we are allowed to clobber or ignore at any time.
-/// Other physregs are values that the register allocated program is using that
-/// we cannot CHANGE, but we can read if we like. We keep track of this on a
-/// per-stack-slot basis as the low bit in the value of the SpillSlotsAvailable
-/// entries. The predicate 'canClobberPhysReg()' checks this bit and
-/// addAvailable sets it if.
-class AvailableSpills {
- const MRegisterInfo *MRI;
- const TargetInstrInfo *TII;
-
- // SpillSlotsAvailable - This map keeps track of all of the spilled virtual
- // register values that are still available, due to being loaded or stored to,
- // but not invalidated yet.
- std::map<int, unsigned> SpillSlotsAvailable;
-
- // PhysRegsAvailable - This is the inverse of SpillSlotsAvailable, indicating
- // which stack slot values are currently held by a physreg. This is used to
- // invalidate entries in SpillSlotsAvailable when a physreg is modified.
- std::multimap<unsigned, int> PhysRegsAvailable;
-
- void ClobberPhysRegOnly(unsigned PhysReg);
-public:
- AvailableSpills(const MRegisterInfo *mri, const TargetInstrInfo *tii)
- : MRI(mri), TII(tii) {
- }
-
- /// getSpillSlotPhysReg - If the specified stack slot is available in a
- /// physical register, return that PhysReg, otherwise return 0.
- unsigned getSpillSlotPhysReg(int Slot) const {
- std::map<int, unsigned>::const_iterator I = SpillSlotsAvailable.find(Slot);
- if (I != SpillSlotsAvailable.end())
- return I->second >> 1; // Remove the CanClobber bit.
- return 0;
- }
-
- const MRegisterInfo *getRegInfo() const { return MRI; }
-
- /// addAvailable - Mark that the specified stack slot is available in the
- /// specified physreg. If CanClobber is true, the physreg can be modified at
- /// any time without changing the semantics of the program.
- void addAvailable(int Slot, unsigned Reg, bool CanClobber = true) {
- // If this stack slot is thought to be available in some other physreg,
- // remove its record.
- ModifyStackSlot(Slot);
-
- PhysRegsAvailable.insert(std::make_pair(Reg, Slot));
- SpillSlotsAvailable[Slot] = (Reg << 1) | (unsigned)CanClobber;
-
- DEBUG(std::cerr << "Remembering SS#" << Slot << " in physreg "
- << MRI->getName(Reg) << "\n");
- }
-
- /// canClobberPhysReg - Return true if the spiller is allowed to change the
- /// value of the specified stackslot register if it desires. The specified
- /// stack slot must be available in a physreg for this query to make sense.
- bool canClobberPhysReg(int Slot) const {
- assert(SpillSlotsAvailable.count(Slot) && "Slot not available!");
- return SpillSlotsAvailable.find(Slot)->second & 1;
+void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
+ MachineInstr *NewMI, ModRef MRInfo) {
+ // Move previous memory references folded to new instruction.
+ MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI);
+ for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI),
+ E = MI2VirtMap.end(); I != E && I->first == OldMI; ) {
+ MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second));
+ MI2VirtMap.erase(I++);
}
-
- /// ClobberPhysReg - This is called when the specified physreg changes
- /// value. We use this to invalidate any info about stuff we thing lives in
- /// it and any of its aliases.
- void ClobberPhysReg(unsigned PhysReg);
-
- /// ModifyStackSlot - This method is called when the value in a stack slot
- /// changes. This removes information about which register the previous value
- /// for this slot lives in (as the previous value is dead now).
- void ModifyStackSlot(int Slot);
-};
-/// ClobberPhysRegOnly - This is called when the specified physreg changes
-/// value. We use this to invalidate any info about stuff we thing lives in it.
-void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) {
- std::multimap<unsigned, int>::iterator I =
- PhysRegsAvailable.lower_bound(PhysReg);
- while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
- int Slot = I->second;
- PhysRegsAvailable.erase(I++);
- assert((SpillSlotsAvailable[Slot] >> 1) == PhysReg &&
- "Bidirectional map mismatch!");
- SpillSlotsAvailable.erase(Slot);
- DEBUG(std::cerr << "PhysReg " << MRI->getName(PhysReg)
- << " clobbered, invalidating SS#" << Slot << "\n");
- }
+ // add new memory reference
+ MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo)));
}
-/// ClobberPhysReg - This is called when the specified physreg changes
-/// value. We use this to invalidate any info about stuff we thing lives in
-/// it and any of its aliases.
-void AvailableSpills::ClobberPhysReg(unsigned PhysReg) {
- for (const unsigned *AS = MRI->getAliasSet(PhysReg); *AS; ++AS)
- ClobberPhysRegOnly(*AS);
- ClobberPhysRegOnly(PhysReg);
+void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) {
+ MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(MI);
+ MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo)));
}
-/// ModifyStackSlot - This method is called when the value in a stack slot
-/// changes. This removes information about which register the previous value
-/// for this slot lives in (as the previous value is dead now).
-void AvailableSpills::ModifyStackSlot(int Slot) {
- std::map<int, unsigned>::iterator It = SpillSlotsAvailable.find(Slot);
- if (It == SpillSlotsAvailable.end()) return;
- unsigned Reg = It->second >> 1;
- SpillSlotsAvailable.erase(It);
-
- // This register may hold the value of multiple stack slots, only remove this
- // stack slot from the set of values the register contains.
- std::multimap<unsigned, int>::iterator I = PhysRegsAvailable.lower_bound(Reg);
- for (; ; ++I) {
- assert(I != PhysRegsAvailable.end() && I->first == Reg &&
- "Map inverse broken!");
- if (I->second == Slot) break;
+void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) {
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = MI->getOperand(i);
+ if (!MO.isFI())
+ continue;
+ int FI = MO.getIndex();
+ if (MF->getFrameInfo()->isFixedObjectIndex(FI))
+ continue;
+ // This stack reference was produced by instruction selection and
+ // is not a spill
+ if (FI < LowSpillSlot)
+ continue;
+ assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
+ && "Invalid spill slot");
+ SpillSlotToUsesMap[FI-LowSpillSlot].erase(MI);
}
- PhysRegsAvailable.erase(I);
+ MI2VirtMap.erase(MI);
+ SpillPt2VirtMap.erase(MI);
+ RestorePt2VirtMap.erase(MI);
+ EmergencySpillMap.erase(MI);
}
+/// FindUnusedRegisters - Gather a list of allocatable registers that
+/// have not been allocated to any virtual register.
+bool VirtRegMap::FindUnusedRegisters(LiveIntervals* LIs) {
+ unsigned NumRegs = TRI->getNumRegs();
+ UnusedRegs.reset();
+ UnusedRegs.resize(NumRegs);
-
-// ReusedOp - For each reused operand, we keep track of a bit of information, in
-// case we need to rollback upon processing a new operand. See comments below.
-namespace {
- struct ReusedOp {
- // The MachineInstr operand that reused an available value.
- unsigned Operand;
-
- // StackSlot - The spill slot of the value being reused.
- unsigned StackSlot;
-
- // PhysRegReused - The physical register the value was available in.
- unsigned PhysRegReused;
-
- // AssignedPhysReg - The physreg that was assigned for use by the reload.
- unsigned AssignedPhysReg;
-
- // VirtReg - The virtual register itself.
- unsigned VirtReg;
-
- ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr,
- unsigned vreg)
- : Operand(o), StackSlot(ss), PhysRegReused(prr), AssignedPhysReg(apr),
- VirtReg(vreg) {}
- };
-
- /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that
- /// is reused instead of reloaded.
- class ReuseInfo {
- MachineInstr &MI;
- std::vector<ReusedOp> Reuses;
- public:
- ReuseInfo(MachineInstr &mi) : MI(mi) {}
-
- bool hasReuses() const {
- return !Reuses.empty();
- }
-
- /// addReuse - If we choose to reuse a virtual register that is already
- /// available instead of reloading it, remember that we did so.
- void addReuse(unsigned OpNo, unsigned StackSlot,
- unsigned PhysRegReused, unsigned AssignedPhysReg,
- unsigned VirtReg) {
- // If the reload is to the assigned register anyway, no undo will be
- // required.
- if (PhysRegReused == AssignedPhysReg) return;
-
- // Otherwise, remember this.
- Reuses.push_back(ReusedOp(OpNo, StackSlot, PhysRegReused,
- AssignedPhysReg, VirtReg));
- }
-
- /// GetRegForReload - We are about to emit a reload into PhysReg. If there
- /// is some other operand that is using the specified register, either pick
- /// a new register to use, or evict the previous reload and use this reg.
- unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
- AvailableSpills &Spills,
- std::map<int, MachineInstr*> &MaybeDeadStores) {
- if (Reuses.empty()) return PhysReg; // This is most often empty.
-
- for (unsigned ro = 0, e = Reuses.size(); ro != e; ++ro) {
- ReusedOp &Op = Reuses[ro];
- // If we find some other reuse that was supposed to use this register
- // exactly for its reload, we can change this reload to use ITS reload
- // register.
- if (Op.PhysRegReused == PhysReg) {
- // Yup, use the reload register that we didn't use before.
- return GetRegForReload(Op.AssignedPhysReg, MI,
- Spills, MaybeDeadStores);
- } else {
- // Otherwise, we might also have a problem if a previously reused
- // value aliases the new register. If so, codegen the previous reload
- // and use this one.
- unsigned PRRU = Op.PhysRegReused;
- const MRegisterInfo *MRI = Spills.getRegInfo();
- if (MRI->areAliases(PRRU, PhysReg)) {
- // Okay, we found out that an alias of a reused register
- // was used. This isn't good because it means we have
- // to undo a previous reuse.
- MachineBasicBlock *MBB = MI->getParent();
- const TargetRegisterClass *AliasRC =
- MBB->getParent()->getSSARegMap()->getRegClass(Op.VirtReg);
- MRI->loadRegFromStackSlot(*MBB, MI, Op.AssignedPhysReg,
- Op.StackSlot, AliasRC);
- Spills.ClobberPhysReg(Op.AssignedPhysReg);
- Spills.ClobberPhysReg(Op.PhysRegReused);
-
- // Any stores to this stack slot are not dead anymore.
- MaybeDeadStores.erase(Op.StackSlot);
-
- MI->SetMachineOperandReg(Op.Operand, Op.AssignedPhysReg);
-
- Spills.addAvailable(Op.StackSlot, Op.AssignedPhysReg);
- ++NumLoads;
- DEBUG(MachineBasicBlock::iterator MII = MI;
- std::cerr << '\t' << *prior(MII));
-
- DEBUG(std::cerr << "Reuse undone!\n");
- Reuses.erase(Reuses.begin()+ro);
- --NumReused;
- return PhysReg;
- }
- }
- }
- return PhysReg;
- }
- };
-}
-
-
-/// rewriteMBB - Keep track of which spills are available even after the
-/// register allocator is done with them. If possible, avoid reloading vregs.
-void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, const VirtRegMap &VRM) {
-
- DEBUG(std::cerr << MBB.getBasicBlock()->getName() << ":\n");
-
- // Spills - Keep track of which spilled values are available in physregs so
- // that we can choose to reuse the physregs instead of emitting reloads.
- AvailableSpills Spills(MRI, TII);
-
- // DefAndUseVReg - When we see a def&use operand that is spilled, keep track
- // of it. ".first" is the machine operand index (should always be 0 for now),
- // and ".second" is the virtual register that is spilled.
- std::vector<std::pair<unsigned, unsigned> > DefAndUseVReg;
-
- // MaybeDeadStores - When we need to write a value back into a stack slot,
- // keep track of the inserted store. If the stack slot value is never read
- // (because the value was used from some available register, for example), and
- // subsequently stored to, the original store is dead. This map keeps track
- // of inserted stores that are not used. If we see a subsequent store to the
- // same stack slot, the original store is deleted.
- std::map<int, MachineInstr*> MaybeDeadStores;
-
- bool *PhysRegsUsed = MBB.getParent()->getUsedPhysregs();
-
- if (MBB.getBasicBlock()->getName() == "endif.3.i")
- std::cerr << "HERE\n";
-
- for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
- MII != E; ) {
- MachineInstr &MI = *MII;
- MachineBasicBlock::iterator NextMII = MII; ++NextMII;
-
- /// ReusedOperands - Keep track of operand reuse in case we need to undo
- /// reuse.
- ReuseInfo ReusedOperands(MI);
-
- DefAndUseVReg.clear();
-
- // Process all of the spilled uses and all non spilled reg references.
- for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI.getOperand(i);
- if (!MO.isRegister() || MO.getReg() == 0)
- continue; // Ignore non-register operands.
-
- if (MRegisterInfo::isPhysicalRegister(MO.getReg())) {
- // Ignore physregs for spilling, but remember that it is used by this
- // function.
- PhysRegsUsed[MO.getReg()] = true;
- continue;
- }
-
- assert(MRegisterInfo::isVirtualRegister(MO.getReg()) &&
- "Not a virtual or a physical register?");
-
- unsigned VirtReg = MO.getReg();
- if (!VRM.hasStackSlot(VirtReg)) {
- // This virtual register was assigned a physreg!
- unsigned Phys = VRM.getPhys(VirtReg);
- PhysRegsUsed[Phys] = true;
- MI.SetMachineOperandReg(i, Phys);
- continue;
- }
-
- // This virtual register is now known to be a spilled value.
- if (!MO.isUse())
- continue; // Handle defs in the loop below (handle use&def here though)
-
- // If this is both a def and a use, we need to emit a store to the
- // stack slot after the instruction. Keep track of D&U operands
- // because we are about to change it to a physreg here.
- if (MO.isDef()) {
- // Remember that this was a def-and-use operand, and that the
- // stack slot is live after this instruction executes.
- DefAndUseVReg.push_back(std::make_pair(i, VirtReg));
- }
-
- int StackSlot = VRM.getStackSlot(VirtReg);
- unsigned PhysReg;
-
- // Check to see if this stack slot is available.
- if ((PhysReg = Spills.getSpillSlotPhysReg(StackSlot)) &&
- // Don't reuse it for a def&use operand if we aren't allowed to change
- // the physreg!
- (!MO.isDef() || Spills.canClobberPhysReg(StackSlot))) {
- // If this stack slot value is already available, reuse it!
- DEBUG(std::cerr << "Reusing SS#" << StackSlot << " from physreg "
- << MRI->getName(PhysReg) << " for vreg"
- << VirtReg <<" instead of reloading into physreg "
- << MRI->getName(VRM.getPhys(VirtReg)) << "\n");
- MI.SetMachineOperandReg(i, PhysReg);
-
- // The only technical detail we have is that we don't know that
- // PhysReg won't be clobbered by a reloaded stack slot that occurs
- // later in the instruction. In particular, consider 'op V1, V2'.
- // If V1 is available in physreg R0, we would choose to reuse it
- // here, instead of reloading it into the register the allocator
- // indicated (say R1). However, V2 might have to be reloaded
- // later, and it might indicate that it needs to live in R0. When
- // this occurs, we need to have information available that
- // indicates it is safe to use R1 for the reload instead of R0.
- //
- // To further complicate matters, we might conflict with an alias,
- // or R0 and R1 might not be compatible with each other. In this
- // case, we actually insert a reload for V1 in R1, ensuring that
- // we can get at R0 or its alias.
- ReusedOperands.addReuse(i, StackSlot, PhysReg,
- VRM.getPhys(VirtReg), VirtReg);
- ++NumReused;
- continue;
- }
-
- // Otherwise, reload it and remember that we have it.
- PhysReg = VRM.getPhys(VirtReg);
- assert(PhysReg && "Must map virtreg to physreg!");
- const TargetRegisterClass* RC =
- MBB.getParent()->getSSARegMap()->getRegClass(VirtReg);
-
- // Note that, if we reused a register for a previous operand, the
- // register we want to reload into might not actually be
- // available. If this occurs, use the register indicated by the
- // reuser.
- if (ReusedOperands.hasReuses())
- PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI,
- Spills, MaybeDeadStores);
-
- PhysRegsUsed[PhysReg] = true;
- MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
- // This invalidates PhysReg.
- Spills.ClobberPhysReg(PhysReg);
-
- // Any stores to this stack slot are not dead anymore.
- MaybeDeadStores.erase(StackSlot);
- Spills.addAvailable(StackSlot, PhysReg);
- ++NumLoads;
- MI.SetMachineOperandReg(i, PhysReg);
- DEBUG(std::cerr << '\t' << *prior(MII));
- }
-
- // Loop over all of the implicit defs, clearing them from our available
- // sets.
- for (const unsigned *ImpDef = TII->getImplicitDefs(MI.getOpcode());
- *ImpDef; ++ImpDef) {
- PhysRegsUsed[*ImpDef] = true;
- Spills.ClobberPhysReg(*ImpDef);
- }
-
- DEBUG(std::cerr << '\t' << MI);
-
- // If we have folded references to memory operands, make sure we clear all
- // physical registers that may contain the value of the spilled virtual
- // register
- VirtRegMap::MI2VirtMapTy::const_iterator I, End;
- for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) {
- DEBUG(std::cerr << "Folded vreg: " << I->second.first << " MR: "
- << I->second.second);
- unsigned VirtReg = I->second.first;
- VirtRegMap::ModRef MR = I->second.second;
- if (!VRM.hasStackSlot(VirtReg)) {
- DEBUG(std::cerr << ": No stack slot!\n");
- continue;
- }
- int SS = VRM.getStackSlot(VirtReg);
- DEBUG(std::cerr << " - StackSlot: " << SS << "\n");
-
- // If this folded instruction is just a use, check to see if it's a
- // straight load from the virt reg slot.
- if ((MR & VirtRegMap::isRef) && !(MR & VirtRegMap::isMod)) {
- int FrameIdx;
- if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) {
- // If this spill slot is available, turn it into a copy (or nothing)
- // instead of leaving it as a load!
- unsigned InReg;
- if (FrameIdx == SS && (InReg = Spills.getSpillSlotPhysReg(SS))) {
- DEBUG(std::cerr << "Promoted Load To Copy: " << MI);
- MachineFunction &MF = *MBB.getParent();
- if (DestReg != InReg) {
- MRI->copyRegToReg(MBB, &MI, DestReg, InReg,
- MF.getSSARegMap()->getRegClass(VirtReg));
- // Revisit the copy so we make sure to notice the effects of the
- // operation on the destreg (either needing to RA it if it's
- // virtual or needing to clobber any values if it's physical).
- NextMII = &MI;
- --NextMII; // backtrack to the copy.
- }
- MBB.erase(&MI);
- goto ProcessNextInst;
- }
- }
- }
-
- // If this reference is not a use, any previous store is now dead.
- // Otherwise, the store to this stack slot is not dead anymore.
- std::map<int, MachineInstr*>::iterator MDSI = MaybeDeadStores.find(SS);
- if (MDSI != MaybeDeadStores.end()) {
- if (MR & VirtRegMap::isRef) // Previous store is not dead.
- MaybeDeadStores.erase(MDSI);
- else {
- // If we get here, the store is dead, nuke it now.
- assert(MR == VirtRegMap::isMod && "Can't be modref!");
- MBB.erase(MDSI->second);
- MaybeDeadStores.erase(MDSI);
- ++NumDSE;
+ BitVector Used(NumRegs);
+ for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
+ e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
+ if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
+ Used.set(Virt2PhysMap[i]);
+
+ BitVector Allocatable = TRI->getAllocatableSet(*MF);
+ bool AnyUnused = false;
+ for (unsigned Reg = 1; Reg < NumRegs; ++Reg) {
+ if (Allocatable[Reg] && !Used[Reg] && !LIs->hasInterval(Reg)) {
+ bool ReallyUnused = true;
+ for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
+ if (Used[*AS] || LIs->hasInterval(*AS)) {
+ ReallyUnused = false;
+ break;
}
}
-
- // If the spill slot value is available, and this is a new definition of
- // the value, the value is not available anymore.
- if (MR & VirtRegMap::isMod) {
- // Notice that the value in this stack slot has been modified.
- Spills.ModifyStackSlot(SS);
-
- // If this is *just* a mod of the value, check to see if this is just a
- // store to the spill slot (i.e. the spill got merged into the copy). If
- // so, realize that the vreg is available now, and add the store to the
- // MaybeDeadStore info.
- int StackSlot;
- if (!(MR & VirtRegMap::isRef)) {
- if (unsigned SrcReg = TII->isStoreToStackSlot(&MI, StackSlot)) {
- assert(MRegisterInfo::isPhysicalRegister(SrcReg) &&
- "Src hasn't been allocated yet?");
- // Okay, this is certainly a store of SrcReg to [StackSlot]. Mark
- // this as a potentially dead store in case there is a subsequent
- // store into the stack slot without a read from it.
- MaybeDeadStores[StackSlot] = &MI;
-
- // If the stack slot value was previously available in some other
- // register, change it now. Otherwise, make the register available,
- // in PhysReg.
- Spills.addAvailable(StackSlot, SrcReg, false /*don't clobber*/);
- }
- }
+ if (ReallyUnused) {
+ AnyUnused = true;
+ UnusedRegs.set(Reg);
}
}
+ }
- // Process all of the spilled defs.
- for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI.getOperand(i);
- if (MO.isRegister() && MO.getReg() && MO.isDef()) {
- unsigned VirtReg = MO.getReg();
-
- if (!MRegisterInfo::isVirtualRegister(VirtReg)) {
- // Check to see if this is a def-and-use vreg operand that we do need
- // to insert a store for.
- bool OpTakenCareOf = false;
- if (MO.isUse() && !DefAndUseVReg.empty()) {
- for (unsigned dau = 0, e = DefAndUseVReg.size(); dau != e; ++dau)
- if (DefAndUseVReg[dau].first == i) {
- VirtReg = DefAndUseVReg[dau].second;
- OpTakenCareOf = true;
- break;
- }
- }
-
- if (!OpTakenCareOf) {
- // Check to see if this is a noop copy. If so, eliminate the
- // instruction before considering the dest reg to be changed.
- unsigned Src, Dst;
- if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) {
- ++NumDCE;
- DEBUG(std::cerr << "Removing now-noop copy: " << MI);
- MBB.erase(&MI);
- goto ProcessNextInst;
- }
- Spills.ClobberPhysReg(VirtReg);
- continue;
- }
- }
-
- // The only vregs left are stack slot definitions.
- int StackSlot = VRM.getStackSlot(VirtReg);
- const TargetRegisterClass *RC =
- MBB.getParent()->getSSARegMap()->getRegClass(VirtReg);
- unsigned PhysReg;
+ return AnyUnused;
+}
- // If this is a def&use operand, and we used a different physreg for
- // it than the one assigned, make sure to execute the store from the
- // correct physical register.
- if (MO.getReg() == VirtReg)
- PhysReg = VRM.getPhys(VirtReg);
- else
- PhysReg = MO.getReg();
+void VirtRegMap::print(std::ostream &OS, const Module* M) const {
+ raw_os_ostream RawOS(OS);
+ print(RawOS, M);
+}
- PhysRegsUsed[PhysReg] = true;
- MRI->storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot, RC);
- DEBUG(std::cerr << "Store:\t" << *next(MII));
- MI.SetMachineOperandReg(i, PhysReg);
+void VirtRegMap::print(raw_ostream &OS, const Module* M) const {
+ const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
- // Check to see if this is a noop copy. If so, eliminate the
- // instruction before considering the dest reg to be changed.
- {
- unsigned Src, Dst;
- if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) {
- ++NumDCE;
- DEBUG(std::cerr << "Removing now-noop copy: " << MI);
- MBB.erase(&MI);
- goto ProcessNextInst;
- }
- }
-
- // If there is a dead store to this stack slot, nuke it now.
- MachineInstr *&LastStore = MaybeDeadStores[StackSlot];
- if (LastStore) {
- DEBUG(std::cerr << " Killed store:\t" << *LastStore);
- ++NumDSE;
- MBB.erase(LastStore);
- }
- LastStore = next(MII);
-
- // If the stack slot value was previously available in some other
- // register, change it now. Otherwise, make the register available,
- // in PhysReg.
- Spills.ModifyStackSlot(StackSlot);
- Spills.ClobberPhysReg(PhysReg);
- Spills.addAvailable(StackSlot, PhysReg);
- ++NumStores;
- }
- }
- ProcessNextInst:
- MII = NextMII;
+ OS << "********** REGISTER MAP **********\n";
+ for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
+ e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) {
+ if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
+ OS << "[reg" << i << " -> " << TRI->getName(Virt2PhysMap[i])
+ << "]\n";
}
-}
-
+ for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
+ e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
+ if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT)
+ OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n";
+ OS << '\n';
+}
-llvm::Spiller* llvm::createSpiller() {
- switch (SpillerOpt) {
- default: assert(0 && "Unreachable!");
- case local:
- return new LocalSpiller();
- case simple:
- return new SimpleSpiller();
- }
+void VirtRegMap::dump() const {
+ print(cerr);
}