X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FMips%2FMipsDelaySlotFiller.cpp;h=f8daec9e50f0550f0ec5ec4685076d45b4e5a88e;hb=9f85dccfc64b5f0b0c63ddfa0a42d8615aa1fcb3;hp=c5558eb9cff0da260e4c6558f4563561e8418f74;hpb=a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8;p=oota-llvm.git diff --git a/lib/Target/Mips/MipsDelaySlotFiller.cpp b/lib/Target/Mips/MipsDelaySlotFiller.cpp index c5558eb9cff..f8daec9e50f 100644 --- a/lib/Target/Mips/MipsDelaySlotFiller.cpp +++ b/lib/Target/Mips/MipsDelaySlotFiller.cpp @@ -11,17 +11,19 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "delay-slot-filler" - +#include "MCTargetDesc/MipsMCNaCl.h" #include "Mips.h" +#include "MipsInstrInfo.h" #include "MipsTargetMachine.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/PseudoSourceValue.h" #include "llvm/Support/CommandLine.h" #include "llvm/Target/TargetInstrInfo.h" @@ -30,6 +32,8 @@ using namespace llvm; +#define DEBUG_TYPE "delay-slot-filler" + STATISTIC(FilledSlots, "Number of delay slots filled"); STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" " are not NOP."); @@ -40,18 +44,45 @@ static cl::opt DisableDelaySlotFiller( cl::desc("Fill all delay slots with NOPs."), cl::Hidden); -// This option can be used to silence complaints by machine verifier passes. -static cl::opt SkipDelaySlotFiller( - "skip-mips-delay-filler", +static cl::opt DisableForwardSearch( + "disable-mips-df-forward-search", + cl::init(true), + cl::desc("Disallow MIPS delay filler to search forward."), + cl::Hidden); + +static cl::opt DisableSuccBBSearch( + "disable-mips-df-succbb-search", + cl::init(true), + cl::desc("Disallow MIPS delay filler to search successor basic blocks."), + cl::Hidden); + +static cl::opt DisableBackwardSearch( + "disable-mips-df-backward-search", cl::init(false), - cl::desc("Skip MIPS' delay slot filling pass."), + cl::desc("Disallow MIPS delay filler to search backward."), cl::Hidden); namespace { + typedef MachineBasicBlock::iterator Iter; + typedef MachineBasicBlock::reverse_iterator ReverseIter; + typedef SmallDenseMap BB2BrMap; + class RegDefsUses { public: RegDefsUses(TargetMachine &TM); void init(const MachineInstr &MI); + + /// This function sets all caller-saved registers in Defs. + void setCallerSaved(const MachineInstr &MI); + + /// This function sets all unallocatable registers in Defs. + void setUnallocatableRegs(const MachineFunction &MF); + + /// Set bits in Uses corresponding to MBB's live-out registers except for + /// the registers that are live-in to SuccBB. + void addLiveOut(const MachineBasicBlock &MBB, + const MachineBasicBlock &SuccBB); + bool update(const MachineInstr &MI, unsigned Begin, unsigned End); private: @@ -65,85 +96,202 @@ namespace { BitVector Defs, Uses; }; - /// This class maintains memory dependence information. - class MemDefsUses { + /// Base class for inspecting loads and stores. + class InspectMemInstr { public: - MemDefsUses(const MachineFrameInfo *MFI); + InspectMemInstr(bool ForbidMemInstr_) + : OrigSeenLoad(false), OrigSeenStore(false), SeenLoad(false), + SeenStore(false), ForbidMemInstr(ForbidMemInstr_) {} /// Return true if MI cannot be moved to delay slot. bool hasHazard(const MachineInstr &MI); + virtual ~InspectMemInstr() {} + + protected: + /// Flags indicating whether loads or stores have been seen. + bool OrigSeenLoad, OrigSeenStore, SeenLoad, SeenStore; + + /// Memory instructions are not allowed to move to delay slot if this flag + /// is true. + bool ForbidMemInstr; + private: + virtual bool hasHazard_(const MachineInstr &MI) = 0; + }; + + /// This subclass rejects any memory instructions. + class NoMemInstr : public InspectMemInstr { + public: + NoMemInstr() : InspectMemInstr(true) {} + private: + bool hasHazard_(const MachineInstr &MI) override { return true; } + }; + + /// This subclass accepts loads from stacks and constant loads. + class LoadFromStackOrConst : public InspectMemInstr { + public: + LoadFromStackOrConst() : InspectMemInstr(false) {} + private: + bool hasHazard_(const MachineInstr &MI) override; + }; + + /// This subclass uses memory dependence information to determine whether a + /// memory instruction can be moved to a delay slot. + class MemDefsUses : public InspectMemInstr { + public: + MemDefsUses(const MachineFrameInfo *MFI); + + private: + typedef PointerUnion ValueType; + + bool hasHazard_(const MachineInstr &MI) override; + /// Update Defs and Uses. Return true if there exist dependences that - /// disqualify the delay slot candidate between V and values in Uses and Defs. - bool updateDefsUses(const Value *V, bool MayStore); + /// disqualify the delay slot candidate between V and values in Uses and + /// Defs. + bool updateDefsUses(ValueType V, bool MayStore); /// Get the list of underlying objects of MI's memory operand. bool getUnderlyingObjects(const MachineInstr &MI, - SmallVectorImpl &Objects) const; + SmallVectorImpl &Objects) const; const MachineFrameInfo *MFI; - SmallPtrSet Uses, Defs; - - /// Flags indicating whether loads or stores have been seen. - bool SeenLoad, SeenStore; + SmallPtrSet Uses, Defs; /// Flags indicating whether loads or stores with no underlying objects have /// been seen. bool SeenNoObjLoad, SeenNoObjStore; - - /// Memory instructions are not allowed to move to delay slot if this flag - /// is true. - bool ForbidMemInstr; }; class Filler : public MachineFunctionPass { public: Filler(TargetMachine &tm) - : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } + : MachineFunctionPass(ID), TM(tm) { } - virtual const char *getPassName() const { + const char *getPassName() const override { return "Mips Delay Slot Filler"; } - bool runOnMachineFunction(MachineFunction &F) { - if (SkipDelaySlotFiller) - return false; - + bool runOnMachineFunction(MachineFunction &F) override { bool Changed = false; for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) Changed |= runOnMachineBasicBlock(*FI); + + // This pass invalidates liveness information when it reorders + // instructions to fill delay slot. Without this, -verify-machineinstrs + // will fail. + if (Changed) + F.getRegInfo().invalidateLiveness(); + return Changed; } - private: - typedef MachineBasicBlock::iterator Iter; - typedef MachineBasicBlock::reverse_iterator ReverseIter; + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + MachineFunctionPass::getAnalysisUsage(AU); + } + private: bool runOnMachineBasicBlock(MachineBasicBlock &MBB); /// This function checks if it is valid to move Candidate to the delay slot /// and returns true if it isn't. It also updates memory and register /// dependence information. bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, - MemDefsUses &MemDU) const; - - bool findDelayInstr(MachineBasicBlock &MBB, Iter slot, Iter &Filler) const; + InspectMemInstr &IM) const; + + /// This function searches range [Begin, End) for an instruction that can be + /// moved to the delay slot. Returns true on success. + template + bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, + RegDefsUses &RegDU, InspectMemInstr &IM, + IterTy &Filler) const; + + /// This function searches in the backward direction for an instruction that + /// can be moved to the delay slot. Returns true on success. + bool searchBackward(MachineBasicBlock &MBB, Iter Slot) const; + + /// This function searches MBB in the forward direction for an instruction + /// that can be moved to the delay slot. Returns true on success. + bool searchForward(MachineBasicBlock &MBB, Iter Slot) const; + + /// This function searches one of MBB's successor blocks for an instruction + /// that can be moved to the delay slot and inserts clones of the + /// instruction into the successor's predecessor blocks. + bool searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const; + + /// Pick a successor block of MBB. Return NULL if MBB doesn't have a + /// successor block that is not a landing pad. + MachineBasicBlock *selectSuccBB(MachineBasicBlock &B) const; + + /// This function analyzes MBB and returns an instruction with an unoccupied + /// slot that branches to Dst. + std::pair + getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const; + + /// Examine Pred and see if it is possible to insert an instruction into + /// one of its branches delay slot or its end. + bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ, + RegDefsUses &RegDU, bool &HasMultipleSuccs, + BB2BrMap &BrMap) const; bool terminateSearch(const MachineInstr &Candidate) const; TargetMachine &TM; - const TargetInstrInfo *TII; static char ID; }; char Filler::ID = 0; } // end of anonymous namespace +static bool hasUnoccupiedSlot(const MachineInstr *MI) { + return MI->hasDelaySlot() && !MI->isBundledWithSucc(); +} + +/// This function inserts clones of Filler into predecessor blocks. +static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) { + MachineFunction *MF = Filler->getParent()->getParent(); + + for (BB2BrMap::const_iterator I = BrMap.begin(); I != BrMap.end(); ++I) { + if (I->second) { + MIBundleBuilder(I->second).append(MF->CloneMachineInstr(&*Filler)); + ++UsefulSlots; + } else { + I->first->insert(I->first->end(), MF->CloneMachineInstr(&*Filler)); + } + } +} + +/// This function adds registers Filler defines to MBB's live-in register list. +static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) { + for (unsigned I = 0, E = Filler->getNumOperands(); I != E; ++I) { + const MachineOperand &MO = Filler->getOperand(I); + unsigned R; + + if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg())) + continue; + +#ifndef NDEBUG + const MachineFunction &MF = *MBB.getParent(); + assert(MF.getTarget() + .getSubtargetImpl() + ->getRegisterInfo() + ->getAllocatableSet(MF) + .test(R) && + "Shouldn't move an instruction with unallocatable registers across " + "basic block boundaries."); +#endif + + if (!MBB.isLiveIn(R)) + MBB.addLiveIn(R); + } +} + RegDefsUses::RegDefsUses(TargetMachine &TM) - : TRI(*TM.getRegisterInfo()), Defs(TRI.getNumRegs(), false), - Uses(TRI.getNumRegs(), false) {} + : TRI(*TM.getSubtargetImpl()->getRegisterInfo()), + Defs(TRI.getNumRegs(), false), Uses(TRI.getNumRegs(), false) {} void RegDefsUses::init(const MachineInstr &MI) { // Add all register operands which are explicit and non-variadic. @@ -162,6 +310,45 @@ void RegDefsUses::init(const MachineInstr &MI) { } } +void RegDefsUses::setCallerSaved(const MachineInstr &MI) { + assert(MI.isCall()); + + // If MI is a call, add all caller-saved registers to Defs. + BitVector CallerSavedRegs(TRI.getNumRegs(), true); + + CallerSavedRegs.reset(Mips::ZERO); + CallerSavedRegs.reset(Mips::ZERO_64); + + for (const MCPhysReg *R = TRI.getCalleeSavedRegs(); *R; ++R) + for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI) + CallerSavedRegs.reset(*AI); + + Defs |= CallerSavedRegs; +} + +void RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) { + BitVector AllocSet = TRI.getAllocatableSet(MF); + + for (int R = AllocSet.find_first(); R != -1; R = AllocSet.find_next(R)) + for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI) + AllocSet.set(*AI); + + AllocSet.set(Mips::ZERO); + AllocSet.set(Mips::ZERO_64); + + Defs |= AllocSet.flip(); +} + +void RegDefsUses::addLiveOut(const MachineBasicBlock &MBB, + const MachineBasicBlock &SuccBB) { + for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), + SE = MBB.succ_end(); SI != SE; ++SI) + if (*SI != &SuccBB) + for (MachineBasicBlock::livein_iterator LI = (*SI)->livein_begin(), + LE = (*SI)->livein_end(); LI != LE; ++LI) + Uses.set(*LI); +} + bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) { BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs()); bool HasHazard = false; @@ -200,19 +387,15 @@ bool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const { return false; } -MemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_) - : MFI(MFI_), SeenLoad(false), SeenStore(false), SeenNoObjLoad(false), - SeenNoObjStore(false), ForbidMemInstr(false) {} - -bool MemDefsUses::hasHazard(const MachineInstr &MI) { +bool InspectMemInstr::hasHazard(const MachineInstr &MI) { if (!MI.mayStore() && !MI.mayLoad()) return false; if (ForbidMemInstr) return true; - bool OrigSeenLoad = SeenLoad, OrigSeenStore = SeenStore; - + OrigSeenLoad = SeenLoad; + OrigSeenStore = SeenStore; SeenLoad |= MI.mayLoad(); SeenStore |= MI.mayStore(); @@ -223,12 +406,37 @@ bool MemDefsUses::hasHazard(const MachineInstr &MI) { return true; } + return hasHazard_(MI); +} + +bool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) { + if (MI.mayStore()) + return true; + + if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getPseudoValue()) + return true; + + if (const PseudoSourceValue *PSV = + (*MI.memoperands_begin())->getPseudoValue()) { + if (isa(PSV)) + return false; + return !PSV->isConstant(nullptr) && PSV != PseudoSourceValue::getStack(); + } + + return true; +} + +MemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_) + : InspectMemInstr(false), MFI(MFI_), SeenNoObjLoad(false), + SeenNoObjStore(false) {} + +bool MemDefsUses::hasHazard_(const MachineInstr &MI) { bool HasHazard = false; - SmallVector Objs; + SmallVector Objs; // Check underlying object list. if (getUnderlyingObjects(MI, Objs)) { - for (SmallVector::const_iterator I = Objs.begin(); + for (SmallVectorImpl::const_iterator I = Objs.begin(); I != Objs.end(); ++I) HasHazard |= updateDefsUses(*I, MI.mayStore()); @@ -245,7 +453,7 @@ bool MemDefsUses::hasHazard(const MachineInstr &MI) { return HasHazard; } -bool MemDefsUses::updateDefsUses(const Value *V, bool MayStore) { +bool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) { if (MayStore) return !Defs.insert(V) || Uses.count(V) || SeenNoObjStore || SeenNoObjLoad; @@ -255,21 +463,28 @@ bool MemDefsUses::updateDefsUses(const Value *V, bool MayStore) { bool MemDefsUses:: getUnderlyingObjects(const MachineInstr &MI, - SmallVectorImpl &Objects) const { - if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getValue()) + SmallVectorImpl &Objects) const { + if (!MI.hasOneMemOperand() || + (!(*MI.memoperands_begin())->getValue() && + !(*MI.memoperands_begin())->getPseudoValue())) return false; + if (const PseudoSourceValue *PSV = + (*MI.memoperands_begin())->getPseudoValue()) { + if (!PSV->isAliased(MFI)) + return false; + Objects.push_back(PSV); + return true; + } + const Value *V = (*MI.memoperands_begin())->getValue(); SmallVector Objs; GetUnderlyingObjects(const_cast(V), Objs); - for (SmallVector::iterator I = Objs.begin(), E = Objs.end(); + for (SmallVectorImpl::iterator I = Objs.begin(), E = Objs.end(); I != E; ++I) { - if (const PseudoSourceValue *PSV = dyn_cast(*I)) { - if (PSV->isAliased(MFI)) - return false; - } else if (!isIdentifiedObject(V)) + if (!isIdentifiedObject(V)) return false; Objects.push_back(*I); @@ -284,23 +499,30 @@ bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { bool Changed = false; for (Iter I = MBB.begin(); I != MBB.end(); ++I) { - if (!I->hasDelaySlot()) + if (!hasUnoccupiedSlot(&*I)) continue; ++FilledSlots; Changed = true; - Iter D; // Delay slot filling is disabled at -O0. - if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None) && - findDelayInstr(MBB, I, D)) { - MBB.splice(llvm::next(I), &MBB, D); - ++UsefulSlots; - } else - BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); + if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None)) { + if (searchBackward(MBB, I)) + continue; + + if (I->isTerminator()) { + if (searchSuccBBs(MBB, I)) + continue; + } else if (searchForward(MBB, I)) { + continue; + } + } - // Bundle the delay slot filler to the instruction with the delay slot. - MIBundleBuilder(MBB, I, llvm::next(llvm::next(I))); + // Bundle the NOP to the instruction with the delay slot. + const MipsInstrInfo *TII = static_cast( + TM.getSubtargetImpl()->getInstrInfo()); + BuildMI(MBB, std::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); + MIBundleBuilder(MBB, I, std::next(I, 2)); } return Changed; @@ -312,14 +534,11 @@ FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { return new Filler(tm); } -bool Filler::findDelayInstr(MachineBasicBlock &MBB, Iter Slot, - Iter &Filler) const { - RegDefsUses RegDU(TM); - MemDefsUses MemDU(MBB.getParent()->getFrameInfo()); - - RegDU.init(*Slot); - - for (ReverseIter I(Slot); I != MBB.rend(); ++I) { +template +bool Filler::searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, + RegDefsUses &RegDU, InspectMemInstr& IM, + IterTy &Filler) const { + for (IterTy I = Begin; I != End; ++I) { // skip debug value if (I->isDebugValue()) continue; @@ -330,21 +549,188 @@ bool Filler::findDelayInstr(MachineBasicBlock &MBB, Iter Slot, assert((!I->isCall() && !I->isReturn() && !I->isBranch()) && "Cannot put calls, returns or branches in delay slot."); - if (delayHasHazard(*I, RegDU, MemDU)) + if (delayHasHazard(*I, RegDU, IM)) continue; - Filler = llvm::next(I).base(); + if (TM.getSubtarget().isTargetNaCl()) { + // In NaCl, instructions that must be masked are forbidden in delay slots. + // We only check for loads, stores and SP changes. Calls, returns and + // branches are not checked because non-NaCl targets never put them in + // delay slots. + unsigned AddrIdx; + if ((isBasePlusOffsetMemoryAccess(I->getOpcode(), &AddrIdx) && + baseRegNeedsLoadStoreMask(I->getOperand(AddrIdx).getReg())) || + I->modifiesRegister(Mips::SP, + TM.getSubtargetImpl()->getRegisterInfo())) + continue; + } + + Filler = I; return true; } return false; } +bool Filler::searchBackward(MachineBasicBlock &MBB, Iter Slot) const { + if (DisableBackwardSearch) + return false; + + RegDefsUses RegDU(TM); + MemDefsUses MemDU(MBB.getParent()->getFrameInfo()); + ReverseIter Filler; + + RegDU.init(*Slot); + + if (!searchRange(MBB, ReverseIter(Slot), MBB.rend(), RegDU, MemDU, Filler)) + return false; + + MBB.splice(std::next(Slot), &MBB, std::next(Filler).base()); + MIBundleBuilder(MBB, Slot, std::next(Slot, 2)); + ++UsefulSlots; + return true; +} + +bool Filler::searchForward(MachineBasicBlock &MBB, Iter Slot) const { + // Can handle only calls. + if (DisableForwardSearch || !Slot->isCall()) + return false; + + RegDefsUses RegDU(TM); + NoMemInstr NM; + Iter Filler; + + RegDU.setCallerSaved(*Slot); + + if (!searchRange(MBB, std::next(Slot), MBB.end(), RegDU, NM, Filler)) + return false; + + MBB.splice(std::next(Slot), &MBB, Filler); + MIBundleBuilder(MBB, Slot, std::next(Slot, 2)); + ++UsefulSlots; + return true; +} + +bool Filler::searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const { + if (DisableSuccBBSearch) + return false; + + MachineBasicBlock *SuccBB = selectSuccBB(MBB); + + if (!SuccBB) + return false; + + RegDefsUses RegDU(TM); + bool HasMultipleSuccs = false; + BB2BrMap BrMap; + std::unique_ptr IM; + Iter Filler; + + // Iterate over SuccBB's predecessor list. + for (MachineBasicBlock::pred_iterator PI = SuccBB->pred_begin(), + PE = SuccBB->pred_end(); PI != PE; ++PI) + if (!examinePred(**PI, *SuccBB, RegDU, HasMultipleSuccs, BrMap)) + return false; + + // Do not allow moving instructions which have unallocatable register operands + // across basic block boundaries. + RegDU.setUnallocatableRegs(*MBB.getParent()); + + // Only allow moving loads from stack or constants if any of the SuccBB's + // predecessors have multiple successors. + if (HasMultipleSuccs) { + IM.reset(new LoadFromStackOrConst()); + } else { + const MachineFrameInfo *MFI = MBB.getParent()->getFrameInfo(); + IM.reset(new MemDefsUses(MFI)); + } + + if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Filler)) + return false; + + insertDelayFiller(Filler, BrMap); + addLiveInRegs(Filler, *SuccBB); + Filler->eraseFromParent(); + + return true; +} + +MachineBasicBlock *Filler::selectSuccBB(MachineBasicBlock &B) const { + if (B.succ_empty()) + return nullptr; + + // Select the successor with the larget edge weight. + auto &Prob = getAnalysis(); + MachineBasicBlock *S = *std::max_element(B.succ_begin(), B.succ_end(), + [&](const MachineBasicBlock *Dst0, + const MachineBasicBlock *Dst1) { + return Prob.getEdgeWeight(&B, Dst0) < Prob.getEdgeWeight(&B, Dst1); + }); + return S->isLandingPad() ? nullptr : S; +} + +std::pair +Filler::getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const { + const MipsInstrInfo *TII = + static_cast(TM.getSubtargetImpl()->getInstrInfo()); + MachineBasicBlock *TrueBB = nullptr, *FalseBB = nullptr; + SmallVector BranchInstrs; + SmallVector Cond; + + MipsInstrInfo::BranchType R = + TII->AnalyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs); + + if ((R == MipsInstrInfo::BT_None) || (R == MipsInstrInfo::BT_NoBranch)) + return std::make_pair(R, nullptr); + + if (R != MipsInstrInfo::BT_CondUncond) { + if (!hasUnoccupiedSlot(BranchInstrs[0])) + return std::make_pair(MipsInstrInfo::BT_None, nullptr); + + assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst))); + + return std::make_pair(R, BranchInstrs[0]); + } + + assert((TrueBB == &Dst) || (FalseBB == &Dst)); + + // Examine the conditional branch. See if its slot is occupied. + if (hasUnoccupiedSlot(BranchInstrs[0])) + return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]); + + // If that fails, try the unconditional branch. + if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst)) + return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]); + + return std::make_pair(MipsInstrInfo::BT_None, nullptr); +} + +bool Filler::examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ, + RegDefsUses &RegDU, bool &HasMultipleSuccs, + BB2BrMap &BrMap) const { + std::pair P = + getBranch(Pred, Succ); + + // Return if either getBranch wasn't able to analyze the branches or there + // were no branches with unoccupied slots. + if (P.first == MipsInstrInfo::BT_None) + return false; + + if ((P.first != MipsInstrInfo::BT_Uncond) && + (P.first != MipsInstrInfo::BT_NoBranch)) { + HasMultipleSuccs = true; + RegDU.addLiveOut(Pred, Succ); + } + + BrMap[&Pred] = P.second; + return true; +} + bool Filler::delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, - MemDefsUses &MemDU) const { + InspectMemInstr &IM) const { bool HasHazard = (Candidate.isImplicitDef() || Candidate.isKill()); - HasHazard |= MemDU.hasHazard(Candidate); + HasHazard |= IM.hasHazard(Candidate); HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands()); return HasHazard; @@ -352,6 +738,6 @@ bool Filler::delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, bool Filler::terminateSearch(const MachineInstr &Candidate) const { return (Candidate.isTerminator() || Candidate.isCall() || - Candidate.isLabel() || Candidate.isInlineAsm() || + Candidate.isPosition() || Candidate.isInlineAsm() || Candidate.hasUnmodeledSideEffects()); }