MipsDelaySlotFiller.cpp revision 280031
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#include "MCTargetDesc/MipsMCNaCl.h" 15#include "Mips.h" 16#include "MipsInstrInfo.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/MachineBranchProbabilityInfo.h" 24#include "llvm/CodeGen/MachineFunctionPass.h" 25#include "llvm/CodeGen/MachineInstrBuilder.h" 26#include "llvm/CodeGen/MachineRegisterInfo.h" 27#include "llvm/CodeGen/PseudoSourceValue.h" 28#include "llvm/Support/CommandLine.h" 29#include "llvm/Target/TargetInstrInfo.h" 30#include "llvm/Target/TargetMachine.h" 31#include "llvm/Target/TargetRegisterInfo.h" 32 33using namespace llvm; 34 35#define DEBUG_TYPE "delay-slot-filler" 36 37STATISTIC(FilledSlots, "Number of delay slots filled"); 38STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 39 " are not NOP."); 40 41static cl::opt<bool> DisableDelaySlotFiller( 42 "disable-mips-delay-filler", 43 cl::init(false), 44 cl::desc("Fill all delay slots with NOPs."), 45 cl::Hidden); 46 47static cl::opt<bool> DisableForwardSearch( 48 "disable-mips-df-forward-search", 49 cl::init(true), 50 cl::desc("Disallow MIPS delay filler to search forward."), 51 cl::Hidden); 52 53static cl::opt<bool> DisableSuccBBSearch( 54 "disable-mips-df-succbb-search", 55 cl::init(true), 56 cl::desc("Disallow MIPS delay filler to search successor basic blocks."), 57 cl::Hidden); 58 59static cl::opt<bool> DisableBackwardSearch( 60 "disable-mips-df-backward-search", 61 cl::init(false), 62 cl::desc("Disallow MIPS delay filler to search backward."), 63 cl::Hidden); 64 65namespace { 66 typedef MachineBasicBlock::iterator Iter; 67 typedef MachineBasicBlock::reverse_iterator ReverseIter; 68 typedef SmallDenseMap<MachineBasicBlock*, MachineInstr*, 2> BB2BrMap; 69 70 class RegDefsUses { 71 public: 72 RegDefsUses(TargetMachine &TM); 73 void init(const MachineInstr &MI); 74 75 /// This function sets all caller-saved registers in Defs. 76 void setCallerSaved(const MachineInstr &MI); 77 78 /// This function sets all unallocatable registers in Defs. 79 void setUnallocatableRegs(const MachineFunction &MF); 80 81 /// Set bits in Uses corresponding to MBB's live-out registers except for 82 /// the registers that are live-in to SuccBB. 83 void addLiveOut(const MachineBasicBlock &MBB, 84 const MachineBasicBlock &SuccBB); 85 86 bool update(const MachineInstr &MI, unsigned Begin, unsigned End); 87 88 private: 89 bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg, 90 bool IsDef) const; 91 92 /// Returns true if Reg or its alias is in RegSet. 93 bool isRegInSet(const BitVector &RegSet, unsigned Reg) const; 94 95 const TargetRegisterInfo &TRI; 96 BitVector Defs, Uses; 97 }; 98 99 /// Base class for inspecting loads and stores. 100 class InspectMemInstr { 101 public: 102 InspectMemInstr(bool ForbidMemInstr_) 103 : OrigSeenLoad(false), OrigSeenStore(false), SeenLoad(false), 104 SeenStore(false), ForbidMemInstr(ForbidMemInstr_) {} 105 106 /// Return true if MI cannot be moved to delay slot. 107 bool hasHazard(const MachineInstr &MI); 108 109 virtual ~InspectMemInstr() {} 110 111 protected: 112 /// Flags indicating whether loads or stores have been seen. 113 bool OrigSeenLoad, OrigSeenStore, SeenLoad, SeenStore; 114 115 /// Memory instructions are not allowed to move to delay slot if this flag 116 /// is true. 117 bool ForbidMemInstr; 118 119 private: 120 virtual bool hasHazard_(const MachineInstr &MI) = 0; 121 }; 122 123 /// This subclass rejects any memory instructions. 124 class NoMemInstr : public InspectMemInstr { 125 public: 126 NoMemInstr() : InspectMemInstr(true) {} 127 private: 128 bool hasHazard_(const MachineInstr &MI) override { return true; } 129 }; 130 131 /// This subclass accepts loads from stacks and constant loads. 132 class LoadFromStackOrConst : public InspectMemInstr { 133 public: 134 LoadFromStackOrConst() : InspectMemInstr(false) {} 135 private: 136 bool hasHazard_(const MachineInstr &MI) override; 137 }; 138 139 /// This subclass uses memory dependence information to determine whether a 140 /// memory instruction can be moved to a delay slot. 141 class MemDefsUses : public InspectMemInstr { 142 public: 143 MemDefsUses(const MachineFrameInfo *MFI); 144 145 private: 146 typedef PointerUnion<const Value *, const PseudoSourceValue *> ValueType; 147 148 bool hasHazard_(const MachineInstr &MI) override; 149 150 /// Update Defs and Uses. Return true if there exist dependences that 151 /// disqualify the delay slot candidate between V and values in Uses and 152 /// Defs. 153 bool updateDefsUses(ValueType V, bool MayStore); 154 155 /// Get the list of underlying objects of MI's memory operand. 156 bool getUnderlyingObjects(const MachineInstr &MI, 157 SmallVectorImpl<ValueType> &Objects) const; 158 159 const MachineFrameInfo *MFI; 160 SmallPtrSet<ValueType, 4> Uses, Defs; 161 162 /// Flags indicating whether loads or stores with no underlying objects have 163 /// been seen. 164 bool SeenNoObjLoad, SeenNoObjStore; 165 }; 166 167 class Filler : public MachineFunctionPass { 168 public: 169 Filler(TargetMachine &tm) 170 : MachineFunctionPass(ID), TM(tm) { } 171 172 const char *getPassName() const override { 173 return "Mips Delay Slot Filler"; 174 } 175 176 bool runOnMachineFunction(MachineFunction &F) override { 177 bool Changed = false; 178 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 179 FI != FE; ++FI) 180 Changed |= runOnMachineBasicBlock(*FI); 181 182 // This pass invalidates liveness information when it reorders 183 // instructions to fill delay slot. Without this, -verify-machineinstrs 184 // will fail. 185 if (Changed) 186 F.getRegInfo().invalidateLiveness(); 187 188 return Changed; 189 } 190 191 void getAnalysisUsage(AnalysisUsage &AU) const override { 192 AU.addRequired<MachineBranchProbabilityInfo>(); 193 MachineFunctionPass::getAnalysisUsage(AU); 194 } 195 196 private: 197 bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 198 199 Iter replaceWithCompactBranch(MachineBasicBlock &MBB, 200 Iter Branch, DebugLoc DL); 201 202 /// This function checks if it is valid to move Candidate to the delay slot 203 /// and returns true if it isn't. It also updates memory and register 204 /// dependence information. 205 bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, 206 InspectMemInstr &IM) const; 207 208 /// This function searches range [Begin, End) for an instruction that can be 209 /// moved to the delay slot. Returns true on success. 210 template<typename IterTy> 211 bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, 212 RegDefsUses &RegDU, InspectMemInstr &IM, 213 IterTy &Filler, Iter Slot) const; 214 215 /// This function searches in the backward direction for an instruction that 216 /// can be moved to the delay slot. Returns true on success. 217 bool searchBackward(MachineBasicBlock &MBB, Iter Slot) const; 218 219 /// This function searches MBB in the forward direction for an instruction 220 /// that can be moved to the delay slot. Returns true on success. 221 bool searchForward(MachineBasicBlock &MBB, Iter Slot) const; 222 223 /// This function searches one of MBB's successor blocks for an instruction 224 /// that can be moved to the delay slot and inserts clones of the 225 /// instruction into the successor's predecessor blocks. 226 bool searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const; 227 228 /// Pick a successor block of MBB. Return NULL if MBB doesn't have a 229 /// successor block that is not a landing pad. 230 MachineBasicBlock *selectSuccBB(MachineBasicBlock &B) const; 231 232 /// This function analyzes MBB and returns an instruction with an unoccupied 233 /// slot that branches to Dst. 234 std::pair<MipsInstrInfo::BranchType, MachineInstr *> 235 getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const; 236 237 /// Examine Pred and see if it is possible to insert an instruction into 238 /// one of its branches delay slot or its end. 239 bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ, 240 RegDefsUses &RegDU, bool &HasMultipleSuccs, 241 BB2BrMap &BrMap) const; 242 243 bool terminateSearch(const MachineInstr &Candidate) const; 244 245 TargetMachine &TM; 246 247 static char ID; 248 }; 249 char Filler::ID = 0; 250} // end of anonymous namespace 251 252static bool hasUnoccupiedSlot(const MachineInstr *MI) { 253 return MI->hasDelaySlot() && !MI->isBundledWithSucc(); 254} 255 256/// This function inserts clones of Filler into predecessor blocks. 257static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) { 258 MachineFunction *MF = Filler->getParent()->getParent(); 259 260 for (BB2BrMap::const_iterator I = BrMap.begin(); I != BrMap.end(); ++I) { 261 if (I->second) { 262 MIBundleBuilder(I->second).append(MF->CloneMachineInstr(&*Filler)); 263 ++UsefulSlots; 264 } else { 265 I->first->insert(I->first->end(), MF->CloneMachineInstr(&*Filler)); 266 } 267 } 268} 269 270/// This function adds registers Filler defines to MBB's live-in register list. 271static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) { 272 for (unsigned I = 0, E = Filler->getNumOperands(); I != E; ++I) { 273 const MachineOperand &MO = Filler->getOperand(I); 274 unsigned R; 275 276 if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg())) 277 continue; 278 279#ifndef NDEBUG 280 const MachineFunction &MF = *MBB.getParent(); 281 assert(MF.getTarget() 282 .getSubtargetImpl() 283 ->getRegisterInfo() 284 ->getAllocatableSet(MF) 285 .test(R) && 286 "Shouldn't move an instruction with unallocatable registers across " 287 "basic block boundaries."); 288#endif 289 290 if (!MBB.isLiveIn(R)) 291 MBB.addLiveIn(R); 292 } 293} 294 295RegDefsUses::RegDefsUses(TargetMachine &TM) 296 : TRI(*TM.getSubtargetImpl()->getRegisterInfo()), 297 Defs(TRI.getNumRegs(), false), Uses(TRI.getNumRegs(), false) {} 298 299void RegDefsUses::init(const MachineInstr &MI) { 300 // Add all register operands which are explicit and non-variadic. 301 update(MI, 0, MI.getDesc().getNumOperands()); 302 303 // If MI is a call, add RA to Defs to prevent users of RA from going into 304 // delay slot. 305 if (MI.isCall()) 306 Defs.set(Mips::RA); 307 308 // Add all implicit register operands of branch instructions except 309 // register AT. 310 if (MI.isBranch()) { 311 update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands()); 312 Defs.reset(Mips::AT); 313 } 314} 315 316void RegDefsUses::setCallerSaved(const MachineInstr &MI) { 317 assert(MI.isCall()); 318 319 // If MI is a call, add all caller-saved registers to Defs. 320 BitVector CallerSavedRegs(TRI.getNumRegs(), true); 321 322 CallerSavedRegs.reset(Mips::ZERO); 323 CallerSavedRegs.reset(Mips::ZERO_64); 324 325 for (const MCPhysReg *R = TRI.getCalleeSavedRegs(); *R; ++R) 326 for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI) 327 CallerSavedRegs.reset(*AI); 328 329 Defs |= CallerSavedRegs; 330} 331 332void RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) { 333 BitVector AllocSet = TRI.getAllocatableSet(MF); 334 335 for (int R = AllocSet.find_first(); R != -1; R = AllocSet.find_next(R)) 336 for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI) 337 AllocSet.set(*AI); 338 339 AllocSet.set(Mips::ZERO); 340 AllocSet.set(Mips::ZERO_64); 341 342 Defs |= AllocSet.flip(); 343} 344 345void RegDefsUses::addLiveOut(const MachineBasicBlock &MBB, 346 const MachineBasicBlock &SuccBB) { 347 for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 348 SE = MBB.succ_end(); SI != SE; ++SI) 349 if (*SI != &SuccBB) 350 for (MachineBasicBlock::livein_iterator LI = (*SI)->livein_begin(), 351 LE = (*SI)->livein_end(); LI != LE; ++LI) 352 Uses.set(*LI); 353} 354 355bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) { 356 BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs()); 357 bool HasHazard = false; 358 359 for (unsigned I = Begin; I != End; ++I) { 360 const MachineOperand &MO = MI.getOperand(I); 361 362 if (MO.isReg() && MO.getReg()) 363 HasHazard |= checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef()); 364 } 365 366 Defs |= NewDefs; 367 Uses |= NewUses; 368 369 return HasHazard; 370} 371 372bool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, 373 unsigned Reg, bool IsDef) const { 374 if (IsDef) { 375 NewDefs.set(Reg); 376 // check whether Reg has already been defined or used. 377 return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg)); 378 } 379 380 NewUses.set(Reg); 381 // check whether Reg has already been defined. 382 return isRegInSet(Defs, Reg); 383} 384 385bool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const { 386 // Check Reg and all aliased Registers. 387 for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI) 388 if (RegSet.test(*AI)) 389 return true; 390 return false; 391} 392 393bool InspectMemInstr::hasHazard(const MachineInstr &MI) { 394 if (!MI.mayStore() && !MI.mayLoad()) 395 return false; 396 397 if (ForbidMemInstr) 398 return true; 399 400 OrigSeenLoad = SeenLoad; 401 OrigSeenStore = SeenStore; 402 SeenLoad |= MI.mayLoad(); 403 SeenStore |= MI.mayStore(); 404 405 // If MI is an ordered or volatile memory reference, disallow moving 406 // subsequent loads and stores to delay slot. 407 if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) { 408 ForbidMemInstr = true; 409 return true; 410 } 411 412 return hasHazard_(MI); 413} 414 415bool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) { 416 if (MI.mayStore()) 417 return true; 418 419 if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getPseudoValue()) 420 return true; 421 422 if (const PseudoSourceValue *PSV = 423 (*MI.memoperands_begin())->getPseudoValue()) { 424 if (isa<FixedStackPseudoSourceValue>(PSV)) 425 return false; 426 return !PSV->isConstant(nullptr) && PSV != PseudoSourceValue::getStack(); 427 } 428 429 return true; 430} 431 432MemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_) 433 : InspectMemInstr(false), MFI(MFI_), SeenNoObjLoad(false), 434 SeenNoObjStore(false) {} 435 436bool MemDefsUses::hasHazard_(const MachineInstr &MI) { 437 bool HasHazard = false; 438 SmallVector<ValueType, 4> Objs; 439 440 // Check underlying object list. 441 if (getUnderlyingObjects(MI, Objs)) { 442 for (SmallVectorImpl<ValueType>::const_iterator I = Objs.begin(); 443 I != Objs.end(); ++I) 444 HasHazard |= updateDefsUses(*I, MI.mayStore()); 445 446 return HasHazard; 447 } 448 449 // No underlying objects found. 450 HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore); 451 HasHazard |= MI.mayLoad() || OrigSeenStore; 452 453 SeenNoObjLoad |= MI.mayLoad(); 454 SeenNoObjStore |= MI.mayStore(); 455 456 return HasHazard; 457} 458 459bool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) { 460 if (MayStore) 461 return !Defs.insert(V).second || Uses.count(V) || SeenNoObjStore || 462 SeenNoObjLoad; 463 464 Uses.insert(V); 465 return Defs.count(V) || SeenNoObjStore; 466} 467 468bool MemDefsUses:: 469getUnderlyingObjects(const MachineInstr &MI, 470 SmallVectorImpl<ValueType> &Objects) const { 471 if (!MI.hasOneMemOperand() || 472 (!(*MI.memoperands_begin())->getValue() && 473 !(*MI.memoperands_begin())->getPseudoValue())) 474 return false; 475 476 if (const PseudoSourceValue *PSV = 477 (*MI.memoperands_begin())->getPseudoValue()) { 478 if (!PSV->isAliased(MFI)) 479 return false; 480 Objects.push_back(PSV); 481 return true; 482 } 483 484 const Value *V = (*MI.memoperands_begin())->getValue(); 485 486 SmallVector<Value *, 4> Objs; 487 GetUnderlyingObjects(const_cast<Value *>(V), Objs); 488 489 for (SmallVectorImpl<Value *>::iterator I = Objs.begin(), E = Objs.end(); 490 I != E; ++I) { 491 if (!isIdentifiedObject(V)) 492 return false; 493 494 Objects.push_back(*I); 495 } 496 497 return true; 498} 499 500// Replace Branch with the compact branch instruction. 501Iter Filler::replaceWithCompactBranch(MachineBasicBlock &MBB, 502 Iter Branch, DebugLoc DL) { 503 const MipsInstrInfo *TII= static_cast<const MipsInstrInfo *>( 504 TM.getSubtargetImpl()->getInstrInfo()); 505 506 unsigned NewOpcode = 507 (((unsigned) Branch->getOpcode()) == Mips::BEQ) ? Mips::BEQZC_MM 508 : Mips::BNEZC_MM; 509 510 const MCInstrDesc &NewDesc = TII->get(NewOpcode); 511 MachineInstrBuilder MIB = BuildMI(MBB, Branch, DL, NewDesc); 512 513 MIB.addReg(Branch->getOperand(0).getReg()); 514 MIB.addMBB(Branch->getOperand(2).getMBB()); 515 516 Iter tmpIter = Branch; 517 Branch = std::prev(Branch); 518 MBB.erase(tmpIter); 519 520 return Branch; 521} 522 523// For given opcode returns opcode of corresponding instruction with short 524// delay slot. 525static int getEquivalentCallShort(int Opcode) { 526 switch (Opcode) { 527 case Mips::BGEZAL: 528 return Mips::BGEZALS_MM; 529 case Mips::BLTZAL: 530 return Mips::BLTZALS_MM; 531 case Mips::JAL: 532 return Mips::JALS_MM; 533 case Mips::JALR: 534 return Mips::JALRS_MM; 535 case Mips::JALR16_MM: 536 return Mips::JALRS16_MM; 537 default: 538 llvm_unreachable("Unexpected call instruction for microMIPS."); 539 } 540} 541 542/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 543/// We assume there is only one delay slot per delayed instruction. 544bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 545 bool Changed = false; 546 bool InMicroMipsMode = TM.getSubtarget<MipsSubtarget>().inMicroMipsMode(); 547 const MipsInstrInfo *TII = 548 static_cast<const MipsInstrInfo *>(TM.getSubtargetImpl()->getInstrInfo()); 549 550 for (Iter I = MBB.begin(); I != MBB.end(); ++I) { 551 if (!hasUnoccupiedSlot(&*I)) 552 continue; 553 554 ++FilledSlots; 555 Changed = true; 556 557 // Delay slot filling is disabled at -O0. 558 if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None)) { 559 bool Filled = false; 560 561 if (searchBackward(MBB, I)) { 562 Filled = true; 563 } else if (I->isTerminator()) { 564 if (searchSuccBBs(MBB, I)) { 565 Filled = true; 566 } 567 } else if (searchForward(MBB, I)) { 568 Filled = true; 569 } 570 571 if (Filled) { 572 // Get instruction with delay slot. 573 MachineBasicBlock::instr_iterator DSI(I); 574 575 if (InMicroMipsMode && TII->GetInstSizeInBytes(std::next(DSI)) == 2 && 576 DSI->isCall()) { 577 // If instruction in delay slot is 16b change opcode to 578 // corresponding instruction with short delay slot. 579 DSI->setDesc(TII->get(getEquivalentCallShort(DSI->getOpcode()))); 580 } 581 582 continue; 583 } 584 } 585 586 // If instruction is BEQ or BNE with one ZERO register, then instead of 587 // adding NOP replace this instruction with the corresponding compact 588 // branch instruction, i.e. BEQZC or BNEZC. 589 unsigned Opcode = I->getOpcode(); 590 if (InMicroMipsMode && 591 (Opcode == Mips::BEQ || Opcode == Mips::BNE) && 592 ((unsigned) I->getOperand(1).getReg()) == Mips::ZERO) { 593 594 I = replaceWithCompactBranch(MBB, I, I->getDebugLoc()); 595 596 } else { 597 // Bundle the NOP to the instruction with the delay slot. 598 BuildMI(MBB, std::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); 599 MIBundleBuilder(MBB, I, std::next(I, 2)); 600 } 601 } 602 603 return Changed; 604} 605 606/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 607/// slots in Mips MachineFunctions 608FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 609 return new Filler(tm); 610} 611 612template<typename IterTy> 613bool Filler::searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, 614 RegDefsUses &RegDU, InspectMemInstr& IM, 615 IterTy &Filler, Iter Slot) const { 616 for (IterTy I = Begin; I != End; ++I) { 617 // skip debug value 618 if (I->isDebugValue()) 619 continue; 620 621 if (terminateSearch(*I)) 622 break; 623 624 assert((!I->isCall() && !I->isReturn() && !I->isBranch()) && 625 "Cannot put calls, returns or branches in delay slot."); 626 627 if (delayHasHazard(*I, RegDU, IM)) 628 continue; 629 630 if (TM.getSubtarget<MipsSubtarget>().isTargetNaCl()) { 631 // In NaCl, instructions that must be masked are forbidden in delay slots. 632 // We only check for loads, stores and SP changes. Calls, returns and 633 // branches are not checked because non-NaCl targets never put them in 634 // delay slots. 635 unsigned AddrIdx; 636 if ((isBasePlusOffsetMemoryAccess(I->getOpcode(), &AddrIdx) && 637 baseRegNeedsLoadStoreMask(I->getOperand(AddrIdx).getReg())) || 638 I->modifiesRegister(Mips::SP, 639 TM.getSubtargetImpl()->getRegisterInfo())) 640 continue; 641 } 642 643 bool InMicroMipsMode = TM.getSubtarget<MipsSubtarget>().inMicroMipsMode(); 644 const MipsInstrInfo *TII = static_cast<const MipsInstrInfo *>( 645 TM.getSubtargetImpl()->getInstrInfo()); 646 unsigned Opcode = (*Slot).getOpcode(); 647 if (InMicroMipsMode && TII->GetInstSizeInBytes(&(*I)) == 2 && 648 (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch || 649 Opcode == Mips::PseudoReturn)) 650 continue; 651 652 Filler = I; 653 return true; 654 } 655 656 return false; 657} 658 659bool Filler::searchBackward(MachineBasicBlock &MBB, Iter Slot) const { 660 if (DisableBackwardSearch) 661 return false; 662 663 RegDefsUses RegDU(TM); 664 MemDefsUses MemDU(MBB.getParent()->getFrameInfo()); 665 ReverseIter Filler; 666 667 RegDU.init(*Slot); 668 669 if (!searchRange(MBB, ReverseIter(Slot), MBB.rend(), RegDU, MemDU, Filler, 670 Slot)) 671 return false; 672 673 MBB.splice(std::next(Slot), &MBB, std::next(Filler).base()); 674 MIBundleBuilder(MBB, Slot, std::next(Slot, 2)); 675 ++UsefulSlots; 676 return true; 677} 678 679bool Filler::searchForward(MachineBasicBlock &MBB, Iter Slot) const { 680 // Can handle only calls. 681 if (DisableForwardSearch || !Slot->isCall()) 682 return false; 683 684 RegDefsUses RegDU(TM); 685 NoMemInstr NM; 686 Iter Filler; 687 688 RegDU.setCallerSaved(*Slot); 689 690 if (!searchRange(MBB, std::next(Slot), MBB.end(), RegDU, NM, Filler, Slot)) 691 return false; 692 693 MBB.splice(std::next(Slot), &MBB, Filler); 694 MIBundleBuilder(MBB, Slot, std::next(Slot, 2)); 695 ++UsefulSlots; 696 return true; 697} 698 699bool Filler::searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const { 700 if (DisableSuccBBSearch) 701 return false; 702 703 MachineBasicBlock *SuccBB = selectSuccBB(MBB); 704 705 if (!SuccBB) 706 return false; 707 708 RegDefsUses RegDU(TM); 709 bool HasMultipleSuccs = false; 710 BB2BrMap BrMap; 711 std::unique_ptr<InspectMemInstr> IM; 712 Iter Filler; 713 714 // Iterate over SuccBB's predecessor list. 715 for (MachineBasicBlock::pred_iterator PI = SuccBB->pred_begin(), 716 PE = SuccBB->pred_end(); PI != PE; ++PI) 717 if (!examinePred(**PI, *SuccBB, RegDU, HasMultipleSuccs, BrMap)) 718 return false; 719 720 // Do not allow moving instructions which have unallocatable register operands 721 // across basic block boundaries. 722 RegDU.setUnallocatableRegs(*MBB.getParent()); 723 724 // Only allow moving loads from stack or constants if any of the SuccBB's 725 // predecessors have multiple successors. 726 if (HasMultipleSuccs) { 727 IM.reset(new LoadFromStackOrConst()); 728 } else { 729 const MachineFrameInfo *MFI = MBB.getParent()->getFrameInfo(); 730 IM.reset(new MemDefsUses(MFI)); 731 } 732 733 if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Filler, 734 Slot)) 735 return false; 736 737 insertDelayFiller(Filler, BrMap); 738 addLiveInRegs(Filler, *SuccBB); 739 Filler->eraseFromParent(); 740 741 return true; 742} 743 744MachineBasicBlock *Filler::selectSuccBB(MachineBasicBlock &B) const { 745 if (B.succ_empty()) 746 return nullptr; 747 748 // Select the successor with the larget edge weight. 749 auto &Prob = getAnalysis<MachineBranchProbabilityInfo>(); 750 MachineBasicBlock *S = *std::max_element(B.succ_begin(), B.succ_end(), 751 [&](const MachineBasicBlock *Dst0, 752 const MachineBasicBlock *Dst1) { 753 return Prob.getEdgeWeight(&B, Dst0) < Prob.getEdgeWeight(&B, Dst1); 754 }); 755 return S->isLandingPad() ? nullptr : S; 756} 757 758std::pair<MipsInstrInfo::BranchType, MachineInstr *> 759Filler::getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const { 760 const MipsInstrInfo *TII = 761 static_cast<const MipsInstrInfo *>(TM.getSubtargetImpl()->getInstrInfo()); 762 MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr; 763 SmallVector<MachineInstr*, 2> BranchInstrs; 764 SmallVector<MachineOperand, 2> Cond; 765 766 MipsInstrInfo::BranchType R = 767 TII->AnalyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs); 768 769 if ((R == MipsInstrInfo::BT_None) || (R == MipsInstrInfo::BT_NoBranch)) 770 return std::make_pair(R, nullptr); 771 772 if (R != MipsInstrInfo::BT_CondUncond) { 773 if (!hasUnoccupiedSlot(BranchInstrs[0])) 774 return std::make_pair(MipsInstrInfo::BT_None, nullptr); 775 776 assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst))); 777 778 return std::make_pair(R, BranchInstrs[0]); 779 } 780 781 assert((TrueBB == &Dst) || (FalseBB == &Dst)); 782 783 // Examine the conditional branch. See if its slot is occupied. 784 if (hasUnoccupiedSlot(BranchInstrs[0])) 785 return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]); 786 787 // If that fails, try the unconditional branch. 788 if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst)) 789 return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]); 790 791 return std::make_pair(MipsInstrInfo::BT_None, nullptr); 792} 793 794bool Filler::examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ, 795 RegDefsUses &RegDU, bool &HasMultipleSuccs, 796 BB2BrMap &BrMap) const { 797 std::pair<MipsInstrInfo::BranchType, MachineInstr *> P = 798 getBranch(Pred, Succ); 799 800 // Return if either getBranch wasn't able to analyze the branches or there 801 // were no branches with unoccupied slots. 802 if (P.first == MipsInstrInfo::BT_None) 803 return false; 804 805 if ((P.first != MipsInstrInfo::BT_Uncond) && 806 (P.first != MipsInstrInfo::BT_NoBranch)) { 807 HasMultipleSuccs = true; 808 RegDU.addLiveOut(Pred, Succ); 809 } 810 811 BrMap[&Pred] = P.second; 812 return true; 813} 814 815bool Filler::delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, 816 InspectMemInstr &IM) const { 817 bool HasHazard = (Candidate.isImplicitDef() || Candidate.isKill()); 818 819 HasHazard |= IM.hasHazard(Candidate); 820 HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands()); 821 822 return HasHazard; 823} 824 825bool Filler::terminateSearch(const MachineInstr &Candidate) const { 826 return (Candidate.isTerminator() || Candidate.isCall() || 827 Candidate.isPosition() || Candidate.isInlineAsm() || 828 Candidate.hasUnmodeledSideEffects()); 829} 830