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