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 #define DEBUG_TYPE "regalloc"
     20 #include "VirtRegMap.h"
     21 #include "llvm/Function.h"
     22 #include "llvm/CodeGen/MachineFrameInfo.h"
     23 #include "llvm/CodeGen/MachineFunction.h"
     24 #include "llvm/CodeGen/MachineInstrBuilder.h"
     25 #include "llvm/CodeGen/MachineRegisterInfo.h"
     26 #include "llvm/CodeGen/SlotIndexes.h"
     27 #include "llvm/Target/TargetMachine.h"
     28 #include "llvm/Target/TargetInstrInfo.h"
     29 #include "llvm/Target/TargetRegisterInfo.h"
     30 #include "llvm/Support/CommandLine.h"
     31 #include "llvm/Support/Compiler.h"
     32 #include "llvm/Support/Debug.h"
     33 #include "llvm/Support/raw_ostream.h"
     34 #include "llvm/ADT/Statistic.h"
     35 #include "llvm/ADT/STLExtras.h"
     36 #include <algorithm>
     37 using namespace llvm;
     38 
     39 STATISTIC(NumSpillSlots, "Number of spill slots allocated");
     40 STATISTIC(NumIdCopies,   "Number of identity moves eliminated after rewriting");
     41 
     42 //===----------------------------------------------------------------------===//
     43 //  VirtRegMap implementation
     44 //===----------------------------------------------------------------------===//
     45 
     46 char VirtRegMap::ID = 0;
     47 
     48 INITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false)
     49 
     50 bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
     51   MRI = &mf.getRegInfo();
     52   TII = mf.getTarget().getInstrInfo();
     53   TRI = mf.getTarget().getRegisterInfo();
     54   MF = &mf;
     55 
     56   Virt2PhysMap.clear();
     57   Virt2StackSlotMap.clear();
     58   Virt2SplitMap.clear();
     59 
     60   grow();
     61   return false;
     62 }
     63 
     64 void VirtRegMap::grow() {
     65   unsigned NumRegs = MF->getRegInfo().getNumVirtRegs();
     66   Virt2PhysMap.resize(NumRegs);
     67   Virt2StackSlotMap.resize(NumRegs);
     68   Virt2SplitMap.resize(NumRegs);
     69 }
     70 
     71 unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) {
     72   int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(),
     73                                                       RC->getAlignment());
     74   ++NumSpillSlots;
     75   return SS;
     76 }
     77 
     78 unsigned VirtRegMap::getRegAllocPref(unsigned virtReg) {
     79   std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(virtReg);
     80   unsigned physReg = Hint.second;
     81   if (TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg))
     82     physReg = getPhys(physReg);
     83   if (Hint.first == 0)
     84     return (TargetRegisterInfo::isPhysicalRegister(physReg))
     85       ? physReg : 0;
     86   return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF);
     87 }
     88 
     89 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
     90   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
     91   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
     92          "attempt to assign stack slot to already spilled register");
     93   const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg);
     94   return Virt2StackSlotMap[virtReg] = createSpillSlot(RC);
     95 }
     96 
     97 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
     98   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
     99   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
    100          "attempt to assign stack slot to already spilled register");
    101   assert((SS >= 0 ||
    102           (SS >= MF->getFrameInfo()->getObjectIndexBegin())) &&
    103          "illegal fixed frame index");
    104   Virt2StackSlotMap[virtReg] = SS;
    105 }
    106 
    107 void VirtRegMap::rewrite(SlotIndexes *Indexes) {
    108   DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n"
    109                << "********** Function: "
    110                << MF->getFunction()->getName() << '\n');
    111   DEBUG(dump());
    112   SmallVector<unsigned, 8> SuperDeads;
    113   SmallVector<unsigned, 8> SuperDefs;
    114   SmallVector<unsigned, 8> SuperKills;
    115 #ifndef NDEBUG
    116   BitVector Reserved = TRI->getReservedRegs(*MF);
    117 #endif
    118 
    119   for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
    120        MBBI != MBBE; ++MBBI) {
    121     DEBUG(MBBI->print(dbgs(), Indexes));
    122     for (MachineBasicBlock::instr_iterator
    123            MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) {
    124       MachineInstr *MI = MII;
    125       ++MII;
    126 
    127       for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
    128            MOE = MI->operands_end(); MOI != MOE; ++MOI) {
    129         MachineOperand &MO = *MOI;
    130 
    131         // Make sure MRI knows about registers clobbered by regmasks.
    132         if (MO.isRegMask())
    133           MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
    134 
    135         if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
    136           continue;
    137         unsigned VirtReg = MO.getReg();
    138         unsigned PhysReg = getPhys(VirtReg);
    139         assert(PhysReg != NO_PHYS_REG && "Instruction uses unmapped VirtReg");
    140         assert(!Reserved.test(PhysReg) && "Reserved register assignment");
    141 
    142         // Preserve semantics of sub-register operands.
    143         if (MO.getSubReg()) {
    144           // A virtual register kill refers to the whole register, so we may
    145           // have to add <imp-use,kill> operands for the super-register.  A
    146           // partial redef always kills and redefines the super-register.
    147           if (MO.readsReg() && (MO.isDef() || MO.isKill()))
    148             SuperKills.push_back(PhysReg);
    149 
    150           if (MO.isDef()) {
    151             // The <def,undef> flag only makes sense for sub-register defs, and
    152             // we are substituting a full physreg.  An <imp-use,kill> operand
    153             // from the SuperKills list will represent the partial read of the
    154             // super-register.
    155             MO.setIsUndef(false);
    156 
    157             // Also add implicit defs for the super-register.
    158             if (MO.isDead())
    159               SuperDeads.push_back(PhysReg);
    160             else
    161               SuperDefs.push_back(PhysReg);
    162           }
    163 
    164           // PhysReg operands cannot have subregister indexes.
    165           PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg());
    166           assert(PhysReg && "Invalid SubReg for physical register");
    167           MO.setSubReg(0);
    168         }
    169         // Rewrite. Note we could have used MachineOperand::substPhysReg(), but
    170         // we need the inlining here.
    171         MO.setReg(PhysReg);
    172       }
    173 
    174       // Add any missing super-register kills after rewriting the whole
    175       // instruction.
    176       while (!SuperKills.empty())
    177         MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true);
    178 
    179       while (!SuperDeads.empty())
    180         MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true);
    181 
    182       while (!SuperDefs.empty())
    183         MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI);
    184 
    185       DEBUG(dbgs() << "> " << *MI);
    186 
    187       // Finally, remove any identity copies.
    188       if (MI->isIdentityCopy()) {
    189         ++NumIdCopies;
    190         if (MI->getNumOperands() == 2) {
    191           DEBUG(dbgs() << "Deleting identity copy.\n");
    192           if (Indexes)
    193             Indexes->removeMachineInstrFromMaps(MI);
    194           // It's safe to erase MI because MII has already been incremented.
    195           MI->eraseFromParent();
    196         } else {
    197           // Transform identity copy to a KILL to deal with subregisters.
    198           MI->setDesc(TII->get(TargetOpcode::KILL));
    199           DEBUG(dbgs() << "Identity copy: " << *MI);
    200         }
    201       }
    202     }
    203   }
    204 
    205   // Tell MRI about physical registers in use.
    206   for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg)
    207     if (!MRI->reg_nodbg_empty(Reg))
    208       MRI->setPhysRegUsed(Reg);
    209 }
    210 
    211 void VirtRegMap::print(raw_ostream &OS, const Module* M) const {
    212   const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
    213   const MachineRegisterInfo &MRI = MF->getRegInfo();
    214 
    215   OS << "********** REGISTER MAP **********\n";
    216   for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
    217     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
    218     if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) {
    219       OS << '[' << PrintReg(Reg, TRI) << " -> "
    220          << PrintReg(Virt2PhysMap[Reg], TRI) << "] "
    221          << MRI.getRegClass(Reg)->getName() << "\n";
    222     }
    223   }
    224 
    225   for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
    226     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
    227     if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) {
    228       OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg]
    229          << "] " << MRI.getRegClass(Reg)->getName() << "\n";
    230     }
    231   }
    232   OS << '\n';
    233 }
    234 
    235 void VirtRegMap::dump() const {
    236   print(dbgs());
    237 }
    238