LLVM API Documentation

VirtRegMap.cpp

Go to the documentation of this file.
00001 //===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the VirtRegMap class.
00011 //
00012 // It also contains implementations of the the Spiller interface, which, given a
00013 // virtual register map and a machine function, eliminates all virtual
00014 // references by replacing them with physical register references - adding spill
00015 // code as necessary.
00016 //
00017 //===----------------------------------------------------------------------===//
00018 
00019 #define DEBUG_TYPE "virtregmap"
00020 #include "VirtRegMap.h"
00021 #include "llvm/Function.h"
00022 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
00023 #include "llvm/CodeGen/MachineFrameInfo.h"
00024 #include "llvm/CodeGen/MachineFunction.h"
00025 #include "llvm/CodeGen/MachineInstrBuilder.h"
00026 #include "llvm/CodeGen/MachineRegisterInfo.h"
00027 #include "llvm/Target/TargetMachine.h"
00028 #include "llvm/Target/TargetInstrInfo.h"
00029 #include "llvm/Target/TargetRegisterInfo.h"
00030 #include "llvm/Support/CommandLine.h"
00031 #include "llvm/Support/Compiler.h"
00032 #include "llvm/Support/Debug.h"
00033 #include "llvm/Support/raw_ostream.h"
00034 #include "llvm/ADT/BitVector.h"
00035 #include "llvm/ADT/DenseMap.h"
00036 #include "llvm/ADT/DepthFirstIterator.h"
00037 #include "llvm/ADT/Statistic.h"
00038 #include "llvm/ADT/STLExtras.h"
00039 #include "llvm/ADT/SmallSet.h"
00040 #include <algorithm>
00041 using namespace llvm;
00042 
00043 STATISTIC(NumSpills  , "Number of register spills");
00044 
00045 //===----------------------------------------------------------------------===//
00046 //  VirtRegMap implementation
00047 //===----------------------------------------------------------------------===//
00048 
00049 char VirtRegMap::ID = 0;
00050 
00051 static RegisterPass<VirtRegMap>
00052 X("virtregmap", "Virtual Register Map");
00053 
00054 bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
00055   MRI = &mf.getRegInfo();
00056   TII = mf.getTarget().getInstrInfo();
00057   TRI = mf.getTarget().getRegisterInfo();
00058   MF = &mf;
00059   
00060   ReMatId = MAX_STACK_SLOT+1;
00061   LowSpillSlot = HighSpillSlot = NO_STACK_SLOT;
00062   
00063   Virt2PhysMap.clear();
00064   Virt2StackSlotMap.clear();
00065   Virt2ReMatIdMap.clear();
00066   Virt2SplitMap.clear();
00067   Virt2SplitKillMap.clear();
00068   ReMatMap.clear();
00069   ImplicitDefed.clear();
00070   SpillSlotToUsesMap.clear();
00071   MI2VirtMap.clear();
00072   SpillPt2VirtMap.clear();
00073   RestorePt2VirtMap.clear();
00074   EmergencySpillMap.clear();
00075   EmergencySpillSlots.clear();
00076   
00077   SpillSlotToUsesMap.resize(8);
00078   ImplicitDefed.resize(MF->getRegInfo().getLastVirtReg()+1-
00079                        TargetRegisterInfo::FirstVirtualRegister);
00080 
00081   allocatableRCRegs.clear();
00082   for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(),
00083          E = TRI->regclass_end(); I != E; ++I)
00084     allocatableRCRegs.insert(std::make_pair(*I,
00085                                             TRI->getAllocatableSet(mf, *I)));
00086 
00087   grow();
00088   
00089   return false;
00090 }
00091 
00092 void VirtRegMap::grow() {
00093   unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg();
00094   Virt2PhysMap.grow(LastVirtReg);
00095   Virt2StackSlotMap.grow(LastVirtReg);
00096   Virt2ReMatIdMap.grow(LastVirtReg);
00097   Virt2SplitMap.grow(LastVirtReg);
00098   Virt2SplitKillMap.grow(LastVirtReg);
00099   ReMatMap.grow(LastVirtReg);
00100   ImplicitDefed.resize(LastVirtReg-TargetRegisterInfo::FirstVirtualRegister+1);
00101 }
00102 
00103 unsigned VirtRegMap::getRegAllocPref(unsigned virtReg) {
00104   std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(virtReg);
00105   unsigned physReg = Hint.second;
00106   if (physReg &&
00107       TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg))
00108     physReg = getPhys(physReg);
00109   if (Hint.first == 0)
00110     return (physReg && TargetRegisterInfo::isPhysicalRegister(physReg))
00111       ? physReg : 0;
00112   return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF);
00113 }
00114 
00115 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
00116   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
00117   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
00118          "attempt to assign stack slot to already spilled register");
00119   const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg);
00120   int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
00121                                                 RC->getAlignment());
00122   if (LowSpillSlot == NO_STACK_SLOT)
00123     LowSpillSlot = SS;
00124   if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
00125     HighSpillSlot = SS;
00126   unsigned Idx = SS-LowSpillSlot;
00127   while (Idx >= SpillSlotToUsesMap.size())
00128     SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2);
00129   Virt2StackSlotMap[virtReg] = SS;
00130   ++NumSpills;
00131   return SS;
00132 }
00133 
00134 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
00135   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
00136   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
00137          "attempt to assign stack slot to already spilled register");
00138   assert((SS >= 0 ||
00139           (SS >= MF->getFrameInfo()->getObjectIndexBegin())) &&
00140          "illegal fixed frame index");
00141   Virt2StackSlotMap[virtReg] = SS;
00142 }
00143 
00144 int VirtRegMap::assignVirtReMatId(unsigned virtReg) {
00145   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
00146   assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
00147          "attempt to assign re-mat id to already spilled register");
00148   Virt2ReMatIdMap[virtReg] = ReMatId;
00149   return ReMatId++;
00150 }
00151 
00152 void VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) {
00153   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
00154   assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
00155          "attempt to assign re-mat id to already spilled register");
00156   Virt2ReMatIdMap[virtReg] = id;
00157 }
00158 
00159 int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass *RC) {
00160   std::map<const TargetRegisterClass*, int>::iterator I =
00161     EmergencySpillSlots.find(RC);
00162   if (I != EmergencySpillSlots.end())
00163     return I->second;
00164   int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
00165                                                 RC->getAlignment());
00166   if (LowSpillSlot == NO_STACK_SLOT)
00167     LowSpillSlot = SS;
00168   if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
00169     HighSpillSlot = SS;
00170   EmergencySpillSlots[RC] = SS;
00171   return SS;
00172 }
00173 
00174 void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) {
00175   if (!MF->getFrameInfo()->isFixedObjectIndex(FI)) {
00176     // If FI < LowSpillSlot, this stack reference was produced by
00177     // instruction selection and is not a spill
00178     if (FI >= LowSpillSlot) {
00179       assert(FI >= 0 && "Spill slot index should not be negative!");
00180       assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
00181              && "Invalid spill slot");
00182       SpillSlotToUsesMap[FI-LowSpillSlot].insert(MI);
00183     }
00184   }
00185 }
00186 
00187 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
00188                             MachineInstr *NewMI, ModRef MRInfo) {
00189   // Move previous memory references folded to new instruction.
00190   MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI);
00191   for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI),
00192          E = MI2VirtMap.end(); I != E && I->first == OldMI; ) {
00193     MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second));
00194     MI2VirtMap.erase(I++);
00195   }
00196 
00197   // add new memory reference
00198   MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo)));
00199 }
00200 
00201 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) {
00202   MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(MI);
00203   MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo)));
00204 }
00205 
00206 void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) {
00207   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
00208     MachineOperand &MO = MI->getOperand(i);
00209     if (!MO.isFI())
00210       continue;
00211     int FI = MO.getIndex();
00212     if (MF->getFrameInfo()->isFixedObjectIndex(FI))
00213       continue;
00214     // This stack reference was produced by instruction selection and
00215     // is not a spill
00216     if (FI < LowSpillSlot)
00217       continue;
00218     assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
00219            && "Invalid spill slot");
00220     SpillSlotToUsesMap[FI-LowSpillSlot].erase(MI);
00221   }
00222   MI2VirtMap.erase(MI);
00223   SpillPt2VirtMap.erase(MI);
00224   RestorePt2VirtMap.erase(MI);
00225   EmergencySpillMap.erase(MI);
00226 }
00227 
00228 /// FindUnusedRegisters - Gather a list of allocatable registers that
00229 /// have not been allocated to any virtual register.
00230 bool VirtRegMap::FindUnusedRegisters(LiveIntervals* LIs) {
00231   unsigned NumRegs = TRI->getNumRegs();
00232   UnusedRegs.reset();
00233   UnusedRegs.resize(NumRegs);
00234 
00235   BitVector Used(NumRegs);
00236   for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
00237          e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
00238     if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
00239       Used.set(Virt2PhysMap[i]);
00240 
00241   BitVector Allocatable = TRI->getAllocatableSet(*MF);
00242   bool AnyUnused = false;
00243   for (unsigned Reg = 1; Reg < NumRegs; ++Reg) {
00244     if (Allocatable[Reg] && !Used[Reg] && !LIs->hasInterval(Reg)) {
00245       bool ReallyUnused = true;
00246       for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
00247         if (Used[*AS] || LIs->hasInterval(*AS)) {
00248           ReallyUnused = false;
00249           break;
00250         }
00251       }
00252       if (ReallyUnused) {
00253         AnyUnused = true;
00254         UnusedRegs.set(Reg);
00255       }
00256     }
00257   }
00258 
00259   return AnyUnused;
00260 }
00261 
00262 void VirtRegMap::print(std::ostream &OS, const Module* M) const {
00263   raw_os_ostream RawOS(OS);
00264   print(RawOS, M);
00265 }
00266 
00267 void VirtRegMap::print(raw_ostream &OS, const Module* M) const {
00268   const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
00269 
00270   OS << "********** REGISTER MAP **********\n";
00271   for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
00272          e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) {
00273     if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
00274       OS << "[reg" << i << " -> " << TRI->getName(Virt2PhysMap[i])
00275          << "]\n";
00276   }
00277 
00278   for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
00279          e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
00280     if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT)
00281       OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n";
00282   OS << '\n';
00283 }
00284 
00285 void VirtRegMap::dump() const {
00286   print(cerr);
00287 }