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