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/InitializePasses.h" 19 #include "llvm/Pass.h" 20 #include "llvm/PassRegistry.h" 21 #include <utility> 22 using namespace llvm; 23 24 namespace { 25 class UnpackMachineBundles : public MachineFunctionPass { 26 public: 27 static char ID; // Pass identification 28 UnpackMachineBundles( 29 std::function<bool(const MachineFunction &)> Ftor = nullptr) 30 : MachineFunctionPass(ID), PredicateFtor(std::move(Ftor)) { 31 initializeUnpackMachineBundlesPass(*PassRegistry::getPassRegistry()); 32 } 33 34 bool runOnMachineFunction(MachineFunction &MF) override; 35 36 private: 37 std::function<bool(const MachineFunction &)> PredicateFtor; 38 }; 39 } // end anonymous namespace 40 41 char UnpackMachineBundles::ID = 0; 42 char &llvm::UnpackMachineBundlesID = UnpackMachineBundles::ID; 43 INITIALIZE_PASS(UnpackMachineBundles, "unpack-mi-bundles", 44 "Unpack machine instruction bundles", false, false) 45 46 bool UnpackMachineBundles::runOnMachineFunction(MachineFunction &MF) { 47 if (PredicateFtor && !PredicateFtor(MF)) 48 return false; 49 50 bool Changed = false; 51 for (MachineBasicBlock &MBB : MF) { 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 (MachineOperand &MO : MII->operands()) { 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( 81 std::function<bool(const MachineFunction &)> Ftor) { 82 return new UnpackMachineBundles(std::move(Ftor)); 83 } 84 85 namespace { 86 class FinalizeMachineBundles : public MachineFunctionPass { 87 public: 88 static char ID; // Pass identification 89 FinalizeMachineBundles() : MachineFunctionPass(ID) { 90 initializeFinalizeMachineBundlesPass(*PassRegistry::getPassRegistry()); 91 } 92 93 bool runOnMachineFunction(MachineFunction &MF) override; 94 }; 95 } // end anonymous namespace 96 97 char FinalizeMachineBundles::ID = 0; 98 char &llvm::FinalizeMachineBundlesID = FinalizeMachineBundles::ID; 99 INITIALIZE_PASS(FinalizeMachineBundles, "finalize-mi-bundles", 100 "Finalize machine instruction bundles", false, false) 101 102 bool FinalizeMachineBundles::runOnMachineFunction(MachineFunction &MF) { 103 return llvm::finalizeBundles(MF); 104 } 105 106 /// Return the first found DebugLoc that has a DILocation, given a range of 107 /// instructions. The search range is from FirstMI to LastMI (exclusive). If no 108 /// DILocation is found, then an empty location is returned. 109 static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI, 110 MachineBasicBlock::instr_iterator LastMI) { 111 for (auto MII = FirstMI; MII != LastMI; ++MII) 112 if (MII->getDebugLoc()) 113 return MII->getDebugLoc(); 114 return DebugLoc(); 115 } 116 117 /// finalizeBundle - Finalize a machine instruction bundle which includes 118 /// a sequence of instructions starting from FirstMI to LastMI (exclusive). 119 /// This routine adds a BUNDLE instruction to represent the bundle, it adds 120 /// IsInternalRead markers to MachineOperands which are defined inside the 121 /// bundle, and it copies externally visible defs and uses to the BUNDLE 122 /// instruction. 123 void llvm::finalizeBundle(MachineBasicBlock &MBB, 124 MachineBasicBlock::instr_iterator FirstMI, 125 MachineBasicBlock::instr_iterator LastMI) { 126 assert(FirstMI != LastMI && "Empty bundle?"); 127 MIBundleBuilder Bundle(MBB, FirstMI, LastMI); 128 129 MachineFunction &MF = *MBB.getParent(); 130 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo(); 131 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); 132 133 MachineInstrBuilder MIB = 134 BuildMI(MF, getDebugLoc(FirstMI, LastMI), TII->get(TargetOpcode::BUNDLE)); 135 Bundle.prepend(MIB); 136 137 SmallVector<Register, 32> LocalDefs; 138 SmallSet<Register, 32> LocalDefSet; 139 SmallSet<Register, 8> DeadDefSet; 140 SmallSet<Register, 16> KilledDefSet; 141 SmallVector<Register, 8> ExternUses; 142 SmallSet<Register, 8> ExternUseSet; 143 SmallSet<Register, 8> KilledUseSet; 144 SmallSet<Register, 8> UndefUseSet; 145 SmallVector<MachineOperand*, 4> Defs; 146 for (auto MII = FirstMI; MII != LastMI; ++MII) { 147 // Debug instructions have no effects to track. 148 if (MII->isDebugInstr()) 149 continue; 150 151 for (MachineOperand &MO : MII->operands()) { 152 if (!MO.isReg()) 153 continue; 154 if (MO.isDef()) { 155 Defs.push_back(&MO); 156 continue; 157 } 158 159 Register Reg = MO.getReg(); 160 if (!Reg) 161 continue; 162 163 if (LocalDefSet.count(Reg)) { 164 MO.setIsInternalRead(); 165 if (MO.isKill()) 166 // Internal def is now killed. 167 KilledDefSet.insert(Reg); 168 } else { 169 if (ExternUseSet.insert(Reg).second) { 170 ExternUses.push_back(Reg); 171 if (MO.isUndef()) 172 UndefUseSet.insert(Reg); 173 } 174 if (MO.isKill()) 175 // External def is now killed. 176 KilledUseSet.insert(Reg); 177 } 178 } 179 180 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 181 MachineOperand &MO = *Defs[i]; 182 Register Reg = MO.getReg(); 183 if (!Reg) 184 continue; 185 186 if (LocalDefSet.insert(Reg).second) { 187 LocalDefs.push_back(Reg); 188 if (MO.isDead()) { 189 DeadDefSet.insert(Reg); 190 } 191 } else { 192 // Re-defined inside the bundle, it's no longer killed. 193 KilledDefSet.erase(Reg); 194 if (!MO.isDead()) 195 // Previously defined but dead. 196 DeadDefSet.erase(Reg); 197 } 198 199 if (!MO.isDead() && Reg.isPhysical()) { 200 for (MCPhysReg SubReg : TRI->subregs(Reg)) { 201 if (LocalDefSet.insert(SubReg).second) 202 LocalDefs.push_back(SubReg); 203 } 204 } 205 } 206 207 Defs.clear(); 208 } 209 210 SmallSet<Register, 32> Added; 211 for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) { 212 Register Reg = LocalDefs[i]; 213 if (Added.insert(Reg).second) { 214 // If it's not live beyond end of the bundle, mark it dead. 215 bool isDead = DeadDefSet.count(Reg) || KilledDefSet.count(Reg); 216 MIB.addReg(Reg, getDefRegState(true) | getDeadRegState(isDead) | 217 getImplRegState(true)); 218 } 219 } 220 221 for (unsigned i = 0, e = ExternUses.size(); i != e; ++i) { 222 Register Reg = ExternUses[i]; 223 bool isKill = KilledUseSet.count(Reg); 224 bool isUndef = UndefUseSet.count(Reg); 225 MIB.addReg(Reg, getKillRegState(isKill) | getUndefRegState(isUndef) | 226 getImplRegState(true)); 227 } 228 229 // Set FrameSetup/FrameDestroy for the bundle. If any of the instructions got 230 // the property, then also set it on the bundle. 231 for (auto MII = FirstMI; MII != LastMI; ++MII) { 232 if (MII->getFlag(MachineInstr::FrameSetup)) 233 MIB.setMIFlag(MachineInstr::FrameSetup); 234 if (MII->getFlag(MachineInstr::FrameDestroy)) 235 MIB.setMIFlag(MachineInstr::FrameDestroy); 236 } 237 } 238 239 /// finalizeBundle - Same functionality as the previous finalizeBundle except 240 /// the last instruction in the bundle is not provided as an input. This is 241 /// used in cases where bundles are pre-determined by marking instructions 242 /// with 'InsideBundle' marker. It returns the MBB instruction iterator that 243 /// points to the end of the bundle. 244 MachineBasicBlock::instr_iterator 245 llvm::finalizeBundle(MachineBasicBlock &MBB, 246 MachineBasicBlock::instr_iterator FirstMI) { 247 MachineBasicBlock::instr_iterator E = MBB.instr_end(); 248 MachineBasicBlock::instr_iterator LastMI = std::next(FirstMI); 249 while (LastMI != E && LastMI->isInsideBundle()) 250 ++LastMI; 251 finalizeBundle(MBB, FirstMI, LastMI); 252 return LastMI; 253 } 254 255 /// finalizeBundles - Finalize instruction bundles in the specified 256 /// MachineFunction. Return true if any bundles are finalized. 257 bool llvm::finalizeBundles(MachineFunction &MF) { 258 bool Changed = false; 259 for (MachineBasicBlock &MBB : MF) { 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 VirtRegInfo llvm::AnalyzeVirtRegInBundle( 281 MachineInstr &MI, Register Reg, 282 SmallVectorImpl<std::pair<MachineInstr *, unsigned>> *Ops) { 283 VirtRegInfo RI = {false, false, false}; 284 for (MIBundleOperands O(MI); O.isValid(); ++O) { 285 MachineOperand &MO = *O; 286 if (!MO.isReg() || MO.getReg() != Reg) 287 continue; 288 289 // Remember each (MI, OpNo) that refers to Reg. 290 if (Ops) 291 Ops->push_back(std::make_pair(MO.getParent(), O.getOperandNo())); 292 293 // Both defs and uses can read virtual registers. 294 if (MO.readsReg()) { 295 RI.Reads = true; 296 if (MO.isDef()) 297 RI.Tied = true; 298 } 299 300 // Only defs can write. 301 if (MO.isDef()) 302 RI.Writes = true; 303 else if (!RI.Tied && 304 MO.getParent()->isRegTiedToDefOperand(O.getOperandNo())) 305 RI.Tied = true; 306 } 307 return RI; 308 } 309 310 std::pair<LaneBitmask, LaneBitmask> 311 llvm::AnalyzeVirtRegLanesInBundle(const MachineInstr &MI, Register Reg, 312 const MachineRegisterInfo &MRI, 313 const TargetRegisterInfo &TRI) { 314 315 LaneBitmask UseMask, DefMask; 316 317 for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { 318 const MachineOperand &MO = *O; 319 if (!MO.isReg() || MO.getReg() != Reg) 320 continue; 321 322 unsigned SubReg = MO.getSubReg(); 323 if (SubReg == 0 && MO.isUse() && !MO.isUndef()) 324 UseMask |= MRI.getMaxLaneMaskForVReg(Reg); 325 326 LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(SubReg); 327 if (MO.isDef()) { 328 if (!MO.isUndef()) 329 UseMask |= ~SubRegMask; 330 DefMask |= SubRegMask; 331 } else if (!MO.isUndef()) 332 UseMask |= SubRegMask; 333 } 334 335 return {UseMask, DefMask}; 336 } 337 338 PhysRegInfo llvm::AnalyzePhysRegInBundle(const MachineInstr &MI, Register Reg, 339 const TargetRegisterInfo *TRI) { 340 bool AllDefsDead = true; 341 PhysRegInfo PRI = {false, false, false, false, false, false, false, false}; 342 343 assert(Reg.isPhysical() && "analyzePhysReg not given a physical register!"); 344 for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { 345 const MachineOperand &MO = *O; 346 347 if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) { 348 PRI.Clobbered = true; 349 continue; 350 } 351 352 if (!MO.isReg()) 353 continue; 354 355 Register MOReg = MO.getReg(); 356 if (!MOReg || !MOReg.isPhysical()) 357 continue; 358 359 if (!TRI->regsOverlap(MOReg, Reg)) 360 continue; 361 362 bool Covered = TRI->isSuperRegisterEq(Reg, MOReg); 363 if (MO.readsReg()) { 364 PRI.Read = true; 365 if (Covered) { 366 PRI.FullyRead = true; 367 if (MO.isKill()) 368 PRI.Killed = true; 369 } 370 } else if (MO.isDef()) { 371 PRI.Defined = true; 372 if (Covered) 373 PRI.FullyDefined = true; 374 if (!MO.isDead()) 375 AllDefsDead = false; 376 } 377 } 378 379 if (AllDefsDead) { 380 if (PRI.FullyDefined || PRI.Clobbered) 381 PRI.DeadDef = true; 382 else if (PRI.Defined) 383 PRI.PartialDeadDef = true; 384 } 385 386 return PRI; 387 } 388