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