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 (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()) 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<Register, 32> LocalDefs; 139 SmallSet<Register, 32> LocalDefSet; 140 SmallSet<Register, 8> DeadDefSet; 141 SmallSet<Register, 16> KilledDefSet; 142 SmallVector<Register, 8> ExternUses; 143 SmallSet<Register, 8> ExternUseSet; 144 SmallSet<Register, 8> KilledUseSet; 145 SmallSet<Register, 8> UndefUseSet; 146 SmallVector<MachineOperand*, 4> Defs; 147 for (auto MII = FirstMI; MII != LastMI; ++MII) { 148 // Debug instructions have no effects to track. 149 if (MII->isDebugInstr()) 150 continue; 151 152 for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) { 153 MachineOperand &MO = MII->getOperand(i); 154 if (!MO.isReg()) 155 continue; 156 if (MO.isDef()) { 157 Defs.push_back(&MO); 158 continue; 159 } 160 161 Register Reg = MO.getReg(); 162 if (!Reg) 163 continue; 164 165 if (LocalDefSet.count(Reg)) { 166 MO.setIsInternalRead(); 167 if (MO.isKill()) 168 // Internal def is now killed. 169 KilledDefSet.insert(Reg); 170 } else { 171 if (ExternUseSet.insert(Reg).second) { 172 ExternUses.push_back(Reg); 173 if (MO.isUndef()) 174 UndefUseSet.insert(Reg); 175 } 176 if (MO.isKill()) 177 // External def is now killed. 178 KilledUseSet.insert(Reg); 179 } 180 } 181 182 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 183 MachineOperand &MO = *Defs[i]; 184 Register Reg = MO.getReg(); 185 if (!Reg) 186 continue; 187 188 if (LocalDefSet.insert(Reg).second) { 189 LocalDefs.push_back(Reg); 190 if (MO.isDead()) { 191 DeadDefSet.insert(Reg); 192 } 193 } else { 194 // Re-defined inside the bundle, it's no longer killed. 195 KilledDefSet.erase(Reg); 196 if (!MO.isDead()) 197 // Previously defined but dead. 198 DeadDefSet.erase(Reg); 199 } 200 201 if (!MO.isDead() && Register::isPhysicalRegister(Reg)) { 202 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 203 unsigned SubReg = *SubRegs; 204 if (LocalDefSet.insert(SubReg).second) 205 LocalDefs.push_back(SubReg); 206 } 207 } 208 } 209 210 Defs.clear(); 211 } 212 213 SmallSet<Register, 32> Added; 214 for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) { 215 Register Reg = LocalDefs[i]; 216 if (Added.insert(Reg).second) { 217 // If it's not live beyond end of the bundle, mark it dead. 218 bool isDead = DeadDefSet.count(Reg) || KilledDefSet.count(Reg); 219 MIB.addReg(Reg, getDefRegState(true) | getDeadRegState(isDead) | 220 getImplRegState(true)); 221 } 222 } 223 224 for (unsigned i = 0, e = ExternUses.size(); i != e; ++i) { 225 Register Reg = ExternUses[i]; 226 bool isKill = KilledUseSet.count(Reg); 227 bool isUndef = UndefUseSet.count(Reg); 228 MIB.addReg(Reg, getKillRegState(isKill) | getUndefRegState(isUndef) | 229 getImplRegState(true)); 230 } 231 232 // Set FrameSetup/FrameDestroy for the bundle. If any of the instructions got 233 // the property, then also set it on the bundle. 234 for (auto MII = FirstMI; MII != LastMI; ++MII) { 235 if (MII->getFlag(MachineInstr::FrameSetup)) 236 MIB.setMIFlag(MachineInstr::FrameSetup); 237 if (MII->getFlag(MachineInstr::FrameDestroy)) 238 MIB.setMIFlag(MachineInstr::FrameDestroy); 239 } 240 } 241 242 /// finalizeBundle - Same functionality as the previous finalizeBundle except 243 /// the last instruction in the bundle is not provided as an input. This is 244 /// used in cases where bundles are pre-determined by marking instructions 245 /// with 'InsideBundle' marker. It returns the MBB instruction iterator that 246 /// points to the end of the bundle. 247 MachineBasicBlock::instr_iterator 248 llvm::finalizeBundle(MachineBasicBlock &MBB, 249 MachineBasicBlock::instr_iterator FirstMI) { 250 MachineBasicBlock::instr_iterator E = MBB.instr_end(); 251 MachineBasicBlock::instr_iterator LastMI = std::next(FirstMI); 252 while (LastMI != E && LastMI->isInsideBundle()) 253 ++LastMI; 254 finalizeBundle(MBB, FirstMI, LastMI); 255 return LastMI; 256 } 257 258 /// finalizeBundles - Finalize instruction bundles in the specified 259 /// MachineFunction. Return true if any bundles are finalized. 260 bool llvm::finalizeBundles(MachineFunction &MF) { 261 bool Changed = false; 262 for (MachineBasicBlock &MBB : MF) { 263 MachineBasicBlock::instr_iterator MII = MBB.instr_begin(); 264 MachineBasicBlock::instr_iterator MIE = MBB.instr_end(); 265 if (MII == MIE) 266 continue; 267 assert(!MII->isInsideBundle() && 268 "First instr cannot be inside bundle before finalization!"); 269 270 for (++MII; MII != MIE; ) { 271 if (!MII->isInsideBundle()) 272 ++MII; 273 else { 274 MII = finalizeBundle(MBB, std::prev(MII)); 275 Changed = true; 276 } 277 } 278 } 279 280 return Changed; 281 } 282 283 VirtRegInfo llvm::AnalyzeVirtRegInBundle( 284 MachineInstr &MI, Register Reg, 285 SmallVectorImpl<std::pair<MachineInstr *, unsigned>> *Ops) { 286 VirtRegInfo RI = {false, false, false}; 287 for (MIBundleOperands O(MI); O.isValid(); ++O) { 288 MachineOperand &MO = *O; 289 if (!MO.isReg() || MO.getReg() != Reg) 290 continue; 291 292 // Remember each (MI, OpNo) that refers to Reg. 293 if (Ops) 294 Ops->push_back(std::make_pair(MO.getParent(), O.getOperandNo())); 295 296 // Both defs and uses can read virtual registers. 297 if (MO.readsReg()) { 298 RI.Reads = true; 299 if (MO.isDef()) 300 RI.Tied = true; 301 } 302 303 // Only defs can write. 304 if (MO.isDef()) 305 RI.Writes = true; 306 else if (!RI.Tied && 307 MO.getParent()->isRegTiedToDefOperand(O.getOperandNo())) 308 RI.Tied = true; 309 } 310 return RI; 311 } 312 313 PhysRegInfo llvm::AnalyzePhysRegInBundle(const MachineInstr &MI, Register Reg, 314 const TargetRegisterInfo *TRI) { 315 bool AllDefsDead = true; 316 PhysRegInfo PRI = {false, false, false, false, false, false, false, false}; 317 318 assert(Reg.isPhysical() && "analyzePhysReg not given a physical register!"); 319 for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { 320 const MachineOperand &MO = *O; 321 322 if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) { 323 PRI.Clobbered = true; 324 continue; 325 } 326 327 if (!MO.isReg()) 328 continue; 329 330 Register MOReg = MO.getReg(); 331 if (!MOReg || !Register::isPhysicalRegister(MOReg)) 332 continue; 333 334 if (!TRI->regsOverlap(MOReg, Reg)) 335 continue; 336 337 bool Covered = TRI->isSuperRegisterEq(Reg, MOReg); 338 if (MO.readsReg()) { 339 PRI.Read = true; 340 if (Covered) { 341 PRI.FullyRead = true; 342 if (MO.isKill()) 343 PRI.Killed = true; 344 } 345 } else if (MO.isDef()) { 346 PRI.Defined = true; 347 if (Covered) 348 PRI.FullyDefined = true; 349 if (!MO.isDead()) 350 AllDefsDead = false; 351 } 352 } 353 354 if (AllDefsDead) { 355 if (PRI.FullyDefined || PRI.Clobbered) 356 PRI.DeadDef = true; 357 else if (PRI.Defined) 358 PRI.PartialDeadDef = true; 359 } 360 361 return PRI; 362 } 363