Home | History | Annotate | Download | only in CodeGen 
      1 //===-- lib/CodeGen/MachineInstrBundle.cpp --------------------------------===//
      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 #include "llvm/CodeGen/MachineInstrBundle.h"
     11 #include "llvm/ADT/SmallSet.h"
     12 #include "llvm/ADT/SmallVector.h"
     13 #include "llvm/CodeGen/MachineFunctionPass.h"
     14 #include "llvm/CodeGen/MachineInstrBuilder.h"
     15 #include "llvm/CodeGen/Passes.h"
     16 #include "llvm/Target/TargetInstrInfo.h"
     17 #include "llvm/Target/TargetMachine.h"
     18 #include "llvm/Target/TargetRegisterInfo.h"
     19 using namespace llvm;
     20 
     21 namespace {
     22   class UnpackMachineBundles : public MachineFunctionPass {
     23   public:
     24     static char ID; // Pass identification
     25     UnpackMachineBundles() : MachineFunctionPass(ID) {
     26       initializeUnpackMachineBundlesPass(*PassRegistry::getPassRegistry());
     27     }
     28 
     29     virtual bool runOnMachineFunction(MachineFunction &MF);
     30   };
     31 } // end anonymous namespace
     32 
     33 char UnpackMachineBundles::ID = 0;
     34 char &llvm::UnpackMachineBundlesID = UnpackMachineBundles::ID;
     35 INITIALIZE_PASS(UnpackMachineBundles, "unpack-mi-bundles",
     36                 "Unpack machine instruction bundles", false, false)
     37 
     38 bool UnpackMachineBundles::runOnMachineFunction(MachineFunction &MF) {
     39   bool Changed = false;
     40   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
     41     MachineBasicBlock *MBB = &*I;
     42 
     43     for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
     44            MIE = MBB->instr_end(); MII != MIE; ) {
     45       MachineInstr *MI = &*MII;
     46 
     47       // Remove BUNDLE instruction and the InsideBundle flags from bundled
     48       // instructions.
     49       if (MI->isBundle()) {
     50         while (++MII != MIE && MII->isBundledWithPred()) {
     51           MII->unbundleFromPred();
     52           for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
     53             MachineOperand &MO = MII->getOperand(i);
     54             if (MO.isReg() && MO.isInternalRead())
     55               MO.setIsInternalRead(false);
     56           }
     57         }
     58         MI->eraseFromParent();
     59 
     60         Changed = true;
     61         continue;
     62       }
     63 
     64       ++MII;
     65     }
     66   }
     67 
     68   return Changed;
     69 }
     70 
     71 
     72 namespace {
     73   class FinalizeMachineBundles : public MachineFunctionPass {
     74   public:
     75     static char ID; // Pass identification
     76     FinalizeMachineBundles() : MachineFunctionPass(ID) {
     77       initializeFinalizeMachineBundlesPass(*PassRegistry::getPassRegistry());
     78     }
     79 
     80     virtual bool runOnMachineFunction(MachineFunction &MF);
     81   };
     82 } // end anonymous namespace
     83 
     84 char FinalizeMachineBundles::ID = 0;
     85 char &llvm::FinalizeMachineBundlesID = FinalizeMachineBundles::ID;
     86 INITIALIZE_PASS(FinalizeMachineBundles, "finalize-mi-bundles",
     87                 "Finalize machine instruction bundles", false, false)
     88 
     89 bool FinalizeMachineBundles::runOnMachineFunction(MachineFunction &MF) {
     90   return llvm::finalizeBundles(MF);
     91 }
     92 
     93 
     94 /// finalizeBundle - Finalize a machine instruction bundle which includes
     95 /// a sequence of instructions starting from FirstMI to LastMI (exclusive).
     96 /// This routine adds a BUNDLE instruction to represent the bundle, it adds
     97 /// IsInternalRead markers to MachineOperands which are defined inside the
     98 /// bundle, and it copies externally visible defs and uses to the BUNDLE
     99 /// instruction.
    100 void llvm::finalizeBundle(MachineBasicBlock &MBB,
    101                           MachineBasicBlock::instr_iterator FirstMI,
    102                           MachineBasicBlock::instr_iterator LastMI) {
    103   assert(FirstMI != LastMI && "Empty bundle?");
    104   MIBundleBuilder Bundle(MBB, FirstMI, LastMI);
    105 
    106   const TargetMachine &TM = MBB.getParent()->getTarget();
    107   const TargetInstrInfo *TII = TM.getInstrInfo();
    108   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
    109 
    110   MachineInstrBuilder MIB = BuildMI(*MBB.getParent(), FirstMI->getDebugLoc(),
    111                                     TII->get(TargetOpcode::BUNDLE));
    112   Bundle.prepend(MIB);
    113 
    114   SmallVector<unsigned, 32> LocalDefs;
    115   SmallSet<unsigned, 32> LocalDefSet;
    116   SmallSet<unsigned, 8> DeadDefSet;
    117   SmallSet<unsigned, 16> KilledDefSet;
    118   SmallVector<unsigned, 8> ExternUses;
    119   SmallSet<unsigned, 8> ExternUseSet;
    120   SmallSet<unsigned, 8> KilledUseSet;
    121   SmallSet<unsigned, 8> UndefUseSet;
    122   SmallVector<MachineOperand*, 4> Defs;
    123   for (; FirstMI != LastMI; ++FirstMI) {
    124     for (unsigned i = 0, e = FirstMI->getNumOperands(); i != e; ++i) {
    125       MachineOperand &MO = FirstMI->getOperand(i);
    126       if (!MO.isReg())
    127         continue;
    128       if (MO.isDef()) {
    129         Defs.push_back(&MO);
    130         continue;
    131       }
    132 
    133       unsigned Reg = MO.getReg();
    134       if (!Reg)
    135         continue;
    136       assert(TargetRegisterInfo::isPhysicalRegister(Reg));
    137       if (LocalDefSet.count(Reg)) {
    138         MO.setIsInternalRead();
    139         if (MO.isKill())
    140           // Internal def is now killed.
    141           KilledDefSet.insert(Reg);
    142       } else {
    143         if (ExternUseSet.insert(Reg)) {
    144           ExternUses.push_back(Reg);
    145           if (MO.isUndef())
    146             UndefUseSet.insert(Reg);
    147         }
    148         if (MO.isKill())
    149           // External def is now killed.
    150           KilledUseSet.insert(Reg);
    151       }
    152     }
    153 
    154     for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
    155       MachineOperand &MO = *Defs[i];
    156       unsigned Reg = MO.getReg();
    157       if (!Reg)
    158         continue;
    159 
    160       if (LocalDefSet.insert(Reg)) {
    161         LocalDefs.push_back(Reg);
    162         if (MO.isDead()) {
    163           DeadDefSet.insert(Reg);
    164         }
    165       } else {
    166         // Re-defined inside the bundle, it's no longer killed.
    167         KilledDefSet.erase(Reg);
    168         if (!MO.isDead())
    169           // Previously defined but dead.
    170           DeadDefSet.erase(Reg);
    171       }
    172 
    173       if (!MO.isDead()) {
    174         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
    175           unsigned SubReg = *SubRegs;
    176           if (LocalDefSet.insert(SubReg))
    177             LocalDefs.push_back(SubReg);
    178         }
    179       }
    180     }
    181 
    182     Defs.clear();
    183   }
    184 
    185   SmallSet<unsigned, 32> Added;
    186   for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
    187     unsigned Reg = LocalDefs[i];
    188     if (Added.insert(Reg)) {
    189       // If it's not live beyond end of the bundle, mark it dead.
    190       bool isDead = DeadDefSet.count(Reg) || KilledDefSet.count(Reg);
    191       MIB.addReg(Reg, getDefRegState(true) | getDeadRegState(isDead) |
    192                  getImplRegState(true));
    193     }
    194   }
    195 
    196   for (unsigned i = 0, e = ExternUses.size(); i != e; ++i) {
    197     unsigned Reg = ExternUses[i];
    198     bool isKill = KilledUseSet.count(Reg);
    199     bool isUndef = UndefUseSet.count(Reg);
    200     MIB.addReg(Reg, getKillRegState(isKill) | getUndefRegState(isUndef) |
    201                getImplRegState(true));
    202   }
    203 }
    204 
    205 /// finalizeBundle - Same functionality as the previous finalizeBundle except
    206 /// the last instruction in the bundle is not provided as an input. This is
    207 /// used in cases where bundles are pre-determined by marking instructions
    208 /// with 'InsideBundle' marker. It returns the MBB instruction iterator that
    209 /// points to the end of the bundle.
    210 MachineBasicBlock::instr_iterator
    211 llvm::finalizeBundle(MachineBasicBlock &MBB,
    212                      MachineBasicBlock::instr_iterator FirstMI) {
    213   MachineBasicBlock::instr_iterator E = MBB.instr_end();
    214   MachineBasicBlock::instr_iterator LastMI = llvm::next(FirstMI);
    215   while (LastMI != E && LastMI->isInsideBundle())
    216     ++LastMI;
    217   finalizeBundle(MBB, FirstMI, LastMI);
    218   return LastMI;
    219 }
    220 
    221 /// finalizeBundles - Finalize instruction bundles in the specified
    222 /// MachineFunction. Return true if any bundles are finalized.
    223 bool llvm::finalizeBundles(MachineFunction &MF) {
    224   bool Changed = false;
    225   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
    226     MachineBasicBlock &MBB = *I;
    227     MachineBasicBlock::instr_iterator MII = MBB.instr_begin();
    228     MachineBasicBlock::instr_iterator MIE = MBB.instr_end();
    229     if (MII == MIE)
    230       continue;
    231     assert(!MII->isInsideBundle() &&
    232            "First instr cannot be inside bundle before finalization!");
    233 
    234     for (++MII; MII != MIE; ) {
    235       if (!MII->isInsideBundle())
    236         ++MII;
    237       else {
    238         MII = finalizeBundle(MBB, llvm::prior(MII));
    239         Changed = true;
    240       }
    241     }
    242   }
    243 
    244   return Changed;
    245 }
    246 
    247 //===----------------------------------------------------------------------===//
    248 // MachineOperand iterator
    249 //===----------------------------------------------------------------------===//
    250 
    251 MachineOperandIteratorBase::VirtRegInfo
    252 MachineOperandIteratorBase::analyzeVirtReg(unsigned Reg,
    253                     SmallVectorImpl<std::pair<MachineInstr*, unsigned> > *Ops) {
    254   VirtRegInfo RI = { false, false, false };
    255   for(; isValid(); ++*this) {
    256     MachineOperand &MO = deref();
    257     if (!MO.isReg() || MO.getReg() != Reg)
    258       continue;
    259 
    260     // Remember each (MI, OpNo) that refers to Reg.
    261     if (Ops)
    262       Ops->push_back(std::make_pair(MO.getParent(), getOperandNo()));
    263 
    264     // Both defs and uses can read virtual registers.
    265     if (MO.readsReg()) {
    266       RI.Reads = true;
    267       if (MO.isDef())
    268         RI.Tied = true;
    269     }
    270 
    271     // Only defs can write.
    272     if (MO.isDef())
    273       RI.Writes = true;
    274     else if (!RI.Tied && MO.getParent()->isRegTiedToDefOperand(getOperandNo()))
    275       RI.Tied = true;
    276   }
    277   return RI;
    278 }
    279 
    280 MachineOperandIteratorBase::PhysRegInfo
    281 MachineOperandIteratorBase::analyzePhysReg(unsigned Reg,
    282                                            const TargetRegisterInfo *TRI) {
    283   bool AllDefsDead = true;
    284   PhysRegInfo PRI = {false, false, false, false, false, false};
    285 
    286   assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
    287          "analyzePhysReg not given a physical register!");
    288   for (; isValid(); ++*this) {
    289     MachineOperand &MO = deref();
    290 
    291     if (MO.isRegMask() && MO.clobbersPhysReg(Reg))
    292       PRI.Clobbers = true;    // Regmask clobbers Reg.
    293 
    294     if (!MO.isReg())
    295       continue;
    296 
    297     unsigned MOReg = MO.getReg();
    298     if (!MOReg || !TargetRegisterInfo::isPhysicalRegister(MOReg))
    299       continue;
    300 
    301     bool IsRegOrSuperReg = MOReg == Reg || TRI->isSubRegister(MOReg, Reg);
    302     bool IsRegOrOverlapping = MOReg == Reg || TRI->regsOverlap(MOReg, Reg);
    303 
    304     if (IsRegOrSuperReg && MO.readsReg()) {
    305       // Reg or a super-reg is read, and perhaps killed also.
    306       PRI.Reads = true;
    307       PRI.Kills = MO.isKill();
    308     }
    309 
    310     if (IsRegOrOverlapping && MO.readsReg()) {
    311       PRI.ReadsOverlap = true;// Reg or an overlapping register is read.
    312     }
    313 
    314     if (!MO.isDef())
    315       continue;
    316 
    317     if (IsRegOrSuperReg) {
    318       PRI.Defines = true;     // Reg or a super-register is defined.
    319       if (!MO.isDead())
    320         AllDefsDead = false;
    321     }
    322     if (IsRegOrOverlapping)
    323       PRI.Clobbers = true;    // Reg or an overlapping reg is defined.
    324   }
    325 
    326   if (AllDefsDead && PRI.Defines)
    327     PRI.DefinesDead = true;   // Reg or super-register was defined and was dead.
    328 
    329   return PRI;
    330 }
    331