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/Statistic.h"
  26 #include "Support/Debug.h"
  27 #include "Support/DenseMap.h"
  28 #include "Support/STLExtras.h"
  29 #include <iostream>
  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 }
  39
  40 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
  41 {
  42     assert(MRegisterInfo::isVirtualRegister(virtReg));
  43     assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
  44            "attempt to assign stack slot to already spilled register");
  45     const TargetRegisterClass* rc =
  46         mf_->getSSARegMap()->getRegClass(virtReg);
  47     int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
  48     v2ssMap_[virtReg] = frameIndex;
  49     ++numSpills;
  50     return frameIndex;
  51 }
  52
  53 void VirtRegMap::virtFolded(unsigned virtReg,
  54                             MachineInstr* oldMI,
  55                             MachineInstr* newMI)
  56 {
  57     // move previous memory references folded to new instruction
  58     MI2VirtMap::iterator i, e;
  59     std::vector<MI2VirtMap::mapped_type> regs;
  60     for (tie(i, e) = mi2vMap_.equal_range(oldMI); i != e; ) {
  61         regs.push_back(i->second);
  62         mi2vMap_.erase(i++);
  63     }
  64     for (unsigned i = 0, e = regs.size(); i != e; ++i)
  65         mi2vMap_.insert(std::make_pair(newMI, i));
  66
  67     // add new memory reference
  68     mi2vMap_.insert(std::make_pair(newMI, virtReg));
  69 }
  70
  71 std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
  72 {
  73     const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo();
  74
  75     std::cerr << "********** REGISTER MAP **********\n";
  76     for (unsigned i = MRegisterInfo::FirstVirtualRegister,
  77              e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
  78         if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG)
  79             std::cerr << "[reg" << i << " -> "
  80                       << mri->getName(vrm.v2pMap_[i]) << "]\n";
  81     }
  82     for (unsigned i = MRegisterInfo::FirstVirtualRegister,
  83              e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
  84         if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
  85             std::cerr << "[reg" << i << " -> fi#"
  86                       << vrm.v2ssMap_[i] << "]\n";
  87     }
  88     return std::cerr << '\n';
  89 }
  90
  91 namespace {
  92
  93     class Spiller {
  94         typedef std::vector<unsigned> Phys2VirtMap;
  95         typedef std::vector<bool> PhysFlag;
  96         typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
  97
  98         MachineFunction& mf_;
  99         const TargetMachine& tm_;
 100         const TargetInstrInfo& tii_;
 101         const MRegisterInfo& mri_;
 102         const VirtRegMap& vrm_;
 103         Phys2VirtMap p2vMap_;
 104         PhysFlag dirty_;
 105         Virt2MI lastDef_;
 106
 107     public:
 108         Spiller(MachineFunction& mf, const VirtRegMap& vrm)
 109             : mf_(mf),
 110               tm_(mf_.getTarget()),
 111               tii_(tm_.getInstrInfo()),
 112               mri_(*tm_.getRegisterInfo()),
 113               vrm_(vrm),
 114               p2vMap_(mri_.getNumRegs(), 0),
 115               dirty_(mri_.getNumRegs(), false),
 116               lastDef_() {
 117             DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
 118             DEBUG(std::cerr << "********** Function: "
 119                   << mf_.getFunction()->getName() << '\n');
 120         }
 121
 122         void eliminateVirtRegs() {
 123             for (MachineFunction::iterator mbbi = mf_.begin(),
 124                      mbbe = mf_.end(); mbbi != mbbe; ++mbbi) {
 125                 lastDef_.grow(mf_.getSSARegMap()->getLastVirtReg());
 126                 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
 127                 eliminateVirtRegsInMbb(*mbbi);
 128                 // clear map, dirty flag and last ref
 129                 p2vMap_.assign(p2vMap_.size(), 0);
 130                 dirty_.assign(dirty_.size(), false);
 131                 lastDef_.clear();
 132             }
 133         }
 134
 135     private:
 136         void vacateJustPhysReg(MachineBasicBlock& mbb,
 137                                MachineBasicBlock::iterator mii,
 138                                unsigned physReg) {
 139             unsigned virtReg = p2vMap_[physReg];
 140             if (dirty_[physReg] && vrm_.hasStackSlot(virtReg)) {
 141                 assert(lastDef_[virtReg] && "virtual register is mapped "
 142                        "to a register and but was not defined!");
 143                 MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
 144                 MachineBasicBlock::iterator nextLastRef = next(lastDef);
 145                 mri_.storeRegToStackSlot(*lastDef->getParent(),
 146                                          nextLastRef,
 147                                          physReg,
 148                                          vrm_.getStackSlot(virtReg),
 149                                          mri_.getRegClass(physReg));
 150                 ++numStores;
 151                 DEBUG(std::cerr << "added: ";
 152                       prior(nextLastRef)->print(std::cerr, tm_);
 153                       std::cerr << "after: ";
 154                       lastDef->print(std::cerr, tm_));
 155                 lastDef_[virtReg] = 0;
 156             }
 157             p2vMap_[physReg] = 0;
 158             dirty_[physReg] = false;
 159         }
 160
 161         void vacatePhysReg(MachineBasicBlock& mbb,
 162                            MachineBasicBlock::iterator mii,
 163                            unsigned physReg) {
 164             vacateJustPhysReg(mbb, mii, physReg);
 165             for (const unsigned* as = mri_.getAliasSet(physReg); *as; ++as)
 166                 vacateJustPhysReg(mbb, mii, *as);
 167         }
 168
 169         void handleUse(MachineBasicBlock& mbb,
 170                        MachineBasicBlock::iterator mii,
 171                        unsigned virtReg,
 172                        unsigned physReg) {
 173             // check if we are replacing a previous mapping
 174             if (p2vMap_[physReg] != virtReg) {
 175                 vacatePhysReg(mbb, mii, physReg);
 176                 p2vMap_[physReg] = virtReg;
 177                 // load if necessary
 178                 if (vrm_.hasStackSlot(virtReg)) {
 179                     mri_.loadRegFromStackSlot(mbb, mii, physReg,
 180                                               vrm_.getStackSlot(virtReg),
 181                                               mri_.getRegClass(physReg));
 182                     ++numLoads;
 183                     DEBUG(std::cerr << "added: ";
 184                           prior(mii)->print(std::cerr,tm_));
 185                     lastDef_[virtReg] = mii;
 186                 }
 187             }
 188         }
 189
 190         void handleDef(MachineBasicBlock& mbb,
 191                        MachineBasicBlock::iterator mii,
 192                        unsigned virtReg,
 193                        unsigned physReg) {
 194             // check if we are replacing a previous mapping
 195             if (p2vMap_[physReg] != virtReg)
 196                 vacatePhysReg(mbb, mii, physReg);
 197
 198             p2vMap_[physReg] = virtReg;
 199             dirty_[physReg] = true;
 200             lastDef_[virtReg] = mii;
 201         }
 202
 203         void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) {
 204             for (MachineBasicBlock::iterator mii = mbb.begin(),
 205                      mie = mbb.end(); mii != mie; ++mii) {
 206
 207                 // if we have references to memory operands make sure
 208                 // we clear all physical registers that may contain
 209                 // the value of the spilled virtual register
 210                 VirtRegMap::MI2VirtMap::const_iterator i, e;
 211                 for (tie(i, e) = vrm_.getFoldedVirts(mii); i != e; ++i) {
 212                     unsigned physReg = vrm_.getPhys(i->second);
 213                     if (physReg) vacateJustPhysReg(mbb, mii, physReg);
 214                 }
 215
 216                 // rewrite all used operands
 217                 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
 218                     MachineOperand& op = mii->getOperand(i);
 219                     if (op.isRegister() && op.getReg() && op.isUse() &&
 220                         MRegisterInfo::isVirtualRegister(op.getReg())) {
 221                         unsigned virtReg = op.getReg();
 222                         unsigned physReg = vrm_.getPhys(virtReg);
 223                         handleUse(mbb, mii, virtReg, physReg);
 224                         mii->SetMachineOperandReg(i, physReg);
 225                         // mark as dirty if this is def&use
 226                         if (op.isDef()) {
 227                             dirty_[physReg] = true;
 228                             lastDef_[virtReg] = mii;
 229                         }
 230                     }
 231                 }
 232
 233                 // spill implicit defs
 234                 const TargetInstrDescriptor& tid =tii_.get(mii->getOpcode());
 235                 for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
 236                     vacatePhysReg(mbb, mii, *id);
 237
 238                 // rewrite def operands (def&use was handled with the
 239                 // uses so don't check for those here)
 240                 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
 241                     MachineOperand& op = mii->getOperand(i);
 242                     if (op.isRegister() && op.getReg() && !op.isUse())
 243                         if (MRegisterInfo::isPhysicalRegister(op.getReg()))
 244                             vacatePhysReg(mbb, mii, op.getReg());
 245                         else {
 246                             unsigned physReg = vrm_.getPhys(op.getReg());
 247                             handleDef(mbb, mii, op.getReg(), physReg);
 248                             mii->SetMachineOperandReg(i, physReg);
 249                         }
 250                 }
 251
 252                 DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_));
 253             }
 254
 255             for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
 256                 vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i);
 257
 258         }
 259     };
 260 }
 261
 262
 263 void llvm::eliminateVirtRegs(MachineFunction& mf, const VirtRegMap& vrm)
 264 {
 265     Spiller(mf, vrm).eliminateVirtRegs();
 266 }