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