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