MipsDelaySlotFiller.cpp revision 309124
1249423Sdim//===-- MipsDelaySlotFiller.cpp - Mips Delay Slot Filler ------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10249423Sdim// Simple pass to fill delay slots with useful instructions. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14276479Sdim#include "MCTargetDesc/MipsMCNaCl.h" 15193323Sed#include "Mips.h" 16249423Sdim#include "MipsInstrInfo.h" 17193323Sed#include "MipsTargetMachine.h" 18249423Sdim#include "llvm/ADT/BitVector.h" 19249423Sdim#include "llvm/ADT/SmallPtrSet.h" 20249423Sdim#include "llvm/ADT/Statistic.h" 21249423Sdim#include "llvm/Analysis/AliasAnalysis.h" 22249423Sdim#include "llvm/Analysis/ValueTracking.h" 23249423Sdim#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 24193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 25193323Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 26276479Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 27249423Sdim#include "llvm/CodeGen/PseudoSourceValue.h" 28226633Sdim#include "llvm/Support/CommandLine.h" 29249423Sdim#include "llvm/Target/TargetInstrInfo.h" 30226633Sdim#include "llvm/Target/TargetMachine.h" 31226633Sdim#include "llvm/Target/TargetRegisterInfo.h" 32193323Sed 33193323Sedusing namespace llvm; 34193323Sed 35276479Sdim#define DEBUG_TYPE "delay-slot-filler" 36276479Sdim 37193323SedSTATISTIC(FilledSlots, "Number of delay slots filled"); 38226633SdimSTATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 39226633Sdim " are not NOP."); 40193323Sed 41243830Sdimstatic cl::opt<bool> DisableDelaySlotFiller( 42243830Sdim "disable-mips-delay-filler", 43226633Sdim cl::init(false), 44249423Sdim cl::desc("Fill all delay slots with NOPs."), 45226633Sdim cl::Hidden); 46226633Sdim 47249423Sdimstatic cl::opt<bool> DisableForwardSearch( 48249423Sdim "disable-mips-df-forward-search", 49249423Sdim cl::init(true), 50249423Sdim cl::desc("Disallow MIPS delay filler to search forward."), 51249423Sdim cl::Hidden); 52249423Sdim 53249423Sdimstatic cl::opt<bool> DisableSuccBBSearch( 54249423Sdim "disable-mips-df-succbb-search", 55249423Sdim cl::init(true), 56249423Sdim cl::desc("Disallow MIPS delay filler to search successor basic blocks."), 57249423Sdim cl::Hidden); 58249423Sdim 59249423Sdimstatic cl::opt<bool> DisableBackwardSearch( 60249423Sdim "disable-mips-df-backward-search", 61239462Sdim cl::init(false), 62249423Sdim cl::desc("Disallow MIPS delay filler to search backward."), 63239462Sdim cl::Hidden); 64239462Sdim 65309124Sdimenum CompactBranchPolicy { 66309124Sdim CB_Never, ///< The policy 'never' may in some circumstances or for some 67309124Sdim ///< ISAs not be absolutely adhered to. 68309124Sdim CB_Optimal, ///< Optimal is the default and will produce compact branches 69309124Sdim ///< when delay slots cannot be filled. 70309124Sdim CB_Always ///< 'always' may in some circumstances may not be 71309124Sdim ///< absolutely adhered to there may not be a corresponding 72309124Sdim ///< compact form of a branch. 73309124Sdim}; 74309124Sdim 75309124Sdimstatic cl::opt<CompactBranchPolicy> MipsCompactBranchPolicy( 76309124Sdim "mips-compact-branches",cl::Optional, 77309124Sdim cl::init(CB_Optimal), 78309124Sdim cl::desc("MIPS Specific: Compact branch policy."), 79309124Sdim cl::values( 80309124Sdim clEnumValN(CB_Never, "never", "Do not use compact branches if possible."), 81309124Sdim clEnumValN(CB_Optimal, "optimal", "Use compact branches where appropiate (default)."), 82309124Sdim clEnumValN(CB_Always, "always", "Always use compact branches if possible."), 83309124Sdim clEnumValEnd 84309124Sdim ) 85309124Sdim); 86309124Sdim 87193323Sednamespace { 88249423Sdim typedef MachineBasicBlock::iterator Iter; 89249423Sdim typedef MachineBasicBlock::reverse_iterator ReverseIter; 90249423Sdim typedef SmallDenseMap<MachineBasicBlock*, MachineInstr*, 2> BB2BrMap; 91193323Sed 92249423Sdim class RegDefsUses { 93249423Sdim public: 94288943Sdim RegDefsUses(const TargetRegisterInfo &TRI); 95249423Sdim void init(const MachineInstr &MI); 96249423Sdim 97249423Sdim /// This function sets all caller-saved registers in Defs. 98249423Sdim void setCallerSaved(const MachineInstr &MI); 99249423Sdim 100249423Sdim /// This function sets all unallocatable registers in Defs. 101249423Sdim void setUnallocatableRegs(const MachineFunction &MF); 102249423Sdim 103249423Sdim /// Set bits in Uses corresponding to MBB's live-out registers except for 104249423Sdim /// the registers that are live-in to SuccBB. 105249423Sdim void addLiveOut(const MachineBasicBlock &MBB, 106249423Sdim const MachineBasicBlock &SuccBB); 107249423Sdim 108249423Sdim bool update(const MachineInstr &MI, unsigned Begin, unsigned End); 109249423Sdim 110249423Sdim private: 111249423Sdim bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg, 112249423Sdim bool IsDef) const; 113249423Sdim 114249423Sdim /// Returns true if Reg or its alias is in RegSet. 115249423Sdim bool isRegInSet(const BitVector &RegSet, unsigned Reg) const; 116249423Sdim 117249423Sdim const TargetRegisterInfo &TRI; 118249423Sdim BitVector Defs, Uses; 119249423Sdim }; 120249423Sdim 121249423Sdim /// Base class for inspecting loads and stores. 122249423Sdim class InspectMemInstr { 123249423Sdim public: 124249423Sdim InspectMemInstr(bool ForbidMemInstr_) 125249423Sdim : OrigSeenLoad(false), OrigSeenStore(false), SeenLoad(false), 126249423Sdim SeenStore(false), ForbidMemInstr(ForbidMemInstr_) {} 127249423Sdim 128249423Sdim /// Return true if MI cannot be moved to delay slot. 129249423Sdim bool hasHazard(const MachineInstr &MI); 130249423Sdim 131249423Sdim virtual ~InspectMemInstr() {} 132249423Sdim 133249423Sdim protected: 134249423Sdim /// Flags indicating whether loads or stores have been seen. 135249423Sdim bool OrigSeenLoad, OrigSeenStore, SeenLoad, SeenStore; 136249423Sdim 137249423Sdim /// Memory instructions are not allowed to move to delay slot if this flag 138249423Sdim /// is true. 139249423Sdim bool ForbidMemInstr; 140249423Sdim 141249423Sdim private: 142249423Sdim virtual bool hasHazard_(const MachineInstr &MI) = 0; 143249423Sdim }; 144249423Sdim 145249423Sdim /// This subclass rejects any memory instructions. 146249423Sdim class NoMemInstr : public InspectMemInstr { 147249423Sdim public: 148249423Sdim NoMemInstr() : InspectMemInstr(true) {} 149249423Sdim private: 150276479Sdim bool hasHazard_(const MachineInstr &MI) override { return true; } 151249423Sdim }; 152249423Sdim 153249423Sdim /// This subclass accepts loads from stacks and constant loads. 154249423Sdim class LoadFromStackOrConst : public InspectMemInstr { 155249423Sdim public: 156249423Sdim LoadFromStackOrConst() : InspectMemInstr(false) {} 157249423Sdim private: 158276479Sdim bool hasHazard_(const MachineInstr &MI) override; 159249423Sdim }; 160249423Sdim 161249423Sdim /// This subclass uses memory dependence information to determine whether a 162249423Sdim /// memory instruction can be moved to a delay slot. 163249423Sdim class MemDefsUses : public InspectMemInstr { 164249423Sdim public: 165288943Sdim MemDefsUses(const DataLayout &DL, const MachineFrameInfo *MFI); 166249423Sdim 167249423Sdim private: 168276479Sdim typedef PointerUnion<const Value *, const PseudoSourceValue *> ValueType; 169249423Sdim 170276479Sdim bool hasHazard_(const MachineInstr &MI) override; 171276479Sdim 172249423Sdim /// Update Defs and Uses. Return true if there exist dependences that 173249423Sdim /// disqualify the delay slot candidate between V and values in Uses and 174249423Sdim /// Defs. 175276479Sdim bool updateDefsUses(ValueType V, bool MayStore); 176249423Sdim 177249423Sdim /// Get the list of underlying objects of MI's memory operand. 178249423Sdim bool getUnderlyingObjects(const MachineInstr &MI, 179276479Sdim SmallVectorImpl<ValueType> &Objects) const; 180249423Sdim 181249423Sdim const MachineFrameInfo *MFI; 182276479Sdim SmallPtrSet<ValueType, 4> Uses, Defs; 183288943Sdim const DataLayout &DL; 184249423Sdim 185249423Sdim /// Flags indicating whether loads or stores with no underlying objects have 186249423Sdim /// been seen. 187249423Sdim bool SeenNoObjLoad, SeenNoObjStore; 188249423Sdim }; 189249423Sdim 190249423Sdim class Filler : public MachineFunctionPass { 191249423Sdim public: 192218893Sdim Filler(TargetMachine &tm) 193261991Sdim : MachineFunctionPass(ID), TM(tm) { } 194193323Sed 195276479Sdim const char *getPassName() const override { 196193323Sed return "Mips Delay Slot Filler"; 197193323Sed } 198193323Sed 199276479Sdim bool runOnMachineFunction(MachineFunction &F) override { 200193323Sed bool Changed = false; 201193323Sed for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 202193323Sed FI != FE; ++FI) 203193323Sed Changed |= runOnMachineBasicBlock(*FI); 204276479Sdim 205276479Sdim // This pass invalidates liveness information when it reorders 206276479Sdim // instructions to fill delay slot. Without this, -verify-machineinstrs 207276479Sdim // will fail. 208276479Sdim if (Changed) 209276479Sdim F.getRegInfo().invalidateLiveness(); 210276479Sdim 211193323Sed return Changed; 212193323Sed } 213193323Sed 214309124Sdim MachineFunctionProperties getRequiredProperties() const override { 215309124Sdim return MachineFunctionProperties().set( 216309124Sdim MachineFunctionProperties::Property::AllVRegsAllocated); 217309124Sdim } 218309124Sdim 219276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 220249423Sdim AU.addRequired<MachineBranchProbabilityInfo>(); 221249423Sdim MachineFunctionPass::getAnalysisUsage(AU); 222249423Sdim } 223226633Sdim 224249423Sdim private: 225249423Sdim bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 226226633Sdim 227309124Sdim Iter replaceWithCompactBranch(MachineBasicBlock &MBB, Iter Branch, 228309124Sdim const DebugLoc &DL); 229280031Sdim 230249423Sdim /// This function checks if it is valid to move Candidate to the delay slot 231249423Sdim /// and returns true if it isn't. It also updates memory and register 232249423Sdim /// dependence information. 233249423Sdim bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, 234249423Sdim InspectMemInstr &IM) const; 235226633Sdim 236249423Sdim /// This function searches range [Begin, End) for an instruction that can be 237249423Sdim /// moved to the delay slot. Returns true on success. 238249423Sdim template<typename IterTy> 239249423Sdim bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, 240288943Sdim RegDefsUses &RegDU, InspectMemInstr &IM, Iter Slot, 241288943Sdim IterTy &Filler) const; 242226633Sdim 243249423Sdim /// This function searches in the backward direction for an instruction that 244249423Sdim /// can be moved to the delay slot. Returns true on success. 245249423Sdim bool searchBackward(MachineBasicBlock &MBB, Iter Slot) const; 246226633Sdim 247249423Sdim /// This function searches MBB in the forward direction for an instruction 248249423Sdim /// that can be moved to the delay slot. Returns true on success. 249249423Sdim bool searchForward(MachineBasicBlock &MBB, Iter Slot) const; 250226633Sdim 251249423Sdim /// This function searches one of MBB's successor blocks for an instruction 252249423Sdim /// that can be moved to the delay slot and inserts clones of the 253249423Sdim /// instruction into the successor's predecessor blocks. 254249423Sdim bool searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const; 255226633Sdim 256249423Sdim /// Pick a successor block of MBB. Return NULL if MBB doesn't have a 257249423Sdim /// successor block that is not a landing pad. 258249423Sdim MachineBasicBlock *selectSuccBB(MachineBasicBlock &B) const; 259249423Sdim 260249423Sdim /// This function analyzes MBB and returns an instruction with an unoccupied 261249423Sdim /// slot that branches to Dst. 262249423Sdim std::pair<MipsInstrInfo::BranchType, MachineInstr *> 263249423Sdim getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const; 264249423Sdim 265249423Sdim /// Examine Pred and see if it is possible to insert an instruction into 266249423Sdim /// one of its branches delay slot or its end. 267249423Sdim bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ, 268249423Sdim RegDefsUses &RegDU, bool &HasMultipleSuccs, 269249423Sdim BB2BrMap &BrMap) const; 270249423Sdim 271249423Sdim bool terminateSearch(const MachineInstr &Candidate) const; 272249423Sdim 273249423Sdim TargetMachine &TM; 274249423Sdim 275249423Sdim static char ID; 276193323Sed }; 277193323Sed char Filler::ID = 0; 278193323Sed} // end of anonymous namespace 279193323Sed 280249423Sdimstatic bool hasUnoccupiedSlot(const MachineInstr *MI) { 281249423Sdim return MI->hasDelaySlot() && !MI->isBundledWithSucc(); 282249423Sdim} 283249423Sdim 284249423Sdim/// This function inserts clones of Filler into predecessor blocks. 285249423Sdimstatic void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) { 286249423Sdim MachineFunction *MF = Filler->getParent()->getParent(); 287249423Sdim 288249423Sdim for (BB2BrMap::const_iterator I = BrMap.begin(); I != BrMap.end(); ++I) { 289249423Sdim if (I->second) { 290249423Sdim MIBundleBuilder(I->second).append(MF->CloneMachineInstr(&*Filler)); 291249423Sdim ++UsefulSlots; 292249423Sdim } else { 293249423Sdim I->first->insert(I->first->end(), MF->CloneMachineInstr(&*Filler)); 294249423Sdim } 295249423Sdim } 296249423Sdim} 297249423Sdim 298249423Sdim/// This function adds registers Filler defines to MBB's live-in register list. 299249423Sdimstatic void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) { 300249423Sdim for (unsigned I = 0, E = Filler->getNumOperands(); I != E; ++I) { 301249423Sdim const MachineOperand &MO = Filler->getOperand(I); 302249423Sdim unsigned R; 303249423Sdim 304249423Sdim if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg())) 305249423Sdim continue; 306249423Sdim 307249423Sdim#ifndef NDEBUG 308249423Sdim const MachineFunction &MF = *MBB.getParent(); 309288943Sdim assert(MF.getSubtarget().getRegisterInfo()->getAllocatableSet(MF).test(R) && 310249423Sdim "Shouldn't move an instruction with unallocatable registers across " 311249423Sdim "basic block boundaries."); 312249423Sdim#endif 313249423Sdim 314249423Sdim if (!MBB.isLiveIn(R)) 315249423Sdim MBB.addLiveIn(R); 316249423Sdim } 317249423Sdim} 318249423Sdim 319288943SdimRegDefsUses::RegDefsUses(const TargetRegisterInfo &TRI) 320288943Sdim : TRI(TRI), Defs(TRI.getNumRegs(), false), Uses(TRI.getNumRegs(), false) {} 321249423Sdim 322249423Sdimvoid RegDefsUses::init(const MachineInstr &MI) { 323249423Sdim // Add all register operands which are explicit and non-variadic. 324249423Sdim update(MI, 0, MI.getDesc().getNumOperands()); 325249423Sdim 326249423Sdim // If MI is a call, add RA to Defs to prevent users of RA from going into 327249423Sdim // delay slot. 328249423Sdim if (MI.isCall()) 329249423Sdim Defs.set(Mips::RA); 330249423Sdim 331249423Sdim // Add all implicit register operands of branch instructions except 332249423Sdim // register AT. 333249423Sdim if (MI.isBranch()) { 334249423Sdim update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands()); 335249423Sdim Defs.reset(Mips::AT); 336249423Sdim } 337249423Sdim} 338249423Sdim 339249423Sdimvoid RegDefsUses::setCallerSaved(const MachineInstr &MI) { 340249423Sdim assert(MI.isCall()); 341249423Sdim 342288943Sdim // Add RA/RA_64 to Defs to prevent users of RA/RA_64 from going into 343288943Sdim // the delay slot. The reason is that RA/RA_64 must not be changed 344288943Sdim // in the delay slot so that the callee can return to the caller. 345288943Sdim if (MI.definesRegister(Mips::RA) || MI.definesRegister(Mips::RA_64)) { 346288943Sdim Defs.set(Mips::RA); 347288943Sdim Defs.set(Mips::RA_64); 348288943Sdim } 349288943Sdim 350249423Sdim // If MI is a call, add all caller-saved registers to Defs. 351249423Sdim BitVector CallerSavedRegs(TRI.getNumRegs(), true); 352249423Sdim 353249423Sdim CallerSavedRegs.reset(Mips::ZERO); 354249423Sdim CallerSavedRegs.reset(Mips::ZERO_64); 355249423Sdim 356288943Sdim for (const MCPhysReg *R = TRI.getCalleeSavedRegs(MI.getParent()->getParent()); 357288943Sdim *R; ++R) 358249423Sdim for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI) 359249423Sdim CallerSavedRegs.reset(*AI); 360249423Sdim 361249423Sdim Defs |= CallerSavedRegs; 362249423Sdim} 363249423Sdim 364249423Sdimvoid RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) { 365249423Sdim BitVector AllocSet = TRI.getAllocatableSet(MF); 366249423Sdim 367249423Sdim for (int R = AllocSet.find_first(); R != -1; R = AllocSet.find_next(R)) 368249423Sdim for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI) 369249423Sdim AllocSet.set(*AI); 370249423Sdim 371249423Sdim AllocSet.set(Mips::ZERO); 372249423Sdim AllocSet.set(Mips::ZERO_64); 373249423Sdim 374249423Sdim Defs |= AllocSet.flip(); 375249423Sdim} 376249423Sdim 377249423Sdimvoid RegDefsUses::addLiveOut(const MachineBasicBlock &MBB, 378249423Sdim const MachineBasicBlock &SuccBB) { 379249423Sdim for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 380249423Sdim SE = MBB.succ_end(); SI != SE; ++SI) 381249423Sdim if (*SI != &SuccBB) 382296417Sdim for (const auto &LI : (*SI)->liveins()) 383296417Sdim Uses.set(LI.PhysReg); 384249423Sdim} 385249423Sdim 386249423Sdimbool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) { 387249423Sdim BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs()); 388249423Sdim bool HasHazard = false; 389249423Sdim 390249423Sdim for (unsigned I = Begin; I != End; ++I) { 391249423Sdim const MachineOperand &MO = MI.getOperand(I); 392249423Sdim 393249423Sdim if (MO.isReg() && MO.getReg()) 394249423Sdim HasHazard |= checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef()); 395249423Sdim } 396249423Sdim 397249423Sdim Defs |= NewDefs; 398249423Sdim Uses |= NewUses; 399249423Sdim 400249423Sdim return HasHazard; 401249423Sdim} 402249423Sdim 403249423Sdimbool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, 404249423Sdim unsigned Reg, bool IsDef) const { 405249423Sdim if (IsDef) { 406249423Sdim NewDefs.set(Reg); 407249423Sdim // check whether Reg has already been defined or used. 408249423Sdim return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg)); 409249423Sdim } 410249423Sdim 411249423Sdim NewUses.set(Reg); 412249423Sdim // check whether Reg has already been defined. 413249423Sdim return isRegInSet(Defs, Reg); 414249423Sdim} 415249423Sdim 416249423Sdimbool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const { 417249423Sdim // Check Reg and all aliased Registers. 418249423Sdim for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI) 419249423Sdim if (RegSet.test(*AI)) 420249423Sdim return true; 421249423Sdim return false; 422249423Sdim} 423249423Sdim 424249423Sdimbool InspectMemInstr::hasHazard(const MachineInstr &MI) { 425249423Sdim if (!MI.mayStore() && !MI.mayLoad()) 426249423Sdim return false; 427249423Sdim 428249423Sdim if (ForbidMemInstr) 429249423Sdim return true; 430249423Sdim 431249423Sdim OrigSeenLoad = SeenLoad; 432249423Sdim OrigSeenStore = SeenStore; 433249423Sdim SeenLoad |= MI.mayLoad(); 434249423Sdim SeenStore |= MI.mayStore(); 435249423Sdim 436249423Sdim // If MI is an ordered or volatile memory reference, disallow moving 437249423Sdim // subsequent loads and stores to delay slot. 438249423Sdim if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) { 439249423Sdim ForbidMemInstr = true; 440249423Sdim return true; 441249423Sdim } 442249423Sdim 443249423Sdim return hasHazard_(MI); 444249423Sdim} 445249423Sdim 446249423Sdimbool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) { 447249423Sdim if (MI.mayStore()) 448249423Sdim return true; 449249423Sdim 450276479Sdim if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getPseudoValue()) 451249423Sdim return true; 452249423Sdim 453276479Sdim if (const PseudoSourceValue *PSV = 454276479Sdim (*MI.memoperands_begin())->getPseudoValue()) { 455276479Sdim if (isa<FixedStackPseudoSourceValue>(PSV)) 456276479Sdim return false; 457296417Sdim return !PSV->isConstant(nullptr) && !PSV->isStack(); 458276479Sdim } 459249423Sdim 460249423Sdim return true; 461249423Sdim} 462249423Sdim 463288943SdimMemDefsUses::MemDefsUses(const DataLayout &DL, const MachineFrameInfo *MFI_) 464288943Sdim : InspectMemInstr(false), MFI(MFI_), DL(DL), SeenNoObjLoad(false), 465288943Sdim SeenNoObjStore(false) {} 466249423Sdim 467249423Sdimbool MemDefsUses::hasHazard_(const MachineInstr &MI) { 468249423Sdim bool HasHazard = false; 469276479Sdim SmallVector<ValueType, 4> Objs; 470249423Sdim 471249423Sdim // Check underlying object list. 472249423Sdim if (getUnderlyingObjects(MI, Objs)) { 473276479Sdim for (SmallVectorImpl<ValueType>::const_iterator I = Objs.begin(); 474249423Sdim I != Objs.end(); ++I) 475249423Sdim HasHazard |= updateDefsUses(*I, MI.mayStore()); 476249423Sdim 477249423Sdim return HasHazard; 478249423Sdim } 479249423Sdim 480249423Sdim // No underlying objects found. 481249423Sdim HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore); 482249423Sdim HasHazard |= MI.mayLoad() || OrigSeenStore; 483249423Sdim 484249423Sdim SeenNoObjLoad |= MI.mayLoad(); 485249423Sdim SeenNoObjStore |= MI.mayStore(); 486249423Sdim 487249423Sdim return HasHazard; 488249423Sdim} 489249423Sdim 490276479Sdimbool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) { 491249423Sdim if (MayStore) 492280031Sdim return !Defs.insert(V).second || Uses.count(V) || SeenNoObjStore || 493280031Sdim SeenNoObjLoad; 494249423Sdim 495249423Sdim Uses.insert(V); 496249423Sdim return Defs.count(V) || SeenNoObjStore; 497249423Sdim} 498249423Sdim 499249423Sdimbool MemDefsUses:: 500249423SdimgetUnderlyingObjects(const MachineInstr &MI, 501276479Sdim SmallVectorImpl<ValueType> &Objects) const { 502276479Sdim if (!MI.hasOneMemOperand() || 503276479Sdim (!(*MI.memoperands_begin())->getValue() && 504276479Sdim !(*MI.memoperands_begin())->getPseudoValue())) 505249423Sdim return false; 506249423Sdim 507276479Sdim if (const PseudoSourceValue *PSV = 508276479Sdim (*MI.memoperands_begin())->getPseudoValue()) { 509276479Sdim if (!PSV->isAliased(MFI)) 510276479Sdim return false; 511276479Sdim Objects.push_back(PSV); 512276479Sdim return true; 513276479Sdim } 514276479Sdim 515249423Sdim const Value *V = (*MI.memoperands_begin())->getValue(); 516249423Sdim 517249423Sdim SmallVector<Value *, 4> Objs; 518288943Sdim GetUnderlyingObjects(const_cast<Value *>(V), Objs, DL); 519249423Sdim 520261991Sdim for (SmallVectorImpl<Value *>::iterator I = Objs.begin(), E = Objs.end(); 521249423Sdim I != E; ++I) { 522276479Sdim if (!isIdentifiedObject(V)) 523249423Sdim return false; 524249423Sdim 525249423Sdim Objects.push_back(*I); 526249423Sdim } 527249423Sdim 528249423Sdim return true; 529249423Sdim} 530249423Sdim 531280031Sdim// Replace Branch with the compact branch instruction. 532309124SdimIter Filler::replaceWithCompactBranch(MachineBasicBlock &MBB, Iter Branch, 533309124Sdim const DebugLoc &DL) { 534309124Sdim const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>(); 535309124Sdim const MipsInstrInfo *TII = STI.getInstrInfo(); 536280031Sdim 537309124Sdim unsigned NewOpcode = TII->getEquivalentCompactForm(Branch); 538309124Sdim Branch = TII->genInstrWithNewOpc(NewOpcode, Branch); 539280031Sdim 540309124Sdim std::next(Branch)->eraseFromParent(); 541280031Sdim return Branch; 542280031Sdim} 543280031Sdim 544280031Sdim// For given opcode returns opcode of corresponding instruction with short 545280031Sdim// delay slot. 546280031Sdimstatic int getEquivalentCallShort(int Opcode) { 547280031Sdim switch (Opcode) { 548280031Sdim case Mips::BGEZAL: 549280031Sdim return Mips::BGEZALS_MM; 550280031Sdim case Mips::BLTZAL: 551280031Sdim return Mips::BLTZALS_MM; 552280031Sdim case Mips::JAL: 553280031Sdim return Mips::JALS_MM; 554280031Sdim case Mips::JALR: 555280031Sdim return Mips::JALRS_MM; 556280031Sdim case Mips::JALR16_MM: 557280031Sdim return Mips::JALRS16_MM; 558280031Sdim default: 559280031Sdim llvm_unreachable("Unexpected call instruction for microMIPS."); 560280031Sdim } 561280031Sdim} 562280031Sdim 563193323Sed/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 564226633Sdim/// We assume there is only one delay slot per delayed instruction. 565249423Sdimbool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 566193323Sed bool Changed = false; 567288943Sdim const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>(); 568288943Sdim bool InMicroMipsMode = STI.inMicroMipsMode(); 569288943Sdim const MipsInstrInfo *TII = STI.getInstrInfo(); 570226633Sdim 571309124Sdim if (InMicroMipsMode && STI.hasMips32r6()) { 572309124Sdim // This is microMIPS32r6 or microMIPS64r6 processor. Delay slot for 573309124Sdim // branching instructions is not needed. 574309124Sdim return Changed; 575309124Sdim } 576309124Sdim 577249423Sdim for (Iter I = MBB.begin(); I != MBB.end(); ++I) { 578249423Sdim if (!hasUnoccupiedSlot(&*I)) 579249423Sdim continue; 580218893Sdim 581249423Sdim ++FilledSlots; 582249423Sdim Changed = true; 583226633Sdim 584249423Sdim // Delay slot filling is disabled at -O0. 585249423Sdim if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None)) { 586280031Sdim bool Filled = false; 587226633Sdim 588309124Sdim if (MipsCompactBranchPolicy.getValue() != CB_Always || 589309124Sdim !TII->getEquivalentCompactForm(I)) { 590309124Sdim if (searchBackward(MBB, I)) { 591280031Sdim Filled = true; 592309124Sdim } else if (I->isTerminator()) { 593309124Sdim if (searchSuccBBs(MBB, I)) { 594309124Sdim Filled = true; 595309124Sdim } 596309124Sdim } else if (searchForward(MBB, I)) { 597309124Sdim Filled = true; 598280031Sdim } 599280031Sdim } 600280031Sdim 601280031Sdim if (Filled) { 602280031Sdim // Get instruction with delay slot. 603309124Sdim MachineBasicBlock::instr_iterator DSI = I.getInstrIterator(); 604280031Sdim 605309124Sdim if (InMicroMipsMode && TII->GetInstSizeInBytes(*std::next(DSI)) == 2 && 606280031Sdim DSI->isCall()) { 607280031Sdim // If instruction in delay slot is 16b change opcode to 608280031Sdim // corresponding instruction with short delay slot. 609280031Sdim DSI->setDesc(TII->get(getEquivalentCallShort(DSI->getOpcode()))); 610280031Sdim } 611249423Sdim continue; 612249423Sdim } 613249423Sdim } 614239462Sdim 615309124Sdim // For microMIPS if instruction is BEQ or BNE with one ZERO register, then 616309124Sdim // instead of adding NOP replace this instruction with the corresponding 617309124Sdim // compact branch instruction, i.e. BEQZC or BNEZC. Additionally 618309124Sdim // PseudoReturn and PseudoIndirectBranch are expanded to JR_MM, so they can 619309124Sdim // be replaced with JRC16_MM. 620309124Sdim 621309124Sdim // For MIPSR6 attempt to produce the corresponding compact (no delay slot) 622309124Sdim // form of the CTI. For indirect jumps this will not require inserting a 623309124Sdim // NOP and for branches will hopefully avoid requiring a NOP. 624309124Sdim if ((InMicroMipsMode || 625309124Sdim (STI.hasMips32r6() && MipsCompactBranchPolicy != CB_Never)) && 626309124Sdim TII->getEquivalentCompactForm(I)) { 627309124Sdim I = replaceWithCompactBranch(MBB, I, I->getDebugLoc()); 628309124Sdim continue; 629280031Sdim } 630309124Sdim 631288943Sdim // Bundle the NOP to the instruction with the delay slot. 632288943Sdim BuildMI(MBB, std::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); 633288943Sdim MIBundleBuilder(MBB, I, std::next(I, 2)); 634249423Sdim } 635249423Sdim 636193323Sed return Changed; 637193323Sed} 638193323Sed 639193323Sed/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 640193323Sed/// slots in Mips MachineFunctions 641193323SedFunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 642193323Sed return new Filler(tm); 643193323Sed} 644193323Sed 645249423Sdimtemplate<typename IterTy> 646249423Sdimbool Filler::searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, 647288943Sdim RegDefsUses &RegDU, InspectMemInstr& IM, Iter Slot, 648288943Sdim IterTy &Filler) const { 649288943Sdim bool IsReverseIter = std::is_convertible<IterTy, ReverseIter>::value; 650288943Sdim 651288943Sdim for (IterTy I = Begin; I != End;) { 652288943Sdim IterTy CurrI = I; 653288943Sdim ++I; 654288943Sdim 655226633Sdim // skip debug value 656288943Sdim if (CurrI->isDebugValue()) 657226633Sdim continue; 658226633Sdim 659288943Sdim if (terminateSearch(*CurrI)) 660226633Sdim break; 661226633Sdim 662288943Sdim assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) && 663249423Sdim "Cannot put calls, returns or branches in delay slot."); 664249423Sdim 665288943Sdim if (CurrI->isKill()) { 666288943Sdim CurrI->eraseFromParent(); 667288943Sdim 668288943Sdim // This special case is needed for reverse iterators, because when we 669288943Sdim // erase an instruction, the iterators are updated to point to the next 670288943Sdim // instruction. 671288943Sdim if (IsReverseIter && I != End) 672288943Sdim I = CurrI; 673226633Sdim continue; 674288943Sdim } 675226633Sdim 676288943Sdim if (delayHasHazard(*CurrI, RegDU, IM)) 677288943Sdim continue; 678288943Sdim 679288943Sdim const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>(); 680288943Sdim if (STI.isTargetNaCl()) { 681276479Sdim // In NaCl, instructions that must be masked are forbidden in delay slots. 682276479Sdim // We only check for loads, stores and SP changes. Calls, returns and 683276479Sdim // branches are not checked because non-NaCl targets never put them in 684276479Sdim // delay slots. 685276479Sdim unsigned AddrIdx; 686288943Sdim if ((isBasePlusOffsetMemoryAccess(CurrI->getOpcode(), &AddrIdx) && 687288943Sdim baseRegNeedsLoadStoreMask(CurrI->getOperand(AddrIdx).getReg())) || 688288943Sdim CurrI->modifiesRegister(Mips::SP, STI.getRegisterInfo())) 689276479Sdim continue; 690276479Sdim } 691276479Sdim 692288943Sdim bool InMicroMipsMode = STI.inMicroMipsMode(); 693288943Sdim const MipsInstrInfo *TII = STI.getInstrInfo(); 694280031Sdim unsigned Opcode = (*Slot).getOpcode(); 695309124Sdim if (InMicroMipsMode && TII->GetInstSizeInBytes(*CurrI) == 2 && 696280031Sdim (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch || 697280031Sdim Opcode == Mips::PseudoReturn)) 698280031Sdim continue; 699280031Sdim 700288943Sdim Filler = CurrI; 701226633Sdim return true; 702226633Sdim } 703226633Sdim 704226633Sdim return false; 705226633Sdim} 706226633Sdim 707249423Sdimbool Filler::searchBackward(MachineBasicBlock &MBB, Iter Slot) const { 708249423Sdim if (DisableBackwardSearch) 709249423Sdim return false; 710226633Sdim 711296417Sdim auto *Fn = MBB.getParent(); 712296417Sdim RegDefsUses RegDU(*Fn->getSubtarget().getRegisterInfo()); 713296417Sdim MemDefsUses MemDU(Fn->getDataLayout(), Fn->getFrameInfo()); 714249423Sdim ReverseIter Filler; 715226633Sdim 716249423Sdim RegDU.init(*Slot); 717249423Sdim 718288943Sdim if (!searchRange(MBB, ReverseIter(Slot), MBB.rend(), RegDU, MemDU, Slot, 719288943Sdim Filler)) 720261991Sdim return false; 721226633Sdim 722276479Sdim MBB.splice(std::next(Slot), &MBB, std::next(Filler).base()); 723276479Sdim MIBundleBuilder(MBB, Slot, std::next(Slot, 2)); 724261991Sdim ++UsefulSlots; 725261991Sdim return true; 726249423Sdim} 727226633Sdim 728249423Sdimbool Filler::searchForward(MachineBasicBlock &MBB, Iter Slot) const { 729249423Sdim // Can handle only calls. 730249423Sdim if (DisableForwardSearch || !Slot->isCall()) 731249423Sdim return false; 732226633Sdim 733288943Sdim RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo()); 734249423Sdim NoMemInstr NM; 735249423Sdim Iter Filler; 736226633Sdim 737249423Sdim RegDU.setCallerSaved(*Slot); 738249423Sdim 739288943Sdim if (!searchRange(MBB, std::next(Slot), MBB.end(), RegDU, NM, Slot, Filler)) 740261991Sdim return false; 741249423Sdim 742276479Sdim MBB.splice(std::next(Slot), &MBB, Filler); 743276479Sdim MIBundleBuilder(MBB, Slot, std::next(Slot, 2)); 744261991Sdim ++UsefulSlots; 745261991Sdim return true; 746226633Sdim} 747226633Sdim 748249423Sdimbool Filler::searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const { 749249423Sdim if (DisableSuccBBSearch) 750249423Sdim return false; 751234353Sdim 752249423Sdim MachineBasicBlock *SuccBB = selectSuccBB(MBB); 753226633Sdim 754249423Sdim if (!SuccBB) 755249423Sdim return false; 756226633Sdim 757288943Sdim RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo()); 758249423Sdim bool HasMultipleSuccs = false; 759249423Sdim BB2BrMap BrMap; 760276479Sdim std::unique_ptr<InspectMemInstr> IM; 761249423Sdim Iter Filler; 762296417Sdim auto *Fn = MBB.getParent(); 763226633Sdim 764249423Sdim // Iterate over SuccBB's predecessor list. 765249423Sdim for (MachineBasicBlock::pred_iterator PI = SuccBB->pred_begin(), 766249423Sdim PE = SuccBB->pred_end(); PI != PE; ++PI) 767249423Sdim if (!examinePred(**PI, *SuccBB, RegDU, HasMultipleSuccs, BrMap)) 768249423Sdim return false; 769249423Sdim 770249423Sdim // Do not allow moving instructions which have unallocatable register operands 771249423Sdim // across basic block boundaries. 772296417Sdim RegDU.setUnallocatableRegs(*Fn); 773249423Sdim 774249423Sdim // Only allow moving loads from stack or constants if any of the SuccBB's 775249423Sdim // predecessors have multiple successors. 776249423Sdim if (HasMultipleSuccs) { 777249423Sdim IM.reset(new LoadFromStackOrConst()); 778249423Sdim } else { 779296417Sdim const MachineFrameInfo *MFI = Fn->getFrameInfo(); 780296417Sdim IM.reset(new MemDefsUses(Fn->getDataLayout(), MFI)); 781226633Sdim } 782249423Sdim 783288943Sdim if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Slot, 784288943Sdim Filler)) 785249423Sdim return false; 786249423Sdim 787249423Sdim insertDelayFiller(Filler, BrMap); 788249423Sdim addLiveInRegs(Filler, *SuccBB); 789249423Sdim Filler->eraseFromParent(); 790249423Sdim 791249423Sdim return true; 792226633Sdim} 793226633Sdim 794249423SdimMachineBasicBlock *Filler::selectSuccBB(MachineBasicBlock &B) const { 795249423Sdim if (B.succ_empty()) 796276479Sdim return nullptr; 797249423Sdim 798249423Sdim // Select the successor with the larget edge weight. 799276479Sdim auto &Prob = getAnalysis<MachineBranchProbabilityInfo>(); 800296417Sdim MachineBasicBlock *S = *std::max_element( 801296417Sdim B.succ_begin(), B.succ_end(), 802296417Sdim [&](const MachineBasicBlock *Dst0, const MachineBasicBlock *Dst1) { 803296417Sdim return Prob.getEdgeProbability(&B, Dst0) < 804296417Sdim Prob.getEdgeProbability(&B, Dst1); 805296417Sdim }); 806296417Sdim return S->isEHPad() ? nullptr : S; 807226633Sdim} 808249423Sdim 809249423Sdimstd::pair<MipsInstrInfo::BranchType, MachineInstr *> 810249423SdimFiller::getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const { 811249423Sdim const MipsInstrInfo *TII = 812288943Sdim MBB.getParent()->getSubtarget<MipsSubtarget>().getInstrInfo(); 813276479Sdim MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr; 814249423Sdim SmallVector<MachineInstr*, 2> BranchInstrs; 815249423Sdim SmallVector<MachineOperand, 2> Cond; 816249423Sdim 817249423Sdim MipsInstrInfo::BranchType R = 818309124Sdim TII->analyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs); 819249423Sdim 820249423Sdim if ((R == MipsInstrInfo::BT_None) || (R == MipsInstrInfo::BT_NoBranch)) 821276479Sdim return std::make_pair(R, nullptr); 822249423Sdim 823249423Sdim if (R != MipsInstrInfo::BT_CondUncond) { 824249423Sdim if (!hasUnoccupiedSlot(BranchInstrs[0])) 825276479Sdim return std::make_pair(MipsInstrInfo::BT_None, nullptr); 826249423Sdim 827249423Sdim assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst))); 828249423Sdim 829249423Sdim return std::make_pair(R, BranchInstrs[0]); 830249423Sdim } 831249423Sdim 832249423Sdim assert((TrueBB == &Dst) || (FalseBB == &Dst)); 833249423Sdim 834249423Sdim // Examine the conditional branch. See if its slot is occupied. 835249423Sdim if (hasUnoccupiedSlot(BranchInstrs[0])) 836249423Sdim return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]); 837249423Sdim 838249423Sdim // If that fails, try the unconditional branch. 839249423Sdim if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst)) 840249423Sdim return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]); 841249423Sdim 842276479Sdim return std::make_pair(MipsInstrInfo::BT_None, nullptr); 843249423Sdim} 844249423Sdim 845249423Sdimbool Filler::examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ, 846249423Sdim RegDefsUses &RegDU, bool &HasMultipleSuccs, 847249423Sdim BB2BrMap &BrMap) const { 848249423Sdim std::pair<MipsInstrInfo::BranchType, MachineInstr *> P = 849249423Sdim getBranch(Pred, Succ); 850249423Sdim 851249423Sdim // Return if either getBranch wasn't able to analyze the branches or there 852249423Sdim // were no branches with unoccupied slots. 853249423Sdim if (P.first == MipsInstrInfo::BT_None) 854249423Sdim return false; 855249423Sdim 856249423Sdim if ((P.first != MipsInstrInfo::BT_Uncond) && 857249423Sdim (P.first != MipsInstrInfo::BT_NoBranch)) { 858249423Sdim HasMultipleSuccs = true; 859249423Sdim RegDU.addLiveOut(Pred, Succ); 860249423Sdim } 861249423Sdim 862249423Sdim BrMap[&Pred] = P.second; 863249423Sdim return true; 864249423Sdim} 865249423Sdim 866249423Sdimbool Filler::delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, 867249423Sdim InspectMemInstr &IM) const { 868288943Sdim assert(!Candidate.isKill() && 869288943Sdim "KILL instructions should have been eliminated at this point."); 870249423Sdim 871288943Sdim bool HasHazard = Candidate.isImplicitDef(); 872288943Sdim 873249423Sdim HasHazard |= IM.hasHazard(Candidate); 874249423Sdim HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands()); 875249423Sdim 876249423Sdim return HasHazard; 877249423Sdim} 878249423Sdim 879249423Sdimbool Filler::terminateSearch(const MachineInstr &Candidate) const { 880249423Sdim return (Candidate.isTerminator() || Candidate.isCall() || 881276479Sdim Candidate.isPosition() || Candidate.isInlineAsm() || 882249423Sdim Candidate.hasUnmodeledSideEffects()); 883249423Sdim} 884