lib/CodeGen/VirtRegMap.cpp

   1 //===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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 "spiller"
  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/SSARegMap.h"
  25 #include "llvm/Target/TargetMachine.h"
  26 #include "llvm/Target/TargetInstrInfo.h"
  27 #include "llvm/Support/CommandLine.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/ADT/Statistic.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 using namespace llvm;
  32
  33 namespace {
  34   Statistic<> NumSpills("spiller", "Number of register spills");
  35   Statistic<> NumStores("spiller", "Number of stores added");
  36   Statistic<> NumLoads ("spiller", "Number of loads added");
  37
  38   enum SpillerName { simple, local };
  39
  40   cl::opt<SpillerName>
  41   SpillerOpt("spiller",
  42              cl::desc("Spiller to use: (default: local)"),
  43              cl::Prefix,
  44              cl::values(clEnumVal(simple, "  simple spiller"),
  45                         clEnumVal(local,  "  local spiller"),
  46                         clEnumValEnd),
  47              cl::init(local));
  48 }
  49
  50 //===----------------------------------------------------------------------===//
  51 //  VirtRegMap implementation
  52 //===----------------------------------------------------------------------===//
  53
  54 void VirtRegMap::grow() {
  55   Virt2PhysMap.grow(MF.getSSARegMap()->getLastVirtReg());
  56   Virt2StackSlotMap.grow(MF.getSSARegMap()->getLastVirtReg());
  57 }
  58
  59 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
  60   assert(MRegisterInfo::isVirtualRegister(virtReg));
  61   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
  62          "attempt to assign stack slot to already spilled register");
  63   const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(virtReg);
  64   int frameIndex = MF.getFrameInfo()->CreateStackObject(RC->getSize(),
  65                                                         RC->getAlignment());
  66   Virt2StackSlotMap[virtReg] = frameIndex;
  67   ++NumSpills;
  68   return frameIndex;
  69 }
  70
  71 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) {
  72   assert(MRegisterInfo::isVirtualRegister(virtReg));
  73   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
  74          "attempt to assign stack slot to already spilled register");
  75   Virt2StackSlotMap[virtReg] = frameIndex;
  76 }
  77
  78 void VirtRegMap::virtFolded(unsigned virtReg,
  79                             MachineInstr* oldMI,
  80                             MachineInstr* newMI) {
  81   // move previous memory references folded to new instruction
  82   MI2VirtMapTy::iterator i, e;
  83   std::vector<MI2VirtMapTy::mapped_type> regs;
  84   for (tie(i, e) = MI2VirtMap.equal_range(oldMI); i != e; ) {
  85     regs.push_back(i->second);
  86     MI2VirtMap.erase(i++);
  87   }
  88   for (unsigned i = 0, e = regs.size(); i != e; ++i)
  89     MI2VirtMap.insert(std::make_pair(newMI, i));
  90
  91   // add new memory reference
  92   MI2VirtMap.insert(std::make_pair(newMI, virtReg));
  93 }
  94
  95 void VirtRegMap::print(std::ostream &OS) const {
  96   const MRegisterInfo* MRI = MF.getTarget().getRegisterInfo();
  97
  98   OS << "********** REGISTER MAP **********\n";
  99   for (unsigned i = MRegisterInfo::FirstVirtualRegister,
 100          e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
 101     if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
 102       OS << "[reg" << i << " -> " << MRI->getName(Virt2PhysMap[i]) << "]\n";
 103
 104   }
 105
 106   for (unsigned i = MRegisterInfo::FirstVirtualRegister,
 107          e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i)
 108     if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT)
 109       OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n";
 110   OS << '\n';
 111 }
 112
 113 void VirtRegMap::dump() const { print(std::cerr); }
 114
 115
 116 //===----------------------------------------------------------------------===//
 117 // Simple Spiller Implementation
 118 //===----------------------------------------------------------------------===//
 119
 120 Spiller::~Spiller() {}
 121
 122 namespace {
 123   struct SimpleSpiller : public Spiller {
 124     bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap &VRM);
 125   };
 126 }
 127
 128 bool SimpleSpiller::runOnMachineFunction(MachineFunction& MF,
 129                                          const VirtRegMap& VRM) {
 130   DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
 131   DEBUG(std::cerr << "********** Function: "
 132                   << MF.getFunction()->getName() << '\n');
 133   const TargetMachine& TM = MF.getTarget();
 134   const MRegisterInfo& MRI = *TM.getRegisterInfo();
 135
 136   // LoadedRegs - Keep track of which vregs are loaded, so that we only load
 137   // each vreg once (in the case where a spilled vreg is used by multiple
 138   // operands).  This is always smaller than the number of operands to the
 139   // current machine instr, so it should be small.
 140   std::vector<unsigned> LoadedRegs;
 141
 142   for (MachineFunction::iterator mbbi = MF.begin(), E = MF.end();
 143        mbbi != E; ++mbbi) {
 144     DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
 145     for (MachineBasicBlock::iterator mii = mbbi->begin(),
 146            mie = mbbi->end(); mii != mie; ++mii) {
 147       for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
 148         MachineOperand& mop = mii->getOperand(i);
 149         if (mop.isRegister() && mop.getReg() &&
 150             MRegisterInfo::isVirtualRegister(mop.getReg())) {
 151           unsigned virtReg = mop.getReg();
 152           unsigned physReg = VRM.getPhys(virtReg);
 153           if (mop.isUse() && VRM.hasStackSlot(mop.getReg()) &&
 154               std::find(LoadedRegs.begin(), LoadedRegs.end(),
 155                         virtReg) == LoadedRegs.end()) {
 156             MRI.loadRegFromStackSlot(*mbbi, mii, physReg,
 157                                      VRM.getStackSlot(virtReg));
 158             LoadedRegs.push_back(virtReg);
 159             DEBUG(std::cerr << '\t';
 160                   prior(mii)->print(std::cerr, &TM));
 161             ++NumLoads;
 162           }
 163
 164           if (mop.isDef() && VRM.hasStackSlot(mop.getReg())) {
 165             MRI.storeRegToStackSlot(*mbbi, next(mii), physReg,
 166                                     VRM.getStackSlot(virtReg));
 167             ++NumStores;
 168           }
 169           mii->SetMachineOperandReg(i, physReg);
 170         }
 171       }
 172       DEBUG(std::cerr << '\t'; mii->print(std::cerr, &TM));
 173       LoadedRegs.clear();
 174     }
 175   }
 176   return true;
 177 }
 178
 179 //===----------------------------------------------------------------------===//
 180 //  Local Spiller Implementation
 181 //===----------------------------------------------------------------------===//
 182
 183 namespace {
 184   class LocalSpiller : public Spiller {
 185     typedef std::vector<unsigned> Phys2VirtMap;
 186     typedef std::vector<bool> PhysFlag;
 187     typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
 188
 189     MachineFunction *MF;
 190     const TargetMachine *TM;
 191     const TargetInstrInfo *TII;
 192     const MRegisterInfo *MRI;
 193     const VirtRegMap *VRM;
 194     Phys2VirtMap p2vMap_;
 195     PhysFlag dirty_;
 196     Virt2MI lastDef_;
 197
 198   public:
 199     bool runOnMachineFunction(MachineFunction &MF, const VirtRegMap &VRM);
 200
 201   private:
 202     void vacateJustPhysReg(MachineBasicBlock& mbb,
 203                            MachineBasicBlock::iterator mii,
 204                            unsigned physReg);
 205
 206     void vacatePhysReg(MachineBasicBlock& mbb,
 207                        MachineBasicBlock::iterator mii,
 208                        unsigned physReg) {
 209       vacateJustPhysReg(mbb, mii, physReg);
 210       for (const unsigned* as = MRI->getAliasSet(physReg); *as; ++as)
 211         vacateJustPhysReg(mbb, mii, *as);
 212     }
 213
 214     void handleUse(MachineBasicBlock& mbb,
 215                    MachineBasicBlock::iterator mii,
 216                    unsigned virtReg,
 217                    unsigned physReg) {
 218       // check if we are replacing a previous mapping
 219       if (p2vMap_[physReg] != virtReg) {
 220         vacatePhysReg(mbb, mii, physReg);
 221         p2vMap_[physReg] = virtReg;
 222         // load if necessary
 223         if (VRM->hasStackSlot(virtReg)) {
 224           MRI->loadRegFromStackSlot(mbb, mii, physReg,
 225                                      VRM->getStackSlot(virtReg));
 226           ++NumLoads;
 227           DEBUG(std::cerr << "added: ";
 228                 prior(mii)->print(std::cerr, TM));
 229           lastDef_[virtReg] = mii;
 230         }
 231       }
 232     }
 233
 234     void handleDef(MachineBasicBlock& mbb,
 235                    MachineBasicBlock::iterator mii,
 236                    unsigned virtReg,
 237                    unsigned physReg) {
 238       // check if we are replacing a previous mapping
 239       if (p2vMap_[physReg] != virtReg)
 240         vacatePhysReg(mbb, mii, physReg);
 241
 242       p2vMap_[physReg] = virtReg;
 243       dirty_[physReg] = true;
 244       lastDef_[virtReg] = mii;
 245     }
 246
 247     void eliminateVirtRegsInMbb(MachineBasicBlock& mbb);
 248   };
 249 }
 250
 251 bool LocalSpiller::runOnMachineFunction(MachineFunction &mf,
 252                                         const VirtRegMap &vrm) {
 253   MF = &mf;
 254   TM = &MF->getTarget();
 255   TII = TM->getInstrInfo();
 256   MRI = TM->getRegisterInfo();
 257   VRM = &vrm;
 258   p2vMap_.assign(MRI->getNumRegs(), 0);
 259   dirty_.assign(MRI->getNumRegs(), false);
 260
 261   DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
 262   DEBUG(std::cerr << "********** Function: "
 263         << MF->getFunction()->getName() << '\n');
 264
 265   for (MachineFunction::iterator mbbi = MF->begin(),
 266          mbbe = MF->end(); mbbi != mbbe; ++mbbi) {
 267     lastDef_.grow(MF->getSSARegMap()->getLastVirtReg());
 268     DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
 269     eliminateVirtRegsInMbb(*mbbi);
 270     // clear map, dirty flag and last ref
 271     p2vMap_.assign(p2vMap_.size(), 0);
 272     dirty_.assign(dirty_.size(), false);
 273     lastDef_.clear();
 274   }
 275   return true;
 276 }
 277
 278 void LocalSpiller::vacateJustPhysReg(MachineBasicBlock& mbb,
 279                                      MachineBasicBlock::iterator mii,
 280                                      unsigned physReg) {
 281   unsigned virtReg = p2vMap_[physReg];
 282   if (dirty_[physReg] && VRM->hasStackSlot(virtReg)) {
 283     assert(lastDef_[virtReg] && "virtual register is mapped "
 284            "to a register and but was not defined!");
 285     MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
 286     MachineBasicBlock::iterator nextLastRef = next(lastDef);
 287     MRI->storeRegToStackSlot(*lastDef->getParent(),
 288                               nextLastRef,
 289                               physReg,
 290                               VRM->getStackSlot(virtReg));
 291     ++NumStores;
 292     DEBUG(std::cerr << "added: ";
 293           prior(nextLastRef)->print(std::cerr, TM);
 294           std::cerr << "after: ";
 295           lastDef->print(std::cerr, TM));
 296     lastDef_[virtReg] = 0;
 297   }
 298   p2vMap_[physReg] = 0;
 299   dirty_[physReg] = false;
 300 }
 301
 302 void LocalSpiller::eliminateVirtRegsInMbb(MachineBasicBlock &MBB) {
 303   for (MachineBasicBlock::iterator MI = MBB.begin(), E = MBB.end();
 304        MI != E; ++MI) {
 305
 306     // if we have references to memory operands make sure
 307     // we clear all physical registers that may contain
 308     // the value of the spilled virtual register
 309     VirtRegMap::MI2VirtMapTy::const_iterator i, e;
 310     for (tie(i, e) = VRM->getFoldedVirts(MI); i != e; ++i) {
 311       if (VRM->hasPhys(i->second))
 312         vacateJustPhysReg(MBB, MI, VRM->getPhys(i->second));
 313     }
 314
 315     // rewrite all used operands
 316     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 317       MachineOperand& op = MI->getOperand(i);
 318       if (op.isRegister() && op.getReg() && op.isUse() &&
 319           MRegisterInfo::isVirtualRegister(op.getReg())) {
 320         unsigned virtReg = op.getReg();
 321         unsigned physReg = VRM->getPhys(virtReg);
 322         handleUse(MBB, MI, virtReg, physReg);
 323         MI->SetMachineOperandReg(i, physReg);
 324         // mark as dirty if this is def&use
 325         if (op.isDef()) {
 326           dirty_[physReg] = true;
 327           lastDef_[virtReg] = MI;
 328         }
 329       }
 330     }
 331
 332     // spill implicit physical register defs
 333     const TargetInstrDescriptor& tid = TII->get(MI->getOpcode());
 334     for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
 335       vacatePhysReg(MBB, MI, *id);
 336
 337     // spill explicit physical register defs
 338     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 339       MachineOperand& op = MI->getOperand(i);
 340       if (op.isRegister() && op.getReg() && !op.isUse() &&
 341           MRegisterInfo::isPhysicalRegister(op.getReg()))
 342         vacatePhysReg(MBB, MI, op.getReg());
 343     }
 344
 345     // rewrite def operands (def&use was handled with the
 346     // uses so don't check for those here)
 347     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 348       MachineOperand& op = MI->getOperand(i);
 349       if (op.isRegister() && op.getReg() && !op.isUse())
 350         if (MRegisterInfo::isPhysicalRegister(op.getReg()))
 351           vacatePhysReg(MBB, MI, op.getReg());
 352         else {
 353           unsigned physReg = VRM->getPhys(op.getReg());
 354           handleDef(MBB, MI, op.getReg(), physReg);
 355           MI->SetMachineOperandReg(i, physReg);
 356         }
 357     }
 358
 359     DEBUG(std::cerr << '\t'; MI->print(std::cerr, TM));
 360   }
 361
 362   for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
 363     vacateJustPhysReg(MBB, MBB.getFirstTerminator(), i);
 364 }
 365
 366
 367 llvm::Spiller* llvm::createSpiller() {
 368   switch (SpillerOpt) {
 369   default: assert(0 && "Unreachable!");
 370   case local:
 371     return new LocalSpiller();
 372   case simple:
 373     return new SimpleSpiller();
 374   }
 375 }