MipsDelaySlotFiller.cpp revision 70cdcd5114b30c4983ff158278422ea129bd27bb
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" 179684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes#include "MipsTargetMachine.h" 18cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka#include "llvm/ADT/BitVector.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 209684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes#include "llvm/CodeGen/MachineFunctionPass.h" 219684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes#include "llvm/CodeGen/MachineInstrBuilder.h" 22a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka#include "llvm/Support/CommandLine.h" 239684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes#include "llvm/Target/TargetInstrInfo.h" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 25a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka#include "llvm/Target/TargetRegisterInfo.h" 269684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 279684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopesusing namespace llvm; 289684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 299684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso LopesSTATISTIC(FilledSlots, "Number of delay slots filled"); 3098f4d4d2db66375bedb461a9f6f9092a3c6703b2Akira HatanakaSTATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 31176965f46b9f4ca7c83746355853601c05488564Akira Hatanaka " are not NOP."); 329684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 336522a9e04bcfa447299f4fd10ee9afffd5834a47Akira Hatanakastatic cl::opt<bool> DisableDelaySlotFiller( 346522a9e04bcfa447299f4fd10ee9afffd5834a47Akira Hatanaka "disable-mips-delay-filler", 35a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka cl::init(false), 3690db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka cl::desc("Fill all delay slots with NOPs."), 37a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka cl::Hidden); 38a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 39f9c3f3b8a8702e0d98be5fb9cd5428c49c7164a2Akira Hatanaka// This option can be used to silence complaints by machine verifier passes. 40f9c3f3b8a8702e0d98be5fb9cd5428c49c7164a2Akira Hatanakastatic cl::opt<bool> SkipDelaySlotFiller( 41f9c3f3b8a8702e0d98be5fb9cd5428c49c7164a2Akira Hatanaka "skip-mips-delay-filler", 42f9c3f3b8a8702e0d98be5fb9cd5428c49c7164a2Akira Hatanaka cl::init(false), 43f9c3f3b8a8702e0d98be5fb9cd5428c49c7164a2Akira Hatanaka cl::desc("Skip MIPS' delay slot filling pass."), 44f9c3f3b8a8702e0d98be5fb9cd5428c49c7164a2Akira Hatanaka cl::Hidden); 45f9c3f3b8a8702e0d98be5fb9cd5428c49c7164a2Akira Hatanaka 469684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopesnamespace { 4770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka class RegDefsUses { 4870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka public: 4970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka RegDefsUses(TargetMachine &TM); 5070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka void init(const MachineInstr &MI); 5170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool update(const MachineInstr &MI, unsigned Begin, unsigned End); 5270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 5370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka private: 5470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, unsigned Reg, 5570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool IsDef) const; 5670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 5770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka /// Returns true if Reg or its alias is in RegSet. 5870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool isRegInSet(const BitVector &RegSet, unsigned Reg) const; 5970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 6070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka const TargetRegisterInfo &TRI; 6170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka BitVector Defs, Uses; 6270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka }; 6370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 645dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka class Filler : public MachineFunctionPass { 655dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka public: 6690c595425bdc47563714d6ed13f6e9151552ceaeBruno Cardoso Lopes Filler(TargetMachine &tm) 6790c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } 689684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 699684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes virtual const char *getPassName() const { 709684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes return "Mips Delay Slot Filler"; 719684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes } 729684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 739684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes bool runOnMachineFunction(MachineFunction &F) { 74f9c3f3b8a8702e0d98be5fb9cd5428c49c7164a2Akira Hatanaka if (SkipDelaySlotFiller) 75f9c3f3b8a8702e0d98be5fb9cd5428c49c7164a2Akira Hatanaka return false; 76f9c3f3b8a8702e0d98be5fb9cd5428c49c7164a2Akira Hatanaka 779684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes bool Changed = false; 789684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 799684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes FI != FE; ++FI) 809684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes Changed |= runOnMachineBasicBlock(*FI); 819684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes return Changed; 829684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes } 839684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 845dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka private: 85eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka typedef MachineBasicBlock::iterator Iter; 86eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka typedef MachineBasicBlock::reverse_iterator ReverseIter; 875dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka 885dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 895dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka 90cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka /// This function checks if it is valid to move Candidate to the delay slot 91cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka /// and returns true if it isn't. It also updates load and store flags and 92cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka /// register defs and uses. 9390db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka bool delayHasHazard(const MachineInstr &Candidate, bool &SawLoad, 9470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool &SawStore, RegDefsUses &RegDU) const; 95a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 9690db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka bool findDelayInstr(MachineBasicBlock &MBB, Iter slot, Iter &Filler) const; 97eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka 98eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka bool terminateSearch(const MachineInstr &Candidate) const; 99a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 1005dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka TargetMachine &TM; 1015dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka const TargetInstrInfo *TII; 102a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 1035dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka static char ID; 1049684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes }; 1059684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes char Filler::ID = 0; 1069684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes} // end of anonymous namespace 1079684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 10870cdcd5114b30c4983ff158278422ea129bd27bbAkira HatanakaRegDefsUses::RegDefsUses(TargetMachine &TM) 10970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka : TRI(*TM.getRegisterInfo()), Defs(TRI.getNumRegs(), false), 11070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka Uses(TRI.getNumRegs(), false) {} 11170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 11270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanakavoid RegDefsUses::init(const MachineInstr &MI) { 11370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // Add all register operands which are explicit and non-variadic. 11470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka update(MI, 0, MI.getDesc().getNumOperands()); 11570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 11670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // If MI is a call, add RA to Defs to prevent users of RA from going into 11770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // delay slot. 11870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka if (MI.isCall()) 11970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka Defs.set(Mips::RA); 12070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 12170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // Add all implicit register operands of branch instructions except 12270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // register AT. 12370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka if (MI.isBranch()) { 12470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka update(MI, MI.getDesc().getNumOperands(), MI.getNumOperands()); 12570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka Defs.reset(Mips::AT); 12670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka } 12770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka} 12870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 12970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanakabool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) { 13070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka BitVector NewDefs(TRI.getNumRegs()), NewUses(TRI.getNumRegs()); 13170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool HasHazard = false; 13270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 13370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka for (unsigned I = Begin; I != End; ++I) { 13470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka const MachineOperand &MO = MI.getOperand(I); 13570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 13670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka if (MO.isReg() && MO.getReg()) 13770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka HasHazard |= checkRegDefsUses(NewDefs, NewUses, MO.getReg(), MO.isDef()); 13870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka } 13970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 14070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka Defs |= NewDefs; 14170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka Uses |= NewUses; 14270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 14370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka return HasHazard; 14470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka} 14570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 14670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanakabool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses, 14770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka unsigned Reg, bool IsDef) const { 14870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka if (IsDef) { 14970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka NewDefs.set(Reg); 15070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // check whether Reg has already been defined or used. 15170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka return (isRegInSet(Defs, Reg) || isRegInSet(Uses, Reg)); 15270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka } 15370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 15470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka NewUses.set(Reg); 15570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // check whether Reg has already been defined. 15670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka return isRegInSet(Defs, Reg); 15770cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka} 15870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 15970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanakabool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const { 16070cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka // Check Reg and all aliased Registers. 16170cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI) 16270cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka if (RegSet.test(*AI)) 16370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka return true; 16470cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka return false; 16570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka} 16670cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka 1679684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 168a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka/// We assume there is only one delay slot per delayed instruction. 16990db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanakabool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 1709684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes bool Changed = false; 17153120e0a9fde4b3e8057b9d5b9ad8ec50fbaa31dAkira Hatanaka 172eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka for (Iter I = MBB.begin(); I != MBB.end(); ++I) { 1735dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka if (!I->hasDelaySlot()) 1745dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka continue; 1755dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka 1765dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka ++FilledSlots; 1775dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka Changed = true; 178eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka Iter D; 1795dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka 1805dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka // Delay slot filling is disabled at -O0. 1815dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None) && 1825dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka findDelayInstr(MBB, I, D)) { 1835dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka MBB.splice(llvm::next(I), &MBB, D); 1845dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka ++UsefulSlots; 1855dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka } else 1865dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); 187a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 188eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka // Bundle the delay slot filler to the instruction with the delay slot. 189eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka MIBundleBuilder(MBB, I, llvm::next(llvm::next(I))); 1905dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka } 1915dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka 1925dd41c95f3075fc5c01cfb6822a66ac584fcc8c7Akira Hatanaka return Changed; 1939684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes} 1949684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 1959684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 1969684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes/// slots in Mips MachineFunctions 1979684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso LopesFunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 1989684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes return new Filler(tm); 1999684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes} 2009684a697d59cdcbe9dff84bdaf3b42cf0465e821Bruno Cardoso Lopes 20190db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanakabool Filler::findDelayInstr(MachineBasicBlock &MBB, Iter Slot, 20290db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka Iter &Filler) const { 20370cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka RegDefsUses RegDU(TM); 204a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 20570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka RegDU.init(*Slot); 206a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 20790db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka bool SawLoad = false; 20890db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka bool SawStore = false; 209a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 21090db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka for (ReverseIter I(Slot); I != MBB.rend(); ++I) { 211a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka // skip debug value 212a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka if (I->isDebugValue()) 213a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka continue; 214a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 215eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka if (terminateSearch(*I)) 216a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka break; 217a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 21870cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka if (delayHasHazard(*I, SawLoad, SawStore, RegDU)) 219a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka continue; 220a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 22190db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka Filler = llvm::next(I).base(); 2226f818abbe3dce0bee8257ea7d7dd4cb951f4dc7cAkira Hatanaka return true; 223a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka } 2246f818abbe3dce0bee8257ea7d7dd4cb951f4dc7cAkira Hatanaka 2256f818abbe3dce0bee8257ea7d7dd4cb951f4dc7cAkira Hatanaka return false; 226a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka} 227a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 22890db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanakabool Filler::delayHasHazard(const MachineInstr &Candidate, bool &SawLoad, 22970cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka bool &SawStore, RegDefsUses &RegDU) const { 230cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka bool HasHazard = (Candidate.isImplicitDef() || Candidate.isKill()); 231a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 232cfc3fb57372b2ebd580b966469121cba2029bae9Akira Hatanaka // Loads or stores cannot be moved past a store to the delay slot 233bb481f882093fb738d2bb15610c79364bada5496Jia Liu // and stores cannot be moved past a load. 234d977aacf990d241d0224d20518f631a928c1b1a8Akira Hatanaka if (Candidate.mayStore() || Candidate.hasOrderedMemoryRef()) { 235cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka HasHazard |= SawStore | SawLoad; 23690db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka SawStore = true; 237cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka } else if (Candidate.mayLoad()) { 238cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka HasHazard |= SawStore; 239cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka SawLoad = true; 240a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka } 241a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 24290db35a3e7d24ad81aa0ce6b641186faed033cdcAkira Hatanaka assert((!Candidate.isCall() && !Candidate.isReturn()) && 24342be280a288b2bfc5f072ea83802088e0fb073e7Akira Hatanaka "Cannot put calls or returns in delay slot."); 2440c419a7c4bec0a4931dd1dbd9f1adb43ec9b15c2Akira Hatanaka 24570cdcd5114b30c4983ff158278422ea129bd27bbAkira Hatanaka HasHazard |= RegDU.update(Candidate, 0, Candidate.getNumOperands()); 246a3defb07a075e936c435428d5adeedc5f12f5ab5Akira Hatanaka 247cd7319dc5f91ac81ab9d8505f34937e91bfcf65dAkira Hatanaka return HasHazard; 248a032dbd62f46a40b2cf759ce0dd0ebd41ef0614cAkira Hatanaka} 249a032dbd62f46a40b2cf759ce0dd0ebd41ef0614cAkira Hatanaka 250eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanakabool Filler::terminateSearch(const MachineInstr &Candidate) const { 251eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka return (Candidate.isTerminator() || Candidate.isCall() || 252eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka Candidate.isLabel() || Candidate.isInlineAsm() || 253eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka Candidate.hasUnmodeledSideEffects()); 254eba97c573f08332c9c9d1875c304cce1bea2e28eAkira Hatanaka} 255