MipsDelaySlotFiller.cpp revision e760675b0ed8d7adcc2c991a2d645d2b538a5ab3
1//===-- MipsDelaySlotFiller.cpp - Mips 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// Simple pass to fill delay slots with useful instructions. 11// 12//===----------------------------------------------------------------------===// 13 14#define DEBUG_TYPE "delay-slot-filler" 15 16#include "Mips.h" 17#include "MipsTargetMachine.h" 18#include "llvm/ADT/BitVector.h" 19#include "llvm/ADT/SmallPtrSet.h" 20#include "llvm/ADT/Statistic.h" 21#include "llvm/Analysis/AliasAnalysis.h" 22#include "llvm/Analysis/ValueTracking.h" 23#include "llvm/CodeGen/MachineFunctionPass.h" 24#include "llvm/CodeGen/MachineInstrBuilder.h" 25#include "llvm/CodeGen/PseudoSourceValue.h" 26#include "llvm/Support/CommandLine.h" 27#include "llvm/Target/TargetInstrInfo.h" 28#include "llvm/Target/TargetMachine.h" 29#include "llvm/Target/TargetRegisterInfo.h" 30 31using namespace llvm; 32 33STATISTIC(FilledSlots, "Number of delay slots filled"); 34STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 35 " are not NOP."); 36 37static cl::opt<bool> DisableDelaySlotFiller( 38 "disable-mips-delay-filler", 39 cl::init(false), 40 cl::desc("Fill all delay slots with NOPs."), 41 cl::Hidden); 42 43// This option can be used to silence complaints by machine verifier passes. 44static cl::opt<bool> SkipDelaySlotFiller( 45 "skip-mips-delay-filler", 46 cl::init(false), 47 cl::desc("Skip MIPS' delay slot filling pass."), 48 cl::Hidden); 49 50static cl::opt<bool> DisableForwardSearch( 51 "disable-mips-df-forward-search", 52 cl::init(true), 53 cl::desc("Disallow MIPS delay filler to search forward."), 54 cl::Hidden); 55 56namespace { 57 class RegDefsUses { 58 public: 59 RegDefsUses(TargetMachine &TM); 60 void init(const MachineInstr &MI); 61 62 /// This function sets all caller-saved registers in Defs. 63 void setCallerSaved(const MachineInstr &MI); 64 65 bool update(const MachineInstr &MI, unsigned Begin, unsigned End); 66 67 private: 68 bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg, 69 bool IsDef) const; 70 71 /// Returns true if Reg or its alias is in RegSet. 72 bool isRegInSet(const BitVector &RegSet, unsigned Reg) const; 73 74 const TargetRegisterInfo &TRI; 75 BitVector Defs, Uses; 76 }; 77 78 /// Base class for inspecting loads and stores. 79 class InspectMemInstr { 80 public: 81 virtual bool hasHazard(const MachineInstr &MI) = 0; 82 virtual ~InspectMemInstr() {} 83 }; 84 85 /// This subclass rejects any memory instructions. 86 class NoMemInstr : public InspectMemInstr { 87 public: 88 virtual bool hasHazard(const MachineInstr &MI); 89 }; 90 91 /// This subclass uses memory dependence information to determine whether a 92 /// memory instruction can be moved to a delay slot. 93 class MemDefsUses : public InspectMemInstr { 94 public: 95 MemDefsUses(const MachineFrameInfo *MFI); 96 97 /// Return true if MI cannot be moved to delay slot. 98 virtual bool hasHazard(const MachineInstr &MI); 99 100 private: 101 /// Update Defs and Uses. Return true if there exist dependences that 102 /// disqualify the delay slot candidate between V and values in Uses and Defs. 103 bool updateDefsUses(const Value *V, bool MayStore); 104 105 /// Get the list of underlying objects of MI's memory operand. 106 bool getUnderlyingObjects(const MachineInstr &MI, 107 SmallVectorImpl<const Value *> &Objects) const; 108 109 const MachineFrameInfo *MFI; 110 SmallPtrSet<const Value*, 4> Uses, Defs; 111 112 /// Flags indicating whether loads or stores have been seen. 113 bool SeenLoad, SeenStore; 114 115 /// Flags indicating whether loads or stores with no underlying objects have 116 /// been seen. 117 bool SeenNoObjLoad, SeenNoObjStore; 118 119 /// Memory instructions are not allowed to move to delay slot if this flag 120 /// is true. 121 bool ForbidMemInstr; 122 }; 123 124 class Filler : public MachineFunctionPass { 125 public: 126 Filler(TargetMachine &tm) 127 : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } 128 129 virtual const char *getPassName() const { 130 return "Mips Delay Slot Filler"; 131 } 132 133 bool runOnMachineFunction(MachineFunction &F) { 134 if (SkipDelaySlotFiller) 135 return false; 136 137 bool Changed = false; 138 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 139 FI != FE; ++FI) 140 Changed |= runOnMachineBasicBlock(*FI); 141 return Changed; 142 } 143 144 private: 145 typedef MachineBasicBlock::iterator Iter; 146 typedef MachineBasicBlock::reverse_iterator ReverseIter; 147 148 bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 149 150 /// This function checks if it is valid to move Candidate to the delay slot 151 /// and returns true if it isn't. It also updates memory and register 152 /// dependence information. 153 bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, 154 InspectMemInstr &IM) const; 155 156 /// This function searches range [Begin, End) for an instruction that can be 157 /// moved to the delay slot. Returns true on success. 158 template<typename IterTy> 159 bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, 160 RegDefsUses &RegDU, InspectMemInstr &IM, IterTy &Filler) const; 161 162 /// This function searches in the backward direction for an instruction that 163 /// can be moved to the delay slot. Returns true on success. 164 bool searchBackward(MachineBasicBlock &MBB, Iter Slot) const; 165 166 /// This function searches MBB in the forward direction for an instruction 167 /// that can be moved to the delay slot. Returns true on success. 168 bool searchForward(MachineBasicBlock &MBB, Iter Slot) const; 169 170 bool terminateSearch(const MachineInstr &Candidate) const; 171 172 TargetMachine &TM; 173 const TargetInstrInfo *TII; 174 175 static char ID; 176 }; 177 char Filler::ID = 0; 178} // end of anonymous namespace 179 180RegDefsUses::RegDefsUses(TargetMachine &TM) 181 : TRI(*TM.getRegisterInfo()), Defs(TRI.getNumRegs(), false), 182 Uses(TRI.getNumRegs(), false) {} 183 184void RegDefsUses::init(const MachineInstr &MI) { 185 // Add all register operands which are explicit and non-variadic. 186 update(MI, 0, MI.getDesc().getNumOperands()); 187 188 // If MI is a call, add RA to Defs to prevent users of RA from going into 189 // delay slot. 190 if (MI.isCall()) 191 Defs.set(Mips::RA); 192 193 // Add all implicit register operands of branch instructions except 194 // register AT. 195 if (MI.isBranch()) { 196 update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands()); 197 Defs.reset(Mips::AT); 198 } 199} 200 201void RegDefsUses::setCallerSaved(const MachineInstr &MI) { 202 assert(MI.isCall()); 203 204 // If MI is a call, add all caller-saved registers to Defs. 205 BitVector CallerSavedRegs(TRI.getNumRegs(), true); 206 207 CallerSavedRegs.reset(Mips::ZERO); 208 CallerSavedRegs.reset(Mips::ZERO_64); 209 210 for (const MCPhysReg *R = TRI.getCalleeSavedRegs(); *R; ++R) 211 for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI) 212 CallerSavedRegs.reset(*AI); 213 214 Defs |= CallerSavedRegs; 215} 216 217bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) { 218 BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs()); 219 bool HasHazard = false; 220 221 for (unsigned I = Begin; I != End; ++I) { 222 const MachineOperand &MO = MI.getOperand(I); 223 224 if (MO.isReg() && MO.getReg()) 225 HasHazard |= checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef()); 226 } 227 228 Defs |= NewDefs; 229 Uses |= NewUses; 230 231 return HasHazard; 232} 233 234bool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, 235 unsigned Reg, bool IsDef) const { 236 if (IsDef) { 237 NewDefs.set(Reg); 238 // check whether Reg has already been defined or used. 239 return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg)); 240 } 241 242 NewUses.set(Reg); 243 // check whether Reg has already been defined. 244 return isRegInSet(Defs, Reg); 245} 246 247bool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const { 248 // Check Reg and all aliased Registers. 249 for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI) 250 if (RegSet.test(*AI)) 251 return true; 252 return false; 253} 254 255bool NoMemInstr::hasHazard(const MachineInstr &MI) { 256 // Return true if MI accesses memory. 257 return (MI.mayStore() || MI.mayLoad()); 258} 259 260MemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_) 261 : MFI(MFI_), SeenLoad(false), SeenStore(false), SeenNoObjLoad(false), 262 SeenNoObjStore(false), ForbidMemInstr(false) {} 263 264bool MemDefsUses::hasHazard(const MachineInstr &MI) { 265 if (!MI.mayStore() && !MI.mayLoad()) 266 return false; 267 268 if (ForbidMemInstr) 269 return true; 270 271 bool OrigSeenLoad = SeenLoad, OrigSeenStore = SeenStore; 272 273 SeenLoad |= MI.mayLoad(); 274 SeenStore |= MI.mayStore(); 275 276 // If MI is an ordered or volatile memory reference, disallow moving 277 // subsequent loads and stores to delay slot. 278 if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) { 279 ForbidMemInstr = true; 280 return true; 281 } 282 283 bool HasHazard = false; 284 SmallVector<const Value *, 4> Objs; 285 286 // Check underlying object list. 287 if (getUnderlyingObjects(MI, Objs)) { 288 for (SmallVector<const Value *, 4>::const_iterator I = Objs.begin(); 289 I != Objs.end(); ++I) 290 HasHazard |= updateDefsUses(*I, MI.mayStore()); 291 292 return HasHazard; 293 } 294 295 // No underlying objects found. 296 HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore); 297 HasHazard |= MI.mayLoad() || OrigSeenStore; 298 299 SeenNoObjLoad |= MI.mayLoad(); 300 SeenNoObjStore |= MI.mayStore(); 301 302 return HasHazard; 303} 304 305bool MemDefsUses::updateDefsUses(const Value *V, bool MayStore) { 306 if (MayStore) 307 return !Defs.insert(V) || Uses.count(V) || SeenNoObjStore || SeenNoObjLoad; 308 309 Uses.insert(V); 310 return Defs.count(V) || SeenNoObjStore; 311} 312 313bool MemDefsUses:: 314getUnderlyingObjects(const MachineInstr &MI, 315 SmallVectorImpl<const Value *> &Objects) const { 316 if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getValue()) 317 return false; 318 319 const Value *V = (*MI.memoperands_begin())->getValue(); 320 321 SmallVector<Value *, 4> Objs; 322 GetUnderlyingObjects(const_cast<Value *>(V), Objs); 323 324 for (SmallVector<Value*, 4>::iterator I = Objs.begin(), E = Objs.end(); 325 I != E; ++I) { 326 if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(*I)) { 327 if (PSV->isAliased(MFI)) 328 return false; 329 } else if (!isIdentifiedObject(V)) 330 return false; 331 332 Objects.push_back(*I); 333 } 334 335 return true; 336} 337 338/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 339/// We assume there is only one delay slot per delayed instruction. 340bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 341 bool Changed = false; 342 343 for (Iter I = MBB.begin(); I != MBB.end(); ++I) { 344 if (!I->hasDelaySlot()) 345 continue; 346 347 ++FilledSlots; 348 Changed = true; 349 350 // Delay slot filling is disabled at -O0. 351 if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None) && 352 (searchBackward(MBB, I) || searchForward(MBB, I))) 353 continue; 354 355 // Bundle the NOP to the instruction with the delay slot. 356 BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); 357 MIBundleBuilder(MBB, I, llvm::next(llvm::next(I))); 358 } 359 360 return Changed; 361} 362 363/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 364/// slots in Mips MachineFunctions 365FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 366 return new Filler(tm); 367} 368 369template<typename IterTy> 370bool Filler::searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, 371 RegDefsUses &RegDU, InspectMemInstr& IM, 372 IterTy &Filler) const { 373 for (IterTy I = Begin; I != End; ++I) { 374 // skip debug value 375 if (I->isDebugValue()) 376 continue; 377 378 if (terminateSearch(*I)) 379 break; 380 381 assert((!I->isCall() && !I->isReturn() && !I->isBranch()) && 382 "Cannot put calls, returns or branches in delay slot."); 383 384 if (delayHasHazard(*I, RegDU, IM)) 385 continue; 386 387 Filler = I; 388 return true; 389 } 390 391 return false; 392} 393 394bool Filler::searchBackward(MachineBasicBlock &MBB, Iter Slot) const { 395 RegDefsUses RegDU(TM); 396 MemDefsUses MemDU(MBB.getParent()->getFrameInfo()); 397 ReverseIter Filler; 398 399 RegDU.init(*Slot); 400 401 if (searchRange(MBB, ReverseIter(Slot), MBB.rend(), RegDU, MemDU, Filler)) { 402 MBB.splice(llvm::next(Slot), &MBB, llvm::next(Filler).base()); 403 MIBundleBuilder(MBB, Slot, llvm::next(llvm::next(Slot))); 404 ++UsefulSlots; 405 return true; 406 } 407 408 return false; 409} 410 411bool Filler::searchForward(MachineBasicBlock &MBB, Iter Slot) const { 412 // Can handle only calls. 413 if (!Slot->isCall()) 414 return false; 415 416 RegDefsUses RegDU(TM); 417 NoMemInstr NM; 418 Iter Filler; 419 420 RegDU.setCallerSaved(*Slot); 421 422 if (searchRange(MBB, llvm::next(Slot), MBB.end(), RegDU, NM, Filler)) { 423 MBB.splice(llvm::next(Slot), &MBB, Filler); 424 MIBundleBuilder(MBB, Slot, llvm::next(llvm::next(Slot))); 425 ++UsefulSlots; 426 return true; 427 } 428 429 return false; 430} 431 432bool Filler::delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, 433 InspectMemInstr &IM) const { 434 bool HasHazard = (Candidate.isImplicitDef() || Candidate.isKill()); 435 436 HasHazard |= IM.hasHazard(Candidate); 437 HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands()); 438 439 return HasHazard; 440} 441 442bool Filler::terminateSearch(const MachineInstr &Candidate) const { 443 return (Candidate.isTerminator() || Candidate.isCall() || 444 Candidate.isLabel() || Candidate.isInlineAsm() || 445 Candidate.hasUnmodeledSideEffects()); 446} 447