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 (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 51 MachineBasicBlock *MBB = &*I; 52 53 for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(), 54 MIE = MBB->instr_end(); MII != MIE; ) { 55 MachineInstr *MI = &*MII; 56 57 // Remove BUNDLE instruction and the InsideBundle flags from bundled 58 // instructions. 59 if (MI->isBundle()) { 60 while (++MII != MIE && MII->isBundledWithPred()) { 61 MII->unbundleFromPred(); 62 for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) { 63 MachineOperand &MO = MII->getOperand(i); 64 if (MO.isReg() && MO.isInternalRead()) 65 MO.setIsInternalRead(false); 66 } 67 } 68 MI->eraseFromParent(); 69 70 Changed = true; 71 continue; 72 } 73 74 ++MII; 75 } 76 } 77 78 return Changed; 79 } 80 81 FunctionPass * 82 llvm::createUnpackMachineBundles( 83 std::function<bool(const MachineFunction &)> Ftor) { 84 return new UnpackMachineBundles(std::move(Ftor)); 85 } 86 87 namespace { 88 class FinalizeMachineBundles : public MachineFunctionPass { 89 public: 90 static char ID; // Pass identification 91 FinalizeMachineBundles() : MachineFunctionPass(ID) { 92 initializeFinalizeMachineBundlesPass(*PassRegistry::getPassRegistry()); 93 } 94 95 bool runOnMachineFunction(MachineFunction &MF) override; 96 }; 97 } // end anonymous namespace 98 99 char FinalizeMachineBundles::ID = 0; 100 char &llvm::FinalizeMachineBundlesID = FinalizeMachineBundles::ID; 101 INITIALIZE_PASS(FinalizeMachineBundles, "finalize-mi-bundles", 102 "Finalize machine instruction bundles", false, false) 103 104 bool FinalizeMachineBundles::runOnMachineFunction(MachineFunction &MF) { 105 return llvm::finalizeBundles(MF); 106 } 107 108 /// Return the first found DebugLoc that has a DILocation, given a range of 109 /// instructions. The search range is from FirstMI to LastMI (exclusive). If no 110 /// DILocation is found, then an empty location is returned. 111 static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI, 112 MachineBasicBlock::instr_iterator LastMI) { 113 for (auto MII = FirstMI; MII != LastMI; ++MII) 114 if (MII->getDebugLoc().get()) 115 return MII->getDebugLoc(); 116 return DebugLoc(); 117 } 118 119 /// finalizeBundle - Finalize a machine instruction bundle which includes 120 /// a sequence of instructions starting from FirstMI to LastMI (exclusive). 121 /// This routine adds a BUNDLE instruction to represent the bundle, it adds 122 /// IsInternalRead markers to MachineOperands which are defined inside the 123 /// bundle, and it copies externally visible defs and uses to the BUNDLE 124 /// instruction. 125 void llvm::finalizeBundle(MachineBasicBlock &MBB, 126 MachineBasicBlock::instr_iterator FirstMI, 127 MachineBasicBlock::instr_iterator LastMI) { 128 assert(FirstMI != LastMI && "Empty bundle?"); 129 MIBundleBuilder Bundle(MBB, FirstMI, LastMI); 130 131 MachineFunction &MF = *MBB.getParent(); 132 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo(); 133 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); 134 135 MachineInstrBuilder MIB = 136 BuildMI(MF, getDebugLoc(FirstMI, LastMI), TII->get(TargetOpcode::BUNDLE)); 137 Bundle.prepend(MIB); 138 139 SmallVector<Register, 32> LocalDefs; 140 SmallSet<Register, 32> LocalDefSet; 141 SmallSet<Register, 8> DeadDefSet; 142 SmallSet<Register, 16> KilledDefSet; 143 SmallVector<Register, 8> ExternUses; 144 SmallSet<Register, 8> ExternUseSet; 145 SmallSet<Register, 8> KilledUseSet; 146 SmallSet<Register, 8> UndefUseSet; 147 SmallVector<MachineOperand*, 4> Defs; 148 for (auto MII = FirstMI; MII != LastMI; ++MII) { 149 for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) { 150 MachineOperand &MO = MII->getOperand(i); 151 if (!MO.isReg()) 152 continue; 153 if (MO.isDef()) { 154 Defs.push_back(&MO); 155 continue; 156 } 157 158 Register Reg = MO.getReg(); 159 if (!Reg) 160 continue; 161 162 if (LocalDefSet.count(Reg)) { 163 MO.setIsInternalRead(); 164 if (MO.isKill()) 165 // Internal def is now killed. 166 KilledDefSet.insert(Reg); 167 } else { 168 if (ExternUseSet.insert(Reg).second) { 169 ExternUses.push_back(Reg); 170 if (MO.isUndef()) 171 UndefUseSet.insert(Reg); 172 } 173 if (MO.isKill()) 174 // External def is now killed. 175 KilledUseSet.insert(Reg); 176 } 177 } 178 179 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 180 MachineOperand &MO = *Defs[i]; 181 Register Reg = MO.getReg(); 182 if (!Reg) 183 continue; 184 185 if (LocalDefSet.insert(Reg).second) { 186 LocalDefs.push_back(Reg); 187 if (MO.isDead()) { 188 DeadDefSet.insert(Reg); 189 } 190 } else { 191 // Re-defined inside the bundle, it's no longer killed. 192 KilledDefSet.erase(Reg); 193 if (!MO.isDead()) 194 // Previously defined but dead. 195 DeadDefSet.erase(Reg); 196 } 197 198 if (!MO.isDead() && Register::isPhysicalRegister(Reg)) { 199 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 200 unsigned SubReg = *SubRegs; 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 (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 260 MachineBasicBlock &MBB = *I; 261 MachineBasicBlock::instr_iterator MII = MBB.instr_begin(); 262 MachineBasicBlock::instr_iterator MIE = MBB.instr_end(); 263 if (MII == MIE) 264 continue; 265 assert(!MII->isInsideBundle() && 266 "First instr cannot be inside bundle before finalization!"); 267 268 for (++MII; MII != MIE; ) { 269 if (!MII->isInsideBundle()) 270 ++MII; 271 else { 272 MII = finalizeBundle(MBB, std::prev(MII)); 273 Changed = true; 274 } 275 } 276 } 277 278 return Changed; 279 } 280 281 VirtRegInfo llvm::AnalyzeVirtRegInBundle( 282 MachineInstr &MI, Register Reg, 283 SmallVectorImpl<std::pair<MachineInstr *, unsigned>> *Ops) { 284 VirtRegInfo RI = {false, false, false}; 285 for (MIBundleOperands O(MI); O.isValid(); ++O) { 286 MachineOperand &MO = *O; 287 if (!MO.isReg() || MO.getReg() != Reg) 288 continue; 289 290 // Remember each (MI, OpNo) that refers to Reg. 291 if (Ops) 292 Ops->push_back(std::make_pair(MO.getParent(), O.getOperandNo())); 293 294 // Both defs and uses can read virtual registers. 295 if (MO.readsReg()) { 296 RI.Reads = true; 297 if (MO.isDef()) 298 RI.Tied = true; 299 } 300 301 // Only defs can write. 302 if (MO.isDef()) 303 RI.Writes = true; 304 else if (!RI.Tied && 305 MO.getParent()->isRegTiedToDefOperand(O.getOperandNo())) 306 RI.Tied = true; 307 } 308 return RI; 309 } 310 311 PhysRegInfo llvm::AnalyzePhysRegInBundle(const MachineInstr &MI, Register Reg, 312 const TargetRegisterInfo *TRI) { 313 bool AllDefsDead = true; 314 PhysRegInfo PRI = {false, false, false, false, false, false, false, false}; 315 316 assert(Reg.isPhysical() && "analyzePhysReg not given a physical register!"); 317 for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { 318 const MachineOperand &MO = *O; 319 320 if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) { 321 PRI.Clobbered = true; 322 continue; 323 } 324 325 if (!MO.isReg()) 326 continue; 327 328 Register MOReg = MO.getReg(); 329 if (!MOReg || !Register::isPhysicalRegister(MOReg)) 330 continue; 331 332 if (!TRI->regsOverlap(MOReg, Reg)) 333 continue; 334 335 bool Covered = TRI->isSuperRegisterEq(Reg, MOReg); 336 if (MO.readsReg()) { 337 PRI.Read = true; 338 if (Covered) { 339 PRI.FullyRead = true; 340 if (MO.isKill()) 341 PRI.Killed = true; 342 } 343 } else if (MO.isDef()) { 344 PRI.Defined = true; 345 if (Covered) 346 PRI.FullyDefined = true; 347 if (!MO.isDead()) 348 AllDefsDead = false; 349 } 350 } 351 352 if (AllDefsDead) { 353 if (PRI.FullyDefined || PRI.Clobbered) 354 PRI.DeadDef = true; 355 else if (PRI.Defined) 356 PRI.PartialDeadDef = true; 357 } 358 359 return PRI; 360 } 361