1327952Sdim//===- MipsDelaySlotFiller.cpp - Mips Delay Slot Filler -------------------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9249423Sdim// Simple pass to fill delay slots with useful instructions. 10193323Sed// 11193323Sed//===----------------------------------------------------------------------===// 12193323Sed 13276479Sdim#include "MCTargetDesc/MipsMCNaCl.h" 14193323Sed#include "Mips.h" 15249423Sdim#include "MipsInstrInfo.h" 16327952Sdim#include "MipsRegisterInfo.h" 17321369Sdim#include "MipsSubtarget.h" 18249423Sdim#include "llvm/ADT/BitVector.h" 19321369Sdim#include "llvm/ADT/DenseMap.h" 20321369Sdim#include "llvm/ADT/PointerUnion.h" 21249423Sdim#include "llvm/ADT/SmallPtrSet.h" 22321369Sdim#include "llvm/ADT/SmallVector.h" 23249423Sdim#include "llvm/ADT/Statistic.h" 24321369Sdim#include "llvm/ADT/StringRef.h" 25249423Sdim#include "llvm/Analysis/AliasAnalysis.h" 26249423Sdim#include "llvm/Analysis/ValueTracking.h" 27321369Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 28249423Sdim#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 29321369Sdim#include "llvm/CodeGen/MachineFunction.h" 30193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 31321369Sdim#include "llvm/CodeGen/MachineInstr.h" 32193323Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 33321369Sdim#include "llvm/CodeGen/MachineOperand.h" 34276479Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 35249423Sdim#include "llvm/CodeGen/PseudoSourceValue.h" 36327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 37327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 38321369Sdim#include "llvm/MC/MCInstrDesc.h" 39321369Sdim#include "llvm/MC/MCRegisterInfo.h" 40321369Sdim#include "llvm/Support/Casting.h" 41321369Sdim#include "llvm/Support/CodeGen.h" 42226633Sdim#include "llvm/Support/CommandLine.h" 43321369Sdim#include "llvm/Support/ErrorHandling.h" 44226633Sdim#include "llvm/Target/TargetMachine.h" 45321369Sdim#include <algorithm> 46321369Sdim#include <cassert> 47321369Sdim#include <iterator> 48321369Sdim#include <memory> 49321369Sdim#include <utility> 50193323Sed 51193323Sedusing namespace llvm; 52193323Sed 53341825Sdim#define DEBUG_TYPE "mips-delay-slot-filler" 54276479Sdim 55193323SedSTATISTIC(FilledSlots, "Number of delay slots filled"); 56226633SdimSTATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 57226633Sdim " are not NOP."); 58193323Sed 59243830Sdimstatic cl::opt<bool> DisableDelaySlotFiller( 60243830Sdim "disable-mips-delay-filler", 61226633Sdim cl::init(false), 62249423Sdim cl::desc("Fill all delay slots with NOPs."), 63226633Sdim cl::Hidden); 64226633Sdim 65249423Sdimstatic cl::opt<bool> DisableForwardSearch( 66249423Sdim "disable-mips-df-forward-search", 67249423Sdim cl::init(true), 68249423Sdim cl::desc("Disallow MIPS delay filler to search forward."), 69249423Sdim cl::Hidden); 70249423Sdim 71249423Sdimstatic cl::opt<bool> DisableSuccBBSearch( 72249423Sdim "disable-mips-df-succbb-search", 73249423Sdim cl::init(true), 74249423Sdim cl::desc("Disallow MIPS delay filler to search successor basic blocks."), 75249423Sdim cl::Hidden); 76249423Sdim 77249423Sdimstatic cl::opt<bool> DisableBackwardSearch( 78249423Sdim "disable-mips-df-backward-search", 79239462Sdim cl::init(false), 80249423Sdim cl::desc("Disallow MIPS delay filler to search backward."), 81239462Sdim cl::Hidden); 82239462Sdim 83309124Sdimenum CompactBranchPolicy { 84309124Sdim CB_Never, ///< The policy 'never' may in some circumstances or for some 85309124Sdim ///< ISAs not be absolutely adhered to. 86309124Sdim CB_Optimal, ///< Optimal is the default and will produce compact branches 87309124Sdim ///< when delay slots cannot be filled. 88309124Sdim CB_Always ///< 'always' may in some circumstances may not be 89309124Sdim ///< absolutely adhered to there may not be a corresponding 90309124Sdim ///< compact form of a branch. 91309124Sdim}; 92309124Sdim 93309124Sdimstatic cl::opt<CompactBranchPolicy> MipsCompactBranchPolicy( 94360784Sdim "mips-compact-branches", cl::Optional, cl::init(CB_Optimal), 95360784Sdim cl::desc("MIPS Specific: Compact branch policy."), 96360784Sdim cl::values(clEnumValN(CB_Never, "never", 97360784Sdim "Do not use compact branches if possible."), 98360784Sdim clEnumValN(CB_Optimal, "optimal", 99360784Sdim "Use compact branches where appropiate (default)."), 100360784Sdim clEnumValN(CB_Always, "always", 101360784Sdim "Always use compact branches if possible."))); 102309124Sdim 103193323Sednamespace { 104321369Sdim 105327952Sdim using Iter = MachineBasicBlock::iterator; 106327952Sdim using ReverseIter = MachineBasicBlock::reverse_iterator; 107327952Sdim using BB2BrMap = SmallDenseMap<MachineBasicBlock *, MachineInstr *, 2>; 108193323Sed 109249423Sdim class RegDefsUses { 110249423Sdim public: 111288943Sdim RegDefsUses(const TargetRegisterInfo &TRI); 112321369Sdim 113249423Sdim void init(const MachineInstr &MI); 114249423Sdim 115249423Sdim /// This function sets all caller-saved registers in Defs. 116249423Sdim void setCallerSaved(const MachineInstr &MI); 117249423Sdim 118249423Sdim /// This function sets all unallocatable registers in Defs. 119249423Sdim void setUnallocatableRegs(const MachineFunction &MF); 120249423Sdim 121249423Sdim /// Set bits in Uses corresponding to MBB's live-out registers except for 122249423Sdim /// the registers that are live-in to SuccBB. 123249423Sdim void addLiveOut(const MachineBasicBlock &MBB, 124249423Sdim const MachineBasicBlock &SuccBB); 125249423Sdim 126249423Sdim bool update(const MachineInstr &MI, unsigned Begin, unsigned End); 127249423Sdim 128249423Sdim private: 129249423Sdim bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg, 130249423Sdim bool IsDef) const; 131249423Sdim 132249423Sdim /// Returns true if Reg or its alias is in RegSet. 133249423Sdim bool isRegInSet(const BitVector &RegSet, unsigned Reg) const; 134249423Sdim 135249423Sdim const TargetRegisterInfo &TRI; 136249423Sdim BitVector Defs, Uses; 137249423Sdim }; 138249423Sdim 139249423Sdim /// Base class for inspecting loads and stores. 140249423Sdim class InspectMemInstr { 141249423Sdim public: 142321369Sdim InspectMemInstr(bool ForbidMemInstr_) : ForbidMemInstr(ForbidMemInstr_) {} 143321369Sdim virtual ~InspectMemInstr() = default; 144249423Sdim 145249423Sdim /// Return true if MI cannot be moved to delay slot. 146249423Sdim bool hasHazard(const MachineInstr &MI); 147249423Sdim 148249423Sdim protected: 149249423Sdim /// Flags indicating whether loads or stores have been seen. 150321369Sdim bool OrigSeenLoad = false; 151321369Sdim bool OrigSeenStore = false; 152321369Sdim bool SeenLoad = false; 153321369Sdim bool SeenStore = false; 154249423Sdim 155249423Sdim /// Memory instructions are not allowed to move to delay slot if this flag 156249423Sdim /// is true. 157249423Sdim bool ForbidMemInstr; 158249423Sdim 159249423Sdim private: 160249423Sdim virtual bool hasHazard_(const MachineInstr &MI) = 0; 161249423Sdim }; 162249423Sdim 163249423Sdim /// This subclass rejects any memory instructions. 164249423Sdim class NoMemInstr : public InspectMemInstr { 165249423Sdim public: 166249423Sdim NoMemInstr() : InspectMemInstr(true) {} 167321369Sdim 168249423Sdim private: 169276479Sdim bool hasHazard_(const MachineInstr &MI) override { return true; } 170249423Sdim }; 171249423Sdim 172249423Sdim /// This subclass accepts loads from stacks and constant loads. 173249423Sdim class LoadFromStackOrConst : public InspectMemInstr { 174249423Sdim public: 175249423Sdim LoadFromStackOrConst() : InspectMemInstr(false) {} 176321369Sdim 177249423Sdim private: 178276479Sdim bool hasHazard_(const MachineInstr &MI) override; 179249423Sdim }; 180249423Sdim 181249423Sdim /// This subclass uses memory dependence information to determine whether a 182249423Sdim /// memory instruction can be moved to a delay slot. 183249423Sdim class MemDefsUses : public InspectMemInstr { 184249423Sdim public: 185288943Sdim MemDefsUses(const DataLayout &DL, const MachineFrameInfo *MFI); 186249423Sdim 187249423Sdim private: 188327952Sdim using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>; 189249423Sdim 190276479Sdim bool hasHazard_(const MachineInstr &MI) override; 191276479Sdim 192249423Sdim /// Update Defs and Uses. Return true if there exist dependences that 193249423Sdim /// disqualify the delay slot candidate between V and values in Uses and 194249423Sdim /// Defs. 195276479Sdim bool updateDefsUses(ValueType V, bool MayStore); 196249423Sdim 197249423Sdim /// Get the list of underlying objects of MI's memory operand. 198249423Sdim bool getUnderlyingObjects(const MachineInstr &MI, 199276479Sdim SmallVectorImpl<ValueType> &Objects) const; 200249423Sdim 201249423Sdim const MachineFrameInfo *MFI; 202276479Sdim SmallPtrSet<ValueType, 4> Uses, Defs; 203288943Sdim const DataLayout &DL; 204249423Sdim 205249423Sdim /// Flags indicating whether loads or stores with no underlying objects have 206249423Sdim /// been seen. 207321369Sdim bool SeenNoObjLoad = false; 208321369Sdim bool SeenNoObjStore = false; 209249423Sdim }; 210249423Sdim 211341825Sdim class MipsDelaySlotFiller : public MachineFunctionPass { 212249423Sdim public: 213341825Sdim MipsDelaySlotFiller() : MachineFunctionPass(ID) { 214341825Sdim initializeMipsDelaySlotFillerPass(*PassRegistry::getPassRegistry()); 215341825Sdim } 216193323Sed 217314564Sdim StringRef getPassName() const override { return "Mips Delay Slot Filler"; } 218193323Sed 219276479Sdim bool runOnMachineFunction(MachineFunction &F) override { 220321369Sdim TM = &F.getTarget(); 221193323Sed bool Changed = false; 222193323Sed for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 223193323Sed FI != FE; ++FI) 224193323Sed Changed |= runOnMachineBasicBlock(*FI); 225276479Sdim 226276479Sdim // This pass invalidates liveness information when it reorders 227276479Sdim // instructions to fill delay slot. Without this, -verify-machineinstrs 228276479Sdim // will fail. 229276479Sdim if (Changed) 230276479Sdim F.getRegInfo().invalidateLiveness(); 231276479Sdim 232193323Sed return Changed; 233193323Sed } 234193323Sed 235309124Sdim MachineFunctionProperties getRequiredProperties() const override { 236309124Sdim return MachineFunctionProperties().set( 237314564Sdim MachineFunctionProperties::Property::NoVRegs); 238309124Sdim } 239309124Sdim 240276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 241249423Sdim AU.addRequired<MachineBranchProbabilityInfo>(); 242249423Sdim MachineFunctionPass::getAnalysisUsage(AU); 243249423Sdim } 244226633Sdim 245341825Sdim static char ID; 246341825Sdim 247249423Sdim private: 248249423Sdim bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 249226633Sdim 250309124Sdim Iter replaceWithCompactBranch(MachineBasicBlock &MBB, Iter Branch, 251309124Sdim const DebugLoc &DL); 252280031Sdim 253249423Sdim /// This function checks if it is valid to move Candidate to the delay slot 254249423Sdim /// and returns true if it isn't. It also updates memory and register 255249423Sdim /// dependence information. 256249423Sdim bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, 257249423Sdim InspectMemInstr &IM) const; 258226633Sdim 259249423Sdim /// This function searches range [Begin, End) for an instruction that can be 260249423Sdim /// moved to the delay slot. Returns true on success. 261249423Sdim template<typename IterTy> 262249423Sdim bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, 263288943Sdim RegDefsUses &RegDU, InspectMemInstr &IM, Iter Slot, 264288943Sdim IterTy &Filler) const; 265226633Sdim 266249423Sdim /// This function searches in the backward direction for an instruction that 267249423Sdim /// can be moved to the delay slot. Returns true on success. 268314564Sdim bool searchBackward(MachineBasicBlock &MBB, MachineInstr &Slot) const; 269226633Sdim 270249423Sdim /// This function searches MBB in the forward direction for an instruction 271249423Sdim /// that can be moved to the delay slot. Returns true on success. 272249423Sdim bool searchForward(MachineBasicBlock &MBB, Iter Slot) const; 273226633Sdim 274249423Sdim /// This function searches one of MBB's successor blocks for an instruction 275249423Sdim /// that can be moved to the delay slot and inserts clones of the 276249423Sdim /// instruction into the successor's predecessor blocks. 277249423Sdim bool searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const; 278226633Sdim 279249423Sdim /// Pick a successor block of MBB. Return NULL if MBB doesn't have a 280249423Sdim /// successor block that is not a landing pad. 281249423Sdim MachineBasicBlock *selectSuccBB(MachineBasicBlock &B) const; 282249423Sdim 283249423Sdim /// This function analyzes MBB and returns an instruction with an unoccupied 284249423Sdim /// slot that branches to Dst. 285249423Sdim std::pair<MipsInstrInfo::BranchType, MachineInstr *> 286249423Sdim getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const; 287249423Sdim 288249423Sdim /// Examine Pred and see if it is possible to insert an instruction into 289249423Sdim /// one of its branches delay slot or its end. 290249423Sdim bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ, 291249423Sdim RegDefsUses &RegDU, bool &HasMultipleSuccs, 292249423Sdim BB2BrMap &BrMap) const; 293249423Sdim 294249423Sdim bool terminateSearch(const MachineInstr &Candidate) const; 295249423Sdim 296327952Sdim const TargetMachine *TM = nullptr; 297193323Sed }; 298321369Sdim 299321369Sdim} // end anonymous namespace 300321369Sdim 301341825Sdimchar MipsDelaySlotFiller::ID = 0; 302327952Sdim 303249423Sdimstatic bool hasUnoccupiedSlot(const MachineInstr *MI) { 304249423Sdim return MI->hasDelaySlot() && !MI->isBundledWithSucc(); 305249423Sdim} 306249423Sdim 307341825SdimINITIALIZE_PASS(MipsDelaySlotFiller, DEBUG_TYPE, 308341825Sdim "Fill delay slot for MIPS", false, false) 309341825Sdim 310249423Sdim/// This function inserts clones of Filler into predecessor blocks. 311249423Sdimstatic void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) { 312249423Sdim MachineFunction *MF = Filler->getParent()->getParent(); 313249423Sdim 314249423Sdim for (BB2BrMap::const_iterator I = BrMap.begin(); I != BrMap.end(); ++I) { 315249423Sdim if (I->second) { 316249423Sdim MIBundleBuilder(I->second).append(MF->CloneMachineInstr(&*Filler)); 317249423Sdim ++UsefulSlots; 318249423Sdim } else { 319249423Sdim I->first->insert(I->first->end(), MF->CloneMachineInstr(&*Filler)); 320249423Sdim } 321249423Sdim } 322249423Sdim} 323249423Sdim 324249423Sdim/// This function adds registers Filler defines to MBB's live-in register list. 325249423Sdimstatic void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) { 326249423Sdim for (unsigned I = 0, E = Filler->getNumOperands(); I != E; ++I) { 327249423Sdim const MachineOperand &MO = Filler->getOperand(I); 328249423Sdim unsigned R; 329249423Sdim 330249423Sdim if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg())) 331249423Sdim continue; 332249423Sdim 333249423Sdim#ifndef NDEBUG 334249423Sdim const MachineFunction &MF = *MBB.getParent(); 335288943Sdim assert(MF.getSubtarget().getRegisterInfo()->getAllocatableSet(MF).test(R) && 336249423Sdim "Shouldn't move an instruction with unallocatable registers across " 337249423Sdim "basic block boundaries."); 338249423Sdim#endif 339249423Sdim 340249423Sdim if (!MBB.isLiveIn(R)) 341249423Sdim MBB.addLiveIn(R); 342249423Sdim } 343249423Sdim} 344249423Sdim 345288943SdimRegDefsUses::RegDefsUses(const TargetRegisterInfo &TRI) 346288943Sdim : TRI(TRI), Defs(TRI.getNumRegs(), false), Uses(TRI.getNumRegs(), false) {} 347249423Sdim 348249423Sdimvoid RegDefsUses::init(const MachineInstr &MI) { 349249423Sdim // Add all register operands which are explicit and non-variadic. 350249423Sdim update(MI, 0, MI.getDesc().getNumOperands()); 351249423Sdim 352249423Sdim // If MI is a call, add RA to Defs to prevent users of RA from going into 353249423Sdim // delay slot. 354249423Sdim if (MI.isCall()) 355249423Sdim Defs.set(Mips::RA); 356249423Sdim 357249423Sdim // Add all implicit register operands of branch instructions except 358249423Sdim // register AT. 359249423Sdim if (MI.isBranch()) { 360249423Sdim update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands()); 361249423Sdim Defs.reset(Mips::AT); 362249423Sdim } 363249423Sdim} 364249423Sdim 365249423Sdimvoid RegDefsUses::setCallerSaved(const MachineInstr &MI) { 366249423Sdim assert(MI.isCall()); 367249423Sdim 368288943Sdim // Add RA/RA_64 to Defs to prevent users of RA/RA_64 from going into 369288943Sdim // the delay slot. The reason is that RA/RA_64 must not be changed 370288943Sdim // in the delay slot so that the callee can return to the caller. 371288943Sdim if (MI.definesRegister(Mips::RA) || MI.definesRegister(Mips::RA_64)) { 372288943Sdim Defs.set(Mips::RA); 373288943Sdim Defs.set(Mips::RA_64); 374288943Sdim } 375288943Sdim 376249423Sdim // If MI is a call, add all caller-saved registers to Defs. 377249423Sdim BitVector CallerSavedRegs(TRI.getNumRegs(), true); 378249423Sdim 379249423Sdim CallerSavedRegs.reset(Mips::ZERO); 380249423Sdim CallerSavedRegs.reset(Mips::ZERO_64); 381249423Sdim 382288943Sdim for (const MCPhysReg *R = TRI.getCalleeSavedRegs(MI.getParent()->getParent()); 383288943Sdim *R; ++R) 384249423Sdim for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI) 385249423Sdim CallerSavedRegs.reset(*AI); 386249423Sdim 387249423Sdim Defs |= CallerSavedRegs; 388249423Sdim} 389249423Sdim 390249423Sdimvoid RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) { 391249423Sdim BitVector AllocSet = TRI.getAllocatableSet(MF); 392249423Sdim 393321369Sdim for (unsigned R : AllocSet.set_bits()) 394249423Sdim for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI) 395249423Sdim AllocSet.set(*AI); 396249423Sdim 397249423Sdim AllocSet.set(Mips::ZERO); 398249423Sdim AllocSet.set(Mips::ZERO_64); 399249423Sdim 400249423Sdim Defs |= AllocSet.flip(); 401249423Sdim} 402249423Sdim 403249423Sdimvoid RegDefsUses::addLiveOut(const MachineBasicBlock &MBB, 404249423Sdim const MachineBasicBlock &SuccBB) { 405249423Sdim for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 406249423Sdim SE = MBB.succ_end(); SI != SE; ++SI) 407249423Sdim if (*SI != &SuccBB) 408296417Sdim for (const auto &LI : (*SI)->liveins()) 409296417Sdim Uses.set(LI.PhysReg); 410249423Sdim} 411249423Sdim 412249423Sdimbool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) { 413249423Sdim BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs()); 414249423Sdim bool HasHazard = false; 415249423Sdim 416249423Sdim for (unsigned I = Begin; I != End; ++I) { 417249423Sdim const MachineOperand &MO = MI.getOperand(I); 418249423Sdim 419360784Sdim if (MO.isReg() && MO.getReg()) { 420360784Sdim if (checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef())) { 421360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found register hazard for operand " 422360784Sdim << I << ": "; 423360784Sdim MO.dump()); 424360784Sdim HasHazard = true; 425360784Sdim } 426360784Sdim } 427249423Sdim } 428249423Sdim 429249423Sdim Defs |= NewDefs; 430249423Sdim Uses |= NewUses; 431249423Sdim 432249423Sdim return HasHazard; 433249423Sdim} 434249423Sdim 435249423Sdimbool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, 436249423Sdim unsigned Reg, bool IsDef) const { 437249423Sdim if (IsDef) { 438249423Sdim NewDefs.set(Reg); 439249423Sdim // check whether Reg has already been defined or used. 440249423Sdim return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg)); 441249423Sdim } 442249423Sdim 443249423Sdim NewUses.set(Reg); 444249423Sdim // check whether Reg has already been defined. 445249423Sdim return isRegInSet(Defs, Reg); 446249423Sdim} 447249423Sdim 448249423Sdimbool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const { 449249423Sdim // Check Reg and all aliased Registers. 450249423Sdim for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI) 451249423Sdim if (RegSet.test(*AI)) 452249423Sdim return true; 453249423Sdim return false; 454249423Sdim} 455249423Sdim 456249423Sdimbool InspectMemInstr::hasHazard(const MachineInstr &MI) { 457249423Sdim if (!MI.mayStore() && !MI.mayLoad()) 458249423Sdim return false; 459249423Sdim 460249423Sdim if (ForbidMemInstr) 461249423Sdim return true; 462249423Sdim 463249423Sdim OrigSeenLoad = SeenLoad; 464249423Sdim OrigSeenStore = SeenStore; 465249423Sdim SeenLoad |= MI.mayLoad(); 466249423Sdim SeenStore |= MI.mayStore(); 467249423Sdim 468249423Sdim // If MI is an ordered or volatile memory reference, disallow moving 469249423Sdim // subsequent loads and stores to delay slot. 470249423Sdim if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) { 471249423Sdim ForbidMemInstr = true; 472249423Sdim return true; 473249423Sdim } 474249423Sdim 475249423Sdim return hasHazard_(MI); 476249423Sdim} 477249423Sdim 478249423Sdimbool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) { 479249423Sdim if (MI.mayStore()) 480249423Sdim return true; 481249423Sdim 482276479Sdim if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getPseudoValue()) 483249423Sdim return true; 484249423Sdim 485276479Sdim if (const PseudoSourceValue *PSV = 486276479Sdim (*MI.memoperands_begin())->getPseudoValue()) { 487276479Sdim if (isa<FixedStackPseudoSourceValue>(PSV)) 488276479Sdim return false; 489296417Sdim return !PSV->isConstant(nullptr) && !PSV->isStack(); 490276479Sdim } 491249423Sdim 492249423Sdim return true; 493249423Sdim} 494249423Sdim 495288943SdimMemDefsUses::MemDefsUses(const DataLayout &DL, const MachineFrameInfo *MFI_) 496321369Sdim : InspectMemInstr(false), MFI(MFI_), DL(DL) {} 497249423Sdim 498249423Sdimbool MemDefsUses::hasHazard_(const MachineInstr &MI) { 499249423Sdim bool HasHazard = false; 500249423Sdim 501249423Sdim // Check underlying object list. 502353358Sdim SmallVector<ValueType, 4> Objs; 503249423Sdim if (getUnderlyingObjects(MI, Objs)) { 504353358Sdim for (ValueType VT : Objs) 505353358Sdim HasHazard |= updateDefsUses(VT, MI.mayStore()); 506249423Sdim return HasHazard; 507249423Sdim } 508249423Sdim 509249423Sdim // No underlying objects found. 510249423Sdim HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore); 511249423Sdim HasHazard |= MI.mayLoad() || OrigSeenStore; 512249423Sdim 513249423Sdim SeenNoObjLoad |= MI.mayLoad(); 514249423Sdim SeenNoObjStore |= MI.mayStore(); 515249423Sdim 516249423Sdim return HasHazard; 517249423Sdim} 518249423Sdim 519276479Sdimbool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) { 520249423Sdim if (MayStore) 521280031Sdim return !Defs.insert(V).second || Uses.count(V) || SeenNoObjStore || 522280031Sdim SeenNoObjLoad; 523249423Sdim 524249423Sdim Uses.insert(V); 525249423Sdim return Defs.count(V) || SeenNoObjStore; 526249423Sdim} 527249423Sdim 528249423Sdimbool MemDefsUses:: 529249423SdimgetUnderlyingObjects(const MachineInstr &MI, 530276479Sdim SmallVectorImpl<ValueType> &Objects) const { 531353358Sdim if (!MI.hasOneMemOperand()) 532249423Sdim return false; 533249423Sdim 534353358Sdim auto & MMO = **MI.memoperands_begin(); 535353358Sdim 536353358Sdim if (const PseudoSourceValue *PSV = MMO.getPseudoValue()) { 537276479Sdim if (!PSV->isAliased(MFI)) 538276479Sdim return false; 539276479Sdim Objects.push_back(PSV); 540276479Sdim return true; 541276479Sdim } 542276479Sdim 543353358Sdim if (const Value *V = MMO.getValue()) { 544353358Sdim SmallVector<const Value *, 4> Objs; 545353358Sdim GetUnderlyingObjects(V, Objs, DL); 546249423Sdim 547353358Sdim for (const Value *UValue : Objs) { 548353358Sdim if (!isIdentifiedObject(V)) 549353358Sdim return false; 550249423Sdim 551353358Sdim Objects.push_back(UValue); 552353358Sdim } 553353358Sdim return true; 554249423Sdim } 555249423Sdim 556353358Sdim return false; 557249423Sdim} 558249423Sdim 559280031Sdim// Replace Branch with the compact branch instruction. 560341825SdimIter MipsDelaySlotFiller::replaceWithCompactBranch(MachineBasicBlock &MBB, 561341825Sdim Iter Branch, 562341825Sdim const DebugLoc &DL) { 563309124Sdim const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>(); 564309124Sdim const MipsInstrInfo *TII = STI.getInstrInfo(); 565280031Sdim 566309124Sdim unsigned NewOpcode = TII->getEquivalentCompactForm(Branch); 567309124Sdim Branch = TII->genInstrWithNewOpc(NewOpcode, Branch); 568280031Sdim 569309124Sdim std::next(Branch)->eraseFromParent(); 570280031Sdim return Branch; 571280031Sdim} 572280031Sdim 573280031Sdim// For given opcode returns opcode of corresponding instruction with short 574280031Sdim// delay slot. 575321369Sdim// For the pseudo TAILCALL*_MM instructions return the short delay slot 576314564Sdim// form. Unfortunately, TAILCALL<->b16 is denied as b16 has a limited range 577314564Sdim// that is too short to make use of for tail calls. 578280031Sdimstatic int getEquivalentCallShort(int Opcode) { 579280031Sdim switch (Opcode) { 580280031Sdim case Mips::BGEZAL: 581280031Sdim return Mips::BGEZALS_MM; 582280031Sdim case Mips::BLTZAL: 583280031Sdim return Mips::BLTZALS_MM; 584280031Sdim case Mips::JAL: 585341825Sdim case Mips::JAL_MM: 586280031Sdim return Mips::JALS_MM; 587280031Sdim case Mips::JALR: 588280031Sdim return Mips::JALRS_MM; 589280031Sdim case Mips::JALR16_MM: 590280031Sdim return Mips::JALRS16_MM; 591314564Sdim case Mips::TAILCALL_MM: 592314564Sdim llvm_unreachable("Attempting to shorten the TAILCALL_MM pseudo!"); 593314564Sdim case Mips::TAILCALLREG: 594314564Sdim return Mips::JR16_MM; 595280031Sdim default: 596280031Sdim llvm_unreachable("Unexpected call instruction for microMIPS."); 597280031Sdim } 598280031Sdim} 599280031Sdim 600193323Sed/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 601226633Sdim/// We assume there is only one delay slot per delayed instruction. 602341825Sdimbool MipsDelaySlotFiller::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 603193323Sed bool Changed = false; 604288943Sdim const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>(); 605288943Sdim bool InMicroMipsMode = STI.inMicroMipsMode(); 606288943Sdim const MipsInstrInfo *TII = STI.getInstrInfo(); 607226633Sdim 608249423Sdim for (Iter I = MBB.begin(); I != MBB.end(); ++I) { 609249423Sdim if (!hasUnoccupiedSlot(&*I)) 610249423Sdim continue; 611218893Sdim 612327952Sdim // Delay slot filling is disabled at -O0, or in microMIPS32R6. 613327952Sdim if (!DisableDelaySlotFiller && (TM->getOptLevel() != CodeGenOpt::None) && 614327952Sdim !(InMicroMipsMode && STI.hasMips32r6())) { 615226633Sdim 616280031Sdim bool Filled = false; 617226633Sdim 618309124Sdim if (MipsCompactBranchPolicy.getValue() != CB_Always || 619309124Sdim !TII->getEquivalentCompactForm(I)) { 620314564Sdim if (searchBackward(MBB, *I)) { 621360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot" 622360784Sdim " in backwards search.\n"); 623280031Sdim Filled = true; 624309124Sdim } else if (I->isTerminator()) { 625309124Sdim if (searchSuccBBs(MBB, I)) { 626309124Sdim Filled = true; 627360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot" 628360784Sdim " in successor BB search.\n"); 629309124Sdim } 630309124Sdim } else if (searchForward(MBB, I)) { 631360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot" 632360784Sdim " in forwards search.\n"); 633309124Sdim Filled = true; 634280031Sdim } 635280031Sdim } 636280031Sdim 637280031Sdim if (Filled) { 638280031Sdim // Get instruction with delay slot. 639309124Sdim MachineBasicBlock::instr_iterator DSI = I.getInstrIterator(); 640280031Sdim 641314564Sdim if (InMicroMipsMode && TII->getInstSizeInBytes(*std::next(DSI)) == 2 && 642280031Sdim DSI->isCall()) { 643280031Sdim // If instruction in delay slot is 16b change opcode to 644280031Sdim // corresponding instruction with short delay slot. 645314564Sdim 646314564Sdim // TODO: Implement an instruction mapping table of 16bit opcodes to 647314564Sdim // 32bit opcodes so that an instruction can be expanded. This would 648314564Sdim // save 16 bits as a TAILCALL_MM pseudo requires a fullsized nop. 649341825Sdim // TODO: Permit b16 when branching backwards to the same function 650314564Sdim // if it is in range. 651280031Sdim DSI->setDesc(TII->get(getEquivalentCallShort(DSI->getOpcode()))); 652280031Sdim } 653327952Sdim ++FilledSlots; 654327952Sdim Changed = true; 655249423Sdim continue; 656249423Sdim } 657249423Sdim } 658239462Sdim 659309124Sdim // For microMIPS if instruction is BEQ or BNE with one ZERO register, then 660309124Sdim // instead of adding NOP replace this instruction with the corresponding 661309124Sdim // compact branch instruction, i.e. BEQZC or BNEZC. Additionally 662309124Sdim // PseudoReturn and PseudoIndirectBranch are expanded to JR_MM, so they can 663309124Sdim // be replaced with JRC16_MM. 664309124Sdim 665309124Sdim // For MIPSR6 attempt to produce the corresponding compact (no delay slot) 666309124Sdim // form of the CTI. For indirect jumps this will not require inserting a 667309124Sdim // NOP and for branches will hopefully avoid requiring a NOP. 668309124Sdim if ((InMicroMipsMode || 669309124Sdim (STI.hasMips32r6() && MipsCompactBranchPolicy != CB_Never)) && 670309124Sdim TII->getEquivalentCompactForm(I)) { 671309124Sdim I = replaceWithCompactBranch(MBB, I, I->getDebugLoc()); 672327952Sdim Changed = true; 673309124Sdim continue; 674280031Sdim } 675309124Sdim 676288943Sdim // Bundle the NOP to the instruction with the delay slot. 677360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE << ": could not fill delay slot for "; 678360784Sdim I->dump()); 679288943Sdim BuildMI(MBB, std::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); 680288943Sdim MIBundleBuilder(MBB, I, std::next(I, 2)); 681327952Sdim ++FilledSlots; 682327952Sdim Changed = true; 683249423Sdim } 684249423Sdim 685193323Sed return Changed; 686193323Sed} 687193323Sed 688341825Sdimtemplate <typename IterTy> 689341825Sdimbool MipsDelaySlotFiller::searchRange(MachineBasicBlock &MBB, IterTy Begin, 690341825Sdim IterTy End, RegDefsUses &RegDU, 691341825Sdim InspectMemInstr &IM, Iter Slot, 692341825Sdim IterTy &Filler) const { 693288943Sdim for (IterTy I = Begin; I != End;) { 694288943Sdim IterTy CurrI = I; 695288943Sdim ++I; 696360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE ": checking instruction: "; CurrI->dump()); 697226633Sdim // skip debug value 698360784Sdim if (CurrI->isDebugInstr()) { 699360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE ": ignoring debug instruction: "; 700360784Sdim CurrI->dump()); 701226633Sdim continue; 702360784Sdim } 703226633Sdim 704360784Sdim if (CurrI->isBundle()) { 705360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE ": ignoring BUNDLE instruction: "; 706360784Sdim CurrI->dump()); 707360784Sdim // However, we still need to update the register def-use information. 708360784Sdim RegDU.update(*CurrI, 0, CurrI->getNumOperands()); 709360784Sdim continue; 710360784Sdim } 711360784Sdim 712360784Sdim if (terminateSearch(*CurrI)) { 713360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE ": should terminate search: "; 714360784Sdim CurrI->dump()); 715226633Sdim break; 716360784Sdim } 717226633Sdim 718288943Sdim assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) && 719249423Sdim "Cannot put calls, returns or branches in delay slot."); 720249423Sdim 721288943Sdim if (CurrI->isKill()) { 722288943Sdim CurrI->eraseFromParent(); 723226633Sdim continue; 724288943Sdim } 725226633Sdim 726288943Sdim if (delayHasHazard(*CurrI, RegDU, IM)) 727288943Sdim continue; 728288943Sdim 729288943Sdim const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>(); 730288943Sdim if (STI.isTargetNaCl()) { 731276479Sdim // In NaCl, instructions that must be masked are forbidden in delay slots. 732276479Sdim // We only check for loads, stores and SP changes. Calls, returns and 733276479Sdim // branches are not checked because non-NaCl targets never put them in 734276479Sdim // delay slots. 735276479Sdim unsigned AddrIdx; 736288943Sdim if ((isBasePlusOffsetMemoryAccess(CurrI->getOpcode(), &AddrIdx) && 737288943Sdim baseRegNeedsLoadStoreMask(CurrI->getOperand(AddrIdx).getReg())) || 738288943Sdim CurrI->modifiesRegister(Mips::SP, STI.getRegisterInfo())) 739276479Sdim continue; 740276479Sdim } 741276479Sdim 742288943Sdim bool InMicroMipsMode = STI.inMicroMipsMode(); 743288943Sdim const MipsInstrInfo *TII = STI.getInstrInfo(); 744280031Sdim unsigned Opcode = (*Slot).getOpcode(); 745314564Sdim // This is complicated by the tail call optimization. For non-PIC code 746314564Sdim // there is only a 32bit sized unconditional branch which can be assumed 747314564Sdim // to be able to reach the target. b16 only has a range of +/- 1 KB. 748314564Sdim // It's entirely possible that the target function is reachable with b16 749314564Sdim // but we don't have enough information to make that decision. 750314564Sdim if (InMicroMipsMode && TII->getInstSizeInBytes(*CurrI) == 2 && 751280031Sdim (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch || 752349004Sdim Opcode == Mips::PseudoIndirectBranch_MM || 753314564Sdim Opcode == Mips::PseudoReturn || Opcode == Mips::TAILCALL)) 754280031Sdim continue; 755344779Sdim // Instructions LWP/SWP and MOVEP should not be in a delay slot as that 756341825Sdim // results in unpredictable behaviour 757344779Sdim if (InMicroMipsMode && (Opcode == Mips::LWP_MM || Opcode == Mips::SWP_MM || 758344779Sdim Opcode == Mips::MOVEP_MM)) 759341825Sdim continue; 760280031Sdim 761288943Sdim Filler = CurrI; 762360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot: "; 763360784Sdim CurrI->dump()); 764360784Sdim 765226633Sdim return true; 766226633Sdim } 767226633Sdim 768226633Sdim return false; 769226633Sdim} 770226633Sdim 771341825Sdimbool MipsDelaySlotFiller::searchBackward(MachineBasicBlock &MBB, 772341825Sdim MachineInstr &Slot) const { 773249423Sdim if (DisableBackwardSearch) 774249423Sdim return false; 775226633Sdim 776296417Sdim auto *Fn = MBB.getParent(); 777296417Sdim RegDefsUses RegDU(*Fn->getSubtarget().getRegisterInfo()); 778314564Sdim MemDefsUses MemDU(Fn->getDataLayout(), &Fn->getFrameInfo()); 779249423Sdim ReverseIter Filler; 780226633Sdim 781314564Sdim RegDU.init(Slot); 782249423Sdim 783314564Sdim MachineBasicBlock::iterator SlotI = Slot; 784314564Sdim if (!searchRange(MBB, ++SlotI.getReverse(), MBB.rend(), RegDU, MemDU, Slot, 785360784Sdim Filler)) { 786360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE ": could not find instruction for delay " 787360784Sdim "slot using backwards search.\n"); 788261991Sdim return false; 789360784Sdim } 790226633Sdim 791314564Sdim MBB.splice(std::next(SlotI), &MBB, Filler.getReverse()); 792314564Sdim MIBundleBuilder(MBB, SlotI, std::next(SlotI, 2)); 793261991Sdim ++UsefulSlots; 794261991Sdim return true; 795249423Sdim} 796226633Sdim 797341825Sdimbool MipsDelaySlotFiller::searchForward(MachineBasicBlock &MBB, 798341825Sdim Iter Slot) const { 799249423Sdim // Can handle only calls. 800249423Sdim if (DisableForwardSearch || !Slot->isCall()) 801249423Sdim return false; 802226633Sdim 803288943Sdim RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo()); 804249423Sdim NoMemInstr NM; 805249423Sdim Iter Filler; 806226633Sdim 807249423Sdim RegDU.setCallerSaved(*Slot); 808249423Sdim 809360784Sdim if (!searchRange(MBB, std::next(Slot), MBB.end(), RegDU, NM, Slot, Filler)) { 810360784Sdim LLVM_DEBUG(dbgs() << DEBUG_TYPE ": could not find instruction for delay " 811360784Sdim "slot using forwards search.\n"); 812261991Sdim return false; 813360784Sdim } 814249423Sdim 815276479Sdim MBB.splice(std::next(Slot), &MBB, Filler); 816276479Sdim MIBundleBuilder(MBB, Slot, std::next(Slot, 2)); 817261991Sdim ++UsefulSlots; 818261991Sdim return true; 819226633Sdim} 820226633Sdim 821341825Sdimbool MipsDelaySlotFiller::searchSuccBBs(MachineBasicBlock &MBB, 822341825Sdim Iter Slot) const { 823249423Sdim if (DisableSuccBBSearch) 824249423Sdim return false; 825234353Sdim 826249423Sdim MachineBasicBlock *SuccBB = selectSuccBB(MBB); 827226633Sdim 828249423Sdim if (!SuccBB) 829249423Sdim return false; 830226633Sdim 831288943Sdim RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo()); 832249423Sdim bool HasMultipleSuccs = false; 833249423Sdim BB2BrMap BrMap; 834276479Sdim std::unique_ptr<InspectMemInstr> IM; 835249423Sdim Iter Filler; 836296417Sdim auto *Fn = MBB.getParent(); 837226633Sdim 838249423Sdim // Iterate over SuccBB's predecessor list. 839249423Sdim for (MachineBasicBlock::pred_iterator PI = SuccBB->pred_begin(), 840249423Sdim PE = SuccBB->pred_end(); PI != PE; ++PI) 841249423Sdim if (!examinePred(**PI, *SuccBB, RegDU, HasMultipleSuccs, BrMap)) 842249423Sdim return false; 843249423Sdim 844249423Sdim // Do not allow moving instructions which have unallocatable register operands 845249423Sdim // across basic block boundaries. 846296417Sdim RegDU.setUnallocatableRegs(*Fn); 847249423Sdim 848249423Sdim // Only allow moving loads from stack or constants if any of the SuccBB's 849249423Sdim // predecessors have multiple successors. 850249423Sdim if (HasMultipleSuccs) { 851249423Sdim IM.reset(new LoadFromStackOrConst()); 852249423Sdim } else { 853314564Sdim const MachineFrameInfo &MFI = Fn->getFrameInfo(); 854314564Sdim IM.reset(new MemDefsUses(Fn->getDataLayout(), &MFI)); 855226633Sdim } 856249423Sdim 857288943Sdim if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Slot, 858288943Sdim Filler)) 859249423Sdim return false; 860249423Sdim 861249423Sdim insertDelayFiller(Filler, BrMap); 862249423Sdim addLiveInRegs(Filler, *SuccBB); 863249423Sdim Filler->eraseFromParent(); 864249423Sdim 865249423Sdim return true; 866226633Sdim} 867226633Sdim 868341825SdimMachineBasicBlock * 869341825SdimMipsDelaySlotFiller::selectSuccBB(MachineBasicBlock &B) const { 870249423Sdim if (B.succ_empty()) 871276479Sdim return nullptr; 872249423Sdim 873249423Sdim // Select the successor with the larget edge weight. 874276479Sdim auto &Prob = getAnalysis<MachineBranchProbabilityInfo>(); 875296417Sdim MachineBasicBlock *S = *std::max_element( 876296417Sdim B.succ_begin(), B.succ_end(), 877296417Sdim [&](const MachineBasicBlock *Dst0, const MachineBasicBlock *Dst1) { 878296417Sdim return Prob.getEdgeProbability(&B, Dst0) < 879296417Sdim Prob.getEdgeProbability(&B, Dst1); 880296417Sdim }); 881296417Sdim return S->isEHPad() ? nullptr : S; 882226633Sdim} 883249423Sdim 884249423Sdimstd::pair<MipsInstrInfo::BranchType, MachineInstr *> 885341825SdimMipsDelaySlotFiller::getBranch(MachineBasicBlock &MBB, 886341825Sdim const MachineBasicBlock &Dst) const { 887249423Sdim const MipsInstrInfo *TII = 888288943Sdim MBB.getParent()->getSubtarget<MipsSubtarget>().getInstrInfo(); 889276479Sdim MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr; 890249423Sdim SmallVector<MachineInstr*, 2> BranchInstrs; 891249423Sdim SmallVector<MachineOperand, 2> Cond; 892249423Sdim 893249423Sdim MipsInstrInfo::BranchType R = 894309124Sdim TII->analyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs); 895249423Sdim 896249423Sdim if ((R == MipsInstrInfo::BT_None) || (R == MipsInstrInfo::BT_NoBranch)) 897276479Sdim return std::make_pair(R, nullptr); 898249423Sdim 899249423Sdim if (R != MipsInstrInfo::BT_CondUncond) { 900249423Sdim if (!hasUnoccupiedSlot(BranchInstrs[0])) 901276479Sdim return std::make_pair(MipsInstrInfo::BT_None, nullptr); 902249423Sdim 903249423Sdim assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst))); 904249423Sdim 905249423Sdim return std::make_pair(R, BranchInstrs[0]); 906249423Sdim } 907249423Sdim 908249423Sdim assert((TrueBB == &Dst) || (FalseBB == &Dst)); 909249423Sdim 910249423Sdim // Examine the conditional branch. See if its slot is occupied. 911249423Sdim if (hasUnoccupiedSlot(BranchInstrs[0])) 912249423Sdim return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]); 913249423Sdim 914249423Sdim // If that fails, try the unconditional branch. 915249423Sdim if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst)) 916249423Sdim return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]); 917249423Sdim 918276479Sdim return std::make_pair(MipsInstrInfo::BT_None, nullptr); 919249423Sdim} 920249423Sdim 921341825Sdimbool MipsDelaySlotFiller::examinePred(MachineBasicBlock &Pred, 922341825Sdim const MachineBasicBlock &Succ, 923341825Sdim RegDefsUses &RegDU, 924341825Sdim bool &HasMultipleSuccs, 925341825Sdim BB2BrMap &BrMap) const { 926249423Sdim std::pair<MipsInstrInfo::BranchType, MachineInstr *> P = 927341825Sdim getBranch(Pred, Succ); 928249423Sdim 929249423Sdim // Return if either getBranch wasn't able to analyze the branches or there 930249423Sdim // were no branches with unoccupied slots. 931249423Sdim if (P.first == MipsInstrInfo::BT_None) 932249423Sdim return false; 933249423Sdim 934249423Sdim if ((P.first != MipsInstrInfo::BT_Uncond) && 935249423Sdim (P.first != MipsInstrInfo::BT_NoBranch)) { 936249423Sdim HasMultipleSuccs = true; 937249423Sdim RegDU.addLiveOut(Pred, Succ); 938249423Sdim } 939249423Sdim 940249423Sdim BrMap[&Pred] = P.second; 941249423Sdim return true; 942249423Sdim} 943249423Sdim 944341825Sdimbool MipsDelaySlotFiller::delayHasHazard(const MachineInstr &Candidate, 945341825Sdim RegDefsUses &RegDU, 946341825Sdim InspectMemInstr &IM) const { 947288943Sdim assert(!Candidate.isKill() && 948288943Sdim "KILL instructions should have been eliminated at this point."); 949249423Sdim 950288943Sdim bool HasHazard = Candidate.isImplicitDef(); 951288943Sdim 952249423Sdim HasHazard |= IM.hasHazard(Candidate); 953249423Sdim HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands()); 954249423Sdim 955249423Sdim return HasHazard; 956249423Sdim} 957249423Sdim 958341825Sdimbool MipsDelaySlotFiller::terminateSearch(const MachineInstr &Candidate) const { 959249423Sdim return (Candidate.isTerminator() || Candidate.isCall() || 960276479Sdim Candidate.isPosition() || Candidate.isInlineAsm() || 961249423Sdim Candidate.hasUnmodeledSideEffects()); 962249423Sdim} 963321369Sdim 964321369Sdim/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 965321369Sdim/// slots in Mips MachineFunctions 966360784SdimFunctionPass *llvm::createMipsDelaySlotFillerPass() { 967360784Sdim return new MipsDelaySlotFiller(); 968360784Sdim} 969