lib/CodeGen/VirtRegMap.cpp

   1 //===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===//
   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 the VirtRegMap class.
  11 //
  12 // It also contains implementations of the the Spiller interface, which, given a
  13 // virtual register map and a machine function, eliminates all virtual
  14 // references by replacing them with physical register references - adding spill
  15 // code as necessary.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #define DEBUG_TYPE "virtregmap"
  20 #include "VirtRegMap.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  23 #include "llvm/CodeGen/MachineFrameInfo.h"
  24 #include "llvm/CodeGen/MachineFunction.h"
  25 #include "llvm/CodeGen/MachineInstrBuilder.h"
  26 #include "llvm/CodeGen/MachineRegisterInfo.h"
  27 #include "llvm/Target/TargetMachine.h"
  28 #include "llvm/Target/TargetInstrInfo.h"
  29 #include "llvm/Support/CommandLine.h"
  30 #include "llvm/Support/Compiler.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/ADT/BitVector.h"
  33 #include "llvm/ADT/DenseMap.h"
  34 #include "llvm/ADT/DepthFirstIterator.h"
  35 #include "llvm/ADT/Statistic.h"
  36 #include "llvm/ADT/STLExtras.h"
  37 #include "llvm/ADT/SmallSet.h"
  38 #include <algorithm>
  39 using namespace llvm;
  40
  41 STATISTIC(NumSpills  , "Number of register spills");
  42
  43 //===----------------------------------------------------------------------===//
  44 //  VirtRegMap implementation
  45 //===----------------------------------------------------------------------===//
  46
  47 char VirtRegMap::ID = 0;
  48
  49 static RegisterPass<VirtRegMap>
  50 X("virtregmap", "Virtual Register Map");
  51
  52 bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
  53   TII = mf.getTarget().getInstrInfo();
  54   MF = &mf;
  55
  56   ReMatId = MAX_STACK_SLOT+1;
  57   LowSpillSlot = HighSpillSlot = NO_STACK_SLOT;
  58
  59   Virt2PhysMap.clear();
  60   Virt2StackSlotMap.clear();
  61   Virt2ReMatIdMap.clear();
  62   Virt2SplitMap.clear();
  63   Virt2SplitKillMap.clear();
  64   ReMatMap.clear();
  65   ImplicitDefed.clear();
  66   SpillSlotToUsesMap.clear();
  67   MI2VirtMap.clear();
  68   SpillPt2VirtMap.clear();
  69   RestorePt2VirtMap.clear();
  70   EmergencySpillMap.clear();
  71   EmergencySpillSlots.clear();
  72
  73   SpillSlotToUsesMap.resize(8);
  74   ImplicitDefed.resize(MF->getRegInfo().getLastVirtReg()+1-
  75                        TargetRegisterInfo::FirstVirtualRegister);
  76   grow();
  77
  78   return false;
  79 }
  80
  81 void VirtRegMap::grow() {
  82   unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg();
  83   Virt2PhysMap.grow(LastVirtReg);
  84   Virt2StackSlotMap.grow(LastVirtReg);
  85   Virt2ReMatIdMap.grow(LastVirtReg);
  86   Virt2SplitMap.grow(LastVirtReg);
  87   Virt2SplitKillMap.grow(LastVirtReg);
  88   ReMatMap.grow(LastVirtReg);
  89   ImplicitDefed.resize(LastVirtReg-TargetRegisterInfo::FirstVirtualRegister+1);
  90 }
  91
  92 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
  93   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
  94   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
  95          "attempt to assign stack slot to already spilled register");
  96   const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg);
  97   int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
  98                                                 RC->getAlignment());
  99   if (LowSpillSlot == NO_STACK_SLOT)
 100     LowSpillSlot = SS;
 101   if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
 102     HighSpillSlot = SS;
 103   unsigned Idx = SS-LowSpillSlot;
 104   while (Idx >= SpillSlotToUsesMap.size())
 105     SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2);
 106   Virt2StackSlotMap[virtReg] = SS;
 107   ++NumSpills;
 108   return SS;
 109 }
 110
 111 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
 112   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
 113   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
 114          "attempt to assign stack slot to already spilled register");
 115   assert((SS >= 0 ||
 116           (SS >= MF->getFrameInfo()->getObjectIndexBegin())) &&
 117          "illegal fixed frame index");
 118   Virt2StackSlotMap[virtReg] = SS;
 119 }
 120
 121 int VirtRegMap::assignVirtReMatId(unsigned virtReg) {
 122   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
 123   assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
 124          "attempt to assign re-mat id to already spilled register");
 125   Virt2ReMatIdMap[virtReg] = ReMatId;
 126   return ReMatId++;
 127 }
 128
 129 void VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) {
 130   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
 131   assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
 132          "attempt to assign re-mat id to already spilled register");
 133   Virt2ReMatIdMap[virtReg] = id;
 134 }
 135
 136 int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass *RC) {
 137   std::map<const TargetRegisterClass*, int>::iterator I =
 138     EmergencySpillSlots.find(RC);
 139   if (I != EmergencySpillSlots.end())
 140     return I->second;
 141   int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
 142                                                 RC->getAlignment());
 143   if (LowSpillSlot == NO_STACK_SLOT)
 144     LowSpillSlot = SS;
 145   if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
 146     HighSpillSlot = SS;
 147   EmergencySpillSlots[RC] = SS;
 148   return SS;
 149 }
 150
 151 void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) {
 152   if (!MF->getFrameInfo()->isFixedObjectIndex(FI)) {
 153     // If FI < LowSpillSlot, this stack reference was produced by
 154     // instruction selection and is not a spill
 155     if (FI >= LowSpillSlot) {
 156       assert(FI >= 0 && "Spill slot index should not be negative!");
 157       assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
 158              && "Invalid spill slot");
 159       SpillSlotToUsesMap[FI-LowSpillSlot].insert(MI);
 160     }
 161   }
 162 }
 163
 164 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
 165                             MachineInstr *NewMI, ModRef MRInfo) {
 166   // Move previous memory references folded to new instruction.
 167   MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI);
 168   for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI),
 169          E = MI2VirtMap.end(); I != E && I->first == OldMI; ) {
 170     MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second));
 171     MI2VirtMap.erase(I++);
 172   }
 173
 174   // add new memory reference
 175   MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo)));
 176 }
 177
 178 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) {
 179   MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(MI);
 180   MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo)));
 181 }
 182
 183 void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) {
 184   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 185     MachineOperand &MO = MI->getOperand(i);
 186     if (!MO.isFI())
 187       continue;
 188     int FI = MO.getIndex();
 189     if (MF->getFrameInfo()->isFixedObjectIndex(FI))
 190       continue;
 191     // This stack reference was produced by instruction selection and
 192     // is not a spill
 193     if (FI < LowSpillSlot)
 194       continue;
 195     assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
 196            && "Invalid spill slot");
 197     SpillSlotToUsesMap[FI-LowSpillSlot].erase(MI);
 198   }
 199   MI2VirtMap.erase(MI);
 200   SpillPt2VirtMap.erase(MI);
 201   RestorePt2VirtMap.erase(MI);
 202   EmergencySpillMap.erase(MI);
 203 }
 204
 205 /// FindUnusedRegisters - Gather a list of allocatable registers that
 206 /// have not been allocated to any virtual register.
 207 bool VirtRegMap::FindUnusedRegisters(const TargetRegisterInfo *TRI,
 208                                      LiveIntervals* LIs) {
 209   unsigned NumRegs = TRI->getNumRegs();
 210   UnusedRegs.reset();
 211   UnusedRegs.resize(NumRegs);
 212
 213   BitVector Used(NumRegs);
 214   for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
 215          e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
 216     if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
 217       Used.set(Virt2PhysMap[i]);
 218
 219   BitVector Allocatable = TRI->getAllocatableSet(*MF);
 220   bool AnyUnused = false;
 221   for (unsigned Reg = 1; Reg < NumRegs; ++Reg) {
 222     if (Allocatable[Reg] && !Used[Reg] && !LIs->hasInterval(Reg)) {
 223       bool ReallyUnused = true;
 224       for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
 225         if (Used[*AS] || LIs->hasInterval(*AS)) {
 226           ReallyUnused = false;
 227           break;
 228         }
 229       }
 230       if (ReallyUnused) {
 231         AnyUnused = true;
 232         UnusedRegs.set(Reg);
 233       }
 234     }
 235   }
 236
 237   return AnyUnused;
 238 }
 239
 240 void VirtRegMap::print(std::ostream &OS, const Module* M) const {
 241   const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
 242
 243   OS << "********** REGISTER MAP **********\n";
 244   for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
 245          e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) {
 246     if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
 247       OS << "[reg" << i << " -> " << TRI->getName(Virt2PhysMap[i])
 248          << "]\n";
 249   }
 250
 251   for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
 252          e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
 253     if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT)
 254       OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n";
 255   OS << '\n';
 256 }
 257
 258 void VirtRegMap::dump() const {
 259   print(cerr);
 260 }