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