1193323Sed//===-- DelaySlotFiller.cpp - SPARC delay slot filler ---------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10218893Sdim// This is a simple local pass that attempts to fill delay slots with useful 11218893Sdim// instructions. If no instructions can be moved into the delay slot, then a 12218893Sdim// NOP is placed. 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15218893Sdim#define DEBUG_TYPE "delay-slot-filler" 16193323Sed#include "Sparc.h" 17263509Sdim#include "SparcSubtarget.h" 18252723Sdim#include "llvm/ADT/SmallSet.h" 19252723Sdim#include "llvm/ADT/Statistic.h" 20193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 21193323Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 22263764Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 23218893Sdim#include "llvm/Support/CommandLine.h" 24252723Sdim#include "llvm/Target/TargetInstrInfo.h" 25193323Sed#include "llvm/Target/TargetMachine.h" 26218893Sdim#include "llvm/Target/TargetRegisterInfo.h" 27218893Sdim 28193323Sedusing namespace llvm; 29193323Sed 30193323SedSTATISTIC(FilledSlots, "Number of delay slots filled"); 31193323Sed 32218893Sdimstatic cl::opt<bool> DisableDelaySlotFiller( 33218893Sdim "disable-sparc-delay-filler", 34218893Sdim cl::init(false), 35218893Sdim cl::desc("Disable the Sparc delay slot filler."), 36218893Sdim cl::Hidden); 37218893Sdim 38193323Sednamespace { 39193323Sed struct Filler : public MachineFunctionPass { 40193323Sed /// Target machine description which we query for reg. names, data 41193323Sed /// layout, etc. 42193323Sed /// 43193323Sed TargetMachine &TM; 44263509Sdim const SparcSubtarget *Subtarget; 45193323Sed 46193323Sed static char ID; 47263509Sdim Filler(TargetMachine &tm) 48263509Sdim : MachineFunctionPass(ID), TM(tm), 49263509Sdim Subtarget(&TM.getSubtarget<SparcSubtarget>()) { 50263509Sdim } 51193323Sed 52193323Sed virtual const char *getPassName() const { 53193323Sed return "SPARC Delay Slot Filler"; 54193323Sed } 55193323Sed 56193323Sed bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 57193323Sed bool runOnMachineFunction(MachineFunction &F) { 58193323Sed bool Changed = false; 59263764Sdim 60263764Sdim // This pass invalidates liveness information when it reorders 61263764Sdim // instructions to fill delay slot. 62263764Sdim F.getRegInfo().invalidateLiveness(); 63263764Sdim 64193323Sed for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 65193323Sed FI != FE; ++FI) 66193323Sed Changed |= runOnMachineBasicBlock(*FI); 67193323Sed return Changed; 68193323Sed } 69193323Sed 70263509Sdim void insertCallDefsUses(MachineBasicBlock::iterator MI, 71263509Sdim SmallSet<unsigned, 32>& RegDefs, 72263509Sdim SmallSet<unsigned, 32>& RegUses); 73218893Sdim 74218893Sdim void insertDefsUses(MachineBasicBlock::iterator MI, 75218893Sdim SmallSet<unsigned, 32>& RegDefs, 76218893Sdim SmallSet<unsigned, 32>& RegUses); 77218893Sdim 78218893Sdim bool IsRegInSet(SmallSet<unsigned, 32>& RegSet, 79218893Sdim unsigned Reg); 80218893Sdim 81218893Sdim bool delayHasHazard(MachineBasicBlock::iterator candidate, 82218893Sdim bool &sawLoad, bool &sawStore, 83218893Sdim SmallSet<unsigned, 32> &RegDefs, 84218893Sdim SmallSet<unsigned, 32> &RegUses); 85218893Sdim 86218893Sdim MachineBasicBlock::iterator 87218893Sdim findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot); 88218893Sdim 89219077Sdim bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize); 90218893Sdim 91263509Sdim bool tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB, 92263509Sdim MachineBasicBlock::iterator MBBI); 93263509Sdim 94193323Sed }; 95193323Sed char Filler::ID = 0; 96193323Sed} // end of anonymous namespace 97193323Sed 98193323Sed/// createSparcDelaySlotFillerPass - Returns a pass that fills in delay 99193323Sed/// slots in Sparc MachineFunctions 100193323Sed/// 101193323SedFunctionPass *llvm::createSparcDelaySlotFillerPass(TargetMachine &tm) { 102193323Sed return new Filler(tm); 103193323Sed} 104193323Sed 105219077Sdim 106193323Sed/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 107218893Sdim/// We assume there is only one delay slot per delayed instruction. 108193323Sed/// 109193323Sedbool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 110193323Sed bool Changed = false; 111218893Sdim 112263509Sdim const TargetInstrInfo *TII = TM.getInstrInfo(); 113218893Sdim 114263509Sdim for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) { 115263509Sdim MachineBasicBlock::iterator MI = I; 116263509Sdim ++I; 117218893Sdim 118263509Sdim // If MI is restore, try combining it with previous inst. 119263509Sdim if (!DisableDelaySlotFiller && 120263509Sdim (MI->getOpcode() == SP::RESTORErr 121263509Sdim || MI->getOpcode() == SP::RESTOREri)) { 122263509Sdim Changed |= tryCombineRestoreWithPrevInst(MBB, MI); 123263509Sdim continue; 124263509Sdim } 125263509Sdim 126263509Sdim if (!Subtarget->isV9() && 127263509Sdim (MI->getOpcode() == SP::FCMPS || MI->getOpcode() == SP::FCMPD 128263509Sdim || MI->getOpcode() == SP::FCMPQ)) { 129263509Sdim BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP)); 130193323Sed Changed = true; 131263509Sdim continue; 132263509Sdim } 133218893Sdim 134263509Sdim // If MI has no delay slot, skip. 135263509Sdim if (!MI->hasDelaySlot()) 136263509Sdim continue; 137263509Sdim 138263509Sdim MachineBasicBlock::iterator D = MBB.end(); 139263509Sdim 140263509Sdim if (!DisableDelaySlotFiller) 141263509Sdim D = findDelayInstr(MBB, MI); 142263509Sdim 143263509Sdim ++FilledSlots; 144263509Sdim Changed = true; 145263509Sdim 146263509Sdim if (D == MBB.end()) 147263509Sdim BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP)); 148263509Sdim else 149263509Sdim MBB.splice(I, &MBB, D); 150263509Sdim 151263509Sdim unsigned structSize = 0; 152263509Sdim if (needsUnimp(MI, structSize)) { 153263509Sdim MachineBasicBlock::iterator J = MI; 154263509Sdim ++J; // skip the delay filler. 155263509Sdim assert (J != MBB.end() && "MI needs a delay instruction."); 156263509Sdim BuildMI(MBB, ++J, MI->getDebugLoc(), 157263509Sdim TII->get(SP::UNIMP)).addImm(structSize); 158263764Sdim // Bundle the delay filler and unimp with the instruction. 159263764Sdim MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), J); 160263764Sdim } else { 161263764Sdim MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), I); 162193323Sed } 163263509Sdim } 164193323Sed return Changed; 165193323Sed} 166218893Sdim 167218893SdimMachineBasicBlock::iterator 168218893SdimFiller::findDelayInstr(MachineBasicBlock &MBB, 169218893Sdim MachineBasicBlock::iterator slot) 170218893Sdim{ 171218893Sdim SmallSet<unsigned, 32> RegDefs; 172218893Sdim SmallSet<unsigned, 32> RegUses; 173218893Sdim bool sawLoad = false; 174218893Sdim bool sawStore = false; 175218893Sdim 176263509Sdim if (slot == MBB.begin()) 177263509Sdim return MBB.end(); 178218893Sdim 179263509Sdim if (slot->getOpcode() == SP::RET || slot->getOpcode() == SP::TLS_CALL) 180218893Sdim return MBB.end(); 181218893Sdim 182218893Sdim if (slot->getOpcode() == SP::RETL) { 183263509Sdim MachineBasicBlock::iterator J = slot; 184263509Sdim --J; 185263509Sdim 186263509Sdim if (J->getOpcode() == SP::RESTORErr 187263509Sdim || J->getOpcode() == SP::RESTOREri) { 188263509Sdim // change retl to ret. 189263509Sdim slot->setDesc(TM.getInstrInfo()->get(SP::RET)); 190263509Sdim return J; 191263509Sdim } 192218893Sdim } 193218893Sdim 194263509Sdim // Call's delay filler can def some of call's uses. 195235633Sdim if (slot->isCall()) 196263509Sdim insertCallDefsUses(slot, RegDefs, RegUses); 197218893Sdim else 198218893Sdim insertDefsUses(slot, RegDefs, RegUses); 199218893Sdim 200218893Sdim bool done = false; 201218893Sdim 202263509Sdim MachineBasicBlock::iterator I = slot; 203263509Sdim 204218893Sdim while (!done) { 205218893Sdim done = (I == MBB.begin()); 206218893Sdim 207218893Sdim if (!done) 208218893Sdim --I; 209218893Sdim 210218893Sdim // skip debug value 211218893Sdim if (I->isDebugValue()) 212218893Sdim continue; 213218893Sdim 214218893Sdim 215218893Sdim if (I->hasUnmodeledSideEffects() 216218893Sdim || I->isInlineAsm() 217218893Sdim || I->isLabel() 218235633Sdim || I->hasDelaySlot() 219263764Sdim || I->isBundledWithSucc()) 220218893Sdim break; 221218893Sdim 222218893Sdim if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) { 223218893Sdim insertDefsUses(I, RegDefs, RegUses); 224218893Sdim continue; 225218893Sdim } 226218893Sdim 227218893Sdim return I; 228218893Sdim } 229218893Sdim return MBB.end(); 230218893Sdim} 231218893Sdim 232218893Sdimbool Filler::delayHasHazard(MachineBasicBlock::iterator candidate, 233218893Sdim bool &sawLoad, 234218893Sdim bool &sawStore, 235218893Sdim SmallSet<unsigned, 32> &RegDefs, 236218893Sdim SmallSet<unsigned, 32> &RegUses) 237218893Sdim{ 238218893Sdim 239218893Sdim if (candidate->isImplicitDef() || candidate->isKill()) 240218893Sdim return true; 241218893Sdim 242235633Sdim if (candidate->mayLoad()) { 243218893Sdim sawLoad = true; 244218893Sdim if (sawStore) 245218893Sdim return true; 246218893Sdim } 247218893Sdim 248235633Sdim if (candidate->mayStore()) { 249218893Sdim if (sawStore) 250218893Sdim return true; 251218893Sdim sawStore = true; 252218893Sdim if (sawLoad) 253218893Sdim return true; 254218893Sdim } 255218893Sdim 256218893Sdim for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) { 257218893Sdim const MachineOperand &MO = candidate->getOperand(i); 258218893Sdim if (!MO.isReg()) 259218893Sdim continue; // skip 260218893Sdim 261218893Sdim unsigned Reg = MO.getReg(); 262218893Sdim 263218893Sdim if (MO.isDef()) { 264263509Sdim // check whether Reg is defined or used before delay slot. 265218893Sdim if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg)) 266218893Sdim return true; 267218893Sdim } 268218893Sdim if (MO.isUse()) { 269263509Sdim // check whether Reg is defined before delay slot. 270218893Sdim if (IsRegInSet(RegDefs, Reg)) 271218893Sdim return true; 272218893Sdim } 273218893Sdim } 274218893Sdim return false; 275218893Sdim} 276218893Sdim 277218893Sdim 278263509Sdimvoid Filler::insertCallDefsUses(MachineBasicBlock::iterator MI, 279263509Sdim SmallSet<unsigned, 32>& RegDefs, 280263509Sdim SmallSet<unsigned, 32>& RegUses) 281218893Sdim{ 282263509Sdim // Call defines o7, which is visible to the instruction in delay slot. 283263509Sdim RegDefs.insert(SP::O7); 284218893Sdim 285218893Sdim switch(MI->getOpcode()) { 286218893Sdim default: llvm_unreachable("Unknown opcode."); 287218893Sdim case SP::CALL: break; 288263764Sdim case SP::CALLrr: 289263764Sdim case SP::CALLri: 290218893Sdim assert(MI->getNumOperands() >= 2); 291218893Sdim const MachineOperand &Reg = MI->getOperand(0); 292263764Sdim assert(Reg.isReg() && "CALL first operand is not a register."); 293263764Sdim assert(Reg.isUse() && "CALL first operand is not a use."); 294218893Sdim RegUses.insert(Reg.getReg()); 295218893Sdim 296218893Sdim const MachineOperand &RegOrImm = MI->getOperand(1); 297218893Sdim if (RegOrImm.isImm()) 298218893Sdim break; 299263764Sdim assert(RegOrImm.isReg() && "CALLrr second operand is not a register."); 300263764Sdim assert(RegOrImm.isUse() && "CALLrr second operand is not a use."); 301218893Sdim RegUses.insert(RegOrImm.getReg()); 302218893Sdim break; 303218893Sdim } 304218893Sdim} 305218893Sdim 306263509Sdim// Insert Defs and Uses of MI into the sets RegDefs and RegUses. 307218893Sdimvoid Filler::insertDefsUses(MachineBasicBlock::iterator MI, 308218893Sdim SmallSet<unsigned, 32>& RegDefs, 309218893Sdim SmallSet<unsigned, 32>& RegUses) 310218893Sdim{ 311218893Sdim for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 312218893Sdim const MachineOperand &MO = MI->getOperand(i); 313218893Sdim if (!MO.isReg()) 314218893Sdim continue; 315218893Sdim 316218893Sdim unsigned Reg = MO.getReg(); 317218893Sdim if (Reg == 0) 318218893Sdim continue; 319218893Sdim if (MO.isDef()) 320218893Sdim RegDefs.insert(Reg); 321263509Sdim if (MO.isUse()) { 322263509Sdim // Implicit register uses of retl are return values and 323263509Sdim // retl does not use them. 324263509Sdim if (MO.isImplicit() && MI->getOpcode() == SP::RETL) 325263509Sdim continue; 326218893Sdim RegUses.insert(Reg); 327263509Sdim } 328218893Sdim } 329218893Sdim} 330218893Sdim 331263509Sdim// returns true if the Reg or its alias is in the RegSet. 332218893Sdimbool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) 333218893Sdim{ 334245431Sdim // Check Reg and all aliased Registers. 335245431Sdim for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true); 336245431Sdim AI.isValid(); ++AI) 337245431Sdim if (RegSet.count(*AI)) 338218893Sdim return true; 339218893Sdim return false; 340218893Sdim} 341218893Sdim 342219077Sdimbool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize) 343219077Sdim{ 344235633Sdim if (!I->isCall()) 345219077Sdim return false; 346219077Sdim 347219077Sdim unsigned structSizeOpNum = 0; 348219077Sdim switch (I->getOpcode()) { 349219077Sdim default: llvm_unreachable("Unknown call opcode."); 350219077Sdim case SP::CALL: structSizeOpNum = 1; break; 351263764Sdim case SP::CALLrr: 352263764Sdim case SP::CALLri: structSizeOpNum = 2; break; 353263509Sdim case SP::TLS_CALL: return false; 354219077Sdim } 355219077Sdim 356219077Sdim const MachineOperand &MO = I->getOperand(structSizeOpNum); 357219077Sdim if (!MO.isImm()) 358219077Sdim return false; 359219077Sdim StructSize = MO.getImm(); 360219077Sdim return true; 361219077Sdim} 362263509Sdim 363263509Sdimstatic bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI, 364263509Sdim MachineBasicBlock::iterator AddMI, 365263509Sdim const TargetInstrInfo *TII) 366263509Sdim{ 367263509Sdim // Before: add <op0>, <op1>, %i[0-7] 368263509Sdim // restore %g0, %g0, %i[0-7] 369263509Sdim // 370263509Sdim // After : restore <op0>, <op1>, %o[0-7] 371263509Sdim 372263509Sdim unsigned reg = AddMI->getOperand(0).getReg(); 373263509Sdim if (reg < SP::I0 || reg > SP::I7) 374263509Sdim return false; 375263509Sdim 376263509Sdim // Erase RESTORE. 377263509Sdim RestoreMI->eraseFromParent(); 378263509Sdim 379263509Sdim // Change ADD to RESTORE. 380263509Sdim AddMI->setDesc(TII->get((AddMI->getOpcode() == SP::ADDrr) 381263509Sdim ? SP::RESTORErr 382263509Sdim : SP::RESTOREri)); 383263509Sdim 384263509Sdim // Map the destination register. 385263509Sdim AddMI->getOperand(0).setReg(reg - SP::I0 + SP::O0); 386263509Sdim 387263509Sdim return true; 388263509Sdim} 389263509Sdim 390263509Sdimstatic bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI, 391263509Sdim MachineBasicBlock::iterator OrMI, 392263509Sdim const TargetInstrInfo *TII) 393263509Sdim{ 394263509Sdim // Before: or <op0>, <op1>, %i[0-7] 395263509Sdim // restore %g0, %g0, %i[0-7] 396263509Sdim // and <op0> or <op1> is zero, 397263509Sdim // 398263509Sdim // After : restore <op0>, <op1>, %o[0-7] 399263509Sdim 400263509Sdim unsigned reg = OrMI->getOperand(0).getReg(); 401263509Sdim if (reg < SP::I0 || reg > SP::I7) 402263509Sdim return false; 403263509Sdim 404263509Sdim // check whether it is a copy. 405263509Sdim if (OrMI->getOpcode() == SP::ORrr 406263509Sdim && OrMI->getOperand(1).getReg() != SP::G0 407263509Sdim && OrMI->getOperand(2).getReg() != SP::G0) 408263509Sdim return false; 409263509Sdim 410263509Sdim if (OrMI->getOpcode() == SP::ORri 411263509Sdim && OrMI->getOperand(1).getReg() != SP::G0 412263509Sdim && (!OrMI->getOperand(2).isImm() || OrMI->getOperand(2).getImm() != 0)) 413263509Sdim return false; 414263509Sdim 415263509Sdim // Erase RESTORE. 416263509Sdim RestoreMI->eraseFromParent(); 417263509Sdim 418263509Sdim // Change OR to RESTORE. 419263509Sdim OrMI->setDesc(TII->get((OrMI->getOpcode() == SP::ORrr) 420263509Sdim ? SP::RESTORErr 421263509Sdim : SP::RESTOREri)); 422263509Sdim 423263509Sdim // Map the destination register. 424263509Sdim OrMI->getOperand(0).setReg(reg - SP::I0 + SP::O0); 425263509Sdim 426263509Sdim return true; 427263509Sdim} 428263509Sdim 429263509Sdimstatic bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI, 430263509Sdim MachineBasicBlock::iterator SetHiMI, 431263509Sdim const TargetInstrInfo *TII) 432263509Sdim{ 433263509Sdim // Before: sethi imm3, %i[0-7] 434263509Sdim // restore %g0, %g0, %g0 435263509Sdim // 436263509Sdim // After : restore %g0, (imm3<<10), %o[0-7] 437263509Sdim 438263509Sdim unsigned reg = SetHiMI->getOperand(0).getReg(); 439263509Sdim if (reg < SP::I0 || reg > SP::I7) 440263509Sdim return false; 441263509Sdim 442263509Sdim if (!SetHiMI->getOperand(1).isImm()) 443263509Sdim return false; 444263509Sdim 445263509Sdim int64_t imm = SetHiMI->getOperand(1).getImm(); 446263509Sdim 447263509Sdim // Is it a 3 bit immediate? 448263509Sdim if (!isInt<3>(imm)) 449263509Sdim return false; 450263509Sdim 451263509Sdim // Make it a 13 bit immediate. 452263509Sdim imm = (imm << 10) & 0x1FFF; 453263509Sdim 454263509Sdim assert(RestoreMI->getOpcode() == SP::RESTORErr); 455263509Sdim 456263509Sdim RestoreMI->setDesc(TII->get(SP::RESTOREri)); 457263509Sdim 458263509Sdim RestoreMI->getOperand(0).setReg(reg - SP::I0 + SP::O0); 459263509Sdim RestoreMI->getOperand(1).setReg(SP::G0); 460263509Sdim RestoreMI->getOperand(2).ChangeToImmediate(imm); 461263509Sdim 462263509Sdim 463263509Sdim // Erase the original SETHI. 464263509Sdim SetHiMI->eraseFromParent(); 465263509Sdim 466263509Sdim return true; 467263509Sdim} 468263509Sdim 469263509Sdimbool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB, 470263509Sdim MachineBasicBlock::iterator MBBI) 471263509Sdim{ 472263509Sdim // No previous instruction. 473263509Sdim if (MBBI == MBB.begin()) 474263509Sdim return false; 475263509Sdim 476263509Sdim // assert that MBBI is a "restore %g0, %g0, %g0". 477263509Sdim assert(MBBI->getOpcode() == SP::RESTORErr 478263509Sdim && MBBI->getOperand(0).getReg() == SP::G0 479263509Sdim && MBBI->getOperand(1).getReg() == SP::G0 480263509Sdim && MBBI->getOperand(2).getReg() == SP::G0); 481263509Sdim 482263764Sdim MachineBasicBlock::iterator PrevInst = llvm::prior(MBBI); 483263509Sdim 484263764Sdim // It cannot be combined with a bundled instruction. 485263764Sdim if (PrevInst->isBundledWithSucc()) 486263509Sdim return false; 487263509Sdim 488263509Sdim const TargetInstrInfo *TII = TM.getInstrInfo(); 489263509Sdim 490263509Sdim switch (PrevInst->getOpcode()) { 491263509Sdim default: break; 492263509Sdim case SP::ADDrr: 493263509Sdim case SP::ADDri: return combineRestoreADD(MBBI, PrevInst, TII); break; 494263509Sdim case SP::ORrr: 495263509Sdim case SP::ORri: return combineRestoreOR(MBBI, PrevInst, TII); break; 496263509Sdim case SP::SETHIi: return combineRestoreSETHIi(MBBI, PrevInst, TII); break; 497263509Sdim } 498263509Sdim // It cannot combine with the previous instruction. 499263509Sdim return false; 500263509Sdim} 501