190db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka//===-- MipsDelaySlotFiller.cpp - Mips Delay Slot Filler ------------------===// 29684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes// 39684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes// The LLVM Compiler Infrastructure 49684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 79684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes// 84552c9a3b34ad9b2085635266348d0d9b95514a6Akira Hatanaka//===----------------------------------------------------------------------===// 99684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes// 1090db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka// Simple pass to fill delay slots with useful instructions. 119684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes// 124552c9a3b34ad9b2085635266348d0d9b95514a6Akira Hatanaka//===----------------------------------------------------------------------===// 139684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 149684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes#define DEBUG_TYPE "delay-slot-filler" 159684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 169684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes#include "Mips.h" 171f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka#include "MipsInstrInfo.h" 189684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes#include "MipsTargetMachine.h" 19cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka#include "llvm/ADT/BitVector.h" 20a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka#include "llvm/ADT/SmallPtrSet.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 22a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka#include "llvm/Analysis/AliasAnalysis.h" 23a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka#include "llvm/Analysis/ValueTracking.h" 241f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 259684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes#include "llvm/CodeGen/MachineFunctionPass.h" 269684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes#include "llvm/CodeGen/MachineInstrBuilder.h" 27a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka#include "llvm/CodeGen/PseudoSourceValue.h" 28a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka#include "llvm/Support/CommandLine.h" 299684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes#include "llvm/Target/TargetInstrInfo.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 31a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka#include "llvm/Target/TargetRegisterInfo.h" 329684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 339684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopesusing namespace llvm; 349684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 359684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso LopesSTATISTIC(FilledSlots, "Number of delay slots filled"); 3698f4d4d2db66375bedb461a9f6f9092a3c6703b2Akira HatanakaSTATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 37176965f46b9f4ca7c83746355853601c05488564Akira Hatanaka " are not NOP."); 389684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 396522a9e04bcfa447299f4fd10ee9afffd5834a47Akira Hatanakastatic cl::opt<bool> DisableDelaySlotFiller( 406522a9e04bcfa447299f4fd10ee9afffd5834a47Akira Hatanaka "disable-mips-delay-filler", 41a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka cl::init(false), 4290db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka cl::desc("Fill all delay slots with NOPs."), 43a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka cl::Hidden); 44a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 45e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanakastatic cl::opt<bool> DisableForwardSearch( 46e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka "disable-mips-df-forward-search", 47e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka cl::init(true), 48e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka cl::desc("Disallow MIPS delay filler to search forward."), 49e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka cl::Hidden); 50e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 51b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanakastatic cl::opt<bool> DisableSuccBBSearch( 52b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanaka "disable-mips-df-succbb-search", 53b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanaka cl::init(true), 54b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanaka cl::desc("Disallow MIPS delay filler to search successor basic blocks."), 55b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanaka cl::Hidden); 56b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanaka 57b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanakastatic cl::opt<bool> DisableBackwardSearch( 58b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanaka "disable-mips-df-backward-search", 59b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanaka cl::init(false), 60b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanaka cl::desc("Disallow MIPS delay filler to search backward."), 61b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanaka cl::Hidden); 62b8bc8cc3b0e0d2811b3326d49835e8a1edb1ef61Akira Hatanaka 639684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopesnamespace { 641f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka typedef MachineBasicBlock::iterator Iter; 651f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka typedef MachineBasicBlock::reverse_iterator ReverseIter; 661f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka typedef SmallDenseMap<MachineBasicBlock*, MachineInstr*, 2> BB2BrMap; 671f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 681f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// \brief A functor comparing edge weight of two blocks. 691f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka struct CmpWeight { 701f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka CmpWeight(const MachineBasicBlock &S, 711f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka const MachineBranchProbabilityInfo &P) : Src(S), Prob(P) {} 721f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 731f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka bool operator()(const MachineBasicBlock *Dst0, 741f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka const MachineBasicBlock *Dst1) const { 751f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return Prob.getEdgeWeight(&Src, Dst0) < Prob.getEdgeWeight(&Src, Dst1); 761f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } 771f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 781f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka const MachineBasicBlock &Src; 791f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka const MachineBranchProbabilityInfo &Prob; 801f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka }; 811f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 8270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka class RegDefsUses { 8370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka public: 8470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka RegDefsUses(TargetMachine &TM); 8570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka void init(const MachineInstr &MI); 86e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 87e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka /// This function sets all caller-saved registers in Defs. 88e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka void setCallerSaved(const MachineInstr &MI); 89e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 901f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// This function sets all unallocatable registers in Defs. 911f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka void setUnallocatableRegs(const MachineFunction &MF); 921f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 931f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// Set bits in Uses corresponding to MBB's live-out registers except for 941f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// the registers that are live-in to SuccBB. 951f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka void addLiveOut(const MachineBasicBlock &MBB, 961f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka const MachineBasicBlock &SuccBB); 971f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 9870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool update(const MachineInstr &MI, unsigned Begin, unsigned End); 9970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 10070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka private: 10170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg, 10270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool IsDef) const; 10370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 10470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka /// Returns true if Reg or its alias is in RegSet. 10570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool isRegInSet(const BitVector &RegSet, unsigned Reg) const; 10670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 10770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka const TargetRegisterInfo &TRI; 10870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka BitVector Defs, Uses; 10970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka }; 11070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 111e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka /// Base class for inspecting loads and stores. 112e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka class InspectMemInstr { 113e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka public: 1141f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka InspectMemInstr(bool ForbidMemInstr_) 1151f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka : OrigSeenLoad(false), OrigSeenStore(false), SeenLoad(false), 1161f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka SeenStore(false), ForbidMemInstr(ForbidMemInstr_) {} 1171f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 1181f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// Return true if MI cannot be moved to delay slot. 1191f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka bool hasHazard(const MachineInstr &MI); 1201f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 121e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka virtual ~InspectMemInstr() {} 1221f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 1231f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka protected: 1241f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// Flags indicating whether loads or stores have been seen. 1251f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka bool OrigSeenLoad, OrigSeenStore, SeenLoad, SeenStore; 1261f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 1271f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// Memory instructions are not allowed to move to delay slot if this flag 1281f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// is true. 1291f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka bool ForbidMemInstr; 1301f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 1311f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka private: 1321f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka virtual bool hasHazard_(const MachineInstr &MI) = 0; 133e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka }; 134e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 135e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka /// This subclass rejects any memory instructions. 136e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka class NoMemInstr : public InspectMemInstr { 137e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka public: 1381f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka NoMemInstr() : InspectMemInstr(true) {} 1391f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka private: 1401f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka virtual bool hasHazard_(const MachineInstr &MI) { return true; } 1411f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka }; 1421f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 1431f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// This subclass accepts loads from stacks and constant loads. 1441f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka class LoadFromStackOrConst : public InspectMemInstr { 1451f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka public: 1461f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka LoadFromStackOrConst() : InspectMemInstr(false) {} 1471f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka private: 1481f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka virtual bool hasHazard_(const MachineInstr &MI); 149e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka }; 150e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 151e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka /// This subclass uses memory dependence information to determine whether a 152e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka /// memory instruction can be moved to a delay slot. 153e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka class MemDefsUses : public InspectMemInstr { 154a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka public: 155a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka MemDefsUses(const MachineFrameInfo *MFI); 156a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 157a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka private: 1581f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka virtual bool hasHazard_(const MachineInstr &MI); 1591f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 160a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka /// Update Defs and Uses. Return true if there exist dependences that 161aa49f35240554a78318fe15f375632a66ece5e1fAkira Hatanaka /// disqualify the delay slot candidate between V and values in Uses and 162aa49f35240554a78318fe15f375632a66ece5e1fAkira Hatanaka /// Defs. 163a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka bool updateDefsUses(const Value *V, bool MayStore); 164a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 165a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka /// Get the list of underlying objects of MI's memory operand. 166a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka bool getUnderlyingObjects(const MachineInstr &MI, 167a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka SmallVectorImpl<const Value *> &Objects) const; 168a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 169a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka const MachineFrameInfo *MFI; 170a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka SmallPtrSet<const Value*, 4> Uses, Defs; 171a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 172a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka /// Flags indicating whether loads or stores with no underlying objects have 173a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka /// been seen. 174a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka bool SeenNoObjLoad, SeenNoObjStore; 175a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka }; 176a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 1775dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka class Filler : public MachineFunctionPass { 1785dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka public: 17990c595425bdc47563714d6ed13f6e9151552ceaeBruno Cardoso Lopes Filler(TargetMachine &tm) 18041e632d9e1a55d36cb08b0551ad82a13d9137a5eBill Wendling : MachineFunctionPass(ID), TM(tm) { } 1819684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 1829684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes virtual const char *getPassName() const { 1839684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes return "Mips Delay Slot Filler"; 1849684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes } 1859684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 1869684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes bool runOnMachineFunction(MachineFunction &F) { 1879684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes bool Changed = false; 1889684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 1899684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes FI != FE; ++FI) 1909684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes Changed |= runOnMachineBasicBlock(*FI); 1919684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes return Changed; 1929684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes } 1939684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 1941f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka void getAnalysisUsage(AnalysisUsage &AU) const { 1951f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka AU.addRequired<MachineBranchProbabilityInfo>(); 1961f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka MachineFunctionPass::getAnalysisUsage(AU); 1971f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } 1985dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka 1991f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka private: 2005dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 2015dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka 202cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka /// This function checks if it is valid to move Candidate to the delay slot 203a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka /// and returns true if it isn't. It also updates memory and register 204a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka /// dependence information. 205a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka bool delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, 206e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka InspectMemInstr &IM) const; 207a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 2081f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka /// This function searches range [Begin, End) for an instruction that can be 2091f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka /// moved to the delay slot. Returns true on success. 2101f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka template<typename IterTy> 2111f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka bool searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, 212aa49f35240554a78318fe15f375632a66ece5e1fAkira Hatanaka RegDefsUses &RegDU, InspectMemInstr &IM, 213aa49f35240554a78318fe15f375632a66ece5e1fAkira Hatanaka IterTy &Filler) const; 2141f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka 215e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka /// This function searches in the backward direction for an instruction that 216e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka /// can be moved to the delay slot. Returns true on success. 217e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka bool searchBackward(MachineBasicBlock &MBB, Iter Slot) const; 218e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 219e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka /// This function searches MBB in the forward direction for an instruction 220e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka /// that can be moved to the delay slot. Returns true on success. 221e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka bool searchForward(MachineBasicBlock &MBB, Iter Slot) const; 222eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka 2230c8f21afbd31e796c18a6a59b9f1039a71145c96Akira Hatanaka /// This function searches one of MBB's successor blocks for an instruction 2240c8f21afbd31e796c18a6a59b9f1039a71145c96Akira Hatanaka /// that can be moved to the delay slot and inserts clones of the 2250c8f21afbd31e796c18a6a59b9f1039a71145c96Akira Hatanaka /// instruction into the successor's predecessor blocks. 2261f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka bool searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const; 2271f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 228aa49f35240554a78318fe15f375632a66ece5e1fAkira Hatanaka /// Pick a successor block of MBB. Return NULL if MBB doesn't have a 229aa49f35240554a78318fe15f375632a66ece5e1fAkira Hatanaka /// successor block that is not a landing pad. 2301f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka MachineBasicBlock *selectSuccBB(MachineBasicBlock &B) const; 2311f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 2321f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// This function analyzes MBB and returns an instruction with an unoccupied 2331f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// slot that branches to Dst. 2341f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka std::pair<MipsInstrInfo::BranchType, MachineInstr *> 2351f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const; 2361f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 2371f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// Examine Pred and see if it is possible to insert an instruction into 2381f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka /// one of its branches delay slot or its end. 2391f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka bool examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ, 2401f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka RegDefsUses &RegDU, bool &HasMultipleSuccs, 2411f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka BB2BrMap &BrMap) const; 2421f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 243eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka bool terminateSearch(const MachineInstr &Candidate) const; 244a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 2455dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka TargetMachine &TM; 246a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 2475dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka static char ID; 2489684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes }; 2499684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes char Filler::ID = 0; 2509684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes} // end of anonymous namespace 2519684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 2521f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanakastatic bool hasUnoccupiedSlot(const MachineInstr *MI) { 2531f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return MI->hasDelaySlot() && !MI->isBundledWithSucc(); 2541f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka} 2551f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 2561f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka/// This function inserts clones of Filler into predecessor blocks. 2571f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanakastatic void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) { 2581f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka MachineFunction *MF = Filler->getParent()->getParent(); 2591f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 2601f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka for (BB2BrMap::const_iterator I = BrMap.begin(); I != BrMap.end(); ++I) { 2611f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (I->second) { 2621f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka MIBundleBuilder(I->second).append(MF->CloneMachineInstr(&*Filler)); 2631f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka ++UsefulSlots; 2641f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } else { 2651f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka I->first->insert(I->first->end(), MF->CloneMachineInstr(&*Filler)); 2661f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } 2671f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } 2681f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka} 2691f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 2701f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka/// This function adds registers Filler defines to MBB's live-in register list. 2711f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanakastatic void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) { 2721f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka for (unsigned I = 0, E = Filler->getNumOperands(); I != E; ++I) { 2731f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka const MachineOperand &MO = Filler->getOperand(I); 2741f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka unsigned R; 2751f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 2761f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (!MO.isReg() || !MO.isDef() || !(R = MO.getReg())) 2771f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka continue; 2781f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 2791f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka#ifndef NDEBUG 2801f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka const MachineFunction &MF = *MBB.getParent(); 2811f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka assert(MF.getTarget().getRegisterInfo()->getAllocatableSet(MF).test(R) && 2821f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka "Shouldn't move an instruction with unallocatable registers across " 2831f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka "basic block boundaries."); 2841f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka#endif 2851f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 2861f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (!MBB.isLiveIn(R)) 2871f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka MBB.addLiveIn(R); 2881f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } 2891f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka} 2901f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 29170cdcd5114b30c4983ff158278422ea129bd27bbAkira HatanakaRegDefsUses::RegDefsUses(TargetMachine &TM) 29270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka : TRI(*TM.getRegisterInfo()), Defs(TRI.getNumRegs(), false), 29370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka Uses(TRI.getNumRegs(), false) {} 29470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 29570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanakavoid RegDefsUses::init(const MachineInstr &MI) { 29670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // Add all register operands which are explicit and non-variadic. 29770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka update(MI, 0, MI.getDesc().getNumOperands()); 29870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 29970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // If MI is a call, add RA to Defs to prevent users of RA from going into 30070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // delay slot. 30170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka if (MI.isCall()) 30270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka Defs.set(Mips::RA); 30370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 30470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // Add all implicit register operands of branch instructions except 30570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // register AT. 30670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka if (MI.isBranch()) { 30770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands()); 30870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka Defs.reset(Mips::AT); 30970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka } 31070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka} 31170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 312e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanakavoid RegDefsUses::setCallerSaved(const MachineInstr &MI) { 313e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka assert(MI.isCall()); 314e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 315e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka // If MI is a call, add all caller-saved registers to Defs. 316e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka BitVector CallerSavedRegs(TRI.getNumRegs(), true); 317e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 318e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka CallerSavedRegs.reset(Mips::ZERO); 319e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka CallerSavedRegs.reset(Mips::ZERO_64); 320e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 321e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka for (const MCPhysReg *R = TRI.getCalleeSavedRegs(); *R; ++R) 322e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI) 323e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka CallerSavedRegs.reset(*AI); 324e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 325e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka Defs |= CallerSavedRegs; 326e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka} 327e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 3281f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanakavoid RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) { 3291f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka BitVector AllocSet = TRI.getAllocatableSet(MF); 3301f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 3311f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka for (int R = AllocSet.find_first(); R != -1; R = AllocSet.find_next(R)) 3321f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI) 3331f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka AllocSet.set(*AI); 3341f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 3351f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka AllocSet.set(Mips::ZERO); 3361f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka AllocSet.set(Mips::ZERO_64); 3371f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 3381f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka Defs |= AllocSet.flip(); 3391f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka} 3401f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 3411f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanakavoid RegDefsUses::addLiveOut(const MachineBasicBlock &MBB, 3421f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka const MachineBasicBlock &SuccBB) { 3431f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 3441f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka SE = MBB.succ_end(); SI != SE; ++SI) 3451f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (*SI != &SuccBB) 3461f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka for (MachineBasicBlock::livein_iterator LI = (*SI)->livein_begin(), 3471f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka LE = (*SI)->livein_end(); LI != LE; ++LI) 3481f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka Uses.set(*LI); 3491f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka} 3501f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 35170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanakabool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) { 35270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs()); 35370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool HasHazard = false; 35470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 35570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka for (unsigned I = Begin; I != End; ++I) { 35670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka const MachineOperand &MO = MI.getOperand(I); 35770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 35870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka if (MO.isReg() && MO.getReg()) 35970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka HasHazard |= checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef()); 36070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka } 36170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 36270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka Defs |= NewDefs; 36370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka Uses |= NewUses; 36470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 36570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka return HasHazard; 36670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka} 36770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 36870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanakabool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, 36970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka unsigned Reg, bool IsDef) const { 37070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka if (IsDef) { 37170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka NewDefs.set(Reg); 37270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // check whether Reg has already been defined or used. 37370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg)); 37470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka } 37570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 37670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka NewUses.set(Reg); 37770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // check whether Reg has already been defined. 37870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka return isRegInSet(Defs, Reg); 37970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka} 38070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 38170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanakabool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const { 38270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // Check Reg and all aliased Registers. 38370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI) 38470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka if (RegSet.test(*AI)) 38570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka return true; 38670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka return false; 38770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka} 38870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 3891f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanakabool InspectMemInstr::hasHazard(const MachineInstr &MI) { 390a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka if (!MI.mayStore() && !MI.mayLoad()) 391a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka return false; 392a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 393a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka if (ForbidMemInstr) 394a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka return true; 395a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 3961f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka OrigSeenLoad = SeenLoad; 3971f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka OrigSeenStore = SeenStore; 398a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka SeenLoad |= MI.mayLoad(); 399a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka SeenStore |= MI.mayStore(); 400a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 401a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka // If MI is an ordered or volatile memory reference, disallow moving 402a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka // subsequent loads and stores to delay slot. 403a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka if (MI.hasOrderedMemoryRef() && (OrigSeenLoad || OrigSeenStore)) { 404a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka ForbidMemInstr = true; 405a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka return true; 406a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka } 407a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 4081f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return hasHazard_(MI); 4091f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka} 4101f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 4111f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanakabool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) { 4121f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (MI.mayStore()) 4131f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return true; 4141f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 4151f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getValue()) 4161f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return true; 4171f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 4181f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka const Value *V = (*MI.memoperands_begin())->getValue(); 4191f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 4201f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (isa<FixedStackPseudoSourceValue>(V)) 4211f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return false; 4221f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 4231f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (const PseudoSourceValue *PSV = dyn_cast<const PseudoSourceValue>(V)) 4241f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return !PSV->PseudoSourceValue::isConstant(0) && 4251f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka (V != PseudoSourceValue::getStack()); 4261f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 4271f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return true; 4281f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka} 4291f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 4301f0aca857b899b397a9d82bb21cb1ca819419a90Akira HatanakaMemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_) 4311f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka : InspectMemInstr(false), MFI(MFI_), SeenNoObjLoad(false), 4321f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka SeenNoObjStore(false) {} 4331f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 4341f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanakabool MemDefsUses::hasHazard_(const MachineInstr &MI) { 435a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka bool HasHazard = false; 436a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka SmallVector<const Value *, 4> Objs; 437a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 438a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka // Check underlying object list. 439a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka if (getUnderlyingObjects(MI, Objs)) { 440365ef0b197d7c841f8e501da64296df65be4ca23Craig Topper for (SmallVectorImpl<const Value *>::const_iterator I = Objs.begin(); 441a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka I != Objs.end(); ++I) 442a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka HasHazard |= updateDefsUses(*I, MI.mayStore()); 443a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 444a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka return HasHazard; 445a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka } 446a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 447a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka // No underlying objects found. 448a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka HasHazard = MI.mayStore() && (OrigSeenLoad || OrigSeenStore); 449a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka HasHazard |= MI.mayLoad() || OrigSeenStore; 450a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 451a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka SeenNoObjLoad |= MI.mayLoad(); 452a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka SeenNoObjStore |= MI.mayStore(); 453a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 454a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka return HasHazard; 455a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka} 456a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 457a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanakabool MemDefsUses::updateDefsUses(const Value *V, bool MayStore) { 458a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka if (MayStore) 459a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka return !Defs.insert(V) || Uses.count(V) || SeenNoObjStore || SeenNoObjLoad; 460a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 461a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka Uses.insert(V); 462a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka return Defs.count(V) || SeenNoObjStore; 463a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka} 464a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 465a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanakabool MemDefsUses:: 466a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira HatanakagetUnderlyingObjects(const MachineInstr &MI, 467a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka SmallVectorImpl<const Value *> &Objects) const { 468a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka if (!MI.hasOneMemOperand() || !(*MI.memoperands_begin())->getValue()) 469a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka return false; 470a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 471a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka const Value *V = (*MI.memoperands_begin())->getValue(); 472a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 473a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka SmallVector<Value *, 4> Objs; 474a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka GetUnderlyingObjects(const_cast<Value *>(V), Objs); 475a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 476365ef0b197d7c841f8e501da64296df65be4ca23Craig Topper for (SmallVectorImpl<Value *>::iterator I = Objs.begin(), E = Objs.end(); 477a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka I != E; ++I) { 478a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(*I)) { 479a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka if (PSV->isAliased(MFI)) 480a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka return false; 481a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka } else if (!isIdentifiedObject(V)) 482a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka return false; 483a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 484a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka Objects.push_back(*I); 485a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka } 486a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 487a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka return true; 488a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka} 489a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 4909684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 491a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka/// We assume there is only one delay slot per delayed instruction. 49290db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanakabool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 4939684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes bool Changed = false; 49453120e0a9fde4b3e8057b9d5b9ad8ec50fbaa31dAkira Hatanaka 495eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka for (Iter I = MBB.begin(); I != MBB.end(); ++I) { 4961f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (!hasUnoccupiedSlot(&*I)) 4975dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka continue; 4985dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka 4995dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka ++FilledSlots; 5005dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka Changed = true; 5015dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka 5025dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka // Delay slot filling is disabled at -O0. 5031f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None)) { 5041f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (searchBackward(MBB, I)) 5051f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka continue; 5061f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 5071f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (I->isTerminator()) { 5081f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (searchSuccBBs(MBB, I)) 5091f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka continue; 5101f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } else if (searchForward(MBB, I)) { 5111f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka continue; 5121f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } 5131f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } 514a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 515e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka // Bundle the NOP to the instruction with the delay slot. 51641e632d9e1a55d36cb08b0551ad82a13d9137a5eBill Wendling const MipsInstrInfo *TII = 51741e632d9e1a55d36cb08b0551ad82a13d9137a5eBill Wendling static_cast<const MipsInstrInfo*>(TM.getInstrInfo()); 518e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); 519eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka MIBundleBuilder(MBB, I, llvm::next(llvm::next(I))); 5205dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka } 5215dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka 5225dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka return Changed; 5239684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes} 5249684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 5259684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 5269684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes/// slots in Mips MachineFunctions 5279684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso LopesFunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 5289684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes return new Filler(tm); 5299684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes} 5309684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 5311f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanakatemplate<typename IterTy> 5321f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanakabool Filler::searchRange(MachineBasicBlock &MBB, IterTy Begin, IterTy End, 533e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka RegDefsUses &RegDU, InspectMemInstr& IM, 5341f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka IterTy &Filler) const { 5351f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka for (IterTy I = Begin; I != End; ++I) { 536a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka // skip debug value 537a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka if (I->isDebugValue()) 538a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka continue; 539a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 540eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka if (terminateSearch(*I)) 541a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka break; 542a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 543a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka assert((!I->isCall() && !I->isReturn() && !I->isBranch()) && 544a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka "Cannot put calls, returns or branches in delay slot."); 545a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanaka 546e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka if (delayHasHazard(*I, RegDU, IM)) 547a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka continue; 548a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 5491f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka Filler = I; 5501f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka return true; 5511f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka } 5521f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka 5531f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka return false; 5541f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka} 5551f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka 556e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanakabool Filler::searchBackward(MachineBasicBlock &MBB, Iter Slot) const { 5571f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (DisableBackwardSearch) 5581f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return false; 5591f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 5601f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka RegDefsUses RegDU(TM); 5611f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka MemDefsUses MemDU(MBB.getParent()->getFrameInfo()); 562e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka ReverseIter Filler; 5631f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka 5641f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka RegDU.init(*Slot); 5651f7330b16239f50daee57dbf53b20fbacd028ee4Akira Hatanaka 566e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka if (searchRange(MBB, ReverseIter(Slot), MBB.rend(), RegDU, MemDU, Filler)) { 567e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka MBB.splice(llvm::next(Slot), &MBB, llvm::next(Filler).base()); 568e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka MIBundleBuilder(MBB, Slot, llvm::next(llvm::next(Slot))); 569e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka ++UsefulSlots; 570e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka return true; 571e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka } 572e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 573e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka return false; 574e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka} 575e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 576e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanakabool Filler::searchForward(MachineBasicBlock &MBB, Iter Slot) const { 577e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka // Can handle only calls. 5781f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (DisableForwardSearch || !Slot->isCall()) 579e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka return false; 580e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 581e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka RegDefsUses RegDU(TM); 582e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka NoMemInstr NM; 583e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka Iter Filler; 584e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 585e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka RegDU.setCallerSaved(*Slot); 586e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka 587e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka if (searchRange(MBB, llvm::next(Slot), MBB.end(), RegDU, NM, Filler)) { 588e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka MBB.splice(llvm::next(Slot), &MBB, Filler); 589e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka MIBundleBuilder(MBB, Slot, llvm::next(llvm::next(Slot))); 590e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka ++UsefulSlots; 5916f818abbe3dce0bee8257ea7d7dd4cb951f4dc7cAkira Hatanaka return true; 592a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka } 5936f818abbe3dce0bee8257ea7d7dd4cb951f4dc7cAkira Hatanaka 5946f818abbe3dce0bee8257ea7d7dd4cb951f4dc7cAkira Hatanaka return false; 595a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka} 596a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 5971f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanakabool Filler::searchSuccBBs(MachineBasicBlock &MBB, Iter Slot) const { 5981f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (DisableSuccBBSearch) 5991f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return false; 6001f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6011f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka MachineBasicBlock *SuccBB = selectSuccBB(MBB); 6021f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6031f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (!SuccBB) 6041f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return false; 6051f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6061f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka RegDefsUses RegDU(TM); 6071f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka bool HasMultipleSuccs = false; 6081f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka BB2BrMap BrMap; 6091f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka OwningPtr<InspectMemInstr> IM; 6101f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka Iter Filler; 6111f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6121f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka // Iterate over SuccBB's predecessor list. 6131f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka for (MachineBasicBlock::pred_iterator PI = SuccBB->pred_begin(), 6141f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka PE = SuccBB->pred_end(); PI != PE; ++PI) 6151f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (!examinePred(**PI, *SuccBB, RegDU, HasMultipleSuccs, BrMap)) 6161f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return false; 6171f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6181f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka // Do not allow moving instructions which have unallocatable register operands 6191f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka // across basic block boundaries. 6201f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka RegDU.setUnallocatableRegs(*MBB.getParent()); 6211f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6221f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka // Only allow moving loads from stack or constants if any of the SuccBB's 6231f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka // predecessors have multiple successors. 6241f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (HasMultipleSuccs) { 6251f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka IM.reset(new LoadFromStackOrConst()); 6261f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } else { 6271f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka const MachineFrameInfo *MFI = MBB.getParent()->getFrameInfo(); 6281f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka IM.reset(new MemDefsUses(MFI)); 6291f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } 6301f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6311f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (!searchRange(MBB, SuccBB->begin(), SuccBB->end(), RegDU, *IM, Filler)) 6321f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return false; 6331f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6341f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka insertDelayFiller(Filler, BrMap); 6351f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka addLiveInRegs(Filler, *SuccBB); 6361f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka Filler->eraseFromParent(); 6371f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6381f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return true; 6391f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka} 6401f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6411f0aca857b899b397a9d82bb21cb1ca819419a90Akira HatanakaMachineBasicBlock *Filler::selectSuccBB(MachineBasicBlock &B) const { 6421f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (B.succ_empty()) 6431f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return NULL; 6441f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6451f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka // Select the successor with the larget edge weight. 6461f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka CmpWeight Cmp(B, getAnalysis<MachineBranchProbabilityInfo>()); 6471f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka MachineBasicBlock *S = *std::max_element(B.succ_begin(), B.succ_end(), Cmp); 6481f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return S->isLandingPad() ? NULL : S; 6491f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka} 6501f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6511f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanakastd::pair<MipsInstrInfo::BranchType, MachineInstr *> 6521f0aca857b899b397a9d82bb21cb1ca819419a90Akira HatanakaFiller::getBranch(MachineBasicBlock &MBB, const MachineBasicBlock &Dst) const { 6531f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka const MipsInstrInfo *TII = 6541f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka static_cast<const MipsInstrInfo*>(TM.getInstrInfo()); 6551f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka MachineBasicBlock *TrueBB = 0, *FalseBB = 0; 6561f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka SmallVector<MachineInstr*, 2> BranchInstrs; 6571f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka SmallVector<MachineOperand, 2> Cond; 6581f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6591f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka MipsInstrInfo::BranchType R = 6601f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka TII->AnalyzeBranch(MBB, TrueBB, FalseBB, Cond, false, BranchInstrs); 6611f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6621f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if ((R == MipsInstrInfo::BT_None) || (R == MipsInstrInfo::BT_NoBranch)) 6631f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return std::make_pair(R, (MachineInstr*)NULL); 6641f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6651f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (R != MipsInstrInfo::BT_CondUncond) { 6661f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (!hasUnoccupiedSlot(BranchInstrs[0])) 6671f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return std::make_pair(MipsInstrInfo::BT_None, (MachineInstr*)NULL); 6681f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6691f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka assert(((R != MipsInstrInfo::BT_Uncond) || (TrueBB == &Dst))); 6701f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6711f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return std::make_pair(R, BranchInstrs[0]); 6721f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } 6731f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6741f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka assert((TrueBB == &Dst) || (FalseBB == &Dst)); 6751f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6761f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka // Examine the conditional branch. See if its slot is occupied. 6771f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (hasUnoccupiedSlot(BranchInstrs[0])) 6781f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return std::make_pair(MipsInstrInfo::BT_Cond, BranchInstrs[0]); 6791f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6801f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka // If that fails, try the unconditional branch. 6811f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (hasUnoccupiedSlot(BranchInstrs[1]) && (FalseBB == &Dst)) 6821f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return std::make_pair(MipsInstrInfo::BT_Uncond, BranchInstrs[1]); 6831f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6841f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return std::make_pair(MipsInstrInfo::BT_None, (MachineInstr*)NULL); 6851f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka} 6861f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6871f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanakabool Filler::examinePred(MachineBasicBlock &Pred, const MachineBasicBlock &Succ, 6881f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka RegDefsUses &RegDU, bool &HasMultipleSuccs, 6891f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka BB2BrMap &BrMap) const { 6901f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka std::pair<MipsInstrInfo::BranchType, MachineInstr *> P = 6911f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka getBranch(Pred, Succ); 6921f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6931f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka // Return if either getBranch wasn't able to analyze the branches or there 6941f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka // were no branches with unoccupied slots. 6951f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if (P.first == MipsInstrInfo::BT_None) 6961f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return false; 6971f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 6981f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka if ((P.first != MipsInstrInfo::BT_Uncond) && 6991f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka (P.first != MipsInstrInfo::BT_NoBranch)) { 7001f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka HasMultipleSuccs = true; 7011f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka RegDU.addLiveOut(Pred, Succ); 7021f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka } 7031f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 7041f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka BrMap[&Pred] = P.second; 7051f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka return true; 7061f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka} 7071f0aca857b899b397a9d82bb21cb1ca819419a90Akira Hatanaka 708a56f411961c41d8b4f6ffc62c95c5fc95fbac8c8Akira Hatanakabool Filler::delayHasHazard(const MachineInstr &Candidate, RegDefsUses &RegDU, 709e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka InspectMemInstr &IM) const { 710cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka bool HasHazard = (Candidate.isImplicitDef() || Candidate.isKill()); 711a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 712e760675b0ed8d7adcc2c991a2d645d2b538a5ab3Akira Hatanaka HasHazard |= IM.hasHazard(Candidate); 71370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands()); 714a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 715cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka return HasHazard; 716a032dbd62f46a40b2cf759ce0dd0ebd41ef0614cAkira Hatanaka} 717a032dbd62f46a40b2cf759ce0dd0ebd41ef0614cAkira Hatanaka 718eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanakabool Filler::terminateSearch(const MachineInstr &Candidate) const { 719eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka return (Candidate.isTerminator() || Candidate.isCall() || 720eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka Candidate.isLabel() || Candidate.isInlineAsm() || 721eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka Candidate.hasUnmodeledSideEffects()); 722eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka} 723