lib/CodeGen/VirtRegMap.h

   1 //===-- llvm/CodeGen/VirtRegMap.h - Virtual Register Map -*- C++ -*--------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a virtual register map. This maps virtual registers to
  11 // physical registers and virtual registers to stack slots. It is created and
  12 // updated by a register allocator and then used by a machine code rewriter that
  13 // adds spill code and rewrites virtual into physical register references.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef LLVM_CODEGEN_VIRTREGMAP_H
  18 #define LLVM_CODEGEN_VIRTREGMAP_H
  19
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/LiveInterval.h"
  22 #include "llvm/Target/TargetRegisterInfo.h"
  23 #include "llvm/ADT/BitVector.h"
  24 #include "llvm/ADT/DenseMap.h"
  25 #include "llvm/ADT/IndexedMap.h"
  26 #include "llvm/ADT/SmallPtrSet.h"
  27 #include "llvm/ADT/SmallVector.h"
  28 #include <map>
  29
  30 namespace llvm {
  31   class LiveIntervals;
  32   class MachineInstr;
  33   class MachineFunction;
  34   class MachineRegisterInfo;
  35   class TargetInstrInfo;
  36   class TargetRegisterInfo;
  37   class raw_ostream;
  38   class SlotIndexes;
  39
  40   class VirtRegMap : public MachineFunctionPass {
  41   public:
  42     enum {
  43       NO_PHYS_REG = 0,
  44       NO_STACK_SLOT = (1L << 30)-1,
  45       MAX_STACK_SLOT = (1L << 18)-1
  46     };
  47
  48     enum ModRef { isRef = 1, isMod = 2, isModRef = 3 };
  49     typedef std::multimap<MachineInstr*,
  50                           std::pair<unsigned, ModRef> > MI2VirtMapTy;
  51
  52   private:
  53     MachineRegisterInfo *MRI;
  54     const TargetInstrInfo *TII;
  55     const TargetRegisterInfo *TRI;
  56     MachineFunction *MF;
  57
  58     DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs;
  59
  60     /// Virt2PhysMap - This is a virtual to physical register
  61     /// mapping. Each virtual register is required to have an entry in
  62     /// it; even spilled virtual registers (the register mapped to a
  63     /// spilled register is the temporary used to load it from the
  64     /// stack).
  65     IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap;
  66
  67     /// Virt2StackSlotMap - This is virtual register to stack slot
  68     /// mapping. Each spilled virtual register has an entry in it
  69     /// which corresponds to the stack slot this register is spilled
  70     /// at.
  71     IndexedMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap;
  72
  73     /// Virt2SplitMap - This is virtual register to splitted virtual register
  74     /// mapping.
  75     IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2SplitMap;
  76
  77     /// LowSpillSlot, HighSpillSlot - Lowest and highest spill slot indexes.
  78     int LowSpillSlot, HighSpillSlot;
  79
  80     /// SpillSlotToUsesMap - Records uses for each register spill slot.
  81     SmallVector<SmallPtrSet<MachineInstr*, 4>, 8> SpillSlotToUsesMap;
  82
  83     /// createSpillSlot - Allocate a spill slot for RC from MFI.
  84     unsigned createSpillSlot(const TargetRegisterClass *RC);
  85
  86     VirtRegMap(const VirtRegMap&);     // DO NOT IMPLEMENT
  87     void operator=(const VirtRegMap&); // DO NOT IMPLEMENT
  88
  89   public:
  90     static char ID;
  91     VirtRegMap() : MachineFunctionPass(ID), Virt2PhysMap(NO_PHYS_REG),
  92                    Virt2StackSlotMap(NO_STACK_SLOT), Virt2SplitMap(0),
  93                    LowSpillSlot(NO_STACK_SLOT), HighSpillSlot(NO_STACK_SLOT) { }
  94     virtual bool runOnMachineFunction(MachineFunction &MF);
  95
  96     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  97       AU.setPreservesAll();
  98       MachineFunctionPass::getAnalysisUsage(AU);
  99     }
 100
 101     MachineFunction &getMachineFunction() const {
 102       assert(MF && "getMachineFunction called before runOnMachineFunction");
 103       return *MF;
 104     }
 105
 106     MachineRegisterInfo &getRegInfo() const { return *MRI; }
 107     const TargetRegisterInfo &getTargetRegInfo() const { return *TRI; }
 108
 109     void grow();
 110
 111     /// @brief returns true if the specified virtual register is
 112     /// mapped to a physical register
 113     bool hasPhys(unsigned virtReg) const {
 114       return getPhys(virtReg) != NO_PHYS_REG;
 115     }
 116
 117     /// @brief returns the physical register mapped to the specified
 118     /// virtual register
 119     unsigned getPhys(unsigned virtReg) const {
 120       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
 121       return Virt2PhysMap[virtReg];
 122     }
 123
 124     /// @brief creates a mapping for the specified virtual register to
 125     /// the specified physical register
 126     void assignVirt2Phys(unsigned virtReg, unsigned physReg) {
 127       assert(TargetRegisterInfo::isVirtualRegister(virtReg) &&
 128              TargetRegisterInfo::isPhysicalRegister(physReg));
 129       assert(Virt2PhysMap[virtReg] == NO_PHYS_REG &&
 130              "attempt to assign physical register to already mapped "
 131              "virtual register");
 132       Virt2PhysMap[virtReg] = physReg;
 133     }
 134
 135     /// @brief clears the specified virtual register's, physical
 136     /// register mapping
 137     void clearVirt(unsigned virtReg) {
 138       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
 139       assert(Virt2PhysMap[virtReg] != NO_PHYS_REG &&
 140              "attempt to clear a not assigned virtual register");
 141       Virt2PhysMap[virtReg] = NO_PHYS_REG;
 142     }
 143
 144     /// @brief clears all virtual to physical register mappings
 145     void clearAllVirt() {
 146       Virt2PhysMap.clear();
 147       grow();
 148     }
 149
 150     /// @brief returns the register allocation preference.
 151     unsigned getRegAllocPref(unsigned virtReg);
 152
 153     /// @brief returns true if VirtReg is assigned to its preferred physreg.
 154     bool hasPreferredPhys(unsigned VirtReg) {
 155       return getPhys(VirtReg) == getRegAllocPref(VirtReg);
 156     }
 157
 158     /// @brief records virtReg is a split live interval from SReg.
 159     void setIsSplitFromReg(unsigned virtReg, unsigned SReg) {
 160       Virt2SplitMap[virtReg] = SReg;
 161     }
 162
 163     /// @brief returns the live interval virtReg is split from.
 164     unsigned getPreSplitReg(unsigned virtReg) const {
 165       return Virt2SplitMap[virtReg];
 166     }
 167
 168     /// getOriginal - Return the original virtual register that VirtReg descends
 169     /// from through splitting.
 170     /// A register that was not created by splitting is its own original.
 171     /// This operation is idempotent.
 172     unsigned getOriginal(unsigned VirtReg) const {
 173       unsigned Orig = getPreSplitReg(VirtReg);
 174       return Orig ? Orig : VirtReg;
 175     }
 176
 177     /// @brief returns true if the specified virtual register is not
 178     /// mapped to a stack slot or rematerialized.
 179     bool isAssignedReg(unsigned virtReg) const {
 180       if (getStackSlot(virtReg) == NO_STACK_SLOT)
 181         return true;
 182       // Split register can be assigned a physical register as well as a
 183       // stack slot or remat id.
 184       return (Virt2SplitMap[virtReg] && Virt2PhysMap[virtReg] != NO_PHYS_REG);
 185     }
 186
 187     /// @brief returns the stack slot mapped to the specified virtual
 188     /// register
 189     int getStackSlot(unsigned virtReg) const {
 190       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
 191       return Virt2StackSlotMap[virtReg];
 192     }
 193
 194     /// @brief create a mapping for the specifed virtual register to
 195     /// the next available stack slot
 196     int assignVirt2StackSlot(unsigned virtReg);
 197     /// @brief create a mapping for the specified virtual register to
 198     /// the specified stack slot
 199     void assignVirt2StackSlot(unsigned virtReg, int frameIndex);
 200
 201     /// @brief Records a spill slot use.
 202     void addSpillSlotUse(int FrameIndex, MachineInstr *MI);
 203
 204     /// @brief Returns true if spill slot has been used.
 205     bool isSpillSlotUsed(int FrameIndex) const {
 206       assert(FrameIndex >= 0 && "Spill slot index should not be negative!");
 207       return !SpillSlotToUsesMap[FrameIndex-LowSpillSlot].empty();
 208     }
 209
 210     /// RemoveMachineInstrFromMaps - MI is being erased, remove it from the
 211     /// the folded instruction map and spill point map.
 212     void RemoveMachineInstrFromMaps(MachineInstr *MI);
 213
 214     /// rewrite - Rewrite all instructions in MF to use only physical registers
 215     /// by mapping all virtual register operands to their assigned physical
 216     /// registers.
 217     ///
 218     /// @param Indexes Optionally remove deleted instructions from indexes.
 219     void rewrite(SlotIndexes *Indexes);
 220
 221     void print(raw_ostream &OS, const Module* M = 0) const;
 222     void dump() const;
 223   };
 224
 225   inline raw_ostream &operator<<(raw_ostream &OS, const VirtRegMap &VRM) {
 226     VRM.print(OS);
 227     return OS;
 228   }
 229 } // End llvm namespace
 230
 231 #endif