961 lines · cpp
1//===- MipsDelaySlotFiller.cpp - Mips Delay Slot Filler -------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Simple pass to fill delay slots with useful instructions.10//11//===----------------------------------------------------------------------===//12 13#include "Mips.h"14#include "MipsInstrInfo.h"15#include "MipsSubtarget.h"16#include "llvm/ADT/BitVector.h"17#include "llvm/ADT/DenseMap.h"18#include "llvm/ADT/PointerUnion.h"19#include "llvm/ADT/SmallPtrSet.h"20#include "llvm/ADT/SmallVector.h"21#include "llvm/ADT/Statistic.h"22#include "llvm/ADT/StringRef.h"23#include "llvm/Analysis/AliasAnalysis.h"24#include "llvm/Analysis/ValueTracking.h"25#include "llvm/CodeGen/MachineBasicBlock.h"26#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"27#include "llvm/CodeGen/MachineFunction.h"28#include "llvm/CodeGen/MachineFunctionPass.h"29#include "llvm/CodeGen/MachineInstr.h"30#include "llvm/CodeGen/MachineInstrBuilder.h"31#include "llvm/CodeGen/MachineOperand.h"32#include "llvm/CodeGen/MachineRegisterInfo.h"33#include "llvm/CodeGen/PseudoSourceValue.h"34#include "llvm/CodeGen/TargetRegisterInfo.h"35#include "llvm/CodeGen/TargetSubtargetInfo.h"36#include "llvm/MC/MCInstrDesc.h"37#include "llvm/MC/MCRegisterInfo.h"38#include "llvm/Support/Casting.h"39#include "llvm/Support/CodeGen.h"40#include "llvm/Support/CommandLine.h"41#include "llvm/Support/ErrorHandling.h"42#include "llvm/Target/TargetMachine.h"43#include <cassert>44#include <iterator>45#include <memory>46#include <utility>47 48using namespace llvm;49 50#define DEBUG_TYPE "mips-delay-slot-filler"51 52STATISTIC(FilledSlots, "Number of delay slots filled");53STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that"54 " are not NOP.");55 56static cl::opt<bool> DisableDelaySlotFiller(57 "disable-mips-delay-filler",58 cl::init(false),59 cl::desc("Fill all delay slots with NOPs."),60 cl::Hidden);61 62static cl::opt<bool> DisableForwardSearch(63 "disable-mips-df-forward-search",64 cl::init(true),65 cl::desc("Disallow MIPS delay filler to search forward."),66 cl::Hidden);67 68static cl::opt<bool> DisableSuccBBSearch(69 "disable-mips-df-succbb-search",70 cl::init(true),71 cl::desc("Disallow MIPS delay filler to search successor basic blocks."),72 cl::Hidden);73 74static cl::opt<bool> DisableBackwardSearch(75 "disable-mips-df-backward-search",76 cl::init(false),77 cl::desc("Disallow MIPS delay filler to search backward."),78 cl::Hidden);79 80enum CompactBranchPolicy {81 CB_Never, ///< The policy 'never' may in some circumstances or for some82 ///< ISAs not be absolutely adhered to.83 CB_Optimal, ///< Optimal is the default and will produce compact branches84 ///< when delay slots cannot be filled.85 CB_Always ///< 'always' may in some circumstances may not be86 ///< absolutely adhered to there may not be a corresponding87 ///< compact form of a branch.88};89 90static cl::opt<CompactBranchPolicy> MipsCompactBranchPolicy(91 "mips-compact-branches", cl::Optional, cl::init(CB_Optimal),92 cl::desc("MIPS Specific: Compact branch policy."),93 cl::values(clEnumValN(CB_Never, "never",94 "Do not use compact branches if possible."),95 clEnumValN(CB_Optimal, "optimal",96 "Use compact branches where appropriate (default)."),97 clEnumValN(CB_Always, "always",98 "Always use compact branches if possible.")));99 100namespace {101 102 using Iter = MachineBasicBlock::iterator;103 using ReverseIter = MachineBasicBlock::reverse_iterator;104 using BB2BrMap = SmallDenseMap<MachineBasicBlock *, MachineInstr *, 2>;105 106 class RegDefsUses {107 public:108 RegDefsUses(const TargetRegisterInfo &TRI);109 110 void init(const MachineInstr &MI);111 112 /// This function sets all caller-saved registers in Defs.113 void setCallerSaved(const MachineInstr &MI);114 115 /// This function sets all unallocatable registers in Defs.116 void setUnallocatableRegs(const MachineFunction &MF);117 118 /// Set bits in Uses corresponding to MBB's live-out registers except for119 /// the registers that are live-in to SuccBB.120 void addLiveOut(const MachineBasicBlock &MBB,121 const MachineBasicBlock &SuccBB);122 123 bool update(const MachineInstr &MI, unsigned Begin, unsigned End);124 125 private:126 bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg,127 bool IsDef) const;128 129 /// Returns true if Reg or its alias is in RegSet.130 bool isRegInSet(const BitVector &RegSet, unsigned Reg) const;131 132 const TargetRegisterInfo &TRI;133 BitVector Defs, Uses;134 };135 136 /// Base class for inspecting loads and stores.137 class InspectMemInstr {138 public:139 InspectMemInstr(bool ForbidMemInstr_) : ForbidMemInstr(ForbidMemInstr_) {}140 virtual ~InspectMemInstr() = default;141 142 /// Return true if MI cannot be moved to delay slot.143 bool hasHazard(const MachineInstr &MI);144 145 protected:146 /// Flags indicating whether loads or stores have been seen.147 bool OrigSeenLoad = false;148 bool OrigSeenStore = false;149 bool SeenLoad = false;150 bool SeenStore = false;151 152 /// Memory instructions are not allowed to move to delay slot if this flag153 /// is true.154 bool ForbidMemInstr;155 156 private:157 virtual bool hasHazard_(const MachineInstr &MI) = 0;158 };159 160 /// This subclass rejects any memory instructions.161 class NoMemInstr : public InspectMemInstr {162 public:163 NoMemInstr() : InspectMemInstr(true) {}164 165 private:166 bool hasHazard_(const MachineInstr &MI) override { return true; }167 };168 169 /// This subclass accepts loads from stacks and constant loads.170 class LoadFromStackOrConst : public InspectMemInstr {171 public:172 LoadFromStackOrConst() : InspectMemInstr(false) {}173 174 private:175 bool hasHazard_(const MachineInstr &MI) override;176 };177 178 /// This subclass uses memory dependence information to determine whether a179 /// memory instruction can be moved to a delay slot.180 class MemDefsUses : public InspectMemInstr {181 public:182 explicit MemDefsUses(const MachineFrameInfo *MFI);183 184 private:185 using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>;186 187 bool hasHazard_(const MachineInstr &MI) override;188 189 /// Update Defs and Uses. Return true if there exist dependences that190 /// disqualify the delay slot candidate between V and values in Uses and191 /// Defs.192 bool updateDefsUses(ValueType V, bool MayStore);193 194 /// Get the list of underlying objects of MI's memory operand.195 bool getUnderlyingObjects(const MachineInstr &MI,196 SmallVectorImpl<ValueType> &Objects) const;197 198 const MachineFrameInfo *MFI;199 SmallPtrSet<ValueType, 4> Uses, Defs;200 201 /// Flags indicating whether loads or stores with no underlying objects have202 /// been seen.203 bool SeenNoObjLoad = false;204 bool SeenNoObjStore = false;205 };206 207 class MipsDelaySlotFiller : public MachineFunctionPass {208 public:209 MipsDelaySlotFiller() : MachineFunctionPass(ID) {}210 211 StringRef getPassName() const override { return "Mips Delay Slot Filler"; }212 213 bool runOnMachineFunction(MachineFunction &F) override {214 TM = &F.getTarget();215 bool Changed = false;216 for (MachineBasicBlock &MBB : F)217 Changed |= runOnMachineBasicBlock(MBB);218 219 // This pass invalidates liveness information when it reorders220 // instructions to fill delay slot. Without this, -verify-machineinstrs221 // will fail.222 if (Changed)223 F.getRegInfo().invalidateLiveness();224 225 return Changed;226 }227 228 MachineFunctionProperties getRequiredProperties() const override {229 return MachineFunctionProperties().setNoVRegs();230 }231 232 void getAnalysisUsage(AnalysisUsage &AU) const override {233 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();234 MachineFunctionPass::getAnalysisUsage(AU);235 }236 237 static char ID;238 239 private:240 bool runOnMachineBasicBlock(MachineBasicBlock &MBB);241 242 Iter replaceWithCompactBranch(MachineBasicBlock &MBB, Iter Branch,243 const DebugLoc &DL);244 245 /// This function checks if it is valid to move Candidate to the delay slot246 /// and returns true if it isn't. It also updates memory and register247 /// dependence information.248 bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU,249 InspectMemInstr &IM) const;250 251 /// This function searches range [Begin, End) for an instruction that can be252 /// moved to the delay slot. Returns true on success.253 template<typename IterTy>254 bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End,255 RegDefsUses &RegDU, InspectMemInstr &IM, Iter Slot,256 IterTy &Filler) const;257 258 /// This function searches in the backward direction for an instruction that259 /// can be moved to the delay slot. Returns true on success.260 bool searchBackward(MachineBasicBlock &MBB, MachineInstr &Slot) const;261 262 /// This function searches MBB in the forward direction for an instruction263 /// that can be moved to the delay slot. Returns true on success.264 bool searchForward(MachineBasicBlock &MBB, Iter Slot) const;265 266 /// This function searches one of MBB's successor blocks for an instruction267 /// that can be moved to the delay slot and inserts clones of the268 /// instruction into the successor's predecessor blocks.269 bool searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const;270 271 /// Pick a successor block of MBB. Return NULL if MBB doesn't have a272 /// successor block that is not a landing pad.273 MachineBasicBlock *selectSuccBB(MachineBasicBlock &B) const;274 275 /// This function analyzes MBB and returns an instruction with an unoccupied276 /// slot that branches to Dst.277 std::pair<MipsInstrInfo::BranchType, MachineInstr *>278 getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const;279 280 /// Examine Pred and see if it is possible to insert an instruction into281 /// one of its branches delay slot or its end.282 bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ,283 RegDefsUses &RegDU, bool &HasMultipleSuccs,284 BB2BrMap &BrMap) const;285 286 bool terminateSearch(const MachineInstr &Candidate) const;287 288 const TargetMachine *TM = nullptr;289 };290 291} // end anonymous namespace292 293char MipsDelaySlotFiller::ID = 0;294 295static bool hasUnoccupiedSlot(const MachineInstr *MI) {296 return MI->hasDelaySlot() && !MI->isBundledWithSucc();297}298 299INITIALIZE_PASS(MipsDelaySlotFiller, DEBUG_TYPE,300 "Fill delay slot for MIPS", false, false)301 302/// This function inserts clones of Filler into predecessor blocks.303static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) {304 MachineFunction *MF = Filler->getParent()->getParent();305 306 for (const auto &I : BrMap) {307 if (I.second) {308 MIBundleBuilder(I.second).append(MF->CloneMachineInstr(&*Filler));309 ++UsefulSlots;310 } else {311 I.first->push_back(MF->CloneMachineInstr(&*Filler));312 }313 }314}315 316/// This function adds registers Filler defines to MBB's live-in register list.317static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) {318 for (const MachineOperand &MO : Filler->operands()) {319 unsigned R;320 321 if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg()))322 continue;323 324#ifndef NDEBUG325 const MachineFunction &MF = *MBB.getParent();326 assert(MF.getSubtarget().getRegisterInfo()->getAllocatableSet(MF).test(R) &&327 "Shouldn't move an instruction with unallocatable registers across "328 "basic block boundaries.");329#endif330 331 if (!MBB.isLiveIn(R))332 MBB.addLiveIn(R);333 }334}335 336RegDefsUses::RegDefsUses(const TargetRegisterInfo &TRI)337 : TRI(TRI), Defs(TRI.getNumRegs(), false), Uses(TRI.getNumRegs(), false) {}338 339void RegDefsUses::init(const MachineInstr &MI) {340 // Add all register operands which are explicit and non-variadic.341 update(MI, 0, MI.getDesc().getNumOperands());342 343 // If MI is a call, add RA to Defs to prevent users of RA from going into344 // delay slot.345 if (MI.isCall())346 Defs.set(Mips::RA);347 348 // Add all implicit register operands of branch instructions except349 // register AT.350 if (MI.isBranch()) {351 update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands());352 Defs.reset(Mips::AT);353 }354}355 356void RegDefsUses::setCallerSaved(const MachineInstr &MI) {357 assert(MI.isCall());358 359 // Add RA/RA_64 to Defs to prevent users of RA/RA_64 from going into360 // the delay slot. The reason is that RA/RA_64 must not be changed361 // in the delay slot so that the callee can return to the caller.362 if (MI.definesRegister(Mips::RA, /*TRI=*/nullptr) ||363 MI.definesRegister(Mips::RA_64, /*TRI=*/nullptr)) {364 Defs.set(Mips::RA);365 Defs.set(Mips::RA_64);366 }367 368 // If MI is a call, add all caller-saved registers to Defs.369 BitVector CallerSavedRegs(TRI.getNumRegs(), true);370 371 CallerSavedRegs.reset(Mips::ZERO);372 CallerSavedRegs.reset(Mips::ZERO_64);373 374 for (const MCPhysReg *R = TRI.getCalleeSavedRegs(MI.getParent()->getParent());375 *R; ++R)376 for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI)377 CallerSavedRegs.reset(*AI);378 379 Defs |= CallerSavedRegs;380}381 382void RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) {383 BitVector AllocSet = TRI.getAllocatableSet(MF);384 385 for (unsigned R : AllocSet.set_bits())386 for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI)387 AllocSet.set(*AI);388 389 AllocSet.set(Mips::ZERO);390 AllocSet.set(Mips::ZERO_64);391 392 Defs |= AllocSet.flip();393}394 395void RegDefsUses::addLiveOut(const MachineBasicBlock &MBB,396 const MachineBasicBlock &SuccBB) {397 for (const MachineBasicBlock *S : MBB.successors())398 if (S != &SuccBB)399 for (const auto &LI : S->liveins())400 Uses.set(LI.PhysReg.id());401}402 403bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) {404 BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs());405 bool HasHazard = false;406 407 for (unsigned I = Begin; I != End; ++I) {408 const MachineOperand &MO = MI.getOperand(I);409 410 if (MO.isReg() && MO.getReg()) {411 if (checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef())) {412 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found register hazard for operand "413 << I << ": ";414 MO.dump());415 HasHazard = true;416 }417 }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 moving460 // 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 MachineFrameInfo *MFI_)487 : InspectMemInstr(false), MFI(MFI_) {}488 489bool MemDefsUses::hasHazard_(const MachineInstr &MI) {490 bool HasHazard = false;491 492 // Check underlying object list.493 SmallVector<ValueType, 4> Objs;494 if (getUnderlyingObjects(MI, Objs)) {495 for (ValueType VT : Objs)496 HasHazard |= updateDefsUses(VT, MI.mayStore());497 return HasHazard;498 }499 500 // No underlying objects found.501 HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore);502 HasHazard |= MI.mayLoad() || OrigSeenStore;503 504 SeenNoObjLoad |= MI.mayLoad();505 SeenNoObjStore |= MI.mayStore();506 507 return HasHazard;508}509 510bool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) {511 if (MayStore)512 return !Defs.insert(V).second || Uses.count(V) || SeenNoObjStore ||513 SeenNoObjLoad;514 515 Uses.insert(V);516 return Defs.count(V) || SeenNoObjStore;517}518 519bool MemDefsUses::520getUnderlyingObjects(const MachineInstr &MI,521 SmallVectorImpl<ValueType> &Objects) const {522 if (!MI.hasOneMemOperand())523 return false;524 525 auto & MMO = **MI.memoperands_begin();526 527 if (const PseudoSourceValue *PSV = MMO.getPseudoValue()) {528 if (!PSV->isAliased(MFI))529 return false;530 Objects.push_back(PSV);531 return true;532 }533 534 if (const Value *V = MMO.getValue()) {535 SmallVector<const Value *, 4> Objs;536 ::getUnderlyingObjects(V, Objs);537 538 for (const Value *UValue : Objs) {539 if (!isIdentifiedObject(V))540 return false;541 542 Objects.push_back(UValue);543 }544 return true;545 }546 547 return false;548}549 550// Replace Branch with the compact branch instruction.551Iter MipsDelaySlotFiller::replaceWithCompactBranch(MachineBasicBlock &MBB,552 Iter Branch,553 const DebugLoc &DL) {554 const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();555 const MipsInstrInfo *TII = STI.getInstrInfo();556 557 unsigned NewOpcode = TII->getEquivalentCompactForm(Branch);558 Branch = TII->genInstrWithNewOpc(NewOpcode, Branch);559 560 auto *ToErase = cast<MachineInstr>(&*std::next(Branch));561 // Update call info for the Branch.562 if (ToErase->shouldUpdateAdditionalCallInfo())563 ToErase->getMF()->moveAdditionalCallInfo(ToErase,564 cast<MachineInstr>(&*Branch));565 ToErase->eraseFromParent();566 return Branch;567}568 569// For given opcode returns opcode of corresponding instruction with short570// delay slot.571// For the pseudo TAILCALL*_MM instructions return the short delay slot572// form. Unfortunately, TAILCALL<->b16 is denied as b16 has a limited range573// that is too short to make use of for tail calls.574static int getEquivalentCallShort(int Opcode) {575 switch (Opcode) {576 case Mips::BGEZAL:577 return Mips::BGEZALS_MM;578 case Mips::BLTZAL:579 return Mips::BLTZALS_MM;580 case Mips::JAL:581 case Mips::JAL_MM:582 return Mips::JALS_MM;583 case Mips::JALR:584 return Mips::JALRS_MM;585 case Mips::JALR16_MM:586 return Mips::JALRS16_MM;587 case Mips::TAILCALL_MM:588 llvm_unreachable("Attempting to shorten the TAILCALL_MM pseudo!");589 case Mips::TAILCALLREG:590 return Mips::JR16_MM;591 default:592 llvm_unreachable("Unexpected call instruction for microMIPS.");593 }594}595 596/// runOnMachineBasicBlock - Fill in delay slots for the given basic block.597/// We assume there is only one delay slot per delayed instruction.598bool MipsDelaySlotFiller::runOnMachineBasicBlock(MachineBasicBlock &MBB) {599 bool Changed = false;600 const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();601 bool InMicroMipsMode = STI.inMicroMipsMode();602 const MipsInstrInfo *TII = STI.getInstrInfo();603 604 for (Iter I = MBB.begin(); I != MBB.end(); ++I) {605 if (!hasUnoccupiedSlot(&*I))606 continue;607 608 // Delay slot filling is disabled at -O0, or in microMIPS32R6.609 if (!DisableDelaySlotFiller &&610 (TM->getOptLevel() != CodeGenOptLevel::None) &&611 !(InMicroMipsMode && STI.hasMips32r6())) {612 613 bool Filled = false;614 615 if (MipsCompactBranchPolicy.getValue() != CB_Always ||616 !TII->getEquivalentCompactForm(I)) {617 if (searchBackward(MBB, *I)) {618 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot"619 " in backwards search.\n");620 Filled = true;621 } else if (I->isTerminator()) {622 if (searchSuccBBs(MBB, I)) {623 Filled = true;624 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot"625 " in successor BB search.\n");626 }627 } else if (searchForward(MBB, I)) {628 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot"629 " in forwards search.\n");630 Filled = true;631 }632 }633 634 if (Filled) {635 // Get instruction with delay slot.636 MachineBasicBlock::instr_iterator DSI = I.getInstrIterator();637 638 if (InMicroMipsMode && TII->getInstSizeInBytes(*std::next(DSI)) == 2 &&639 DSI->isCall()) {640 // If instruction in delay slot is 16b change opcode to641 // corresponding instruction with short delay slot.642 643 // TODO: Implement an instruction mapping table of 16bit opcodes to644 // 32bit opcodes so that an instruction can be expanded. This would645 // save 16 bits as a TAILCALL_MM pseudo requires a fullsized nop.646 // TODO: Permit b16 when branching backwards to the same function647 // if it is in range.648 DSI->setDesc(TII->get(getEquivalentCallShort(DSI->getOpcode())));649 }650 ++FilledSlots;651 Changed = true;652 continue;653 }654 }655 656 // For microMIPS if instruction is BEQ or BNE with one ZERO register, then657 // instead of adding NOP replace this instruction with the corresponding658 // compact branch instruction, i.e. BEQZC or BNEZC. Additionally659 // PseudoReturn and PseudoIndirectBranch are expanded to JR_MM, so they can660 // be replaced with JRC16_MM.661 662 // For MIPSR6 attempt to produce the corresponding compact (no delay slot)663 // form of the CTI. For indirect jumps this will not require inserting a664 // NOP and for branches will hopefully avoid requiring a NOP.665 if ((InMicroMipsMode ||666 (STI.hasMips32r6() && MipsCompactBranchPolicy != CB_Never)) &&667 TII->getEquivalentCompactForm(I)) {668 I = replaceWithCompactBranch(MBB, I, I->getDebugLoc());669 Changed = true;670 continue;671 }672 673 // Bundle the NOP to the instruction with the delay slot.674 LLVM_DEBUG(dbgs() << DEBUG_TYPE << ": could not fill delay slot for ";675 I->dump());676 TII->insertNop(MBB, std::next(I), I->getDebugLoc());677 MIBundleBuilder(MBB, I, std::next(I, 2));678 ++FilledSlots;679 Changed = true;680 }681 682 return Changed;683}684 685template <typename IterTy>686bool MipsDelaySlotFiller::searchRange(MachineBasicBlock &MBB, IterTy Begin,687 IterTy End, RegDefsUses &RegDU,688 InspectMemInstr &IM, Iter Slot,689 IterTy &Filler) const {690 for (IterTy I = Begin; I != End;) {691 IterTy CurrI = I;692 ++I;693 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": checking instruction: "; CurrI->dump());694 // Skip debug value.695 // Instruction TargetOpcode::JUMP_TABLE_DEBUG_INFO is only used to note696 // jump table debug info.697 if (CurrI->isDebugInstr() || CurrI->isJumpTableDebugInfo()) {698 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": ignoring debug instruction: ";699 CurrI->dump());700 continue;701 }702 703 if (CurrI->isBundle()) {704 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": ignoring BUNDLE instruction: ";705 CurrI->dump());706 // However, we still need to update the register def-use information.707 RegDU.update(*CurrI, 0, CurrI->getNumOperands());708 continue;709 }710 711 if (terminateSearch(*CurrI)) {712 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": should terminate search: ";713 CurrI->dump());714 break;715 }716 717 assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) &&718 "Cannot put calls, returns or branches in delay slot.");719 720 if (CurrI->isKill()) {721 CurrI->eraseFromParent();722 continue;723 }724 725 if (delayHasHazard(*CurrI, RegDU, IM))726 continue;727 728 const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>();729 bool InMicroMipsMode = STI.inMicroMipsMode();730 const MipsInstrInfo *TII = STI.getInstrInfo();731 unsigned Opcode = (*Slot).getOpcode();732 733 // In mips1-4, should not put mflo into the delay slot for the return.734 if ((IsMFLOMFHI(CurrI->getOpcode())) &&735 (!STI.hasMips32() && !STI.hasMips5()))736 continue;737 738 // This is complicated by the tail call optimization. For non-PIC code739 // there is only a 32bit sized unconditional branch which can be assumed740 // to be able to reach the target. b16 only has a range of +/- 1 KB.741 // It's entirely possible that the target function is reachable with b16742 // but we don't have enough information to make that decision.743 if (InMicroMipsMode && TII->getInstSizeInBytes(*CurrI) == 2 &&744 (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch ||745 Opcode == Mips::PseudoIndirectBranch_MM ||746 Opcode == Mips::PseudoReturn || Opcode == Mips::TAILCALL))747 continue;748 // Instructions LWP/SWP and MOVEP should not be in a delay slot as that749 // results in unpredictable behaviour750 if (InMicroMipsMode && (Opcode == Mips::LWP_MM || Opcode == Mips::SWP_MM ||751 Opcode == Mips::MOVEP_MM))752 continue;753 754 Filler = CurrI;755 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot: ";756 CurrI->dump());757 758 return true;759 }760 761 return false;762}763 764bool MipsDelaySlotFiller::searchBackward(MachineBasicBlock &MBB,765 MachineInstr &Slot) const {766 if (DisableBackwardSearch)767 return false;768 769 auto *Fn = MBB.getParent();770 RegDefsUses RegDU(*Fn->getSubtarget().getRegisterInfo());771 MemDefsUses MemDU(&Fn->getFrameInfo());772 ReverseIter Filler;773 774 RegDU.init(Slot);775 776 MachineBasicBlock::iterator SlotI = Slot;777 if (!searchRange(MBB, ++SlotI.getReverse(), MBB.rend(), RegDU, MemDU, Slot,778 Filler)) {779 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": could not find instruction for delay "780 "slot using backwards search.\n");781 return false;782 }783 784 MBB.splice(std::next(SlotI), &MBB, Filler.getReverse());785 MIBundleBuilder(MBB, SlotI, std::next(SlotI, 2));786 ++UsefulSlots;787 return true;788}789 790bool MipsDelaySlotFiller::searchForward(MachineBasicBlock &MBB,791 Iter Slot) const {792 // Can handle only calls.793 if (DisableForwardSearch || !Slot->isCall())794 return false;795 796 RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());797 NoMemInstr NM;798 Iter Filler;799 800 RegDU.setCallerSaved(*Slot);801 802 if (!searchRange(MBB, std::next(Slot), MBB.end(), RegDU, NM, Slot, Filler)) {803 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": could not find instruction for delay "804 "slot using forwards search.\n");805 return false;806 }807 808 MBB.splice(std::next(Slot), &MBB, Filler);809 MIBundleBuilder(MBB, Slot, std::next(Slot, 2));810 ++UsefulSlots;811 return true;812}813 814bool MipsDelaySlotFiller::searchSuccBBs(MachineBasicBlock &MBB,815 Iter Slot) const {816 if (DisableSuccBBSearch)817 return false;818 819 MachineBasicBlock *SuccBB = selectSuccBB(MBB);820 821 if (!SuccBB)822 return false;823 824 RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo());825 bool HasMultipleSuccs = false;826 BB2BrMap BrMap;827 std::unique_ptr<InspectMemInstr> IM;828 Iter Filler;829 auto *Fn = MBB.getParent();830 831 // Iterate over SuccBB's predecessor list.832 for (MachineBasicBlock *Pred : SuccBB->predecessors())833 if (!examinePred(*Pred, *SuccBB, RegDU, HasMultipleSuccs, BrMap))834 return false;835 836 // Do not allow moving instructions which have unallocatable register operands837 // across basic block boundaries.838 RegDU.setUnallocatableRegs(*Fn);839 840 // Only allow moving loads from stack or constants if any of the SuccBB's841 // predecessors have multiple successors.842 if (HasMultipleSuccs) {843 IM.reset(new LoadFromStackOrConst());844 } else {845 const MachineFrameInfo &MFI = Fn->getFrameInfo();846 IM.reset(new MemDefsUses(&MFI));847 }848 849 if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Slot,850 Filler))851 return false;852 853 insertDelayFiller(Filler, BrMap);854 addLiveInRegs(Filler, *SuccBB);855 Filler->eraseFromParent();856 857 return true;858}859 860MachineBasicBlock *861MipsDelaySlotFiller::selectSuccBB(MachineBasicBlock &B) const {862 if (B.succ_empty())863 return nullptr;864 865 // Select the successor with the larget edge weight.866 auto &Prob = getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();867 MachineBasicBlock *S =868 *llvm::max_element(B.successors(), [&](const MachineBasicBlock *Dst0,869 const MachineBasicBlock *Dst1) {870 return Prob.getEdgeProbability(&B, Dst0) <871 Prob.getEdgeProbability(&B, Dst1);872 });873 return S->isEHPad() ? nullptr : S;874}875 876std::pair<MipsInstrInfo::BranchType, MachineInstr *>877MipsDelaySlotFiller::getBranch(MachineBasicBlock &MBB,878 const MachineBasicBlock &Dst) const {879 const MipsInstrInfo *TII =880 MBB.getParent()->getSubtarget<MipsSubtarget>().getInstrInfo();881 MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr;882 SmallVector<MachineInstr*, 2> BranchInstrs;883 SmallVector<MachineOperand, 2> Cond;884 885 MipsInstrInfo::BranchType R =886 TII->analyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs);887 888 if ((R == MipsInstrInfo::BT_None) || (R == MipsInstrInfo::BT_NoBranch))889 return std::make_pair(R, nullptr);890 891 if (R != MipsInstrInfo::BT_CondUncond) {892 if (!hasUnoccupiedSlot(BranchInstrs[0]))893 return std::make_pair(MipsInstrInfo::BT_None, nullptr);894 895 assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst)));896 897 return std::make_pair(R, BranchInstrs[0]);898 }899 900 assert((TrueBB == &Dst) || (FalseBB == &Dst));901 902 // Examine the conditional branch. See if its slot is occupied.903 if (hasUnoccupiedSlot(BranchInstrs[0]))904 return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]);905 906 // If that fails, try the unconditional branch.907 if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst))908 return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]);909 910 return std::make_pair(MipsInstrInfo::BT_None, nullptr);911}912 913bool MipsDelaySlotFiller::examinePred(MachineBasicBlock &Pred,914 const MachineBasicBlock &Succ,915 RegDefsUses &RegDU,916 bool &HasMultipleSuccs,917 BB2BrMap &BrMap) const {918 std::pair<MipsInstrInfo::BranchType, MachineInstr *> P =919 getBranch(Pred, Succ);920 921 // Return if either getBranch wasn't able to analyze the branches or there922 // were no branches with unoccupied slots.923 if (P.first == MipsInstrInfo::BT_None)924 return false;925 926 if ((P.first != MipsInstrInfo::BT_Uncond) &&927 (P.first != MipsInstrInfo::BT_NoBranch)) {928 HasMultipleSuccs = true;929 RegDU.addLiveOut(Pred, Succ);930 }931 932 BrMap[&Pred] = P.second;933 return true;934}935 936bool MipsDelaySlotFiller::delayHasHazard(const MachineInstr &Candidate,937 RegDefsUses &RegDU,938 InspectMemInstr &IM) const {939 assert(!Candidate.isKill() &&940 "KILL instructions should have been eliminated at this point.");941 942 bool HasHazard = Candidate.isImplicitDef();943 944 HasHazard |= IM.hasHazard(Candidate);945 HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands());946 947 return HasHazard;948}949 950bool MipsDelaySlotFiller::terminateSearch(const MachineInstr &Candidate) const {951 return (Candidate.isTerminator() || Candidate.isCall() ||952 Candidate.isPosition() || Candidate.isInlineAsm() ||953 Candidate.hasUnmodeledSideEffects());954}955 956/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay957/// slots in Mips MachineFunctions958FunctionPass *llvm::createMipsDelaySlotFillerPass() {959 return new MipsDelaySlotFiller();960}961