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