Home | History | Annotate | Download | only in CodeGen 
      1 //===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements the VirtRegMap class.
     11 //
     12 // It also contains implementations of the Spiller interface, which, given a
     13 // virtual register map and a machine function, eliminates all virtual
     14 // references by replacing them with physical register references - adding spill
     15 // code as necessary.
     16 //
     17 //===----------------------------------------------------------------------===//
     18 
     19 #include "llvm/CodeGen/VirtRegMap.h"
     20 #include "LiveDebugVariables.h"
     21 #include "llvm/ADT/STLExtras.h"
     22 #include "llvm/ADT/SparseSet.h"
     23 #include "llvm/ADT/Statistic.h"
     24 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
     25 #include "llvm/CodeGen/LiveStackAnalysis.h"
     26 #include "llvm/CodeGen/MachineFrameInfo.h"
     27 #include "llvm/CodeGen/MachineFunction.h"
     28 #include "llvm/CodeGen/MachineInstrBuilder.h"
     29 #include "llvm/CodeGen/MachineRegisterInfo.h"
     30 #include "llvm/CodeGen/Passes.h"
     31 #include "llvm/IR/Function.h"
     32 #include "llvm/Support/CommandLine.h"
     33 #include "llvm/Support/Compiler.h"
     34 #include "llvm/Support/Debug.h"
     35 #include "llvm/Support/raw_ostream.h"
     36 #include "llvm/Target/TargetInstrInfo.h"
     37 #include "llvm/Target/TargetMachine.h"
     38 #include "llvm/Target/TargetRegisterInfo.h"
     39 #include "llvm/Target/TargetSubtargetInfo.h"
     40 #include <algorithm>
     41 using namespace llvm;
     42 
     43 #define DEBUG_TYPE "regalloc"
     44 
     45 STATISTIC(NumSpillSlots, "Number of spill slots allocated");
     46 STATISTIC(NumIdCopies,   "Number of identity moves eliminated after rewriting");
     47 
     48 //===----------------------------------------------------------------------===//
     49 //  VirtRegMap implementation
     50 //===----------------------------------------------------------------------===//
     51 
     52 char VirtRegMap::ID = 0;
     53 
     54 INITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false)
     55 
     56 bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
     57   MRI = &mf.getRegInfo();
     58   TII = mf.getSubtarget().getInstrInfo();
     59   TRI = mf.getSubtarget().getRegisterInfo();
     60   MF = &mf;
     61 
     62   Virt2PhysMap.clear();
     63   Virt2StackSlotMap.clear();
     64   Virt2SplitMap.clear();
     65 
     66   grow();
     67   return false;
     68 }
     69 
     70 void VirtRegMap::grow() {
     71   unsigned NumRegs = MF->getRegInfo().getNumVirtRegs();
     72   Virt2PhysMap.resize(NumRegs);
     73   Virt2StackSlotMap.resize(NumRegs);
     74   Virt2SplitMap.resize(NumRegs);
     75 }
     76 
     77 unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) {
     78   int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(),
     79                                                       RC->getAlignment());
     80   ++NumSpillSlots;
     81   return SS;
     82 }
     83 
     84 bool VirtRegMap::hasPreferredPhys(unsigned VirtReg) {
     85   unsigned Hint = MRI->getSimpleHint(VirtReg);
     86   if (!Hint)
     87     return 0;
     88   if (TargetRegisterInfo::isVirtualRegister(Hint))
     89     Hint = getPhys(Hint);
     90   return getPhys(VirtReg) == Hint;
     91 }
     92 
     93 bool VirtRegMap::hasKnownPreference(unsigned VirtReg) {
     94   std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(VirtReg);
     95   if (TargetRegisterInfo::isPhysicalRegister(Hint.second))
     96     return true;
     97   if (TargetRegisterInfo::isVirtualRegister(Hint.second))
     98     return hasPhys(Hint.second);
     99   return false;
    100 }
    101 
    102 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
    103   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
    104   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
    105          "attempt to assign stack slot to already spilled register");
    106   const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg);
    107   return Virt2StackSlotMap[virtReg] = createSpillSlot(RC);
    108 }
    109 
    110 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
    111   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
    112   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
    113          "attempt to assign stack slot to already spilled register");
    114   assert((SS >= 0 ||
    115           (SS >= MF->getFrameInfo()->getObjectIndexBegin())) &&
    116          "illegal fixed frame index");
    117   Virt2StackSlotMap[virtReg] = SS;
    118 }
    119 
    120 void VirtRegMap::print(raw_ostream &OS, const Module*) const {
    121   OS << "********** REGISTER MAP **********\n";
    122   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
    123     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
    124     if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) {
    125       OS << '[' << PrintReg(Reg, TRI) << " -> "
    126          << PrintReg(Virt2PhysMap[Reg], TRI) << "] "
    127          << TRI->getRegClassName(MRI->getRegClass(Reg)) << "\n";
    128     }
    129   }
    130 
    131   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
    132     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
    133     if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) {
    134       OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg]
    135          << "] " << TRI->getRegClassName(MRI->getRegClass(Reg)) << "\n";
    136     }
    137   }
    138   OS << '\n';
    139 }
    140 
    141 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    142 void VirtRegMap::dump() const {
    143   print(dbgs());
    144 }
    145 #endif
    146 
    147 //===----------------------------------------------------------------------===//
    148 //                              VirtRegRewriter
    149 //===----------------------------------------------------------------------===//
    150 //
    151 // The VirtRegRewriter is the last of the register allocator passes.
    152 // It rewrites virtual registers to physical registers as specified in the
    153 // VirtRegMap analysis. It also updates live-in information on basic blocks
    154 // according to LiveIntervals.
    155 //
    156 namespace {
    157 class VirtRegRewriter : public MachineFunctionPass {
    158   MachineFunction *MF;
    159   const TargetMachine *TM;
    160   const TargetRegisterInfo *TRI;
    161   const TargetInstrInfo *TII;
    162   MachineRegisterInfo *MRI;
    163   SlotIndexes *Indexes;
    164   LiveIntervals *LIS;
    165   VirtRegMap *VRM;
    166 
    167   void rewrite();
    168   void addMBBLiveIns();
    169   bool readsUndefSubreg(const MachineOperand &MO) const;
    170   void addLiveInsForSubRanges(const LiveInterval &LI, unsigned PhysReg) const;
    171 
    172 public:
    173   static char ID;
    174   VirtRegRewriter() : MachineFunctionPass(ID) {}
    175 
    176   void getAnalysisUsage(AnalysisUsage &AU) const override;
    177 
    178   bool runOnMachineFunction(MachineFunction&) override;
    179 };
    180 } // end anonymous namespace
    181 
    182 char &llvm::VirtRegRewriterID = VirtRegRewriter::ID;
    183 
    184 INITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter",
    185                       "Virtual Register Rewriter", false, false)
    186 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
    187 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
    188 INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables)
    189 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
    190 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
    191 INITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter",
    192                     "Virtual Register Rewriter", false, false)
    193 
    194 char VirtRegRewriter::ID = 0;
    195 
    196 void VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const {
    197   AU.setPreservesCFG();
    198   AU.addRequired<LiveIntervals>();
    199   AU.addRequired<SlotIndexes>();
    200   AU.addPreserved<SlotIndexes>();
    201   AU.addRequired<LiveDebugVariables>();
    202   AU.addRequired<LiveStacks>();
    203   AU.addPreserved<LiveStacks>();
    204   AU.addRequired<VirtRegMap>();
    205   MachineFunctionPass::getAnalysisUsage(AU);
    206 }
    207 
    208 bool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) {
    209   MF = &fn;
    210   TM = &MF->getTarget();
    211   TRI = MF->getSubtarget().getRegisterInfo();
    212   TII = MF->getSubtarget().getInstrInfo();
    213   MRI = &MF->getRegInfo();
    214   Indexes = &getAnalysis<SlotIndexes>();
    215   LIS = &getAnalysis<LiveIntervals>();
    216   VRM = &getAnalysis<VirtRegMap>();
    217   DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n"
    218                << "********** Function: "
    219                << MF->getName() << '\n');
    220   DEBUG(VRM->dump());
    221 
    222   // Add kill flags while we still have virtual registers.
    223   LIS->addKillFlags(VRM);
    224 
    225   // Live-in lists on basic blocks are required for physregs.
    226   addMBBLiveIns();
    227 
    228   // Rewrite virtual registers.
    229   rewrite();
    230 
    231   // Write out new DBG_VALUE instructions.
    232   getAnalysis<LiveDebugVariables>().emitDebugValues(VRM);
    233 
    234   // All machine operands and other references to virtual registers have been
    235   // replaced. Remove the virtual registers and release all the transient data.
    236   VRM->clearAllVirt();
    237   MRI->clearVirtRegs();
    238   return true;
    239 }
    240 
    241 void VirtRegRewriter::addLiveInsForSubRanges(const LiveInterval &LI,
    242                                              unsigned PhysReg) const {
    243   assert(!LI.empty());
    244   assert(LI.hasSubRanges());
    245 
    246   typedef std::pair<const LiveInterval::SubRange *,
    247                     LiveInterval::const_iterator> SubRangeIteratorPair;
    248   SmallVector<SubRangeIteratorPair, 4> SubRanges;
    249   SlotIndex First;
    250   SlotIndex Last;
    251   for (const LiveInterval::SubRange &SR : LI.subranges()) {
    252     SubRanges.push_back(std::make_pair(&SR, SR.begin()));
    253     if (!First.isValid() || SR.segments.front().start < First)
    254       First = SR.segments.front().start;
    255     if (!Last.isValid() || SR.segments.back().end > Last)
    256       Last = SR.segments.back().end;
    257   }
    258 
    259   // Check all mbb start positions between First and Last while
    260   // simulatenously advancing an iterator for each subrange.
    261   for (SlotIndexes::MBBIndexIterator MBBI = Indexes->findMBBIndex(First);
    262        MBBI != Indexes->MBBIndexEnd() && MBBI->first <= Last; ++MBBI) {
    263     SlotIndex MBBBegin = MBBI->first;
    264     // Advance all subrange iterators so that their end position is just
    265     // behind MBBBegin (or the iterator is at the end).
    266     LaneBitmask LaneMask = 0;
    267     for (auto &RangeIterPair : SubRanges) {
    268       const LiveInterval::SubRange *SR = RangeIterPair.first;
    269       LiveInterval::const_iterator &SRI = RangeIterPair.second;
    270       while (SRI != SR->end() && SRI->end <= MBBBegin)
    271         ++SRI;
    272       if (SRI == SR->end())
    273         continue;
    274       if (SRI->start <= MBBBegin)
    275         LaneMask |= SR->LaneMask;
    276     }
    277     if (LaneMask == 0)
    278       continue;
    279     MachineBasicBlock *MBB = MBBI->second;
    280     MBB->addLiveIn(PhysReg, LaneMask);
    281   }
    282 }
    283 
    284 // Compute MBB live-in lists from virtual register live ranges and their
    285 // assignments.
    286 void VirtRegRewriter::addMBBLiveIns() {
    287   for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) {
    288     unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx);
    289     if (MRI->reg_nodbg_empty(VirtReg))
    290       continue;
    291     LiveInterval &LI = LIS->getInterval(VirtReg);
    292     if (LI.empty() || LIS->intervalIsInOneMBB(LI))
    293       continue;
    294     // This is a virtual register that is live across basic blocks. Its
    295     // assigned PhysReg must be marked as live-in to those blocks.
    296     unsigned PhysReg = VRM->getPhys(VirtReg);
    297     assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register.");
    298 
    299     if (LI.hasSubRanges()) {
    300       addLiveInsForSubRanges(LI, PhysReg);
    301     } else {
    302       // Go over MBB begin positions and see if we have segments covering them.
    303       // The following works because segments and the MBBIndex list are both
    304       // sorted by slot indexes.
    305       SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin();
    306       for (const auto &Seg : LI) {
    307         I = Indexes->advanceMBBIndex(I, Seg.start);
    308         for (; I != Indexes->MBBIndexEnd() && I->first < Seg.end; ++I) {
    309           MachineBasicBlock *MBB = I->second;
    310           MBB->addLiveIn(PhysReg);
    311         }
    312       }
    313     }
    314   }
    315 
    316   // Sort and unique MBB LiveIns as we've not checked if SubReg/PhysReg were in
    317   // each MBB's LiveIns set before calling addLiveIn on them.
    318   for (MachineBasicBlock &MBB : *MF)
    319     MBB.sortUniqueLiveIns();
    320 }
    321 
    322 /// Returns true if the given machine operand \p MO only reads undefined lanes.
    323 /// The function only works for use operands with a subregister set.
    324 bool VirtRegRewriter::readsUndefSubreg(const MachineOperand &MO) const {
    325   // Shortcut if the operand is already marked undef.
    326   if (MO.isUndef())
    327     return true;
    328 
    329   unsigned Reg = MO.getReg();
    330   const LiveInterval &LI = LIS->getInterval(Reg);
    331   const MachineInstr &MI = *MO.getParent();
    332   SlotIndex BaseIndex = LIS->getInstructionIndex(&MI);
    333   // This code is only meant to handle reading undefined subregisters which
    334   // we couldn't properly detect before.
    335   assert(LI.liveAt(BaseIndex) &&
    336          "Reads of completely dead register should be marked undef already");
    337   unsigned SubRegIdx = MO.getSubReg();
    338   LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(SubRegIdx);
    339   // See if any of the relevant subregister liveranges is defined at this point.
    340   for (const LiveInterval::SubRange &SR : LI.subranges()) {
    341     if ((SR.LaneMask & UseMask) != 0 && SR.liveAt(BaseIndex))
    342       return false;
    343   }
    344   return true;
    345 }
    346 
    347 void VirtRegRewriter::rewrite() {
    348   bool NoSubRegLiveness = !MRI->subRegLivenessEnabled();
    349   SmallVector<unsigned, 8> SuperDeads;
    350   SmallVector<unsigned, 8> SuperDefs;
    351   SmallVector<unsigned, 8> SuperKills;
    352 
    353   for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
    354        MBBI != MBBE; ++MBBI) {
    355     DEBUG(MBBI->print(dbgs(), Indexes));
    356     for (MachineBasicBlock::instr_iterator
    357            MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) {
    358       MachineInstr *MI = &*MII;
    359       ++MII;
    360 
    361       for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
    362            MOE = MI->operands_end(); MOI != MOE; ++MOI) {
    363         MachineOperand &MO = *MOI;
    364 
    365         // Make sure MRI knows about registers clobbered by regmasks.
    366         if (MO.isRegMask())
    367           MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
    368 
    369         if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
    370           continue;
    371         unsigned VirtReg = MO.getReg();
    372         unsigned PhysReg = VRM->getPhys(VirtReg);
    373         assert(PhysReg != VirtRegMap::NO_PHYS_REG &&
    374                "Instruction uses unmapped VirtReg");
    375         assert(!MRI->isReserved(PhysReg) && "Reserved register assignment");
    376 
    377         // Preserve semantics of sub-register operands.
    378         unsigned SubReg = MO.getSubReg();
    379         if (SubReg != 0) {
    380           if (NoSubRegLiveness) {
    381             // A virtual register kill refers to the whole register, so we may
    382             // have to add <imp-use,kill> operands for the super-register.  A
    383             // partial redef always kills and redefines the super-register.
    384             if (MO.readsReg() && (MO.isDef() || MO.isKill()))
    385               SuperKills.push_back(PhysReg);
    386 
    387             if (MO.isDef()) {
    388               // Also add implicit defs for the super-register.
    389               if (MO.isDead())
    390                 SuperDeads.push_back(PhysReg);
    391               else
    392                 SuperDefs.push_back(PhysReg);
    393             }
    394           } else {
    395             if (MO.isUse()) {
    396               if (readsUndefSubreg(MO))
    397                 // We need to add an <undef> flag if the subregister is
    398                 // completely undefined (and we are not adding super-register
    399                 // defs).
    400                 MO.setIsUndef(true);
    401             } else if (!MO.isDead()) {
    402               assert(MO.isDef());
    403             }
    404           }
    405 
    406           // The <def,undef> flag only makes sense for sub-register defs, and
    407           // we are substituting a full physreg.  An <imp-use,kill> operand
    408           // from the SuperKills list will represent the partial read of the
    409           // super-register.
    410           if (MO.isDef())
    411             MO.setIsUndef(false);
    412 
    413           // PhysReg operands cannot have subregister indexes.
    414           PhysReg = TRI->getSubReg(PhysReg, SubReg);
    415           assert(PhysReg && "Invalid SubReg for physical register");
    416           MO.setSubReg(0);
    417         }
    418         // Rewrite. Note we could have used MachineOperand::substPhysReg(), but
    419         // we need the inlining here.
    420         MO.setReg(PhysReg);
    421       }
    422 
    423       // Add any missing super-register kills after rewriting the whole
    424       // instruction.
    425       while (!SuperKills.empty())
    426         MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true);
    427 
    428       while (!SuperDeads.empty())
    429         MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true);
    430 
    431       while (!SuperDefs.empty())
    432         MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI);
    433 
    434       DEBUG(dbgs() << "> " << *MI);
    435 
    436       // Finally, remove any identity copies.
    437       if (MI->isIdentityCopy()) {
    438         ++NumIdCopies;
    439         DEBUG(dbgs() << "Deleting identity copy.\n");
    440         if (Indexes)
    441           Indexes->removeMachineInstrFromMaps(MI);
    442         // It's safe to erase MI because MII has already been incremented.
    443         MI->eraseFromParent();
    444       }
    445     }
    446   }
    447 }
    448 
    449