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