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: simple)"),
  43              cl::Prefix,
  44              cl::values(clEnumVal(simple, "  simple spiller"),
  45                         clEnumVal(local,  "  local spiller"),
  46                         clEnumValEnd),
  47              cl::init(simple));
  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     MachineBasicBlock &MBB = *MBBI;
 146     for (MachineBasicBlock::iterator MII = MBB.begin(),
 147            E = MBB.end(); MII != E; ++MII) {
 148       MachineInstr &MI = *MII;
 149       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 150         MachineOperand &MOP = MI.getOperand(i);
 151         if (MOP.isRegister() && MOP.getReg() &&
 152             MRegisterInfo::isVirtualRegister(MOP.getReg())){
 153           unsigned VirtReg = MOP.getReg();
 154           unsigned PhysReg = VRM.getPhys(VirtReg);
 155           if (VRM.hasStackSlot(VirtReg)) {
 156             int StackSlot    = VRM.getStackSlot(VirtReg);
 157
 158             if (MOP.isUse() &&
 159                 std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg)
 160                            == LoadedRegs.end()) {
 161               MRI.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot);
 162               LoadedRegs.push_back(VirtReg);
 163               ++NumLoads;
 164               DEBUG(std::cerr << '\t'; prior(MII)->print(std::cerr, &TM));
 165             }
 166
 167             if (MOP.isDef()) {
 168               MRI.storeRegToStackSlot(MBB, next(MII), PhysReg,
 169                                       VRM.getStackSlot(VirtReg));
 170               ++NumStores;
 171             }
 172           }
 173           MI.SetMachineOperandReg(i, PhysReg);
 174         }
 175       }
 176       DEBUG(std::cerr << '\t'; MI.print(std::cerr, &TM));
 177       LoadedRegs.clear();
 178     }
 179   }
 180   return true;
 181 }
 182
 183 //===----------------------------------------------------------------------===//
 184 //  Local Spiller Implementation
 185 //===----------------------------------------------------------------------===//
 186
 187 namespace {
 188   class LocalSpiller : public Spiller {
 189     typedef std::vector<unsigned> Phys2VirtMap;
 190     typedef std::vector<bool> PhysFlag;
 191     typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
 192
 193     MachineFunction *MF;
 194     const TargetMachine *TM;
 195     const TargetInstrInfo *TII;
 196     const MRegisterInfo *MRI;
 197     const VirtRegMap *VRM;
 198     Phys2VirtMap p2vMap_;
 199     PhysFlag dirty_;
 200     Virt2MI lastDef_;
 201
 202   public:
 203     bool runOnMachineFunction(MachineFunction &MF, const VirtRegMap &VRM);
 204
 205   private:
 206     void vacateJustPhysReg(MachineBasicBlock& MBB,
 207                            MachineBasicBlock::iterator MII,
 208                            unsigned PhysReg);
 209
 210     void vacatePhysReg(MachineBasicBlock& MBB,
 211                        MachineBasicBlock::iterator MII,
 212                        unsigned PhysReg) {
 213       vacateJustPhysReg(MBB, MII, PhysReg);
 214       for (const unsigned* as = MRI->getAliasSet(PhysReg); *as; ++as)
 215         vacateJustPhysReg(MBB, MII, *as);
 216     }
 217
 218     void handleUse(MachineBasicBlock& MBB,
 219                    MachineBasicBlock::iterator MII,
 220                    unsigned VirtReg,
 221                    unsigned PhysReg) {
 222       // check if we are replacing a previous mapping
 223       if (p2vMap_[PhysReg] != VirtReg) {
 224         vacatePhysReg(MBB, MII, PhysReg);
 225         p2vMap_[PhysReg] = VirtReg;
 226         // load if necessary
 227         if (VRM->hasStackSlot(VirtReg)) {
 228           MRI->loadRegFromStackSlot(MBB, MII, PhysReg,
 229                                      VRM->getStackSlot(VirtReg));
 230           ++NumLoads;
 231           DEBUG(std::cerr << "added: ";
 232                 prior(MII)->print(std::cerr, TM));
 233           lastDef_[VirtReg] = MII;
 234         }
 235       }
 236     }
 237
 238     void handleDef(MachineBasicBlock& MBB,
 239                    MachineBasicBlock::iterator MII,
 240                    unsigned VirtReg,
 241                    unsigned PhysReg) {
 242       // check if we are replacing a previous mapping
 243       if (p2vMap_[PhysReg] != VirtReg)
 244         vacatePhysReg(MBB, MII, PhysReg);
 245
 246       p2vMap_[PhysReg] = VirtReg;
 247       dirty_[PhysReg] = true;
 248       lastDef_[VirtReg] = MII;
 249     }
 250
 251     void eliminateVirtRegsInMBB(MachineBasicBlock& MBB);
 252   };
 253 }
 254
 255 bool LocalSpiller::runOnMachineFunction(MachineFunction &mf,
 256                                         const VirtRegMap &vrm) {
 257   MF = &mf;
 258   TM = &MF->getTarget();
 259   TII = TM->getInstrInfo();
 260   MRI = TM->getRegisterInfo();
 261   VRM = &vrm;
 262   p2vMap_.assign(MRI->getNumRegs(), 0);
 263   dirty_.assign(MRI->getNumRegs(), false);
 264
 265   DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
 266   DEBUG(std::cerr << "********** Function: "
 267         << MF->getFunction()->getName() << '\n');
 268
 269   for (MachineFunction::iterator MBB = MF->begin(), E = MF->end();
 270        MBB != E; ++MBB) {
 271     lastDef_.grow(MF->getSSARegMap()->getLastVirtReg());
 272     DEBUG(std::cerr << MBB->getBasicBlock()->getName() << ":\n");
 273     eliminateVirtRegsInMBB(*MBB);
 274     // clear map, dirty flag and last ref
 275     p2vMap_.assign(p2vMap_.size(), 0);
 276     dirty_.assign(dirty_.size(), false);
 277     lastDef_.clear();
 278   }
 279   return true;
 280 }
 281
 282 void LocalSpiller::vacateJustPhysReg(MachineBasicBlock& MBB,
 283                                      MachineBasicBlock::iterator MII,
 284                                      unsigned PhysReg) {
 285   unsigned VirtReg = p2vMap_[PhysReg];
 286   if (dirty_[PhysReg] && VRM->hasStackSlot(VirtReg)) {
 287     assert(lastDef_[VirtReg] && "virtual register is mapped "
 288            "to a register and but was not defined!");
 289     MachineBasicBlock::iterator lastDef = lastDef_[VirtReg];
 290     MachineBasicBlock::iterator nextLastRef = next(lastDef);
 291     MRI->storeRegToStackSlot(*lastDef->getParent(),
 292                               nextLastRef,
 293                               PhysReg,
 294                               VRM->getStackSlot(VirtReg));
 295     ++NumStores;
 296     DEBUG(std::cerr << "added: ";
 297           prior(nextLastRef)->print(std::cerr, TM);
 298           std::cerr << "after: ";
 299           lastDef->print(std::cerr, TM));
 300     lastDef_[VirtReg] = 0;
 301   }
 302   p2vMap_[PhysReg] = 0;
 303   dirty_[PhysReg] = false;
 304 }
 305
 306 void LocalSpiller::eliminateVirtRegsInMBB(MachineBasicBlock &MBB) {
 307   for (MachineBasicBlock::iterator MI = MBB.begin(), E = MBB.end();
 308        MI != E; ++MI) {
 309
 310     // if we have references to memory operands make sure
 311     // we clear all physical registers that may contain
 312     // the value of the spilled virtual register
 313     VirtRegMap::MI2VirtMapTy::const_iterator i, e;
 314     for (tie(i, e) = VRM->getFoldedVirts(MI); i != e; ++i) {
 315       if (VRM->hasPhys(i->second))
 316         vacateJustPhysReg(MBB, MI, VRM->getPhys(i->second));
 317     }
 318
 319     // rewrite all used operands
 320     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 321       MachineOperand& op = MI->getOperand(i);
 322       if (op.isRegister() && op.getReg() && op.isUse() &&
 323           MRegisterInfo::isVirtualRegister(op.getReg())) {
 324         unsigned VirtReg = op.getReg();
 325         unsigned PhysReg = VRM->getPhys(VirtReg);
 326         handleUse(MBB, MI, VirtReg, PhysReg);
 327         MI->SetMachineOperandReg(i, PhysReg);
 328         // mark as dirty if this is def&use
 329         if (op.isDef()) {
 330           dirty_[PhysReg] = true;
 331           lastDef_[VirtReg] = MI;
 332         }
 333       }
 334     }
 335
 336     // spill implicit physical register defs
 337     const TargetInstrDescriptor& tid = TII->get(MI->getOpcode());
 338     for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
 339       vacatePhysReg(MBB, MI, *id);
 340
 341     // spill explicit physical register defs
 342     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 343       MachineOperand& op = MI->getOperand(i);
 344       if (op.isRegister() && op.getReg() && !op.isUse() &&
 345           MRegisterInfo::isPhysicalRegister(op.getReg()))
 346         vacatePhysReg(MBB, MI, op.getReg());
 347     }
 348
 349     // rewrite def operands (def&use was handled with the
 350     // uses so don't check for those here)
 351     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 352       MachineOperand& op = MI->getOperand(i);
 353       if (op.isRegister() && op.getReg() && !op.isUse())
 354         if (MRegisterInfo::isPhysicalRegister(op.getReg()))
 355           vacatePhysReg(MBB, MI, op.getReg());
 356         else {
 357           unsigned PhysReg = VRM->getPhys(op.getReg());
 358           handleDef(MBB, MI, op.getReg(), PhysReg);
 359           MI->SetMachineOperandReg(i, PhysReg);
 360         }
 361     }
 362
 363     DEBUG(std::cerr << '\t'; MI->print(std::cerr, TM));
 364   }
 365
 366   for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
 367     vacateJustPhysReg(MBB, MBB.getFirstTerminator(), i);
 368 }
 369
 370
 371 llvm::Spiller* llvm::createSpiller() {
 372   switch (SpillerOpt) {
 373   default: assert(0 && "Unreachable!");
 374   case local:
 375     return new LocalSpiller();
 376   case simple:
 377     return new SimpleSpiller();
 378   }
 379 }