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