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
  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 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
  51 {
  52     assert(MRegisterInfo::isVirtualRegister(virtReg));
  53     assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
  54            "attempt to assign stack slot to already spilled register");
  55     const TargetRegisterClass* RC =
  56         mf_->getSSARegMap()->getRegClass(virtReg);
  57     int frameIndex = mf_->getFrameInfo()->CreateStackObject(RC->getSize(),
  58                                                             RC->getAlignment());
  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                                 loaded[virtReg] = true;
 150                                 DEBUG(std::cerr << '\t';
 151                                       prior(mii)->print(std::cerr, &tm));
 152                                 ++numLoads;
 153                             }
 154                             if (mop.isDef() &&
 155                                 vrm.hasStackSlot(mop.getReg())) {
 156                                 mri.storeRegToStackSlot(
 157                                     *mbbi,
 158                                     next(mii),
 159                                     physReg,
 160                                     vrm.getStackSlot(virtReg));
 161                                 ++numStores;
 162                             }
 163                             mii->SetMachineOperandReg(i, physReg);
 164                         }
 165                     }
 166                     DEBUG(std::cerr << '\t'; mii->print(std::cerr, &tm));
 167                     loaded.clear();
 168                 }
 169             }
 170             return true;
 171         }
 172     };
 173
 174     class LocalSpiller : public Spiller {
 175         typedef std::vector<unsigned> Phys2VirtMap;
 176         typedef std::vector<bool> PhysFlag;
 177         typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
 178
 179         MachineFunction* mf_;
 180         const TargetMachine* tm_;
 181         const TargetInstrInfo* tii_;
 182         const MRegisterInfo* mri_;
 183         const VirtRegMap* vrm_;
 184         Phys2VirtMap p2vMap_;
 185         PhysFlag dirty_;
 186         Virt2MI lastDef_;
 187
 188     public:
 189         bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
 190             mf_ = &mf;
 191             tm_ = &mf_->getTarget();
 192             tii_ = tm_->getInstrInfo();
 193             mri_ = tm_->getRegisterInfo();
 194             vrm_ = &vrm;
 195             p2vMap_.assign(mri_->getNumRegs(), 0);
 196             dirty_.assign(mri_->getNumRegs(), false);
 197
 198             DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
 199             DEBUG(std::cerr << "********** Function: "
 200                   << mf_->getFunction()->getName() << '\n');
 201
 202             for (MachineFunction::iterator mbbi = mf_->begin(),
 203                      mbbe = mf_->end(); mbbi != mbbe; ++mbbi) {
 204                 lastDef_.grow(mf_->getSSARegMap()->getLastVirtReg());
 205                 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
 206                 eliminateVirtRegsInMbb(*mbbi);
 207                 // clear map, dirty flag and last ref
 208                 p2vMap_.assign(p2vMap_.size(), 0);
 209                 dirty_.assign(dirty_.size(), false);
 210                 lastDef_.clear();
 211             }
 212             return true;
 213         }
 214
 215     private:
 216         void vacateJustPhysReg(MachineBasicBlock& mbb,
 217                                MachineBasicBlock::iterator mii,
 218                                unsigned physReg) {
 219             unsigned virtReg = p2vMap_[physReg];
 220             if (dirty_[physReg] && vrm_->hasStackSlot(virtReg)) {
 221                 assert(lastDef_[virtReg] && "virtual register is mapped "
 222                        "to a register and but was not defined!");
 223                 MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
 224                 MachineBasicBlock::iterator nextLastRef = next(lastDef);
 225                 mri_->storeRegToStackSlot(*lastDef->getParent(),
 226                                           nextLastRef,
 227                                           physReg,
 228                                           vrm_->getStackSlot(virtReg));
 229                 ++numStores;
 230                 DEBUG(std::cerr << "added: ";
 231                       prior(nextLastRef)->print(std::cerr, tm_);
 232                       std::cerr << "after: ";
 233                       lastDef->print(std::cerr, tm_));
 234                 lastDef_[virtReg] = 0;
 235             }
 236             p2vMap_[physReg] = 0;
 237             dirty_[physReg] = false;
 238         }
 239
 240         void vacatePhysReg(MachineBasicBlock& mbb,
 241                            MachineBasicBlock::iterator mii,
 242                            unsigned physReg) {
 243             vacateJustPhysReg(mbb, mii, physReg);
 244             for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as)
 245                 vacateJustPhysReg(mbb, mii, *as);
 246         }
 247
 248         void handleUse(MachineBasicBlock& mbb,
 249                        MachineBasicBlock::iterator mii,
 250                        unsigned virtReg,
 251                        unsigned physReg) {
 252             // check if we are replacing a previous mapping
 253             if (p2vMap_[physReg] != virtReg) {
 254                 vacatePhysReg(mbb, mii, physReg);
 255                 p2vMap_[physReg] = virtReg;
 256                 // load if necessary
 257                 if (vrm_->hasStackSlot(virtReg)) {
 258                     mri_->loadRegFromStackSlot(mbb, mii, physReg,
 259                                                vrm_->getStackSlot(virtReg));
 260                     ++numLoads;
 261                     DEBUG(std::cerr << "added: ";
 262                           prior(mii)->print(std::cerr, tm_));
 263                     lastDef_[virtReg] = mii;
 264                 }
 265             }
 266         }
 267
 268         void handleDef(MachineBasicBlock& mbb,
 269                        MachineBasicBlock::iterator mii,
 270                        unsigned virtReg,
 271                        unsigned physReg) {
 272             // check if we are replacing a previous mapping
 273             if (p2vMap_[physReg] != virtReg)
 274                 vacatePhysReg(mbb, mii, physReg);
 275
 276             p2vMap_[physReg] = virtReg;
 277             dirty_[physReg] = true;
 278             lastDef_[virtReg] = mii;
 279         }
 280
 281         void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) {
 282             for (MachineBasicBlock::iterator mii = mbb.begin(),
 283                      mie = mbb.end(); mii != mie; ++mii) {
 284
 285                 // if we have references to memory operands make sure
 286                 // we clear all physical registers that may contain
 287                 // the value of the spilled virtual register
 288                 VirtRegMap::MI2VirtMap::const_iterator i, e;
 289                 for (tie(i, e) = vrm_->getFoldedVirts(mii); i != e; ++i) {
 290                     if (vrm_->hasPhys(i->second))
 291                         vacateJustPhysReg(mbb, mii, vrm_->getPhys(i->second));
 292                 }
 293
 294                 // rewrite all used operands
 295                 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
 296                     MachineOperand& op = mii->getOperand(i);
 297                     if (op.isRegister() && op.getReg() && op.isUse() &&
 298                         MRegisterInfo::isVirtualRegister(op.getReg())) {
 299                         unsigned virtReg = op.getReg();
 300                         unsigned physReg = vrm_->getPhys(virtReg);
 301                         handleUse(mbb, mii, virtReg, physReg);
 302                         mii->SetMachineOperandReg(i, physReg);
 303                         // mark as dirty if this is def&use
 304                         if (op.isDef()) {
 305                             dirty_[physReg] = true;
 306                             lastDef_[virtReg] = mii;
 307                         }
 308                     }
 309                 }
 310
 311                 // spill implicit physical register defs
 312                 const TargetInstrDescriptor& tid = tii_->get(mii->getOpcode());
 313                 for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
 314                     vacatePhysReg(mbb, mii, *id);
 315
 316                 // spill explicit physical register defs
 317                 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
 318                     MachineOperand& op = mii->getOperand(i);
 319                     if (op.isRegister() && op.getReg() && !op.isUse() &&
 320                         MRegisterInfo::isPhysicalRegister(op.getReg()))
 321                         vacatePhysReg(mbb, mii, op.getReg());
 322                 }
 323
 324                 // rewrite def operands (def&use was handled with the
 325                 // uses so don't check for those here)
 326                 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
 327                     MachineOperand& op = mii->getOperand(i);
 328                     if (op.isRegister() && op.getReg() && !op.isUse())
 329                         if (MRegisterInfo::isPhysicalRegister(op.getReg()))
 330                             vacatePhysReg(mbb, mii, op.getReg());
 331                         else {
 332                             unsigned physReg = vrm_->getPhys(op.getReg());
 333                             handleDef(mbb, mii, op.getReg(), physReg);
 334                             mii->SetMachineOperandReg(i, physReg);
 335                         }
 336                 }
 337
 338                 DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_));
 339             }
 340
 341             for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
 342                 vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i);
 343
 344         }
 345     };
 346 }
 347
 348 llvm::Spiller* llvm::createSpiller()
 349 {
 350     switch (SpillerOpt) {
 351     default:
 352         std::cerr << "no spiller selected";
 353         abort();
 354     case local:
 355         return new LocalSpiller();
 356     case simple:
 357         return new SimpleSpiller();
 358     }
 359 }