LLVM API Documentation

VirtRegMap.h

Go to the documentation of this file.
00001 //===-- llvm/CodeGen/VirtRegMap.h - Virtual Register Map -*- C++ -*--------===//
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 a virtual register map. This maps virtual registers to
00011 // physical registers and virtual registers to stack slots. It is created and
00012 // updated by a register allocator and then used by a machine code rewriter that
00013 // adds spill code and rewrites virtual into physical register references.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #ifndef LLVM_CODEGEN_VIRTREGMAP_H
00018 #define LLVM_CODEGEN_VIRTREGMAP_H
00019 
00020 #include "llvm/CodeGen/MachineFunctionPass.h"
00021 #include "llvm/Target/TargetRegisterInfo.h"
00022 #include "llvm/ADT/BitVector.h"
00023 #include "llvm/ADT/DenseMap.h"
00024 #include "llvm/ADT/IndexedMap.h"
00025 #include "llvm/ADT/SmallPtrSet.h"
00026 #include "llvm/ADT/SmallVector.h"
00027 #include "llvm/Support/Streams.h"
00028 #include <map>
00029 
00030 namespace llvm {
00031   class LiveIntervals;
00032   class MachineInstr;
00033   class MachineFunction;
00034   class MachineRegisterInfo;
00035   class TargetInstrInfo;
00036   class TargetRegisterInfo;
00037   class raw_ostream;
00038 
00039   class VirtRegMap : public MachineFunctionPass {
00040   public:
00041     enum {
00042       NO_PHYS_REG = 0,
00043       NO_STACK_SLOT = (1L << 30)-1,
00044       MAX_STACK_SLOT = (1L << 18)-1
00045     };
00046 
00047     enum ModRef { isRef = 1, isMod = 2, isModRef = 3 };
00048     typedef std::multimap<MachineInstr*,
00049                           std::pair<unsigned, ModRef> > MI2VirtMapTy;
00050 
00051   private:
00052     MachineRegisterInfo *MRI;
00053     const TargetInstrInfo *TII;
00054     const TargetRegisterInfo *TRI;
00055     MachineFunction *MF;
00056 
00057     DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs;
00058 
00059     /// Virt2PhysMap - This is a virtual to physical register
00060     /// mapping. Each virtual register is required to have an entry in
00061     /// it; even spilled virtual registers (the register mapped to a
00062     /// spilled register is the temporary used to load it from the
00063     /// stack).
00064     IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap;
00065 
00066     /// Virt2StackSlotMap - This is virtual register to stack slot
00067     /// mapping. Each spilled virtual register has an entry in it
00068     /// which corresponds to the stack slot this register is spilled
00069     /// at.
00070     IndexedMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap;
00071 
00072     /// Virt2ReMatIdMap - This is virtual register to rematerialization id
00073     /// mapping. Each spilled virtual register that should be remat'd has an
00074     /// entry in it which corresponds to the remat id.
00075     IndexedMap<int, VirtReg2IndexFunctor> Virt2ReMatIdMap;
00076 
00077     /// Virt2SplitMap - This is virtual register to splitted virtual register
00078     /// mapping.
00079     IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2SplitMap;
00080 
00081     /// Virt2SplitKillMap - This is splitted virtual register to its last use
00082     /// (kill) index mapping.
00083     IndexedMap<unsigned> Virt2SplitKillMap;
00084 
00085     /// ReMatMap - This is virtual register to re-materialized instruction
00086     /// mapping. Each virtual register whose definition is going to be
00087     /// re-materialized has an entry in it.
00088     IndexedMap<MachineInstr*, VirtReg2IndexFunctor> ReMatMap;
00089 
00090     /// MI2VirtMap - This is MachineInstr to virtual register
00091     /// mapping. In the case of memory spill code being folded into
00092     /// instructions, we need to know which virtual register was
00093     /// read/written by this instruction.
00094     MI2VirtMapTy MI2VirtMap;
00095 
00096     /// SpillPt2VirtMap - This records the virtual registers which should
00097     /// be spilled right after the MachineInstr due to live interval
00098     /// splitting.
00099     std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >
00100     SpillPt2VirtMap;
00101 
00102     /// RestorePt2VirtMap - This records the virtual registers which should
00103     /// be restored right before the MachineInstr due to live interval
00104     /// splitting.
00105     std::map<MachineInstr*, std::vector<unsigned> > RestorePt2VirtMap;
00106 
00107     /// EmergencySpillMap - This records the physical registers that should
00108     /// be spilled / restored around the MachineInstr since the register
00109     /// allocator has run out of registers.
00110     std::map<MachineInstr*, std::vector<unsigned> > EmergencySpillMap;
00111 
00112     /// EmergencySpillSlots - This records emergency spill slots used to
00113     /// spill physical registers when the register allocator runs out of
00114     /// registers. Ideally only one stack slot is used per function per
00115     /// register class.
00116     std::map<const TargetRegisterClass*, int> EmergencySpillSlots;
00117 
00118     /// ReMatId - Instead of assigning a stack slot to a to be rematerialized
00119     /// virtual register, an unique id is being assigned. This keeps track of
00120     /// the highest id used so far. Note, this starts at (1<<18) to avoid
00121     /// conflicts with stack slot numbers.
00122     int ReMatId;
00123 
00124     /// LowSpillSlot, HighSpillSlot - Lowest and highest spill slot indexes.
00125     int LowSpillSlot, HighSpillSlot;
00126 
00127     /// SpillSlotToUsesMap - Records uses for each register spill slot.
00128     SmallVector<SmallPtrSet<MachineInstr*, 4>, 8> SpillSlotToUsesMap;
00129 
00130     /// ImplicitDefed - One bit for each virtual register. If set it indicates
00131     /// the register is implicitly defined.
00132     BitVector ImplicitDefed;
00133 
00134     /// UnusedRegs - A list of physical registers that have not been used.
00135     BitVector UnusedRegs;
00136 
00137     VirtRegMap(const VirtRegMap&);     // DO NOT IMPLEMENT
00138     void operator=(const VirtRegMap&); // DO NOT IMPLEMENT
00139 
00140   public:
00141     static char ID;
00142     VirtRegMap() : MachineFunctionPass(&ID), Virt2PhysMap(NO_PHYS_REG),
00143                    Virt2StackSlotMap(NO_STACK_SLOT), 
00144                    Virt2ReMatIdMap(NO_STACK_SLOT), Virt2SplitMap(0),
00145                    Virt2SplitKillMap(0), ReMatMap(NULL),
00146                    ReMatId(MAX_STACK_SLOT+1),
00147                    LowSpillSlot(NO_STACK_SLOT), HighSpillSlot(NO_STACK_SLOT) { }
00148     virtual bool runOnMachineFunction(MachineFunction &MF);
00149 
00150     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00151       AU.setPreservesAll();
00152       MachineFunctionPass::getAnalysisUsage(AU);
00153     }
00154 
00155     void grow();
00156 
00157     /// @brief returns true if the specified virtual register is
00158     /// mapped to a physical register
00159     bool hasPhys(unsigned virtReg) const {
00160       return getPhys(virtReg) != NO_PHYS_REG;
00161     }
00162 
00163     /// @brief returns the physical register mapped to the specified
00164     /// virtual register
00165     unsigned getPhys(unsigned virtReg) const {
00166       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
00167       return Virt2PhysMap[virtReg];
00168     }
00169 
00170     /// @brief creates a mapping for the specified virtual register to
00171     /// the specified physical register
00172     void assignVirt2Phys(unsigned virtReg, unsigned physReg) {
00173       assert(TargetRegisterInfo::isVirtualRegister(virtReg) &&
00174              TargetRegisterInfo::isPhysicalRegister(physReg));
00175       assert(Virt2PhysMap[virtReg] == NO_PHYS_REG &&
00176              "attempt to assign physical register to already mapped "
00177              "virtual register");
00178       Virt2PhysMap[virtReg] = physReg;
00179     }
00180 
00181     /// @brief clears the specified virtual register's, physical
00182     /// register mapping
00183     void clearVirt(unsigned virtReg) {
00184       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
00185       assert(Virt2PhysMap[virtReg] != NO_PHYS_REG &&
00186              "attempt to clear a not assigned virtual register");
00187       Virt2PhysMap[virtReg] = NO_PHYS_REG;
00188     }
00189 
00190     /// @brief clears all virtual to physical register mappings
00191     void clearAllVirt() {
00192       Virt2PhysMap.clear();
00193       grow();
00194     }
00195 
00196     /// @brief returns the register allocation preference.
00197     unsigned getRegAllocPref(unsigned virtReg);
00198 
00199     /// @brief records virtReg is a split live interval from SReg.
00200     void setIsSplitFromReg(unsigned virtReg, unsigned SReg) {
00201       Virt2SplitMap[virtReg] = SReg;
00202     }
00203 
00204     /// @brief returns the live interval virtReg is split from.
00205     unsigned getPreSplitReg(unsigned virtReg) {
00206       return Virt2SplitMap[virtReg];
00207     }
00208 
00209     /// @brief returns true if the specified virtual register is not
00210     /// mapped to a stack slot or rematerialized.
00211     bool isAssignedReg(unsigned virtReg) const {
00212       if (getStackSlot(virtReg) == NO_STACK_SLOT &&
00213           getReMatId(virtReg) == NO_STACK_SLOT)
00214         return true;
00215       // Split register can be assigned a physical register as well as a
00216       // stack slot or remat id.
00217       return (Virt2SplitMap[virtReg] && Virt2PhysMap[virtReg] != NO_PHYS_REG);
00218     }
00219 
00220     /// @brief returns the stack slot mapped to the specified virtual
00221     /// register
00222     int getStackSlot(unsigned virtReg) const {
00223       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
00224       return Virt2StackSlotMap[virtReg];
00225     }
00226 
00227     /// @brief returns the rematerialization id mapped to the specified virtual
00228     /// register
00229     int getReMatId(unsigned virtReg) const {
00230       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
00231       return Virt2ReMatIdMap[virtReg];
00232     }
00233 
00234     /// @brief create a mapping for the specifed virtual register to
00235     /// the next available stack slot
00236     int assignVirt2StackSlot(unsigned virtReg);
00237     /// @brief create a mapping for the specified virtual register to
00238     /// the specified stack slot
00239     void assignVirt2StackSlot(unsigned virtReg, int frameIndex);
00240 
00241     /// @brief assign an unique re-materialization id to the specified
00242     /// virtual register.
00243     int assignVirtReMatId(unsigned virtReg);
00244     /// @brief assign an unique re-materialization id to the specified
00245     /// virtual register.
00246     void assignVirtReMatId(unsigned virtReg, int id);
00247 
00248     /// @brief returns true if the specified virtual register is being
00249     /// re-materialized.
00250     bool isReMaterialized(unsigned virtReg) const {
00251       return ReMatMap[virtReg] != NULL;
00252     }
00253 
00254     /// @brief returns the original machine instruction being re-issued
00255     /// to re-materialize the specified virtual register.
00256     MachineInstr *getReMaterializedMI(unsigned virtReg) const {
00257       return ReMatMap[virtReg];
00258     }
00259 
00260     /// @brief records the specified virtual register will be
00261     /// re-materialized and the original instruction which will be re-issed
00262     /// for this purpose.  If parameter all is true, then all uses of the
00263     /// registers are rematerialized and it's safe to delete the definition.
00264     void setVirtIsReMaterialized(unsigned virtReg, MachineInstr *def) {
00265       ReMatMap[virtReg] = def;
00266     }
00267 
00268     /// @brief record the last use (kill) of a split virtual register.
00269     void addKillPoint(unsigned virtReg, unsigned index) {
00270       Virt2SplitKillMap[virtReg] = index;
00271     }
00272 
00273     unsigned getKillPoint(unsigned virtReg) const {
00274       return Virt2SplitKillMap[virtReg];
00275     }
00276 
00277     /// @brief remove the last use (kill) of a split virtual register.
00278     void removeKillPoint(unsigned virtReg) {
00279       Virt2SplitKillMap[virtReg] = 0;
00280     }
00281 
00282     /// @brief returns true if the specified MachineInstr is a spill point.
00283     bool isSpillPt(MachineInstr *Pt) const {
00284       return SpillPt2VirtMap.find(Pt) != SpillPt2VirtMap.end();
00285     }
00286 
00287     /// @brief returns the virtual registers that should be spilled due to
00288     /// splitting right after the specified MachineInstr.
00289     std::vector<std::pair<unsigned,bool> > &getSpillPtSpills(MachineInstr *Pt) {
00290       return SpillPt2VirtMap[Pt];
00291     }
00292 
00293     /// @brief records the specified MachineInstr as a spill point for virtReg.
00294     void addSpillPoint(unsigned virtReg, bool isKill, MachineInstr *Pt) {
00295       std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >::iterator
00296         I = SpillPt2VirtMap.find(Pt);
00297       if (I != SpillPt2VirtMap.end())
00298         I->second.push_back(std::make_pair(virtReg, isKill));
00299       else {
00300         std::vector<std::pair<unsigned,bool> > Virts;
00301         Virts.push_back(std::make_pair(virtReg, isKill));
00302         SpillPt2VirtMap.insert(std::make_pair(Pt, Virts));
00303       }
00304     }
00305 
00306     /// @brief - transfer spill point information from one instruction to
00307     /// another.
00308     void transferSpillPts(MachineInstr *Old, MachineInstr *New) {
00309       std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >::iterator
00310         I = SpillPt2VirtMap.find(Old);
00311       if (I == SpillPt2VirtMap.end())
00312         return;
00313       while (!I->second.empty()) {
00314         unsigned virtReg = I->second.back().first;
00315         bool isKill = I->second.back().second;
00316         I->second.pop_back();
00317         addSpillPoint(virtReg, isKill, New);
00318       }
00319       SpillPt2VirtMap.erase(I);
00320     }
00321 
00322     /// @brief returns true if the specified MachineInstr is a restore point.
00323     bool isRestorePt(MachineInstr *Pt) const {
00324       return RestorePt2VirtMap.find(Pt) != RestorePt2VirtMap.end();
00325     }
00326 
00327     /// @brief returns the virtual registers that should be restoreed due to
00328     /// splitting right after the specified MachineInstr.
00329     std::vector<unsigned> &getRestorePtRestores(MachineInstr *Pt) {
00330       return RestorePt2VirtMap[Pt];
00331     }
00332 
00333     /// @brief records the specified MachineInstr as a restore point for virtReg.
00334     void addRestorePoint(unsigned virtReg, MachineInstr *Pt) {
00335       std::map<MachineInstr*, std::vector<unsigned> >::iterator I =
00336         RestorePt2VirtMap.find(Pt);
00337       if (I != RestorePt2VirtMap.end())
00338         I->second.push_back(virtReg);
00339       else {
00340         std::vector<unsigned> Virts;
00341         Virts.push_back(virtReg);
00342         RestorePt2VirtMap.insert(std::make_pair(Pt, Virts));
00343       }
00344     }
00345 
00346     /// @brief - transfer restore point information from one instruction to
00347     /// another.
00348     void transferRestorePts(MachineInstr *Old, MachineInstr *New) {
00349       std::map<MachineInstr*, std::vector<unsigned> >::iterator I =
00350         RestorePt2VirtMap.find(Old);
00351       if (I == RestorePt2VirtMap.end())
00352         return;
00353       while (!I->second.empty()) {
00354         unsigned virtReg = I->second.back();
00355         I->second.pop_back();
00356         addRestorePoint(virtReg, New);
00357       }
00358       RestorePt2VirtMap.erase(I);
00359     }
00360 
00361     /// @brief records that the specified physical register must be spilled
00362     /// around the specified machine instr.
00363     void addEmergencySpill(unsigned PhysReg, MachineInstr *MI) {
00364       if (EmergencySpillMap.find(MI) != EmergencySpillMap.end())
00365         EmergencySpillMap[MI].push_back(PhysReg);
00366       else {
00367         std::vector<unsigned> PhysRegs;
00368         PhysRegs.push_back(PhysReg);
00369         EmergencySpillMap.insert(std::make_pair(MI, PhysRegs));
00370       }
00371     }
00372 
00373     /// @brief returns true if one or more physical registers must be spilled
00374     /// around the specified instruction.
00375     bool hasEmergencySpills(MachineInstr *MI) const {
00376       return EmergencySpillMap.find(MI) != EmergencySpillMap.end();
00377     }
00378 
00379     /// @brief returns the physical registers to be spilled and restored around
00380     /// the instruction.
00381     std::vector<unsigned> &getEmergencySpills(MachineInstr *MI) {
00382       return EmergencySpillMap[MI];
00383     }
00384 
00385     /// @brief - transfer emergency spill information from one instruction to
00386     /// another.
00387     void transferEmergencySpills(MachineInstr *Old, MachineInstr *New) {
00388       std::map<MachineInstr*,std::vector<unsigned> >::iterator I =
00389         EmergencySpillMap.find(Old);
00390       if (I == EmergencySpillMap.end())
00391         return;
00392       while (!I->second.empty()) {
00393         unsigned virtReg = I->second.back();
00394         I->second.pop_back();
00395         addEmergencySpill(virtReg, New);
00396       }
00397       EmergencySpillMap.erase(I);
00398     }
00399 
00400     /// @brief return or get a emergency spill slot for the register class.
00401     int getEmergencySpillSlot(const TargetRegisterClass *RC);
00402 
00403     /// @brief Return lowest spill slot index.
00404     int getLowSpillSlot() const {
00405       return LowSpillSlot;
00406     }
00407 
00408     /// @brief Return highest spill slot index.
00409     int getHighSpillSlot() const {
00410       return HighSpillSlot;
00411     }
00412 
00413     /// @brief Records a spill slot use.
00414     void addSpillSlotUse(int FrameIndex, MachineInstr *MI);
00415 
00416     /// @brief Returns true if spill slot has been used.
00417     bool isSpillSlotUsed(int FrameIndex) const {
00418       assert(FrameIndex >= 0 && "Spill slot index should not be negative!");
00419       return !SpillSlotToUsesMap[FrameIndex-LowSpillSlot].empty();
00420     }
00421 
00422     /// @brief Mark the specified register as being implicitly defined.
00423     void setIsImplicitlyDefined(unsigned VirtReg) {
00424       ImplicitDefed.set(VirtReg-TargetRegisterInfo::FirstVirtualRegister);
00425     }
00426 
00427     /// @brief Returns true if the virtual register is implicitly defined.
00428     bool isImplicitlyDefined(unsigned VirtReg) const {
00429       return ImplicitDefed[VirtReg-TargetRegisterInfo::FirstVirtualRegister];
00430     }
00431 
00432     /// @brief Updates information about the specified virtual register's value
00433     /// folded into newMI machine instruction.
00434     void virtFolded(unsigned VirtReg, MachineInstr *OldMI, MachineInstr *NewMI,
00435                     ModRef MRInfo);
00436 
00437     /// @brief Updates information about the specified virtual register's value
00438     /// folded into the specified machine instruction.
00439     void virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo);
00440 
00441     /// @brief returns the virtual registers' values folded in memory
00442     /// operands of this instruction
00443     std::pair<MI2VirtMapTy::const_iterator, MI2VirtMapTy::const_iterator>
00444     getFoldedVirts(MachineInstr* MI) const {
00445       return MI2VirtMap.equal_range(MI);
00446     }
00447     
00448     /// RemoveMachineInstrFromMaps - MI is being erased, remove it from the
00449     /// the folded instruction map and spill point map.
00450     void RemoveMachineInstrFromMaps(MachineInstr *MI);
00451 
00452     /// FindUnusedRegisters - Gather a list of allocatable registers that
00453     /// have not been allocated to any virtual register.
00454     bool FindUnusedRegisters(LiveIntervals* LIs);
00455 
00456     /// HasUnusedRegisters - Return true if there are any allocatable registers
00457     /// that have not been allocated to any virtual register.
00458     bool HasUnusedRegisters() const {
00459       return !UnusedRegs.none();
00460     }
00461 
00462     /// setRegisterUsed - Remember the physical register is now used.
00463     void setRegisterUsed(unsigned Reg) {
00464       UnusedRegs.reset(Reg);
00465     }
00466 
00467     /// isRegisterUnused - Return true if the physical register has not been
00468     /// used.
00469     bool isRegisterUnused(unsigned Reg) const {
00470       return UnusedRegs[Reg];
00471     }
00472 
00473     /// getFirstUnusedRegister - Return the first physical register that has not
00474     /// been used.
00475     unsigned getFirstUnusedRegister(const TargetRegisterClass *RC) {
00476       int Reg = UnusedRegs.find_first();
00477       while (Reg != -1) {
00478         if (allocatableRCRegs[RC][Reg])
00479           return (unsigned)Reg;
00480         Reg = UnusedRegs.find_next(Reg);
00481       }
00482       return 0;
00483     }
00484 
00485     void print(std::ostream &OS, const Module* M = 0) const;
00486     void print(std::ostream *OS) const { if (OS) print(*OS); }
00487     void print(raw_ostream &OS, const Module* M = 0) const;
00488     void print(raw_ostream *OS) const { if (OS) print(*OS); }
00489     void dump() const;
00490   };
00491 
00492   inline std::ostream *operator<<(std::ostream *OS, const VirtRegMap &VRM) {
00493     VRM.print(OS);
00494     return OS;
00495   }
00496   inline std::ostream &operator<<(std::ostream &OS, const VirtRegMap &VRM) {
00497     VRM.print(OS);
00498     return OS;
00499   }
00500   inline raw_ostream *operator<<(raw_ostream *OS, const VirtRegMap &VRM) {
00501     VRM.print(OS);
00502     return OS;
00503   }
00504   inline raw_ostream &operator<<(raw_ostream &OS, const VirtRegMap &VRM) {
00505     VRM.print(OS);
00506     return OS;
00507   }
00508 } // End llvm namespace
00509 
00510 #endif