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/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/Target/TargetMachine.h"
  27 #include "llvm/Target/TargetInstrInfo.h"
  28 #include "llvm/Support/CommandLine.h"
  29 #include "llvm/Support/Compiler.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/ADT/BitVector.h"
  32 #include "llvm/ADT/DenseMap.h"
  33 #include "llvm/ADT/DepthFirstIterator.h"
  34 #include "llvm/ADT/Statistic.h"
  35 #include "llvm/ADT/STLExtras.h"
  36 #include "llvm/ADT/SmallSet.h"
  37 #include <algorithm>
  38 using namespace llvm;
  39
  40 STATISTIC(NumSpills  , "Number of register spills");
  41
  42 //===----------------------------------------------------------------------===//
  43 //  VirtRegMap implementation
  44 //===----------------------------------------------------------------------===//
  45
  46 VirtRegMap::VirtRegMap(MachineFunction &mf)
  47   : TII(*mf.getTarget().getInstrInfo()), MF(mf),
  48     Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT),
  49     Virt2ReMatIdMap(NO_STACK_SLOT), Virt2SplitMap(0),
  50     Virt2SplitKillMap(0), ReMatMap(NULL), ReMatId(MAX_STACK_SLOT+1),
  51     LowSpillSlot(NO_STACK_SLOT), HighSpillSlot(NO_STACK_SLOT) {
  52   SpillSlotToUsesMap.resize(8);
  53   ImplicitDefed.resize(MF.getRegInfo().getLastVirtReg()+1-
  54                        TargetRegisterInfo::FirstVirtualRegister);
  55   grow();
  56 }
  57
  58 void VirtRegMap::grow() {
  59   unsigned LastVirtReg = MF.getRegInfo().getLastVirtReg();
  60   Virt2PhysMap.grow(LastVirtReg);
  61   Virt2StackSlotMap.grow(LastVirtReg);
  62   Virt2ReMatIdMap.grow(LastVirtReg);
  63   Virt2SplitMap.grow(LastVirtReg);
  64   Virt2SplitKillMap.grow(LastVirtReg);
  65   ReMatMap.grow(LastVirtReg);
  66   ImplicitDefed.resize(LastVirtReg-TargetRegisterInfo::FirstVirtualRegister+1);
  67 }
  68
  69 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
  70   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
  71   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
  72          "attempt to assign stack slot to already spilled register");
  73   const TargetRegisterClass* RC = MF.getRegInfo().getRegClass(virtReg);
  74   int SS = MF.getFrameInfo()->CreateStackObject(RC->getSize(),
  75                                                 RC->getAlignment());
  76   if (LowSpillSlot == NO_STACK_SLOT)
  77     LowSpillSlot = SS;
  78   if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
  79     HighSpillSlot = SS;
  80   unsigned Idx = SS-LowSpillSlot;
  81   while (Idx >= SpillSlotToUsesMap.size())
  82     SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2);
  83   Virt2StackSlotMap[virtReg] = SS;
  84   ++NumSpills;
  85   return SS;
  86 }
  87
  88 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
  89   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
  90   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
  91          "attempt to assign stack slot to already spilled register");
  92   assert((SS >= 0 ||
  93           (SS >= MF.getFrameInfo()->getObjectIndexBegin())) &&
  94          "illegal fixed frame index");
  95   Virt2StackSlotMap[virtReg] = SS;
  96 }
  97
  98 int VirtRegMap::assignVirtReMatId(unsigned virtReg) {
  99   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
 100   assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
 101          "attempt to assign re-mat id to already spilled register");
 102   Virt2ReMatIdMap[virtReg] = ReMatId;
 103   return ReMatId++;
 104 }
 105
 106 void VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) {
 107   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
 108   assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
 109          "attempt to assign re-mat id to already spilled register");
 110   Virt2ReMatIdMap[virtReg] = id;
 111 }
 112
 113 int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass *RC) {
 114   std::map<const TargetRegisterClass*, int>::iterator I =
 115     EmergencySpillSlots.find(RC);
 116   if (I != EmergencySpillSlots.end())
 117     return I->second;
 118   int SS = MF.getFrameInfo()->CreateStackObject(RC->getSize(),
 119                                                 RC->getAlignment());
 120   if (LowSpillSlot == NO_STACK_SLOT)
 121     LowSpillSlot = SS;
 122   if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
 123     HighSpillSlot = SS;
 124   EmergencySpillSlots[RC] = SS;
 125   return SS;
 126 }
 127
 128 void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) {
 129   if (!MF.getFrameInfo()->isFixedObjectIndex(FI)) {
 130     // If FI < LowSpillSlot, this stack reference was produced by
 131     // instruction selection and is not a spill
 132     if (FI >= LowSpillSlot) {
 133       assert(FI >= 0 && "Spill slot index should not be negative!");
 134       assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
 135              && "Invalid spill slot");
 136       SpillSlotToUsesMap[FI-LowSpillSlot].insert(MI);
 137     }
 138   }
 139 }
 140
 141 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
 142                             MachineInstr *NewMI, ModRef MRInfo) {
 143   // Move previous memory references folded to new instruction.
 144   MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI);
 145   for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI),
 146          E = MI2VirtMap.end(); I != E && I->first == OldMI; ) {
 147     MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second));
 148     MI2VirtMap.erase(I++);
 149   }
 150
 151   // add new memory reference
 152   MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo)));
 153 }
 154
 155 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) {
 156   MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(MI);
 157   MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo)));
 158 }
 159
 160 void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) {
 161   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 162     MachineOperand &MO = MI->getOperand(i);
 163     if (!MO.isFI())
 164       continue;
 165     int FI = MO.getIndex();
 166     if (MF.getFrameInfo()->isFixedObjectIndex(FI))
 167       continue;
 168     // This stack reference was produced by instruction selection and
 169     // is not a spill
 170     if (FI < LowSpillSlot)
 171       continue;
 172     assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
 173            && "Invalid spill slot");
 174     SpillSlotToUsesMap[FI-LowSpillSlot].erase(MI);
 175   }
 176   MI2VirtMap.erase(MI);
 177   SpillPt2VirtMap.erase(MI);
 178   RestorePt2VirtMap.erase(MI);
 179   EmergencySpillMap.erase(MI);
 180 }
 181
 182 void VirtRegMap::print(std::ostream &OS) const {
 183   const TargetRegisterInfo* TRI = MF.getTarget().getRegisterInfo();
 184
 185   OS << "********** REGISTER MAP **********\n";
 186   for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
 187          e = MF.getRegInfo().getLastVirtReg(); i <= e; ++i) {
 188     if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
 189       OS << "[reg" << i << " -> " << TRI->getName(Virt2PhysMap[i])
 190          << "]\n";
 191   }
 192
 193   for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
 194          e = MF.getRegInfo().getLastVirtReg(); i <= e; ++i)
 195     if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT)
 196       OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n";
 197   OS << '\n';
 198 }
 199
 200 void VirtRegMap::dump() const {
 201   print(cerr);
 202 }