MipsDelaySlotFiller.cpp revision 234353
1336815Sdim//===-- DelaySlotFiller.cpp - Mips Delay Slot Filler ----------------------===// 2336815Sdim// 3353358Sdim// The LLVM Compiler Infrastructure 4353358Sdim// 5353358Sdim// This file is distributed under the University of Illinois Open Source 6336815Sdim// License. See LICENSE.TXT for details. 7336815Sdim// 8336815Sdim//===----------------------------------------------------------------------===// 9336815Sdim// 10336815Sdim// Simple pass to fills delay slots with useful instructions. 11336815Sdim// 12336815Sdim//===----------------------------------------------------------------------===// 13336815Sdim 14336815Sdim#define DEBUG_TYPE "delay-slot-filler" 15336815Sdim 16336815Sdim#include "Mips.h" 17336815Sdim#include "MipsTargetMachine.h" 18336815Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 19336815Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 20336815Sdim#include "llvm/Support/CommandLine.h" 21336815Sdim#include "llvm/Target/TargetMachine.h" 22336815Sdim#include "llvm/Target/TargetInstrInfo.h" 23336815Sdim#include "llvm/Target/TargetRegisterInfo.h" 24336815Sdim#include "llvm/ADT/SmallSet.h" 25336815Sdim#include "llvm/ADT/Statistic.h" 26336815Sdim 27336815Sdimusing namespace llvm; 28336815Sdim 29336815SdimSTATISTIC(FilledSlots, "Number of delay slots filled"); 30336815SdimSTATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 31336815Sdim " are not NOP."); 32336815Sdim 33336815Sdimstatic cl::opt<bool> EnableDelaySlotFiller( 34336815Sdim "enable-mips-delay-filler", 35336815Sdim cl::init(false), 36336815Sdim cl::desc("Fill the Mips delay slots useful instructions."), 37336815Sdim cl::Hidden); 38336815Sdim 39336815Sdimnamespace { 40336815Sdim struct Filler : public MachineFunctionPass { 41336815Sdim 42336815Sdim TargetMachine &TM; 43336815Sdim const TargetInstrInfo *TII; 44336815Sdim MachineBasicBlock::iterator LastFiller; 45336815Sdim 46336815Sdim static char ID; 47336815Sdim Filler(TargetMachine &tm) 48336815Sdim : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } 49336815Sdim 50336815Sdim virtual const char *getPassName() const { 51336815Sdim return "Mips Delay Slot Filler"; 52336815Sdim } 53336815Sdim 54336815Sdim bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 55336815Sdim bool runOnMachineFunction(MachineFunction &F) { 56336815Sdim bool Changed = false; 57336815Sdim for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 58336815Sdim FI != FE; ++FI) 59336815Sdim Changed |= runOnMachineBasicBlock(*FI); 60336815Sdim return Changed; 61360784Sdim } 62360784Sdim 63336815Sdim bool isDelayFiller(MachineBasicBlock &MBB, 64336815Sdim MachineBasicBlock::iterator candidate); 65336815Sdim 66336815Sdim void insertCallUses(MachineBasicBlock::iterator MI, 67336815Sdim SmallSet<unsigned, 32>& RegDefs, 68336815Sdim SmallSet<unsigned, 32>& RegUses); 69336815Sdim 70336815Sdim void insertDefsUses(MachineBasicBlock::iterator MI, 71336815Sdim SmallSet<unsigned, 32>& RegDefs, 72353358Sdim SmallSet<unsigned, 32>& RegUses); 73336815Sdim 74336815Sdim bool IsRegInSet(SmallSet<unsigned, 32>& RegSet, 75336815Sdim unsigned Reg); 76336815Sdim 77336815Sdim bool delayHasHazard(MachineBasicBlock::iterator candidate, 78336815Sdim bool &sawLoad, bool &sawStore, 79336815Sdim SmallSet<unsigned, 32> &RegDefs, 80336815Sdim SmallSet<unsigned, 32> &RegUses); 81336815Sdim 82336815Sdim bool 83336815Sdim findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot, 84353358Sdim MachineBasicBlock::iterator &Filler); 85336815Sdim 86336815Sdim 87360784Sdim }; 88360784Sdim char Filler::ID = 0; 89360784Sdim} // end of anonymous namespace 90360784Sdim 91360784Sdim/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 92360784Sdim/// We assume there is only one delay slot per delayed instruction. 93360784Sdimbool Filler:: 94336815SdimrunOnMachineBasicBlock(MachineBasicBlock &MBB) { 95336815Sdim bool Changed = false; 96336815Sdim LastFiller = MBB.end(); 97336815Sdim 98336815Sdim for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) 99336815Sdim if (I->hasDelaySlot()) { 100360784Sdim ++FilledSlots; 101336815Sdim Changed = true; 102336815Sdim 103336815Sdim MachineBasicBlock::iterator D; 104336815Sdim 105336815Sdim if (EnableDelaySlotFiller && findDelayInstr(MBB, I, D)) { 106336815Sdim MBB.splice(llvm::next(I), &MBB, D); 107360784Sdim ++UsefulSlots; 108336815Sdim } else 109336815Sdim BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); 110336815Sdim 111336815Sdim // Record the filler instruction that filled the delay slot. 112336815Sdim // The instruction after it will be visited in the next iteration. 113336815Sdim LastFiller = ++I; 114336815Sdim } 115336815Sdim return Changed; 116336815Sdim 117336815Sdim} 118336815Sdim 119336815Sdim/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 120336815Sdim/// slots in Mips MachineFunctions 121336815SdimFunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 122336815Sdim return new Filler(tm); 123360784Sdim} 124360784Sdim 125360784Sdimbool Filler::findDelayInstr(MachineBasicBlock &MBB, 126360784Sdim MachineBasicBlock::iterator slot, 127360784Sdim MachineBasicBlock::iterator &Filler) { 128360784Sdim SmallSet<unsigned, 32> RegDefs; 129360784Sdim SmallSet<unsigned, 32> RegUses; 130360784Sdim 131360784Sdim insertDefsUses(slot, RegDefs, RegUses); 132360784Sdim 133360784Sdim bool sawLoad = false; 134360784Sdim bool sawStore = false; 135360784Sdim 136360784Sdim for (MachineBasicBlock::reverse_iterator I(slot); I != MBB.rend(); ++I) { 137360784Sdim // skip debug value 138360784Sdim if (I->isDebugValue()) 139360784Sdim continue; 140360784Sdim 141360784Sdim // Convert to forward iterator. 142360784Sdim MachineBasicBlock::iterator FI(llvm::next(I).base()); 143336815Sdim 144336815Sdim if (I->hasUnmodeledSideEffects() 145336815Sdim || I->isInlineAsm() 146336815Sdim || I->isLabel() 147336815Sdim || FI == LastFiller 148336815Sdim || I->isPseudo() 149336815Sdim // 150336815Sdim // Should not allow: 151336815Sdim // ERET, DERET or WAIT, PAUSE. Need to add these to instruction 152336815Sdim // list. TBD. 153336815Sdim ) 154336815Sdim break; 155336815Sdim 156336815Sdim if (delayHasHazard(FI, sawLoad, sawStore, RegDefs, RegUses)) { 157336815Sdim insertDefsUses(FI, RegDefs, RegUses); 158336815Sdim continue; 159336815Sdim } 160336815Sdim 161336815Sdim Filler = FI; 162336815Sdim return true; 163336815Sdim } 164336815Sdim 165336815Sdim return false; 166336815Sdim} 167336815Sdim 168336815Sdimbool Filler::delayHasHazard(MachineBasicBlock::iterator candidate, 169336815Sdim bool &sawLoad, bool &sawStore, 170 SmallSet<unsigned, 32> &RegDefs, 171 SmallSet<unsigned, 32> &RegUses) { 172 if (candidate->isImplicitDef() || candidate->isKill()) 173 return true; 174 175 // Loads or stores cannot be moved past a store to the delay slot 176 // and stores cannot be moved past a load. 177 if (candidate->mayLoad()) { 178 if (sawStore) 179 return true; 180 sawLoad = true; 181 } 182 183 if (candidate->mayStore()) { 184 if (sawStore) 185 return true; 186 sawStore = true; 187 if (sawLoad) 188 return true; 189 } 190 191 assert((!candidate->isCall() && !candidate->isReturn()) && 192 "Cannot put calls or returns in delay slot."); 193 194 for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) { 195 const MachineOperand &MO = candidate->getOperand(i); 196 unsigned Reg; 197 198 if (!MO.isReg() || !(Reg = MO.getReg())) 199 continue; // skip 200 201 if (MO.isDef()) { 202 // check whether Reg is defined or used before delay slot. 203 if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg)) 204 return true; 205 } 206 if (MO.isUse()) { 207 // check whether Reg is defined before delay slot. 208 if (IsRegInSet(RegDefs, Reg)) 209 return true; 210 } 211 } 212 return false; 213} 214 215// Insert Defs and Uses of MI into the sets RegDefs and RegUses. 216void Filler::insertDefsUses(MachineBasicBlock::iterator MI, 217 SmallSet<unsigned, 32>& RegDefs, 218 SmallSet<unsigned, 32>& RegUses) { 219 // If MI is a call or return, just examine the explicit non-variadic operands. 220 MCInstrDesc MCID = MI->getDesc(); 221 unsigned e = MI->isCall() || MI->isReturn() ? MCID.getNumOperands() : 222 MI->getNumOperands(); 223 224 // Add RA to RegDefs to prevent users of RA from going into delay slot. 225 if (MI->isCall()) 226 RegDefs.insert(Mips::RA); 227 228 for (unsigned i = 0; i != e; ++i) { 229 const MachineOperand &MO = MI->getOperand(i); 230 unsigned Reg; 231 232 if (!MO.isReg() || !(Reg = MO.getReg())) 233 continue; 234 235 if (MO.isDef()) 236 RegDefs.insert(Reg); 237 else if (MO.isUse()) 238 RegUses.insert(Reg); 239 } 240} 241 242//returns true if the Reg or its alias is in the RegSet. 243bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) { 244 if (RegSet.count(Reg)) 245 return true; 246 // check Aliased Registers 247 for (const uint16_t *Alias = TM.getRegisterInfo()->getAliasSet(Reg); 248 *Alias; ++Alias) 249 if (RegSet.count(*Alias)) 250 return true; 251 252 return false; 253} 254