1234285Sdim//===-- lib/CodeGen/MachineInstrBundle.cpp --------------------------------===// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim 10234285Sdim#include "llvm/CodeGen/MachineInstrBundle.h" 11249423Sdim#include "llvm/ADT/SmallSet.h" 12249423Sdim#include "llvm/ADT/SmallVector.h" 13249423Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 14234285Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 15234285Sdim#include "llvm/CodeGen/Passes.h" 16234285Sdim#include "llvm/Target/TargetInstrInfo.h" 17234285Sdim#include "llvm/Target/TargetMachine.h" 18234285Sdim#include "llvm/Target/TargetRegisterInfo.h" 19234285Sdimusing namespace llvm; 20234285Sdim 21234285Sdimnamespace { 22234285Sdim class UnpackMachineBundles : public MachineFunctionPass { 23234285Sdim public: 24234285Sdim static char ID; // Pass identification 25234285Sdim UnpackMachineBundles() : MachineFunctionPass(ID) { 26234285Sdim initializeUnpackMachineBundlesPass(*PassRegistry::getPassRegistry()); 27234285Sdim } 28234285Sdim 29234285Sdim virtual bool runOnMachineFunction(MachineFunction &MF); 30234285Sdim }; 31234285Sdim} // end anonymous namespace 32234285Sdim 33234285Sdimchar UnpackMachineBundles::ID = 0; 34234285Sdimchar &llvm::UnpackMachineBundlesID = UnpackMachineBundles::ID; 35234285SdimINITIALIZE_PASS(UnpackMachineBundles, "unpack-mi-bundles", 36234285Sdim "Unpack machine instruction bundles", false, false) 37234285Sdim 38234285Sdimbool UnpackMachineBundles::runOnMachineFunction(MachineFunction &MF) { 39234285Sdim bool Changed = false; 40234285Sdim for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 41234285Sdim MachineBasicBlock *MBB = &*I; 42234285Sdim 43234285Sdim for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(), 44234285Sdim MIE = MBB->instr_end(); MII != MIE; ) { 45234285Sdim MachineInstr *MI = &*MII; 46234285Sdim 47234285Sdim // Remove BUNDLE instruction and the InsideBundle flags from bundled 48234285Sdim // instructions. 49234285Sdim if (MI->isBundle()) { 50249423Sdim while (++MII != MIE && MII->isBundledWithPred()) { 51249423Sdim MII->unbundleFromPred(); 52234285Sdim for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) { 53234285Sdim MachineOperand &MO = MII->getOperand(i); 54234285Sdim if (MO.isReg() && MO.isInternalRead()) 55234285Sdim MO.setIsInternalRead(false); 56234285Sdim } 57234285Sdim } 58234285Sdim MI->eraseFromParent(); 59234285Sdim 60234285Sdim Changed = true; 61234285Sdim continue; 62234285Sdim } 63234285Sdim 64234285Sdim ++MII; 65234285Sdim } 66234285Sdim } 67234285Sdim 68234285Sdim return Changed; 69234285Sdim} 70234285Sdim 71234285Sdim 72234285Sdimnamespace { 73234285Sdim class FinalizeMachineBundles : public MachineFunctionPass { 74234285Sdim public: 75234285Sdim static char ID; // Pass identification 76234285Sdim FinalizeMachineBundles() : MachineFunctionPass(ID) { 77234285Sdim initializeFinalizeMachineBundlesPass(*PassRegistry::getPassRegistry()); 78234285Sdim } 79234285Sdim 80234285Sdim virtual bool runOnMachineFunction(MachineFunction &MF); 81234285Sdim }; 82234285Sdim} // end anonymous namespace 83234285Sdim 84234285Sdimchar FinalizeMachineBundles::ID = 0; 85234285Sdimchar &llvm::FinalizeMachineBundlesID = FinalizeMachineBundles::ID; 86234285SdimINITIALIZE_PASS(FinalizeMachineBundles, "finalize-mi-bundles", 87234285Sdim "Finalize machine instruction bundles", false, false) 88234285Sdim 89234285Sdimbool FinalizeMachineBundles::runOnMachineFunction(MachineFunction &MF) { 90234285Sdim return llvm::finalizeBundles(MF); 91234285Sdim} 92234285Sdim 93234285Sdim 94234285Sdim/// finalizeBundle - Finalize a machine instruction bundle which includes 95234285Sdim/// a sequence of instructions starting from FirstMI to LastMI (exclusive). 96234285Sdim/// This routine adds a BUNDLE instruction to represent the bundle, it adds 97234285Sdim/// IsInternalRead markers to MachineOperands which are defined inside the 98234285Sdim/// bundle, and it copies externally visible defs and uses to the BUNDLE 99234285Sdim/// instruction. 100234285Sdimvoid llvm::finalizeBundle(MachineBasicBlock &MBB, 101234285Sdim MachineBasicBlock::instr_iterator FirstMI, 102234285Sdim MachineBasicBlock::instr_iterator LastMI) { 103234285Sdim assert(FirstMI != LastMI && "Empty bundle?"); 104249423Sdim MIBundleBuilder Bundle(MBB, FirstMI, LastMI); 105234285Sdim 106234285Sdim const TargetMachine &TM = MBB.getParent()->getTarget(); 107234285Sdim const TargetInstrInfo *TII = TM.getInstrInfo(); 108234285Sdim const TargetRegisterInfo *TRI = TM.getRegisterInfo(); 109234285Sdim 110249423Sdim MachineInstrBuilder MIB = BuildMI(*MBB.getParent(), FirstMI->getDebugLoc(), 111234285Sdim TII->get(TargetOpcode::BUNDLE)); 112249423Sdim Bundle.prepend(MIB); 113234285Sdim 114243830Sdim SmallVector<unsigned, 32> LocalDefs; 115243830Sdim SmallSet<unsigned, 32> LocalDefSet; 116234285Sdim SmallSet<unsigned, 8> DeadDefSet; 117243830Sdim SmallSet<unsigned, 16> KilledDefSet; 118234285Sdim SmallVector<unsigned, 8> ExternUses; 119234285Sdim SmallSet<unsigned, 8> ExternUseSet; 120234285Sdim SmallSet<unsigned, 8> KilledUseSet; 121234285Sdim SmallSet<unsigned, 8> UndefUseSet; 122234285Sdim SmallVector<MachineOperand*, 4> Defs; 123234285Sdim for (; FirstMI != LastMI; ++FirstMI) { 124234285Sdim for (unsigned i = 0, e = FirstMI->getNumOperands(); i != e; ++i) { 125234285Sdim MachineOperand &MO = FirstMI->getOperand(i); 126234285Sdim if (!MO.isReg()) 127234285Sdim continue; 128234285Sdim if (MO.isDef()) { 129234285Sdim Defs.push_back(&MO); 130234285Sdim continue; 131234285Sdim } 132234285Sdim 133234285Sdim unsigned Reg = MO.getReg(); 134234285Sdim if (!Reg) 135234285Sdim continue; 136234285Sdim assert(TargetRegisterInfo::isPhysicalRegister(Reg)); 137234285Sdim if (LocalDefSet.count(Reg)) { 138234285Sdim MO.setIsInternalRead(); 139234285Sdim if (MO.isKill()) 140234285Sdim // Internal def is now killed. 141234285Sdim KilledDefSet.insert(Reg); 142234285Sdim } else { 143234285Sdim if (ExternUseSet.insert(Reg)) { 144234285Sdim ExternUses.push_back(Reg); 145234285Sdim if (MO.isUndef()) 146234285Sdim UndefUseSet.insert(Reg); 147234285Sdim } 148234285Sdim if (MO.isKill()) 149234285Sdim // External def is now killed. 150234285Sdim KilledUseSet.insert(Reg); 151234285Sdim } 152234285Sdim } 153234285Sdim 154234285Sdim for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 155234285Sdim MachineOperand &MO = *Defs[i]; 156234285Sdim unsigned Reg = MO.getReg(); 157234285Sdim if (!Reg) 158234285Sdim continue; 159234285Sdim 160234285Sdim if (LocalDefSet.insert(Reg)) { 161234285Sdim LocalDefs.push_back(Reg); 162234285Sdim if (MO.isDead()) { 163234285Sdim DeadDefSet.insert(Reg); 164234285Sdim } 165234285Sdim } else { 166234285Sdim // Re-defined inside the bundle, it's no longer killed. 167234285Sdim KilledDefSet.erase(Reg); 168234285Sdim if (!MO.isDead()) 169234285Sdim // Previously defined but dead. 170234285Sdim DeadDefSet.erase(Reg); 171234285Sdim } 172234285Sdim 173234285Sdim if (!MO.isDead()) { 174239462Sdim for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 175239462Sdim unsigned SubReg = *SubRegs; 176234285Sdim if (LocalDefSet.insert(SubReg)) 177234285Sdim LocalDefs.push_back(SubReg); 178234285Sdim } 179234285Sdim } 180234285Sdim } 181234285Sdim 182234285Sdim Defs.clear(); 183234285Sdim } 184234285Sdim 185243830Sdim SmallSet<unsigned, 32> Added; 186234285Sdim for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) { 187234285Sdim unsigned Reg = LocalDefs[i]; 188234285Sdim if (Added.insert(Reg)) { 189234285Sdim // If it's not live beyond end of the bundle, mark it dead. 190234285Sdim bool isDead = DeadDefSet.count(Reg) || KilledDefSet.count(Reg); 191234285Sdim MIB.addReg(Reg, getDefRegState(true) | getDeadRegState(isDead) | 192234285Sdim getImplRegState(true)); 193234285Sdim } 194234285Sdim } 195234285Sdim 196234285Sdim for (unsigned i = 0, e = ExternUses.size(); i != e; ++i) { 197234285Sdim unsigned Reg = ExternUses[i]; 198234285Sdim bool isKill = KilledUseSet.count(Reg); 199234285Sdim bool isUndef = UndefUseSet.count(Reg); 200234285Sdim MIB.addReg(Reg, getKillRegState(isKill) | getUndefRegState(isUndef) | 201234285Sdim getImplRegState(true)); 202234285Sdim } 203234285Sdim} 204234285Sdim 205234285Sdim/// finalizeBundle - Same functionality as the previous finalizeBundle except 206234285Sdim/// the last instruction in the bundle is not provided as an input. This is 207234285Sdim/// used in cases where bundles are pre-determined by marking instructions 208234285Sdim/// with 'InsideBundle' marker. It returns the MBB instruction iterator that 209234285Sdim/// points to the end of the bundle. 210234285SdimMachineBasicBlock::instr_iterator 211234285Sdimllvm::finalizeBundle(MachineBasicBlock &MBB, 212234285Sdim MachineBasicBlock::instr_iterator FirstMI) { 213234285Sdim MachineBasicBlock::instr_iterator E = MBB.instr_end(); 214234285Sdim MachineBasicBlock::instr_iterator LastMI = llvm::next(FirstMI); 215234285Sdim while (LastMI != E && LastMI->isInsideBundle()) 216234285Sdim ++LastMI; 217234285Sdim finalizeBundle(MBB, FirstMI, LastMI); 218234285Sdim return LastMI; 219234285Sdim} 220234285Sdim 221234285Sdim/// finalizeBundles - Finalize instruction bundles in the specified 222234285Sdim/// MachineFunction. Return true if any bundles are finalized. 223234285Sdimbool llvm::finalizeBundles(MachineFunction &MF) { 224234285Sdim bool Changed = false; 225234285Sdim for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 226234285Sdim MachineBasicBlock &MBB = *I; 227234285Sdim MachineBasicBlock::instr_iterator MII = MBB.instr_begin(); 228249423Sdim MachineBasicBlock::instr_iterator MIE = MBB.instr_end(); 229249423Sdim if (MII == MIE) 230249423Sdim continue; 231234285Sdim assert(!MII->isInsideBundle() && 232234285Sdim "First instr cannot be inside bundle before finalization!"); 233234285Sdim 234234285Sdim for (++MII; MII != MIE; ) { 235234285Sdim if (!MII->isInsideBundle()) 236234285Sdim ++MII; 237234285Sdim else { 238234285Sdim MII = finalizeBundle(MBB, llvm::prior(MII)); 239234285Sdim Changed = true; 240234285Sdim } 241234285Sdim } 242234285Sdim } 243234285Sdim 244234285Sdim return Changed; 245234285Sdim} 246234285Sdim 247234285Sdim//===----------------------------------------------------------------------===// 248234285Sdim// MachineOperand iterator 249234285Sdim//===----------------------------------------------------------------------===// 250234285Sdim 251243830SdimMachineOperandIteratorBase::VirtRegInfo 252234285SdimMachineOperandIteratorBase::analyzeVirtReg(unsigned Reg, 253234285Sdim SmallVectorImpl<std::pair<MachineInstr*, unsigned> > *Ops) { 254243830Sdim VirtRegInfo RI = { false, false, false }; 255234285Sdim for(; isValid(); ++*this) { 256234285Sdim MachineOperand &MO = deref(); 257234285Sdim if (!MO.isReg() || MO.getReg() != Reg) 258234285Sdim continue; 259234285Sdim 260234285Sdim // Remember each (MI, OpNo) that refers to Reg. 261234285Sdim if (Ops) 262234285Sdim Ops->push_back(std::make_pair(MO.getParent(), getOperandNo())); 263234285Sdim 264234285Sdim // Both defs and uses can read virtual registers. 265234285Sdim if (MO.readsReg()) { 266234285Sdim RI.Reads = true; 267234285Sdim if (MO.isDef()) 268234285Sdim RI.Tied = true; 269234285Sdim } 270234285Sdim 271234285Sdim // Only defs can write. 272234285Sdim if (MO.isDef()) 273234285Sdim RI.Writes = true; 274234285Sdim else if (!RI.Tied && MO.getParent()->isRegTiedToDefOperand(getOperandNo())) 275234285Sdim RI.Tied = true; 276234285Sdim } 277234285Sdim return RI; 278234285Sdim} 279243830Sdim 280243830SdimMachineOperandIteratorBase::PhysRegInfo 281243830SdimMachineOperandIteratorBase::analyzePhysReg(unsigned Reg, 282243830Sdim const TargetRegisterInfo *TRI) { 283243830Sdim bool AllDefsDead = true; 284249423Sdim PhysRegInfo PRI = {false, false, false, false, false, false}; 285243830Sdim 286243830Sdim assert(TargetRegisterInfo::isPhysicalRegister(Reg) && 287243830Sdim "analyzePhysReg not given a physical register!"); 288243830Sdim for (; isValid(); ++*this) { 289243830Sdim MachineOperand &MO = deref(); 290243830Sdim 291243830Sdim if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) 292243830Sdim PRI.Clobbers = true; // Regmask clobbers Reg. 293243830Sdim 294243830Sdim if (!MO.isReg()) 295243830Sdim continue; 296243830Sdim 297243830Sdim unsigned MOReg = MO.getReg(); 298243830Sdim if (!MOReg || !TargetRegisterInfo::isPhysicalRegister(MOReg)) 299243830Sdim continue; 300243830Sdim 301243830Sdim bool IsRegOrSuperReg = MOReg == Reg || TRI->isSubRegister(MOReg, Reg); 302243830Sdim bool IsRegOrOverlapping = MOReg == Reg || TRI->regsOverlap(MOReg, Reg); 303243830Sdim 304243830Sdim if (IsRegOrSuperReg && MO.readsReg()) { 305243830Sdim // Reg or a super-reg is read, and perhaps killed also. 306243830Sdim PRI.Reads = true; 307243830Sdim PRI.Kills = MO.isKill(); 308249423Sdim } 309249423Sdim 310249423Sdim if (IsRegOrOverlapping && MO.readsReg()) { 311243830Sdim PRI.ReadsOverlap = true;// Reg or an overlapping register is read. 312243830Sdim } 313243830Sdim 314243830Sdim if (!MO.isDef()) 315243830Sdim continue; 316243830Sdim 317243830Sdim if (IsRegOrSuperReg) { 318243830Sdim PRI.Defines = true; // Reg or a super-register is defined. 319243830Sdim if (!MO.isDead()) 320243830Sdim AllDefsDead = false; 321243830Sdim } 322243830Sdim if (IsRegOrOverlapping) 323243830Sdim PRI.Clobbers = true; // Reg or an overlapping reg is defined. 324243830Sdim } 325243830Sdim 326243830Sdim if (AllDefsDead && PRI.Defines) 327243830Sdim PRI.DefinesDead = true; // Reg or super-register was defined and was dead. 328243830Sdim 329243830Sdim return PRI; 330243830Sdim} 331