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