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" 17263508Sdim#include "SparcSubtarget.h" 18249423Sdim#include "llvm/ADT/SmallSet.h" 19249423Sdim#include "llvm/ADT/Statistic.h" 20193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 21193323Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 22263763Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 23218893Sdim#include "llvm/Support/CommandLine.h" 24249423Sdim#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; 44263508Sdim const SparcSubtarget *Subtarget; 45193323Sed 46193323Sed static char ID; 47263508Sdim Filler(TargetMachine &tm) 48263508Sdim : MachineFunctionPass(ID), TM(tm), 49263508Sdim Subtarget(&TM.getSubtarget<SparcSubtarget>()) { 50263508Sdim } 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; 59263763Sdim 60263763Sdim // This pass invalidates liveness information when it reorders 61263763Sdim // instructions to fill delay slot. 62263763Sdim F.getRegInfo().invalidateLiveness(); 63263763Sdim 64193323Sed for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 65193323Sed FI != FE; ++FI) 66193323Sed Changed |= runOnMachineBasicBlock(*FI); 67193323Sed return Changed; 68193323Sed } 69193323Sed 70263508Sdim void insertCallDefsUses(MachineBasicBlock::iterator MI, 71263508Sdim SmallSet<unsigned, 32>& RegDefs, 72263508Sdim 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 91263508Sdim bool tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB, 92263508Sdim MachineBasicBlock::iterator MBBI); 93263508Sdim 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 112263508Sdim const TargetInstrInfo *TII = TM.getInstrInfo(); 113218893Sdim 114263508Sdim for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) { 115263508Sdim MachineBasicBlock::iterator MI = I; 116263508Sdim ++I; 117218893Sdim 118263508Sdim // If MI is restore, try combining it with previous inst. 119263508Sdim if (!DisableDelaySlotFiller && 120263508Sdim (MI->getOpcode() == SP::RESTORErr 121263508Sdim || MI->getOpcode() == SP::RESTOREri)) { 122263508Sdim Changed |= tryCombineRestoreWithPrevInst(MBB, MI); 123263508Sdim continue; 124263508Sdim } 125263508Sdim 126263508Sdim if (!Subtarget->isV9() && 127263508Sdim (MI->getOpcode() == SP::FCMPS || MI->getOpcode() == SP::FCMPD 128263508Sdim || MI->getOpcode() == SP::FCMPQ)) { 129263508Sdim BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP)); 130193323Sed Changed = true; 131263508Sdim continue; 132263508Sdim } 133218893Sdim 134263508Sdim // If MI has no delay slot, skip. 135263508Sdim if (!MI->hasDelaySlot()) 136263508Sdim continue; 137263508Sdim 138263508Sdim MachineBasicBlock::iterator D = MBB.end(); 139263508Sdim 140263508Sdim if (!DisableDelaySlotFiller) 141263508Sdim D = findDelayInstr(MBB, MI); 142263508Sdim 143263508Sdim ++FilledSlots; 144263508Sdim Changed = true; 145263508Sdim 146263508Sdim if (D == MBB.end()) 147263508Sdim BuildMI(MBB, I, MI->getDebugLoc(), TII->get(SP::NOP)); 148263508Sdim else 149263508Sdim MBB.splice(I, &MBB, D); 150263508Sdim 151263508Sdim unsigned structSize = 0; 152263508Sdim if (needsUnimp(MI, structSize)) { 153263508Sdim MachineBasicBlock::iterator J = MI; 154263508Sdim ++J; // skip the delay filler. 155263508Sdim assert (J != MBB.end() && "MI needs a delay instruction."); 156263508Sdim BuildMI(MBB, ++J, MI->getDebugLoc(), 157263508Sdim TII->get(SP::UNIMP)).addImm(structSize); 158263763Sdim // Bundle the delay filler and unimp with the instruction. 159263763Sdim MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), J); 160263763Sdim } else { 161263763Sdim MIBundleBuilder(MBB, MachineBasicBlock::iterator(MI), I); 162193323Sed } 163263508Sdim } 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 176263508Sdim if (slot == MBB.begin()) 177263508Sdim return MBB.end(); 178218893Sdim 179263508Sdim if (slot->getOpcode() == SP::RET || slot->getOpcode() == SP::TLS_CALL) 180218893Sdim return MBB.end(); 181218893Sdim 182218893Sdim if (slot->getOpcode() == SP::RETL) { 183263508Sdim MachineBasicBlock::iterator J = slot; 184263508Sdim --J; 185263508Sdim 186263508Sdim if (J->getOpcode() == SP::RESTORErr 187263508Sdim || J->getOpcode() == SP::RESTOREri) { 188263508Sdim // change retl to ret. 189263508Sdim slot->setDesc(TM.getInstrInfo()->get(SP::RET)); 190263508Sdim return J; 191263508Sdim } 192218893Sdim } 193218893Sdim 194263508Sdim // Call's delay filler can def some of call's uses. 195234353Sdim if (slot->isCall()) 196263508Sdim insertCallDefsUses(slot, RegDefs, RegUses); 197218893Sdim else 198218893Sdim insertDefsUses(slot, RegDefs, RegUses); 199218893Sdim 200218893Sdim bool done = false; 201218893Sdim 202263508Sdim MachineBasicBlock::iterator I = slot; 203263508Sdim 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() 218234353Sdim || I->hasDelaySlot() 219263763Sdim || 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 242234353Sdim if (candidate->mayLoad()) { 243218893Sdim sawLoad = true; 244218893Sdim if (sawStore) 245218893Sdim return true; 246218893Sdim } 247218893Sdim 248234353Sdim 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()) { 264263508Sdim // 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()) { 269263508Sdim // check whether Reg is defined before delay slot. 270218893Sdim if (IsRegInSet(RegDefs, Reg)) 271218893Sdim return true; 272218893Sdim } 273218893Sdim } 274218893Sdim return false; 275218893Sdim} 276218893Sdim 277218893Sdim 278263508Sdimvoid Filler::insertCallDefsUses(MachineBasicBlock::iterator MI, 279263508Sdim SmallSet<unsigned, 32>& RegDefs, 280263508Sdim SmallSet<unsigned, 32>& RegUses) 281218893Sdim{ 282263508Sdim // Call defines o7, which is visible to the instruction in delay slot. 283263508Sdim RegDefs.insert(SP::O7); 284218893Sdim 285218893Sdim switch(MI->getOpcode()) { 286218893Sdim default: llvm_unreachable("Unknown opcode."); 287218893Sdim case SP::CALL: break; 288263763Sdim case SP::CALLrr: 289263763Sdim case SP::CALLri: 290218893Sdim assert(MI->getNumOperands() >= 2); 291218893Sdim const MachineOperand &Reg = MI->getOperand(0); 292263763Sdim assert(Reg.isReg() && "CALL first operand is not a register."); 293263763Sdim 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; 299263763Sdim assert(RegOrImm.isReg() && "CALLrr second operand is not a register."); 300263763Sdim assert(RegOrImm.isUse() && "CALLrr second operand is not a use."); 301218893Sdim RegUses.insert(RegOrImm.getReg()); 302218893Sdim break; 303218893Sdim } 304218893Sdim} 305218893Sdim 306263508Sdim// 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); 321263508Sdim if (MO.isUse()) { 322263508Sdim // Implicit register uses of retl are return values and 323263508Sdim // retl does not use them. 324263508Sdim if (MO.isImplicit() && MI->getOpcode() == SP::RETL) 325263508Sdim continue; 326218893Sdim RegUses.insert(Reg); 327263508Sdim } 328218893Sdim } 329218893Sdim} 330218893Sdim 331263508Sdim// returns true if the Reg or its alias is in the RegSet. 332218893Sdimbool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) 333218893Sdim{ 334239462Sdim // Check Reg and all aliased Registers. 335239462Sdim for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true); 336239462Sdim AI.isValid(); ++AI) 337239462Sdim if (RegSet.count(*AI)) 338218893Sdim return true; 339218893Sdim return false; 340218893Sdim} 341218893Sdim 342219077Sdimbool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize) 343219077Sdim{ 344234353Sdim 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; 351263763Sdim case SP::CALLrr: 352263763Sdim case SP::CALLri: structSizeOpNum = 2; break; 353263508Sdim 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} 362263508Sdim 363263508Sdimstatic bool combineRestoreADD(MachineBasicBlock::iterator RestoreMI, 364263508Sdim MachineBasicBlock::iterator AddMI, 365263508Sdim const TargetInstrInfo *TII) 366263508Sdim{ 367263508Sdim // Before: add <op0>, <op1>, %i[0-7] 368263508Sdim // restore %g0, %g0, %i[0-7] 369263508Sdim // 370263508Sdim // After : restore <op0>, <op1>, %o[0-7] 371263508Sdim 372263508Sdim unsigned reg = AddMI->getOperand(0).getReg(); 373263508Sdim if (reg < SP::I0 || reg > SP::I7) 374263508Sdim return false; 375263508Sdim 376263508Sdim // Erase RESTORE. 377263508Sdim RestoreMI->eraseFromParent(); 378263508Sdim 379263508Sdim // Change ADD to RESTORE. 380263508Sdim AddMI->setDesc(TII->get((AddMI->getOpcode() == SP::ADDrr) 381263508Sdim ? SP::RESTORErr 382263508Sdim : SP::RESTOREri)); 383263508Sdim 384263508Sdim // Map the destination register. 385263508Sdim AddMI->getOperand(0).setReg(reg - SP::I0 + SP::O0); 386263508Sdim 387263508Sdim return true; 388263508Sdim} 389263508Sdim 390263508Sdimstatic bool combineRestoreOR(MachineBasicBlock::iterator RestoreMI, 391263508Sdim MachineBasicBlock::iterator OrMI, 392263508Sdim const TargetInstrInfo *TII) 393263508Sdim{ 394263508Sdim // Before: or <op0>, <op1>, %i[0-7] 395263508Sdim // restore %g0, %g0, %i[0-7] 396263508Sdim // and <op0> or <op1> is zero, 397263508Sdim // 398263508Sdim // After : restore <op0>, <op1>, %o[0-7] 399263508Sdim 400263508Sdim unsigned reg = OrMI->getOperand(0).getReg(); 401263508Sdim if (reg < SP::I0 || reg > SP::I7) 402263508Sdim return false; 403263508Sdim 404263508Sdim // check whether it is a copy. 405263508Sdim if (OrMI->getOpcode() == SP::ORrr 406263508Sdim && OrMI->getOperand(1).getReg() != SP::G0 407263508Sdim && OrMI->getOperand(2).getReg() != SP::G0) 408263508Sdim return false; 409263508Sdim 410263508Sdim if (OrMI->getOpcode() == SP::ORri 411263508Sdim && OrMI->getOperand(1).getReg() != SP::G0 412263508Sdim && (!OrMI->getOperand(2).isImm() || OrMI->getOperand(2).getImm() != 0)) 413263508Sdim return false; 414263508Sdim 415263508Sdim // Erase RESTORE. 416263508Sdim RestoreMI->eraseFromParent(); 417263508Sdim 418263508Sdim // Change OR to RESTORE. 419263508Sdim OrMI->setDesc(TII->get((OrMI->getOpcode() == SP::ORrr) 420263508Sdim ? SP::RESTORErr 421263508Sdim : SP::RESTOREri)); 422263508Sdim 423263508Sdim // Map the destination register. 424263508Sdim OrMI->getOperand(0).setReg(reg - SP::I0 + SP::O0); 425263508Sdim 426263508Sdim return true; 427263508Sdim} 428263508Sdim 429263508Sdimstatic bool combineRestoreSETHIi(MachineBasicBlock::iterator RestoreMI, 430263508Sdim MachineBasicBlock::iterator SetHiMI, 431263508Sdim const TargetInstrInfo *TII) 432263508Sdim{ 433263508Sdim // Before: sethi imm3, %i[0-7] 434263508Sdim // restore %g0, %g0, %g0 435263508Sdim // 436263508Sdim // After : restore %g0, (imm3<<10), %o[0-7] 437263508Sdim 438263508Sdim unsigned reg = SetHiMI->getOperand(0).getReg(); 439263508Sdim if (reg < SP::I0 || reg > SP::I7) 440263508Sdim return false; 441263508Sdim 442263508Sdim if (!SetHiMI->getOperand(1).isImm()) 443263508Sdim return false; 444263508Sdim 445263508Sdim int64_t imm = SetHiMI->getOperand(1).getImm(); 446263508Sdim 447263508Sdim // Is it a 3 bit immediate? 448263508Sdim if (!isInt<3>(imm)) 449263508Sdim return false; 450263508Sdim 451263508Sdim // Make it a 13 bit immediate. 452263508Sdim imm = (imm << 10) & 0x1FFF; 453263508Sdim 454263508Sdim assert(RestoreMI->getOpcode() == SP::RESTORErr); 455263508Sdim 456263508Sdim RestoreMI->setDesc(TII->get(SP::RESTOREri)); 457263508Sdim 458263508Sdim RestoreMI->getOperand(0).setReg(reg - SP::I0 + SP::O0); 459263508Sdim RestoreMI->getOperand(1).setReg(SP::G0); 460263508Sdim RestoreMI->getOperand(2).ChangeToImmediate(imm); 461263508Sdim 462263508Sdim 463263508Sdim // Erase the original SETHI. 464263508Sdim SetHiMI->eraseFromParent(); 465263508Sdim 466263508Sdim return true; 467263508Sdim} 468263508Sdim 469263508Sdimbool Filler::tryCombineRestoreWithPrevInst(MachineBasicBlock &MBB, 470263508Sdim MachineBasicBlock::iterator MBBI) 471263508Sdim{ 472263508Sdim // No previous instruction. 473263508Sdim if (MBBI == MBB.begin()) 474263508Sdim return false; 475263508Sdim 476263508Sdim // assert that MBBI is a "restore %g0, %g0, %g0". 477263508Sdim assert(MBBI->getOpcode() == SP::RESTORErr 478263508Sdim && MBBI->getOperand(0).getReg() == SP::G0 479263508Sdim && MBBI->getOperand(1).getReg() == SP::G0 480263508Sdim && MBBI->getOperand(2).getReg() == SP::G0); 481263508Sdim 482263763Sdim MachineBasicBlock::iterator PrevInst = llvm::prior(MBBI); 483263508Sdim 484263763Sdim // It cannot be combined with a bundled instruction. 485263763Sdim if (PrevInst->isBundledWithSucc()) 486263508Sdim return false; 487263508Sdim 488263508Sdim const TargetInstrInfo *TII = TM.getInstrInfo(); 489263508Sdim 490263508Sdim switch (PrevInst->getOpcode()) { 491263508Sdim default: break; 492263508Sdim case SP::ADDrr: 493263508Sdim case SP::ADDri: return combineRestoreADD(MBBI, PrevInst, TII); break; 494263508Sdim case SP::ORrr: 495263508Sdim case SP::ORri: return combineRestoreOR(MBBI, PrevInst, TII); break; 496263508Sdim case SP::SETHIi: return combineRestoreSETHIi(MBBI, PrevInst, TII); break; 497263508Sdim } 498263508Sdim // It cannot combine with the previous instruction. 499263508Sdim return false; 500263508Sdim} 501