1 //===-- DelaySlotFiller.cpp - SPARC delay slot filler ---------------------===// 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 // This is a simple local pass that attempts to fill delay slots with useful 10 // instructions. If no instructions can be moved into the delay slot, then a 11 // NOP is placed. 12 //===----------------------------------------------------------------------===// 13 14 #include "Sparc.h" 15 #include "SparcSubtarget.h" 16 #include "llvm/ADT/SmallSet.h" 17 #include "llvm/ADT/Statistic.h" 18 #include "llvm/CodeGen/MachineFunctionPass.h" 19 #include "llvm/CodeGen/MachineInstrBuilder.h" 20 #include "llvm/CodeGen/MachineRegisterInfo.h" 21 #include "llvm/CodeGen/TargetInstrInfo.h" 22 #include "llvm/CodeGen/TargetRegisterInfo.h" 23 #include "llvm/Support/CommandLine.h" 24 #include "llvm/Target/TargetMachine.h" 25 26 using namespace llvm; 27 28 #define DEBUG_TYPE "delay-slot-filler" 29 30 STATISTIC(FilledSlots, "Number of delay slots filled"); 31 32 static cl::opt<bool> DisableDelaySlotFiller( 33 "disable-sparc-delay-filler", 34 cl::init(false), 35 cl::desc("Disable the Sparc delay slot filler."), 36 cl::Hidden); 37 38 namespace { 39 struct Filler : public MachineFunctionPass { 40 const SparcSubtarget *Subtarget; 41 42 static char ID; 43 Filler() : MachineFunctionPass(ID) {} 44 45 StringRef getPassName() const override { return "SPARC Delay Slot Filler"; } 46 47 bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 48 bool runOnMachineFunction(MachineFunction &F) override { 49 bool Changed = false; 50 Subtarget = &F.getSubtarget<SparcSubtarget>(); 51 52 // This pass invalidates liveness information when it reorders 53 // instructions to fill delay slot. 54 F.getRegInfo().invalidateLiveness(); 55 56 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 57 FI != FE; ++FI) 58 Changed |= runOnMachineBasicBlock(*FI); 59 return Changed; 60 } 61 62 MachineFunctionProperties getRequiredProperties() const override { 63 return MachineFunctionProperties().set( 64 MachineFunctionProperties::Property::NoVRegs); 65 } 66 67 void insertCallDefsUses(MachineBasicBlock::iterator MI, 68 SmallSet<unsigned, 32>& RegDefs, 69 SmallSet<unsigned, 32>& RegUses); 70 71 void insertDefsUses(MachineBasicBlock::iterator MI, 72 SmallSet<unsigned, 32>& RegDefs, 73 SmallSet<unsigned, 32>& RegUses); 74 75 bool IsRegInSet(SmallSet<unsigned, 32>& RegSet, 76 unsigned Reg); 77 78 bool delayHasHazard(MachineBasicBlock::iterator candidate, 79 bool &sawLoad, bool &sawStore, 80 SmallSet<unsigned, 32> &RegDefs, 81 SmallSet<unsigned, 32> &RegUses); 82 83 MachineBasicBlock::iterator 84 findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot); 85 86 bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize); 87 88 bool tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB, 89 MachineBasicBlock::iterator MBBI); 90 91 }; 92 char Filler::ID = 0; 93 } // end of anonymous namespace 94 95 /// createSparcDelaySlotFillerPass - Returns a pass that fills in delay 96 /// slots in Sparc MachineFunctions 97 /// 98 FunctionPass *llvm::createSparcDelaySlotFillerPass() { 99 return new Filler; 100 } 101 102 103 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 104 /// We assume there is only one delay slot per delayed instruction. 105 /// 106 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 107 bool Changed = false; 108 Subtarget = &MBB.getParent()->getSubtarget<SparcSubtarget>(); 109 const TargetInstrInfo *TII = Subtarget->getInstrInfo(); 110 111 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) { 112 MachineBasicBlock::iterator MI = I; 113 ++I; 114 115 // If MI is restore, try combining it with previous inst. 116 if (!DisableDelaySlotFiller && 117 (MI->getOpcode() == SP::RESTORErr 118 || MI->getOpcode() == SP::RESTOREri)) { 119 Changed |= tryCombineRestoreWithPrevInst(MBB, MI); 120 continue; 121 } 122 123 // TODO: If we ever want to support v7, this needs to be extended 124 // to cover all floating point operations. 125 if (!Subtarget->isV9() && 126 (MI->getOpcode() == SP::FCMPS || MI->getOpcode() == SP::FCMPD 127 || MI->getOpcode() == SP::FCMPQ)) { 128 BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP)); 129 Changed = true; 130 continue; 131 } 132 133 // If MI has no delay slot, skip. 134 if (!MI->hasDelaySlot()) 135 continue; 136 137 MachineBasicBlock::iterator D = MBB.end(); 138 139 if (!DisableDelaySlotFiller) 140 D = findDelayInstr(MBB, MI); 141 142 ++FilledSlots; 143 Changed = true; 144 145 if (D == MBB.end()) 146 BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP)); 147 else 148 MBB.splice(I, &MBB, D); 149 150 unsigned structSize = 0; 151 if (needsUnimp(MI, structSize)) { 152 MachineBasicBlock::iterator J = MI; 153 ++J; // skip the delay filler. 154 assert (J != MBB.end() && "MI needs a delay instruction."); 155 BuildMI(MBB, ++J, MI->getDebugLoc(), 156 TII->get(SP::UNIMP)).addImm(structSize); 157 // Bundle the delay filler and unimp with the instruction. 158 MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), J); 159 } else { 160 MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), I); 161 } 162 } 163 return Changed; 164 } 165 166 MachineBasicBlock::iterator 167 Filler::findDelayInstr(MachineBasicBlock &MBB, 168 MachineBasicBlock::iterator slot) 169 { 170 SmallSet<unsigned, 32> RegDefs; 171 SmallSet<unsigned, 32> RegUses; 172 bool sawLoad = false; 173 bool sawStore = false; 174 175 if (slot == MBB.begin()) 176 return MBB.end(); 177 178 if (slot->getOpcode() == SP::RET || slot->getOpcode() == SP::TLS_CALL) 179 return MBB.end(); 180 181 if (slot->getOpcode() == SP::RETL) { 182 MachineBasicBlock::iterator J = slot; 183 --J; 184 185 if (J->getOpcode() == SP::RESTORErr 186 || J->getOpcode() == SP::RESTOREri) { 187 // change retl to ret. 188 slot->setDesc(Subtarget->getInstrInfo()->get(SP::RET)); 189 return J; 190 } 191 } 192 193 // Call's delay filler can def some of call's uses. 194 if (slot->isCall()) 195 insertCallDefsUses(slot, RegDefs, RegUses); 196 else 197 insertDefsUses(slot, RegDefs, RegUses); 198 199 bool done = false; 200 201 MachineBasicBlock::iterator I = slot; 202 203 while (!done) { 204 done = (I == MBB.begin()); 205 206 if (!done) 207 --I; 208 209 // skip debug instruction 210 if (I->isDebugInstr()) 211 continue; 212 213 if (I->hasUnmodeledSideEffects() || I->isInlineAsm() || I->isPosition() || 214 I->hasDelaySlot() || I->isBundledWithSucc()) 215 break; 216 217 if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) { 218 insertDefsUses(I, RegDefs, RegUses); 219 continue; 220 } 221 222 return I; 223 } 224 return MBB.end(); 225 } 226 227 bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate, 228 bool &sawLoad, 229 bool &sawStore, 230 SmallSet<unsigned, 32> &RegDefs, 231 SmallSet<unsigned, 32> &RegUses) 232 { 233 234 if (candidate->isImplicitDef() || candidate->isKill()) 235 return true; 236 237 if (candidate->mayLoad()) { 238 sawLoad = true; 239 if (sawStore) 240 return true; 241 } 242 243 if (candidate->mayStore()) { 244 if (sawStore) 245 return true; 246 sawStore = true; 247 if (sawLoad) 248 return true; 249 } 250 251 for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) { 252 const MachineOperand &MO = candidate->getOperand(i); 253 if (!MO.isReg()) 254 continue; // skip 255 256 unsigned Reg = MO.getReg(); 257 258 if (MO.isDef()) { 259 // check whether Reg is defined or used before delay slot. 260 if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg)) 261 return true; 262 } 263 if (MO.isUse()) { 264 // check whether Reg is defined before delay slot. 265 if (IsRegInSet(RegDefs, Reg)) 266 return true; 267 } 268 } 269 270 unsigned Opcode = candidate->getOpcode(); 271 // LD and LDD may have NOPs inserted afterwards in the case of some LEON 272 // processors, so we can't use the delay slot if this feature is switched-on. 273 if (Subtarget->insertNOPLoad() 274 && 275 Opcode >= SP::LDDArr && Opcode <= SP::LDrr) 276 return true; 277 278 // Same as above for FDIV and FSQRT on some LEON processors. 279 if (Subtarget->fixAllFDIVSQRT() 280 && 281 Opcode >= SP::FDIVD && Opcode <= SP::FSQRTD) 282 return true; 283 284 285 return false; 286 } 287 288 289 void Filler::insertCallDefsUses(MachineBasicBlock::iterator MI, 290 SmallSet<unsigned, 32>& RegDefs, 291 SmallSet<unsigned, 32>& RegUses) 292 { 293 // Call defines o7, which is visible to the instruction in delay slot. 294 RegDefs.insert(SP::O7); 295 296 switch(MI->getOpcode()) { 297 default: llvm_unreachable("Unknown opcode."); 298 case SP::CALL: break; 299 case SP::CALLrr: 300 case SP::CALLri: 301 assert(MI->getNumOperands() >= 2); 302 const MachineOperand &Reg = MI->getOperand(0); 303 assert(Reg.isReg() && "CALL first operand is not a register."); 304 assert(Reg.isUse() && "CALL first operand is not a use."); 305 RegUses.insert(Reg.getReg()); 306 307 const MachineOperand &Operand1 = MI->getOperand(1); 308 if (Operand1.isImm() || Operand1.isGlobal()) 309 break; 310 assert(Operand1.isReg() && "CALLrr second operand is not a register."); 311 assert(Operand1.isUse() && "CALLrr second operand is not a use."); 312 RegUses.insert(Operand1.getReg()); 313 break; 314 } 315 } 316 317 // Insert Defs and Uses of MI into the sets RegDefs and RegUses. 318 void Filler::insertDefsUses(MachineBasicBlock::iterator MI, 319 SmallSet<unsigned, 32>& RegDefs, 320 SmallSet<unsigned, 32>& RegUses) 321 { 322 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 323 const MachineOperand &MO = MI->getOperand(i); 324 if (!MO.isReg()) 325 continue; 326 327 unsigned Reg = MO.getReg(); 328 if (Reg == 0) 329 continue; 330 if (MO.isDef()) 331 RegDefs.insert(Reg); 332 if (MO.isUse()) { 333 // Implicit register uses of retl are return values and 334 // retl does not use them. 335 if (MO.isImplicit() && MI->getOpcode() == SP::RETL) 336 continue; 337 RegUses.insert(Reg); 338 } 339 } 340 } 341 342 // returns true if the Reg or its alias is in the RegSet. 343 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) 344 { 345 // Check Reg and all aliased Registers. 346 for (MCRegAliasIterator AI(Reg, Subtarget->getRegisterInfo(), true); 347 AI.isValid(); ++AI) 348 if (RegSet.count(*AI)) 349 return true; 350 return false; 351 } 352 353 bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize) 354 { 355 if (!I->isCall()) 356 return false; 357 358 unsigned structSizeOpNum = 0; 359 switch (I->getOpcode()) { 360 default: llvm_unreachable("Unknown call opcode."); 361 case SP::CALL: structSizeOpNum = 1; break; 362 case SP::CALLrr: 363 case SP::CALLri: structSizeOpNum = 2; break; 364 case SP::TLS_CALL: return false; 365 } 366 367 const MachineOperand &MO = I->getOperand(structSizeOpNum); 368 if (!MO.isImm()) 369 return false; 370 StructSize = MO.getImm(); 371 return true; 372 } 373 374 static bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI, 375 MachineBasicBlock::iterator AddMI, 376 const TargetInstrInfo *TII) 377 { 378 // Before: add <op0>, <op1>, %i[0-7] 379 // restore %g0, %g0, %i[0-7] 380 // 381 // After : restore <op0>, <op1>, %o[0-7] 382 383 unsigned reg = AddMI->getOperand(0).getReg(); 384 if (reg < SP::I0 || reg > SP::I7) 385 return false; 386 387 // Erase RESTORE. 388 RestoreMI->eraseFromParent(); 389 390 // Change ADD to RESTORE. 391 AddMI->setDesc(TII->get((AddMI->getOpcode() == SP::ADDrr) 392 ? SP::RESTORErr 393 : SP::RESTOREri)); 394 395 // Map the destination register. 396 AddMI->getOperand(0).setReg(reg - SP::I0 + SP::O0); 397 398 return true; 399 } 400 401 static bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI, 402 MachineBasicBlock::iterator OrMI, 403 const TargetInstrInfo *TII) 404 { 405 // Before: or <op0>, <op1>, %i[0-7] 406 // restore %g0, %g0, %i[0-7] 407 // and <op0> or <op1> is zero, 408 // 409 // After : restore <op0>, <op1>, %o[0-7] 410 411 unsigned reg = OrMI->getOperand(0).getReg(); 412 if (reg < SP::I0 || reg > SP::I7) 413 return false; 414 415 // check whether it is a copy. 416 if (OrMI->getOpcode() == SP::ORrr 417 && OrMI->getOperand(1).getReg() != SP::G0 418 && OrMI->getOperand(2).getReg() != SP::G0) 419 return false; 420 421 if (OrMI->getOpcode() == SP::ORri 422 && OrMI->getOperand(1).getReg() != SP::G0 423 && (!OrMI->getOperand(2).isImm() || OrMI->getOperand(2).getImm() != 0)) 424 return false; 425 426 // Erase RESTORE. 427 RestoreMI->eraseFromParent(); 428 429 // Change OR to RESTORE. 430 OrMI->setDesc(TII->get((OrMI->getOpcode() == SP::ORrr) 431 ? SP::RESTORErr 432 : SP::RESTOREri)); 433 434 // Map the destination register. 435 OrMI->getOperand(0).setReg(reg - SP::I0 + SP::O0); 436 437 return true; 438 } 439 440 static bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI, 441 MachineBasicBlock::iterator SetHiMI, 442 const TargetInstrInfo *TII) 443 { 444 // Before: sethi imm3, %i[0-7] 445 // restore %g0, %g0, %g0 446 // 447 // After : restore %g0, (imm3<<10), %o[0-7] 448 449 unsigned reg = SetHiMI->getOperand(0).getReg(); 450 if (reg < SP::I0 || reg > SP::I7) 451 return false; 452 453 if (!SetHiMI->getOperand(1).isImm()) 454 return false; 455 456 int64_t imm = SetHiMI->getOperand(1).getImm(); 457 458 // Is it a 3 bit immediate? 459 if (!isInt<3>(imm)) 460 return false; 461 462 // Make it a 13 bit immediate. 463 imm = (imm << 10) & 0x1FFF; 464 465 assert(RestoreMI->getOpcode() == SP::RESTORErr); 466 467 RestoreMI->setDesc(TII->get(SP::RESTOREri)); 468 469 RestoreMI->getOperand(0).setReg(reg - SP::I0 + SP::O0); 470 RestoreMI->getOperand(1).setReg(SP::G0); 471 RestoreMI->getOperand(2).ChangeToImmediate(imm); 472 473 474 // Erase the original SETHI. 475 SetHiMI->eraseFromParent(); 476 477 return true; 478 } 479 480 bool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB, 481 MachineBasicBlock::iterator MBBI) 482 { 483 // No previous instruction. 484 if (MBBI == MBB.begin()) 485 return false; 486 487 // assert that MBBI is a "restore %g0, %g0, %g0". 488 assert(MBBI->getOpcode() == SP::RESTORErr 489 && MBBI->getOperand(0).getReg() == SP::G0 490 && MBBI->getOperand(1).getReg() == SP::G0 491 && MBBI->getOperand(2).getReg() == SP::G0); 492 493 MachineBasicBlock::iterator PrevInst = std::prev(MBBI); 494 495 // It cannot be combined with a bundled instruction. 496 if (PrevInst->isBundledWithSucc()) 497 return false; 498 499 const TargetInstrInfo *TII = Subtarget->getInstrInfo(); 500 501 switch (PrevInst->getOpcode()) { 502 default: break; 503 case SP::ADDrr: 504 case SP::ADDri: return combineRestoreADD(MBBI, PrevInst, TII); break; 505 case SP::ORrr: 506 case SP::ORri: return combineRestoreOR(MBBI, PrevInst, TII); break; 507 case SP::SETHIi: return combineRestoreSETHIi(MBBI, PrevInst, TII); break; 508 } 509 // It cannot combine with the previous instruction. 510 return false; 511 } 512