189857Sobrien//===- MipsDelaySlotFiller.cpp - Mips Delay Slot Filler -------------------===// 289857Sobrien// 389857Sobrien// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 489857Sobrien// See https://llvm.org/LICENSE.txt for license information. 589857Sobrien// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 689857Sobrien// 789857Sobrien//===----------------------------------------------------------------------===// 889857Sobrien// 9218822Sdim// Simple pass to fill delay slots with useful instructions. 1089857Sobrien// 1189857Sobrien//===----------------------------------------------------------------------===// 1289857Sobrien 1389857Sobrien#include "MCTargetDesc/MipsMCNaCl.h" 1489857Sobrien#include "Mips.h" 1589857Sobrien#include "MipsInstrInfo.h" 1689857Sobrien#include "MipsRegisterInfo.h" 1789857Sobrien#include "MipsSubtarget.h" 1889857Sobrien#include "llvm/ADT/BitVector.h" 1989857Sobrien#include "llvm/ADT/DenseMap.h" 2089857Sobrien#include "llvm/ADT/PointerUnion.h" 2189857Sobrien#include "llvm/ADT/SmallPtrSet.h" 2289857Sobrien#include "llvm/ADT/SmallVector.h" 2389857Sobrien#include "llvm/ADT/Statistic.h" 2489857Sobrien#include "llvm/ADT/StringRef.h" 2589857Sobrien#include "llvm/Analysis/AliasAnalysis.h" 2689857Sobrien#include "llvm/Analysis/ValueTracking.h" 2789857Sobrien#include "llvm/CodeGen/MachineBasicBlock.h" 2889857Sobrien#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 2989857Sobrien#include "llvm/CodeGen/MachineFunction.h" 3089857Sobrien#include "llvm/CodeGen/MachineFunctionPass.h" 3189857Sobrien#include "llvm/CodeGen/MachineInstr.h" 3289857Sobrien#include "llvm/CodeGen/MachineInstrBuilder.h" 3389857Sobrien#include "llvm/CodeGen/MachineOperand.h" 3489857Sobrien#include "llvm/CodeGen/MachineRegisterInfo.h" 3589857Sobrien#include "llvm/CodeGen/PseudoSourceValue.h" 3689857Sobrien#include "llvm/CodeGen/TargetRegisterInfo.h" 3789857Sobrien#include "llvm/CodeGen/TargetSubtargetInfo.h" 3889857Sobrien#include "llvm/MC/MCInstrDesc.h" 3989857Sobrien#include "llvm/MC/MCRegisterInfo.h" 4089857Sobrien#include "llvm/Support/Casting.h" 4189857Sobrien#include "llvm/Support/CodeGen.h" 4289857Sobrien#include "llvm/Support/CommandLine.h" 4389857Sobrien#include "llvm/Support/ErrorHandling.h" 4489857Sobrien#include "llvm/Target/TargetMachine.h" 4589857Sobrien#include <algorithm> 4689857Sobrien#include <cassert> 4789857Sobrien#include <iterator> 4889857Sobrien#include <memory> 4989857Sobrien#include <utility> 5089857Sobrien 5189857Sobrienusing namespace llvm; 5289857Sobrien 5389857Sobrien#define DEBUG_TYPE "mips-delay-slot-filler" 5489857Sobrien 5589857SobrienSTATISTIC(FilledSlots, "Number of delay slots filled"); 5689857SobrienSTATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 5789857Sobrien " are not NOP."); 5889857Sobrien 5989857Sobrienstatic cl::opt<bool> DisableDelaySlotFiller( 6089857Sobrien "disable-mips-delay-filler", 6189857Sobrien cl::init(false), 6289857Sobrien cl::desc("Fill all delay slots with NOPs."), 6389857Sobrien cl::Hidden); 6489857Sobrien 6589857Sobrienstatic cl::opt<bool> DisableForwardSearch( 6689857Sobrien "disable-mips-df-forward-search", 6789857Sobrien cl::init(true), 6889857Sobrien cl::desc("Disallow MIPS delay filler to search forward."), 6989857Sobrien cl::Hidden); 7089857Sobrien 7189857Sobrienstatic cl::opt<bool> DisableSuccBBSearch( 7289857Sobrien "disable-mips-df-succbb-search", 7389857Sobrien cl::init(true), 7489857Sobrien cl::desc("Disallow MIPS delay filler to search successor basic blocks."), 7589857Sobrien cl::Hidden); 7689857Sobrien 7789857Sobrienstatic cl::opt<bool> DisableBackwardSearch( 7889857Sobrien "disable-mips-df-backward-search", 7989857Sobrien cl::init(false), 8089857Sobrien cl::desc("Disallow MIPS delay filler to search backward."), 8189857Sobrien cl::Hidden); 8289857Sobrien 8389857Sobrienenum CompactBranchPolicy { 8489857Sobrien CB_Never, ///< The policy 'never' may in some circumstances or for some 8589857Sobrien ///< ISAs not be absolutely adhered to. 8689857Sobrien CB_Optimal, ///< Optimal is the default and will produce compact branches 8789857Sobrien ///< when delay slots cannot be filled. 8889857Sobrien CB_Always ///< 'always' may in some circumstances may not be 8989857Sobrien ///< absolutely adhered to there may not be a corresponding 9089857Sobrien ///< compact form of a branch. 9189857Sobrien}; 9289857Sobrien 9389857Sobrienstatic cl::opt<CompactBranchPolicy> MipsCompactBranchPolicy( 9489857Sobrien "mips-compact-branches", cl::Optional, cl::init(CB_Optimal), 9589857Sobrien cl::desc("MIPS Specific: Compact branch policy."), 9689857Sobrien cl::values(clEnumValN(CB_Never, "never", 9789857Sobrien "Do not use compact branches if possible."), 9889857Sobrien clEnumValN(CB_Optimal, "optimal", 9989857Sobrien "Use compact branches where appropriate (default)."), 10089857Sobrien clEnumValN(CB_Always, "always", 10189857Sobrien "Always use compact branches if possible."))); 10289857Sobrien 10389857Sobriennamespace { 10489857Sobrien 10589857Sobrien using Iter = MachineBasicBlock::iterator; 10689857Sobrien using ReverseIter = MachineBasicBlock::reverse_iterator; 10789857Sobrien using BB2BrMap = SmallDenseMap<MachineBasicBlock *, MachineInstr *, 2>; 10889857Sobrien 10989857Sobrien class RegDefsUses { 11089857Sobrien public: 11189857Sobrien RegDefsUses(const TargetRegisterInfo &TRI); 11289857Sobrien 11389857Sobrien void init(const MachineInstr &MI); 11489857Sobrien 11589857Sobrien /// This function sets all caller-saved registers in Defs. 11689857Sobrien void setCallerSaved(const MachineInstr &MI); 11789857Sobrien 11889857Sobrien /// This function sets all unallocatable registers in Defs. 11989857Sobrien void setUnallocatableRegs(const MachineFunction &MF); 12089857Sobrien 12189857Sobrien /// Set bits in Uses corresponding to MBB's live-out registers except for 12289857Sobrien /// the registers that are live-in to SuccBB. 12389857Sobrien void addLiveOut(const MachineBasicBlock &MBB, 12489857Sobrien const MachineBasicBlock &SuccBB); 12589857Sobrien 12689857Sobrien bool update(const MachineInstr &MI, unsigned Begin, unsigned End); 12789857Sobrien 12889857Sobrien private: 12989857Sobrien bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg, 13089857Sobrien bool IsDef) const; 13189857Sobrien 13289857Sobrien /// Returns true if Reg or its alias is in RegSet. 13389857Sobrien bool isRegInSet(const BitVector &RegSet, unsigned Reg) const; 13489857Sobrien 13589857Sobrien const TargetRegisterInfo &TRI; 13689857Sobrien BitVector Defs, Uses; 13789857Sobrien }; 13889857Sobrien 13989857Sobrien /// Base class for inspecting loads and stores. 14089857Sobrien class InspectMemInstr { 14189857Sobrien public: 14289857Sobrien InspectMemInstr(bool ForbidMemInstr_) : ForbidMemInstr(ForbidMemInstr_) {} 14389857Sobrien virtual ~InspectMemInstr() = default; 14489857Sobrien 14589857Sobrien /// Return true if MI cannot be moved to delay slot. 14689857Sobrien bool hasHazard(const MachineInstr &MI); 14789857Sobrien 14889857Sobrien protected: 14989857Sobrien /// Flags indicating whether loads or stores have been seen. 15089857Sobrien bool OrigSeenLoad = false; 15189857Sobrien bool OrigSeenStore = false; 15289857Sobrien bool SeenLoad = false; 15389857Sobrien bool SeenStore = false; 15489857Sobrien 15589857Sobrien /// Memory instructions are not allowed to move to delay slot if this flag 15689857Sobrien /// is true. 15789857Sobrien bool ForbidMemInstr; 15889857Sobrien 15989857Sobrien private: 16089857Sobrien virtual bool hasHazard_(const MachineInstr &MI) = 0; 16189857Sobrien }; 16289857Sobrien 16389857Sobrien /// This subclass rejects any memory instructions. 16489857Sobrien class NoMemInstr : public InspectMemInstr { 16589857Sobrien public: 16689857Sobrien NoMemInstr() : InspectMemInstr(true) {} 16789857Sobrien 16889857Sobrien private: 16989857Sobrien bool hasHazard_(const MachineInstr &MI) override { return true; } 17089857Sobrien }; 17189857Sobrien 17289857Sobrien /// This subclass accepts loads from stacks and constant loads. 17389857Sobrien class LoadFromStackOrConst : public InspectMemInstr { 17489857Sobrien public: 17589857Sobrien LoadFromStackOrConst() : InspectMemInstr(false) {} 17689857Sobrien 17789857Sobrien private: 17889857Sobrien bool hasHazard_(const MachineInstr &MI) override; 17989857Sobrien }; 18089857Sobrien 18189857Sobrien /// This subclass uses memory dependence information to determine whether a 18289857Sobrien /// memory instruction can be moved to a delay slot. 18389857Sobrien class MemDefsUses : public InspectMemInstr { 18489857Sobrien public: 18589857Sobrien explicit MemDefsUses(const MachineFrameInfo *MFI); 18689857Sobrien 18789857Sobrien private: 18889857Sobrien using ValueType = PointerUnion<const Value *, const PseudoSourceValue *>; 18989857Sobrien 19089857Sobrien bool hasHazard_(const MachineInstr &MI) override; 19189857Sobrien 19289857Sobrien /// Update Defs and Uses. Return true if there exist dependences that 19389857Sobrien /// disqualify the delay slot candidate between V and values in Uses and 19489857Sobrien /// Defs. 19589857Sobrien bool updateDefsUses(ValueType V, bool MayStore); 19689857Sobrien 19789857Sobrien /// Get the list of underlying objects of MI's memory operand. 19889857Sobrien bool getUnderlyingObjects(const MachineInstr &MI, 19989857Sobrien SmallVectorImpl<ValueType> &Objects) const; 20089857Sobrien 20189857Sobrien const MachineFrameInfo *MFI; 20289857Sobrien SmallPtrSet<ValueType, 4> Uses, Defs; 20389857Sobrien 20489857Sobrien /// Flags indicating whether loads or stores with no underlying objects have 20589857Sobrien /// been seen. 20689857Sobrien bool SeenNoObjLoad = false; 20789857Sobrien bool SeenNoObjStore = false; 20889857Sobrien }; 20989857Sobrien 21089857Sobrien class MipsDelaySlotFiller : public MachineFunctionPass { 21189857Sobrien public: 21289857Sobrien MipsDelaySlotFiller() : MachineFunctionPass(ID) { 21389857Sobrien initializeMipsDelaySlotFillerPass(*PassRegistry::getPassRegistry()); 21489857Sobrien } 21589857Sobrien 21689857Sobrien StringRef getPassName() const override { return "Mips Delay Slot Filler"; } 21789857Sobrien 21889857Sobrien bool runOnMachineFunction(MachineFunction &F) override { 21989857Sobrien TM = &F.getTarget(); 22089857Sobrien bool Changed = false; 22189857Sobrien for (MachineBasicBlock &MBB : F) 22289857Sobrien Changed |= runOnMachineBasicBlock(MBB); 22389857Sobrien 22489857Sobrien // This pass invalidates liveness information when it reorders 22589857Sobrien // instructions to fill delay slot. Without this, -verify-machineinstrs 22689857Sobrien // will fail. 22789857Sobrien if (Changed) 22889857Sobrien F.getRegInfo().invalidateLiveness(); 22989857Sobrien 23089857Sobrien return Changed; 23189857Sobrien } 23289857Sobrien 23389857Sobrien MachineFunctionProperties getRequiredProperties() const override { 23489857Sobrien return MachineFunctionProperties().set( 23589857Sobrien MachineFunctionProperties::Property::NoVRegs); 23689857Sobrien } 23789857Sobrien 23889857Sobrien void getAnalysisUsage(AnalysisUsage &AU) const override { 23989857Sobrien AU.addRequired<MachineBranchProbabilityInfo>(); 24089857Sobrien MachineFunctionPass::getAnalysisUsage(AU); 24189857Sobrien } 24289857Sobrien 24389857Sobrien static char ID; 24489857Sobrien 24589857Sobrien private: 24689857Sobrien bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 24789857Sobrien 24889857Sobrien Iter replaceWithCompactBranch(MachineBasicBlock &MBB, Iter Branch, 24989857Sobrien const DebugLoc &DL); 25089857Sobrien 25189857Sobrien /// This function checks if it is valid to move Candidate to the delay slot 25289857Sobrien /// and returns true if it isn't. It also updates memory and register 25389857Sobrien /// dependence information. 25489857Sobrien bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, 25589857Sobrien InspectMemInstr &IM) const; 25689857Sobrien 25789857Sobrien /// This function searches range [Begin, End) for an instruction that can be 25889857Sobrien /// moved to the delay slot. Returns true on success. 25989857Sobrien template<typename IterTy> 26089857Sobrien bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, 26189857Sobrien RegDefsUses &RegDU, InspectMemInstr &IM, Iter Slot, 26289857Sobrien IterTy &Filler) const; 26389857Sobrien 26489857Sobrien /// This function searches in the backward direction for an instruction that 26589857Sobrien /// can be moved to the delay slot. Returns true on success. 26689857Sobrien bool searchBackward(MachineBasicBlock &MBB, MachineInstr &Slot) const; 26789857Sobrien 26889857Sobrien /// This function searches MBB in the forward direction for an instruction 26989857Sobrien /// that can be moved to the delay slot. Returns true on success. 27089857Sobrien bool searchForward(MachineBasicBlock &MBB, Iter Slot) const; 27189857Sobrien 27289857Sobrien /// This function searches one of MBB's successor blocks for an instruction 27389857Sobrien /// that can be moved to the delay slot and inserts clones of the 27489857Sobrien /// instruction into the successor's predecessor blocks. 27589857Sobrien bool searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const; 27689857Sobrien 27789857Sobrien /// Pick a successor block of MBB. Return NULL if MBB doesn't have a 27889857Sobrien /// successor block that is not a landing pad. 27989857Sobrien MachineBasicBlock *selectSuccBB(MachineBasicBlock &B) const; 28089857Sobrien 28189857Sobrien /// This function analyzes MBB and returns an instruction with an unoccupied 28289857Sobrien /// slot that branches to Dst. 28389857Sobrien std::pair<MipsInstrInfo::BranchType, MachineInstr *> 28489857Sobrien getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const; 28589857Sobrien 28689857Sobrien /// Examine Pred and see if it is possible to insert an instruction into 28789857Sobrien /// one of its branches delay slot or its end. 28889857Sobrien bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ, 28989857Sobrien RegDefsUses &RegDU, bool &HasMultipleSuccs, 29089857Sobrien BB2BrMap &BrMap) const; 29189857Sobrien 29289857Sobrien bool terminateSearch(const MachineInstr &Candidate) const; 29389857Sobrien 29489857Sobrien const TargetMachine *TM = nullptr; 29589857Sobrien }; 29689857Sobrien 29789857Sobrien} // end anonymous namespace 29889857Sobrien 29989857Sobrienchar MipsDelaySlotFiller::ID = 0; 30089857Sobrien 30189857Sobrienstatic bool hasUnoccupiedSlot(const MachineInstr *MI) { 30289857Sobrien return MI->hasDelaySlot() && !MI->isBundledWithSucc(); 30389857Sobrien} 30489857Sobrien 30589857SobrienINITIALIZE_PASS(MipsDelaySlotFiller, DEBUG_TYPE, 30689857Sobrien "Fill delay slot for MIPS", false, false) 30789857Sobrien 30889857Sobrien/// This function inserts clones of Filler into predecessor blocks. 30989857Sobrienstatic void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) { 31089857Sobrien MachineFunction *MF = Filler->getParent()->getParent(); 31189857Sobrien 31289857Sobrien for (const auto &I : BrMap) { 31389857Sobrien if (I.second) { 31489857Sobrien MIBundleBuilder(I.second).append(MF->CloneMachineInstr(&*Filler)); 31589857Sobrien ++UsefulSlots; 31689857Sobrien } else { 31789857Sobrien I.first->push_back(MF->CloneMachineInstr(&*Filler)); 31889857Sobrien } 31989857Sobrien } 32089857Sobrien} 32189857Sobrien 32289857Sobrien/// This function adds registers Filler defines to MBB's live-in register list. 32389857Sobrienstatic void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) { 32489857Sobrien for (unsigned I = 0, E = Filler->getNumOperands(); I != E; ++I) { 32589857Sobrien const MachineOperand &MO = Filler->getOperand(I); 32689857Sobrien unsigned R; 32789857Sobrien 32889857Sobrien if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg())) 32989857Sobrien continue; 33089857Sobrien 33189857Sobrien#ifndef NDEBUG 33289857Sobrien const MachineFunction &MF = *MBB.getParent(); 33389857Sobrien assert(MF.getSubtarget().getRegisterInfo()->getAllocatableSet(MF).test(R) && 33489857Sobrien "Shouldn't move an instruction with unallocatable registers across " 33589857Sobrien "basic block boundaries."); 33689857Sobrien#endif 33789857Sobrien 33889857Sobrien if (!MBB.isLiveIn(R)) 33989857Sobrien MBB.addLiveIn(R); 34089857Sobrien } 34189857Sobrien} 34289857Sobrien 34389857SobrienRegDefsUses::RegDefsUses(const TargetRegisterInfo &TRI) 34489857Sobrien : TRI(TRI), Defs(TRI.getNumRegs(), false), Uses(TRI.getNumRegs(), false) {} 34589857Sobrien 34689857Sobrienvoid RegDefsUses::init(const MachineInstr &MI) { 34789857Sobrien // Add all register operands which are explicit and non-variadic. 34889857Sobrien update(MI, 0, MI.getDesc().getNumOperands()); 34989857Sobrien 35089857Sobrien // If MI is a call, add RA to Defs to prevent users of RA from going into 35189857Sobrien // delay slot. 35289857Sobrien if (MI.isCall()) 35389857Sobrien Defs.set(Mips::RA); 35489857Sobrien 35589857Sobrien // Add all implicit register operands of branch instructions except 35689857Sobrien // register AT. 35789857Sobrien if (MI.isBranch()) { 35889857Sobrien update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands()); 35989857Sobrien Defs.reset(Mips::AT); 36089857Sobrien } 36189857Sobrien} 36289857Sobrien 36389857Sobrienvoid RegDefsUses::setCallerSaved(const MachineInstr &MI) { 36489857Sobrien assert(MI.isCall()); 36589857Sobrien 36689857Sobrien // Add RA/RA_64 to Defs to prevent users of RA/RA_64 from going into 36789857Sobrien // the delay slot. The reason is that RA/RA_64 must not be changed 36889857Sobrien // in the delay slot so that the callee can return to the caller. 36989857Sobrien if (MI.definesRegister(Mips::RA) || MI.definesRegister(Mips::RA_64)) { 37089857Sobrien Defs.set(Mips::RA); 37189857Sobrien Defs.set(Mips::RA_64); 37289857Sobrien } 37389857Sobrien 37489857Sobrien // If MI is a call, add all caller-saved registers to Defs. 37589857Sobrien BitVector CallerSavedRegs(TRI.getNumRegs(), true); 37689857Sobrien 37789857Sobrien CallerSavedRegs.reset(Mips::ZERO); 37889857Sobrien CallerSavedRegs.reset(Mips::ZERO_64); 37989857Sobrien 38089857Sobrien for (const MCPhysReg *R = TRI.getCalleeSavedRegs(MI.getParent()->getParent()); 38189857Sobrien *R; ++R) 38289857Sobrien for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI) 38389857Sobrien CallerSavedRegs.reset(*AI); 38489857Sobrien 38589857Sobrien Defs |= CallerSavedRegs; 38689857Sobrien} 38789857Sobrien 38889857Sobrienvoid RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) { 38989857Sobrien BitVector AllocSet = TRI.getAllocatableSet(MF); 39089857Sobrien 39189857Sobrien for (unsigned R : AllocSet.set_bits()) 39289857Sobrien for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI) 39389857Sobrien AllocSet.set(*AI); 39489857Sobrien 39589857Sobrien AllocSet.set(Mips::ZERO); 39689857Sobrien AllocSet.set(Mips::ZERO_64); 39789857Sobrien 39889857Sobrien Defs |= AllocSet.flip(); 39989857Sobrien} 40089857Sobrien 40189857Sobrienvoid RegDefsUses::addLiveOut(const MachineBasicBlock &MBB, 40289857Sobrien const MachineBasicBlock &SuccBB) { 40389857Sobrien for (const MachineBasicBlock *S : MBB.successors()) 40489857Sobrien if (S != &SuccBB) 40589857Sobrien for (const auto &LI : S->liveins()) 40689857Sobrien Uses.set(LI.PhysReg); 40789857Sobrien} 40889857Sobrien 40989857Sobrienbool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) { 41089857Sobrien BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs()); 41189857Sobrien bool HasHazard = false; 41289857Sobrien 41389857Sobrien for (unsigned I = Begin; I != End; ++I) { 41489857Sobrien const MachineOperand &MO = MI.getOperand(I); 41589857Sobrien 41689857Sobrien if (MO.isReg() && MO.getReg()) { 41789857Sobrien if (checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef())) { 41889857Sobrien LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found register hazard for operand " 41989857Sobrien << I << ": "; 42089857Sobrien MO.dump()); 42189857Sobrien HasHazard = true; 42289857Sobrien } 42389857Sobrien } 42489857Sobrien } 42589857Sobrien 42689857Sobrien Defs |= NewDefs; 42789857Sobrien Uses |= NewUses; 42889857Sobrien 42989857Sobrien return HasHazard; 43089857Sobrien} 43189857Sobrien 43289857Sobrienbool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, 43389857Sobrien unsigned Reg, bool IsDef) const { 43489857Sobrien if (IsDef) { 43589857Sobrien NewDefs.set(Reg); 43689857Sobrien // check whether Reg has already been defined or used. 43789857Sobrien return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg)); 43889857Sobrien } 43989857Sobrien 44089857Sobrien NewUses.set(Reg); 44189857Sobrien // check whether Reg has already been defined. 44289857Sobrien return isRegInSet(Defs, Reg); 44389857Sobrien} 44489857Sobrien 44589857Sobrienbool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const { 44689857Sobrien // Check Reg and all aliased Registers. 44789857Sobrien for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI) 44889857Sobrien if (RegSet.test(*AI)) 44989857Sobrien return true; 45089857Sobrien return false; 45189857Sobrien} 45289857Sobrien 45389857Sobrienbool InspectMemInstr::hasHazard(const MachineInstr &MI) { 45489857Sobrien if (!MI.mayStore() && !MI.mayLoad()) 45589857Sobrien return false; 45689857Sobrien 45789857Sobrien if (ForbidMemInstr) 45889857Sobrien return true; 45989857Sobrien 46089857Sobrien OrigSeenLoad = SeenLoad; 46189857Sobrien OrigSeenStore = SeenStore; 46289857Sobrien SeenLoad |= MI.mayLoad(); 46389857Sobrien SeenStore |= MI.mayStore(); 46489857Sobrien 46589857Sobrien // If MI is an ordered or volatile memory reference, disallow moving 46689857Sobrien // subsequent loads and stores to delay slot. 46789857Sobrien if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) { 46889857Sobrien ForbidMemInstr = true; 46989857Sobrien return true; 47089857Sobrien } 47189857Sobrien 47289857Sobrien return hasHazard_(MI); 47389857Sobrien} 47489857Sobrien 47589857Sobrienbool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) { 47689857Sobrien if (MI.mayStore()) 47789857Sobrien return true; 47889857Sobrien 47989857Sobrien if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getPseudoValue()) 48089857Sobrien return true; 48189857Sobrien 48289857Sobrien if (const PseudoSourceValue *PSV = 48389857Sobrien (*MI.memoperands_begin())->getPseudoValue()) { 48489857Sobrien if (isa<FixedStackPseudoSourceValue>(PSV)) 48589857Sobrien return false; 48689857Sobrien return !PSV->isConstant(nullptr) && !PSV->isStack(); 48789857Sobrien } 48889857Sobrien 48989857Sobrien return true; 49089857Sobrien} 49189857Sobrien 49289857SobrienMemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_) 49389857Sobrien : InspectMemInstr(false), MFI(MFI_) {} 49489857Sobrien 49589857Sobrienbool MemDefsUses::hasHazard_(const MachineInstr &MI) { 49689857Sobrien bool HasHazard = false; 49789857Sobrien 49889857Sobrien // Check underlying object list. 49989857Sobrien SmallVector<ValueType, 4> Objs; 50089857Sobrien if (getUnderlyingObjects(MI, Objs)) { 50189857Sobrien for (ValueType VT : Objs) 50289857Sobrien HasHazard |= updateDefsUses(VT, MI.mayStore()); 50389857Sobrien return HasHazard; 50489857Sobrien } 50589857Sobrien 50689857Sobrien // No underlying objects found. 50789857Sobrien HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore); 50889857Sobrien HasHazard |= MI.mayLoad() || OrigSeenStore; 50989857Sobrien 51089857Sobrien SeenNoObjLoad |= MI.mayLoad(); 51189857Sobrien SeenNoObjStore |= MI.mayStore(); 51289857Sobrien 51389857Sobrien return HasHazard; 51489857Sobrien} 51589857Sobrien 51689857Sobrienbool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) { 51789857Sobrien if (MayStore) 51889857Sobrien return !Defs.insert(V).second || Uses.count(V) || SeenNoObjStore || 51989857Sobrien SeenNoObjLoad; 52089857Sobrien 52189857Sobrien Uses.insert(V); 52289857Sobrien return Defs.count(V) || SeenNoObjStore; 52389857Sobrien} 52489857Sobrien 52589857Sobrienbool MemDefsUses:: 52689857SobriengetUnderlyingObjects(const MachineInstr &MI, 52789857Sobrien SmallVectorImpl<ValueType> &Objects) const { 52889857Sobrien if (!MI.hasOneMemOperand()) 52989857Sobrien return false; 53089857Sobrien 53189857Sobrien auto & MMO = **MI.memoperands_begin(); 53289857Sobrien 53389857Sobrien if (const PseudoSourceValue *PSV = MMO.getPseudoValue()) { 53489857Sobrien if (!PSV->isAliased(MFI)) 53589857Sobrien return false; 53689857Sobrien Objects.push_back(PSV); 53789857Sobrien return true; 53889857Sobrien } 53989857Sobrien 54089857Sobrien if (const Value *V = MMO.getValue()) { 54189857Sobrien SmallVector<const Value *, 4> Objs; 54289857Sobrien ::getUnderlyingObjects(V, Objs); 54389857Sobrien 54489857Sobrien for (const Value *UValue : Objs) { 54589857Sobrien if (!isIdentifiedObject(V)) 54689857Sobrien return false; 547218822Sdim 54889857Sobrien Objects.push_back(UValue); 54989857Sobrien } 55089857Sobrien return true; 55189857Sobrien } 55289857Sobrien 55389857Sobrien return false; 55489857Sobrien} 55589857Sobrien 55689857Sobrien// Replace Branch with the compact branch instruction. 55789857SobrienIter MipsDelaySlotFiller::replaceWithCompactBranch(MachineBasicBlock &MBB, 55889857Sobrien Iter Branch, 55989857Sobrien const DebugLoc &DL) { 56089857Sobrien const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>(); 56189857Sobrien const MipsInstrInfo *TII = STI.getInstrInfo(); 56289857Sobrien 56389857Sobrien unsigned NewOpcode = TII->getEquivalentCompactForm(Branch); 56489857Sobrien Branch = TII->genInstrWithNewOpc(NewOpcode, Branch); 56589857Sobrien 566 auto *ToErase = cast<MachineInstr>(&*std::next(Branch)); 567 // Update call site info for the Branch. 568 if (ToErase->shouldUpdateCallSiteInfo()) 569 ToErase->getMF()->moveCallSiteInfo(ToErase, cast<MachineInstr>(&*Branch)); 570 ToErase->eraseFromParent(); 571 return Branch; 572} 573 574// For given opcode returns opcode of corresponding instruction with short 575// delay slot. 576// For the pseudo TAILCALL*_MM instructions return the short delay slot 577// form. Unfortunately, TAILCALL<->b16 is denied as b16 has a limited range 578// that is too short to make use of for tail calls. 579static int getEquivalentCallShort(int Opcode) { 580 switch (Opcode) { 581 case Mips::BGEZAL: 582 return Mips::BGEZALS_MM; 583 case Mips::BLTZAL: 584 return Mips::BLTZALS_MM; 585 case Mips::JAL: 586 case Mips::JAL_MM: 587 return Mips::JALS_MM; 588 case Mips::JALR: 589 return Mips::JALRS_MM; 590 case Mips::JALR16_MM: 591 return Mips::JALRS16_MM; 592 case Mips::TAILCALL_MM: 593 llvm_unreachable("Attempting to shorten the TAILCALL_MM pseudo!"); 594 case Mips::TAILCALLREG: 595 return Mips::JR16_MM; 596 default: 597 llvm_unreachable("Unexpected call instruction for microMIPS."); 598 } 599} 600 601/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 602/// We assume there is only one delay slot per delayed instruction. 603bool MipsDelaySlotFiller::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 604 bool Changed = false; 605 const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>(); 606 bool InMicroMipsMode = STI.inMicroMipsMode(); 607 const MipsInstrInfo *TII = STI.getInstrInfo(); 608 609 for (Iter I = MBB.begin(); I != MBB.end(); ++I) { 610 if (!hasUnoccupiedSlot(&*I)) 611 continue; 612 613 // Delay slot filling is disabled at -O0, or in microMIPS32R6. 614 if (!DisableDelaySlotFiller && (TM->getOptLevel() != CodeGenOpt::None) && 615 !(InMicroMipsMode && STI.hasMips32r6())) { 616 617 bool Filled = false; 618 619 if (MipsCompactBranchPolicy.getValue() != CB_Always || 620 !TII->getEquivalentCompactForm(I)) { 621 if (searchBackward(MBB, *I)) { 622 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot" 623 " in backwards search.\n"); 624 Filled = true; 625 } else if (I->isTerminator()) { 626 if (searchSuccBBs(MBB, I)) { 627 Filled = true; 628 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot" 629 " in successor BB search.\n"); 630 } 631 } else if (searchForward(MBB, I)) { 632 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot" 633 " in forwards search.\n"); 634 Filled = true; 635 } 636 } 637 638 if (Filled) { 639 // Get instruction with delay slot. 640 MachineBasicBlock::instr_iterator DSI = I.getInstrIterator(); 641 642 if (InMicroMipsMode && TII->getInstSizeInBytes(*std::next(DSI)) == 2 && 643 DSI->isCall()) { 644 // If instruction in delay slot is 16b change opcode to 645 // corresponding instruction with short delay slot. 646 647 // TODO: Implement an instruction mapping table of 16bit opcodes to 648 // 32bit opcodes so that an instruction can be expanded. This would 649 // save 16 bits as a TAILCALL_MM pseudo requires a fullsized nop. 650 // TODO: Permit b16 when branching backwards to the same function 651 // if it is in range. 652 DSI->setDesc(TII->get(getEquivalentCallShort(DSI->getOpcode()))); 653 } 654 ++FilledSlots; 655 Changed = true; 656 continue; 657 } 658 } 659 660 // For microMIPS if instruction is BEQ or BNE with one ZERO register, then 661 // instead of adding NOP replace this instruction with the corresponding 662 // compact branch instruction, i.e. BEQZC or BNEZC. Additionally 663 // PseudoReturn and PseudoIndirectBranch are expanded to JR_MM, so they can 664 // be replaced with JRC16_MM. 665 666 // For MIPSR6 attempt to produce the corresponding compact (no delay slot) 667 // form of the CTI. For indirect jumps this will not require inserting a 668 // NOP and for branches will hopefully avoid requiring a NOP. 669 if ((InMicroMipsMode || 670 (STI.hasMips32r6() && MipsCompactBranchPolicy != CB_Never)) && 671 TII->getEquivalentCompactForm(I)) { 672 I = replaceWithCompactBranch(MBB, I, I->getDebugLoc()); 673 Changed = true; 674 continue; 675 } 676 677 // Bundle the NOP to the instruction with the delay slot. 678 LLVM_DEBUG(dbgs() << DEBUG_TYPE << ": could not fill delay slot for "; 679 I->dump()); 680 TII->insertNop(MBB, std::next(I), I->getDebugLoc()); 681 MIBundleBuilder(MBB, I, std::next(I, 2)); 682 ++FilledSlots; 683 Changed = true; 684 } 685 686 return Changed; 687} 688 689template <typename IterTy> 690bool MipsDelaySlotFiller::searchRange(MachineBasicBlock &MBB, IterTy Begin, 691 IterTy End, RegDefsUses &RegDU, 692 InspectMemInstr &IM, Iter Slot, 693 IterTy &Filler) const { 694 for (IterTy I = Begin; I != End;) { 695 IterTy CurrI = I; 696 ++I; 697 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": checking instruction: "; CurrI->dump()); 698 // skip debug value 699 if (CurrI->isDebugInstr()) { 700 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": ignoring debug instruction: "; 701 CurrI->dump()); 702 continue; 703 } 704 705 if (CurrI->isBundle()) { 706 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": ignoring BUNDLE instruction: "; 707 CurrI->dump()); 708 // However, we still need to update the register def-use information. 709 RegDU.update(*CurrI, 0, CurrI->getNumOperands()); 710 continue; 711 } 712 713 if (terminateSearch(*CurrI)) { 714 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": should terminate search: "; 715 CurrI->dump()); 716 break; 717 } 718 719 assert((!CurrI->isCall() && !CurrI->isReturn() && !CurrI->isBranch()) && 720 "Cannot put calls, returns or branches in delay slot."); 721 722 if (CurrI->isKill()) { 723 CurrI->eraseFromParent(); 724 continue; 725 } 726 727 if (delayHasHazard(*CurrI, RegDU, IM)) 728 continue; 729 730 const MipsSubtarget &STI = MBB.getParent()->getSubtarget<MipsSubtarget>(); 731 if (STI.isTargetNaCl()) { 732 // In NaCl, instructions that must be masked are forbidden in delay slots. 733 // We only check for loads, stores and SP changes. Calls, returns and 734 // branches are not checked because non-NaCl targets never put them in 735 // delay slots. 736 unsigned AddrIdx; 737 if ((isBasePlusOffsetMemoryAccess(CurrI->getOpcode(), &AddrIdx) && 738 baseRegNeedsLoadStoreMask(CurrI->getOperand(AddrIdx).getReg())) || 739 CurrI->modifiesRegister(Mips::SP, STI.getRegisterInfo())) 740 continue; 741 } 742 743 bool InMicroMipsMode = STI.inMicroMipsMode(); 744 const MipsInstrInfo *TII = STI.getInstrInfo(); 745 unsigned Opcode = (*Slot).getOpcode(); 746 // This is complicated by the tail call optimization. For non-PIC code 747 // there is only a 32bit sized unconditional branch which can be assumed 748 // to be able to reach the target. b16 only has a range of +/- 1 KB. 749 // It's entirely possible that the target function is reachable with b16 750 // but we don't have enough information to make that decision. 751 if (InMicroMipsMode && TII->getInstSizeInBytes(*CurrI) == 2 && 752 (Opcode == Mips::JR || Opcode == Mips::PseudoIndirectBranch || 753 Opcode == Mips::PseudoIndirectBranch_MM || 754 Opcode == Mips::PseudoReturn || Opcode == Mips::TAILCALL)) 755 continue; 756 // Instructions LWP/SWP and MOVEP should not be in a delay slot as that 757 // results in unpredictable behaviour 758 if (InMicroMipsMode && (Opcode == Mips::LWP_MM || Opcode == Mips::SWP_MM || 759 Opcode == Mips::MOVEP_MM)) 760 continue; 761 762 Filler = CurrI; 763 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": found instruction for delay slot: "; 764 CurrI->dump()); 765 766 return true; 767 } 768 769 return false; 770} 771 772bool MipsDelaySlotFiller::searchBackward(MachineBasicBlock &MBB, 773 MachineInstr &Slot) const { 774 if (DisableBackwardSearch) 775 return false; 776 777 auto *Fn = MBB.getParent(); 778 RegDefsUses RegDU(*Fn->getSubtarget().getRegisterInfo()); 779 MemDefsUses MemDU(&Fn->getFrameInfo()); 780 ReverseIter Filler; 781 782 RegDU.init(Slot); 783 784 MachineBasicBlock::iterator SlotI = Slot; 785 if (!searchRange(MBB, ++SlotI.getReverse(), MBB.rend(), RegDU, MemDU, Slot, 786 Filler)) { 787 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": could not find instruction for delay " 788 "slot using backwards search.\n"); 789 return false; 790 } 791 792 MBB.splice(std::next(SlotI), &MBB, Filler.getReverse()); 793 MIBundleBuilder(MBB, SlotI, std::next(SlotI, 2)); 794 ++UsefulSlots; 795 return true; 796} 797 798bool MipsDelaySlotFiller::searchForward(MachineBasicBlock &MBB, 799 Iter Slot) const { 800 // Can handle only calls. 801 if (DisableForwardSearch || !Slot->isCall()) 802 return false; 803 804 RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo()); 805 NoMemInstr NM; 806 Iter Filler; 807 808 RegDU.setCallerSaved(*Slot); 809 810 if (!searchRange(MBB, std::next(Slot), MBB.end(), RegDU, NM, Slot, Filler)) { 811 LLVM_DEBUG(dbgs() << DEBUG_TYPE ": could not find instruction for delay " 812 "slot using forwards search.\n"); 813 return false; 814 } 815 816 MBB.splice(std::next(Slot), &MBB, Filler); 817 MIBundleBuilder(MBB, Slot, std::next(Slot, 2)); 818 ++UsefulSlots; 819 return true; 820} 821 822bool MipsDelaySlotFiller::searchSuccBBs(MachineBasicBlock &MBB, 823 Iter Slot) const { 824 if (DisableSuccBBSearch) 825 return false; 826 827 MachineBasicBlock *SuccBB = selectSuccBB(MBB); 828 829 if (!SuccBB) 830 return false; 831 832 RegDefsUses RegDU(*MBB.getParent()->getSubtarget().getRegisterInfo()); 833 bool HasMultipleSuccs = false; 834 BB2BrMap BrMap; 835 std::unique_ptr<InspectMemInstr> IM; 836 Iter Filler; 837 auto *Fn = MBB.getParent(); 838 839 // Iterate over SuccBB's predecessor list. 840 for (MachineBasicBlock *Pred : SuccBB->predecessors()) 841 if (!examinePred(*Pred, *SuccBB, RegDU, HasMultipleSuccs, BrMap)) 842 return false; 843 844 // Do not allow moving instructions which have unallocatable register operands 845 // across basic block boundaries. 846 RegDU.setUnallocatableRegs(*Fn); 847 848 // Only allow moving loads from stack or constants if any of the SuccBB's 849 // predecessors have multiple successors. 850 if (HasMultipleSuccs) { 851 IM.reset(new LoadFromStackOrConst()); 852 } else { 853 const MachineFrameInfo &MFI = Fn->getFrameInfo(); 854 IM.reset(new MemDefsUses(&MFI)); 855 } 856 857 if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Slot, 858 Filler)) 859 return false; 860 861 insertDelayFiller(Filler, BrMap); 862 addLiveInRegs(Filler, *SuccBB); 863 Filler->eraseFromParent(); 864 865 return true; 866} 867 868MachineBasicBlock * 869MipsDelaySlotFiller::selectSuccBB(MachineBasicBlock &B) const { 870 if (B.succ_empty()) 871 return nullptr; 872 873 // Select the successor with the larget edge weight. 874 auto &Prob = getAnalysis<MachineBranchProbabilityInfo>(); 875 MachineBasicBlock *S = *std::max_element( 876 B.succ_begin(), B.succ_end(), 877 [&](const MachineBasicBlock *Dst0, const MachineBasicBlock *Dst1) { 878 return Prob.getEdgeProbability(&B, Dst0) < 879 Prob.getEdgeProbability(&B, Dst1); 880 }); 881 return S->isEHPad() ? nullptr : S; 882} 883 884std::pair<MipsInstrInfo::BranchType, MachineInstr *> 885MipsDelaySlotFiller::getBranch(MachineBasicBlock &MBB, 886 const MachineBasicBlock &Dst) const { 887 const MipsInstrInfo *TII = 888 MBB.getParent()->getSubtarget<MipsSubtarget>().getInstrInfo(); 889 MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr; 890 SmallVector<MachineInstr*, 2> BranchInstrs; 891 SmallVector<MachineOperand, 2> Cond; 892 893 MipsInstrInfo::BranchType R = 894 TII->analyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs); 895 896 if ((R == MipsInstrInfo::BT_None) || (R == MipsInstrInfo::BT_NoBranch)) 897 return std::make_pair(R, nullptr); 898 899 if (R != MipsInstrInfo::BT_CondUncond) { 900 if (!hasUnoccupiedSlot(BranchInstrs[0])) 901 return std::make_pair(MipsInstrInfo::BT_None, nullptr); 902 903 assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst))); 904 905 return std::make_pair(R, BranchInstrs[0]); 906 } 907 908 assert((TrueBB == &Dst) || (FalseBB == &Dst)); 909 910 // Examine the conditional branch. See if its slot is occupied. 911 if (hasUnoccupiedSlot(BranchInstrs[0])) 912 return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]); 913 914 // If that fails, try the unconditional branch. 915 if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst)) 916 return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]); 917 918 return std::make_pair(MipsInstrInfo::BT_None, nullptr); 919} 920 921bool MipsDelaySlotFiller::examinePred(MachineBasicBlock &Pred, 922 const MachineBasicBlock &Succ, 923 RegDefsUses &RegDU, 924 bool &HasMultipleSuccs, 925 BB2BrMap &BrMap) const { 926 std::pair<MipsInstrInfo::BranchType, MachineInstr *> P = 927 getBranch(Pred, Succ); 928 929 // Return if either getBranch wasn't able to analyze the branches or there 930 // were no branches with unoccupied slots. 931 if (P.first == MipsInstrInfo::BT_None) 932 return false; 933 934 if ((P.first != MipsInstrInfo::BT_Uncond) && 935 (P.first != MipsInstrInfo::BT_NoBranch)) { 936 HasMultipleSuccs = true; 937 RegDU.addLiveOut(Pred, Succ); 938 } 939 940 BrMap[&Pred] = P.second; 941 return true; 942} 943 944bool MipsDelaySlotFiller::delayHasHazard(const MachineInstr &Candidate, 945 RegDefsUses &RegDU, 946 InspectMemInstr &IM) const { 947 assert(!Candidate.isKill() && 948 "KILL instructions should have been eliminated at this point."); 949 950 bool HasHazard = Candidate.isImplicitDef(); 951 952 HasHazard |= IM.hasHazard(Candidate); 953 HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands()); 954 955 return HasHazard; 956} 957 958bool MipsDelaySlotFiller::terminateSearch(const MachineInstr &Candidate) const { 959 return (Candidate.isTerminator() || Candidate.isCall() || 960 Candidate.isPosition() || Candidate.isInlineAsm() || 961 Candidate.hasUnmodeledSideEffects()); 962} 963 964/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 965/// slots in Mips MachineFunctions 966FunctionPass *llvm::createMipsDelaySlotFillerPass() { 967 return new MipsDelaySlotFiller(); 968} 969