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