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