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