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   v2pMap_.grow(mf_->getSSARegMap()->getLastVirtReg());
  56   v2ssMap_.grow(mf_->getSSARegMap()->getLastVirtReg());
  57 }
  58
  59 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
  60   assert(MRegisterInfo::isVirtualRegister(virtReg));
  61   assert(v2ssMap_[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   v2ssMap_[virtReg] = frameIndex;
  67   ++NumSpills;
  68   return frameIndex;
  69 }
  70
  71 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) {
  72   assert(MRegisterInfo::isVirtualRegister(virtReg));
  73   assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
  74          "attempt to assign stack slot to already spilled register");
  75   v2ssMap_[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   MI2VirtMap::iterator i, e;
  83   std::vector<MI2VirtMap::mapped_type> regs;
  84   for (tie(i, e) = mi2vMap_.equal_range(oldMI); i != e; ) {
  85     regs.push_back(i->second);
  86     mi2vMap_.erase(i++);
  87   }
  88   for (unsigned i = 0, e = regs.size(); i != e; ++i)
  89     mi2vMap_.insert(std::make_pair(newMI, i));
  90
  91   // add new memory reference
  92   mi2vMap_.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   std::cerr << "********** REGISTER MAP **********\n";
  99   for (unsigned i = MRegisterInfo::FirstVirtualRegister,
 100          e = mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
 101     if (v2pMap_[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
 102       std::cerr << "[reg" << i << " -> "
 103                 << mri->getName(v2pMap_[i]) << "]\n";
 104   }
 105
 106   for (unsigned i = MRegisterInfo::FirstVirtualRegister,
 107          e = mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
 108     if (v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
 109       std::cerr << "[reg" << i << " -> fi#"
 110                 << v2ssMap_[i] << "]\n";
 111   }
 112   std::cerr << '\n';
 113 }
 114
 115 void VirtRegMap::dump() const { print(std::cerr); }
 116
 117
 118 //===----------------------------------------------------------------------===//
 119 // Simple Spiller Implementation
 120 //===----------------------------------------------------------------------===//
 121
 122 Spiller::~Spiller() {}
 123
 124 namespace {
 125   struct SimpleSpiller : public Spiller {
 126     bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap &VRM);
 127   };
 128 }
 129
 130 bool SimpleSpiller::runOnMachineFunction(MachineFunction& MF,
 131                                          const VirtRegMap& VRM) {
 132   DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
 133   DEBUG(std::cerr << "********** Function: "
 134                   << MF.getFunction()->getName() << '\n');
 135   const TargetMachine& TM = MF.getTarget();
 136   const MRegisterInfo& mri = *TM.getRegisterInfo();
 137
 138   DenseMap<bool, VirtReg2IndexFunctor> Loaded;
 139
 140   for (MachineFunction::iterator mbbi = MF.begin(), E = MF.end();
 141        mbbi != E; ++mbbi) {
 142     DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
 143     for (MachineBasicBlock::iterator mii = mbbi->begin(),
 144            mie = mbbi->end(); mii != mie; ++mii) {
 145       Loaded.grow(MF.getSSARegMap()->getLastVirtReg());
 146       for (unsigned i = 0,e = mii->getNumOperands(); i != e; ++i){
 147         MachineOperand& mop = mii->getOperand(i);
 148         if (mop.isRegister() && mop.getReg() &&
 149             MRegisterInfo::isVirtualRegister(mop.getReg())) {
 150           unsigned virtReg = mop.getReg();
 151           unsigned physReg = VRM.getPhys(virtReg);
 152           if (mop.isUse() && VRM.hasStackSlot(mop.getReg()) &&
 153               !Loaded[virtReg]) {
 154             mri.loadRegFromStackSlot(*mbbi, mii, physReg,
 155                                      VRM.getStackSlot(virtReg));
 156             Loaded[virtReg] = true;
 157             DEBUG(std::cerr << '\t';
 158                   prior(mii)->print(std::cerr, &TM));
 159             ++NumLoads;
 160           }
 161
 162           if (mop.isDef() && VRM.hasStackSlot(mop.getReg())) {
 163             mri.storeRegToStackSlot(*mbbi, next(mii), physReg,
 164                                     VRM.getStackSlot(virtReg));
 165             ++NumStores;
 166           }
 167           mii->SetMachineOperandReg(i, physReg);
 168         }
 169       }
 170       DEBUG(std::cerr << '\t'; mii->print(std::cerr, &TM));
 171       Loaded.clear();
 172     }
 173   }
 174   return true;
 175 }
 176
 177 //===----------------------------------------------------------------------===//
 178 //  Local Spiller Implementation
 179 //===----------------------------------------------------------------------===//
 180
 181 namespace {
 182   class LocalSpiller : public Spiller {
 183     typedef std::vector<unsigned> Phys2VirtMap;
 184     typedef std::vector<bool> PhysFlag;
 185     typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
 186
 187     MachineFunction *MF;
 188     const TargetMachine *TM;
 189     const TargetInstrInfo *TII;
 190     const MRegisterInfo *MRI;
 191     const VirtRegMap *VRM;
 192     Phys2VirtMap p2vMap_;
 193     PhysFlag dirty_;
 194     Virt2MI lastDef_;
 195
 196   public:
 197     bool runOnMachineFunction(MachineFunction &MF, const VirtRegMap &VRM);
 198
 199   private:
 200     void vacateJustPhysReg(MachineBasicBlock& mbb,
 201                            MachineBasicBlock::iterator mii,
 202                            unsigned physReg);
 203
 204     void vacatePhysReg(MachineBasicBlock& mbb,
 205                        MachineBasicBlock::iterator mii,
 206                        unsigned physReg) {
 207       vacateJustPhysReg(mbb, mii, physReg);
 208       for (const unsigned* as = MRI->getAliasSet(physReg); *as; ++as)
 209         vacateJustPhysReg(mbb, mii, *as);
 210     }
 211
 212     void handleUse(MachineBasicBlock& mbb,
 213                    MachineBasicBlock::iterator mii,
 214                    unsigned virtReg,
 215                    unsigned physReg) {
 216       // check if we are replacing a previous mapping
 217       if (p2vMap_[physReg] != virtReg) {
 218         vacatePhysReg(mbb, mii, physReg);
 219         p2vMap_[physReg] = virtReg;
 220         // load if necessary
 221         if (VRM->hasStackSlot(virtReg)) {
 222           MRI->loadRegFromStackSlot(mbb, mii, physReg,
 223                                      VRM->getStackSlot(virtReg));
 224           ++NumLoads;
 225           DEBUG(std::cerr << "added: ";
 226                 prior(mii)->print(std::cerr, TM));
 227           lastDef_[virtReg] = mii;
 228         }
 229       }
 230     }
 231
 232     void handleDef(MachineBasicBlock& mbb,
 233                    MachineBasicBlock::iterator mii,
 234                    unsigned virtReg,
 235                    unsigned physReg) {
 236       // check if we are replacing a previous mapping
 237       if (p2vMap_[physReg] != virtReg)
 238         vacatePhysReg(mbb, mii, physReg);
 239
 240       p2vMap_[physReg] = virtReg;
 241       dirty_[physReg] = true;
 242       lastDef_[virtReg] = mii;
 243     }
 244
 245     void eliminateVirtRegsInMbb(MachineBasicBlock& mbb);
 246   };
 247 }
 248
 249 bool LocalSpiller::runOnMachineFunction(MachineFunction &mf,
 250                                         const VirtRegMap &vrm) {
 251   MF = &mf;
 252   TM = &MF->getTarget();
 253   TII = TM->getInstrInfo();
 254   MRI = TM->getRegisterInfo();
 255   VRM = &vrm;
 256   p2vMap_.assign(MRI->getNumRegs(), 0);
 257   dirty_.assign(MRI->getNumRegs(), false);
 258
 259   DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
 260   DEBUG(std::cerr << "********** Function: "
 261         << MF->getFunction()->getName() << '\n');
 262
 263   for (MachineFunction::iterator mbbi = MF->begin(),
 264          mbbe = MF->end(); mbbi != mbbe; ++mbbi) {
 265     lastDef_.grow(MF->getSSARegMap()->getLastVirtReg());
 266     DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
 267     eliminateVirtRegsInMbb(*mbbi);
 268     // clear map, dirty flag and last ref
 269     p2vMap_.assign(p2vMap_.size(), 0);
 270     dirty_.assign(dirty_.size(), false);
 271     lastDef_.clear();
 272   }
 273   return true;
 274 }
 275
 276 void LocalSpiller::vacateJustPhysReg(MachineBasicBlock& mbb,
 277                                      MachineBasicBlock::iterator mii,
 278                                      unsigned physReg) {
 279   unsigned virtReg = p2vMap_[physReg];
 280   if (dirty_[physReg] && VRM->hasStackSlot(virtReg)) {
 281     assert(lastDef_[virtReg] && "virtual register is mapped "
 282            "to a register and but was not defined!");
 283     MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
 284     MachineBasicBlock::iterator nextLastRef = next(lastDef);
 285     MRI->storeRegToStackSlot(*lastDef->getParent(),
 286                               nextLastRef,
 287                               physReg,
 288                               VRM->getStackSlot(virtReg));
 289     ++NumStores;
 290     DEBUG(std::cerr << "added: ";
 291           prior(nextLastRef)->print(std::cerr, TM);
 292           std::cerr << "after: ";
 293           lastDef->print(std::cerr, TM));
 294     lastDef_[virtReg] = 0;
 295   }
 296   p2vMap_[physReg] = 0;
 297   dirty_[physReg] = false;
 298 }
 299
 300 void LocalSpiller::eliminateVirtRegsInMbb(MachineBasicBlock &MBB) {
 301   for (MachineBasicBlock::iterator MI = MBB.begin(), E = MBB.end();
 302        MI != E; ++MI) {
 303
 304     // if we have references to memory operands make sure
 305     // we clear all physical registers that may contain
 306     // the value of the spilled virtual register
 307     VirtRegMap::MI2VirtMap::const_iterator i, e;
 308     for (tie(i, e) = VRM->getFoldedVirts(MI); i != e; ++i) {
 309       if (VRM->hasPhys(i->second))
 310         vacateJustPhysReg(MBB, MI, VRM->getPhys(i->second));
 311     }
 312
 313     // rewrite all used operands
 314     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 315       MachineOperand& op = MI->getOperand(i);
 316       if (op.isRegister() && op.getReg() && op.isUse() &&
 317           MRegisterInfo::isVirtualRegister(op.getReg())) {
 318         unsigned virtReg = op.getReg();
 319         unsigned physReg = VRM->getPhys(virtReg);
 320         handleUse(MBB, MI, virtReg, physReg);
 321         MI->SetMachineOperandReg(i, physReg);
 322         // mark as dirty if this is def&use
 323         if (op.isDef()) {
 324           dirty_[physReg] = true;
 325           lastDef_[virtReg] = MI;
 326         }
 327       }
 328     }
 329
 330     // spill implicit physical register defs
 331     const TargetInstrDescriptor& tid = TII->get(MI->getOpcode());
 332     for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
 333       vacatePhysReg(MBB, MI, *id);
 334
 335     // spill explicit physical register defs
 336     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 337       MachineOperand& op = MI->getOperand(i);
 338       if (op.isRegister() && op.getReg() && !op.isUse() &&
 339           MRegisterInfo::isPhysicalRegister(op.getReg()))
 340         vacatePhysReg(MBB, MI, op.getReg());
 341     }
 342
 343     // rewrite def operands (def&use was handled with the
 344     // uses so don't check for those here)
 345     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 346       MachineOperand& op = MI->getOperand(i);
 347       if (op.isRegister() && op.getReg() && !op.isUse())
 348         if (MRegisterInfo::isPhysicalRegister(op.getReg()))
 349           vacatePhysReg(MBB, MI, op.getReg());
 350         else {
 351           unsigned physReg = VRM->getPhys(op.getReg());
 352           handleDef(MBB, MI, op.getReg(), physReg);
 353           MI->SetMachineOperandReg(i, physReg);
 354         }
 355     }
 356
 357     DEBUG(std::cerr << '\t'; MI->print(std::cerr, TM));
 358   }
 359
 360   for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
 361     vacateJustPhysReg(MBB, MBB.getFirstTerminator(), i);
 362 }
 363
 364
 365 llvm::Spiller* llvm::createSpiller() {
 366   switch (SpillerOpt) {
 367   default: assert(0 && "Unreachable!");
 368   case local:
 369     return new LocalSpiller();
 370   case simple:
 371     return new SimpleSpiller();
 372   }
 373 }