MipsDelaySlotFiller.cpp revision 6522a9e04bcfa447299f4fd10ee9afffd5834a47
1//===-- DelaySlotFiller.cpp - Mips Delay Slot Filler ----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Simple pass to fills delay slots with useful instructions. 11// 12//===----------------------------------------------------------------------===// 13 14#define DEBUG_TYPE "delay-slot-filler" 15 16#include "Mips.h" 17#include "MipsTargetMachine.h" 18#include "llvm/CodeGen/MachineFunctionPass.h" 19#include "llvm/CodeGen/MachineInstrBuilder.h" 20#include "llvm/Support/CommandLine.h" 21#include "llvm/Target/TargetMachine.h" 22#include "llvm/Target/TargetInstrInfo.h" 23#include "llvm/Target/TargetRegisterInfo.h" 24#include "llvm/ADT/SmallSet.h" 25#include "llvm/ADT/Statistic.h" 26 27using namespace llvm; 28 29STATISTIC(FilledSlots, "Number of delay slots filled"); 30STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 31 " are not NOP."); 32 33static cl::opt<bool> DisableDelaySlotFiller( 34 "disable-mips-delay-filler", 35 cl::init(false), 36 cl::desc("Disable the delay slot filler, which attempts to fill the Mips" 37 "delay slots with useful instructions."), 38 cl::Hidden); 39 40// This option can be used to silence complaints by machine verifier passes. 41static cl::opt<bool> SkipDelaySlotFiller( 42 "skip-mips-delay-filler", 43 cl::init(false), 44 cl::desc("Skip MIPS' delay slot filling pass."), 45 cl::Hidden); 46 47namespace { 48 struct Filler : public MachineFunctionPass { 49 typedef MachineBasicBlock::instr_iterator InstrIter; 50 typedef MachineBasicBlock::reverse_instr_iterator ReverseInstrIter; 51 52 TargetMachine &TM; 53 const TargetInstrInfo *TII; 54 InstrIter LastFiller; 55 56 static char ID; 57 Filler(TargetMachine &tm) 58 : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } 59 60 virtual const char *getPassName() const { 61 return "Mips Delay Slot Filler"; 62 } 63 64 bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 65 bool runOnMachineFunction(MachineFunction &F) { 66 if (SkipDelaySlotFiller) 67 return false; 68 69 bool Changed = false; 70 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 71 FI != FE; ++FI) 72 Changed |= runOnMachineBasicBlock(*FI); 73 return Changed; 74 } 75 76 bool isDelayFiller(MachineBasicBlock &MBB, 77 InstrIter candidate); 78 79 void insertCallUses(InstrIter MI, 80 SmallSet<unsigned, 32> &RegDefs, 81 SmallSet<unsigned, 32> &RegUses); 82 83 void insertDefsUses(InstrIter MI, 84 SmallSet<unsigned, 32> &RegDefs, 85 SmallSet<unsigned, 32> &RegUses); 86 87 bool IsRegInSet(SmallSet<unsigned, 32> &RegSet, 88 unsigned Reg); 89 90 bool delayHasHazard(InstrIter candidate, 91 bool &sawLoad, bool &sawStore, 92 SmallSet<unsigned, 32> &RegDefs, 93 SmallSet<unsigned, 32> &RegUses); 94 95 bool 96 findDelayInstr(MachineBasicBlock &MBB, InstrIter slot, 97 InstrIter &Filler); 98 99 100 }; 101 char Filler::ID = 0; 102} // end of anonymous namespace 103 104/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 105/// We assume there is only one delay slot per delayed instruction. 106bool Filler:: 107runOnMachineBasicBlock(MachineBasicBlock &MBB) { 108 bool Changed = false; 109 LastFiller = MBB.instr_end(); 110 111 for (InstrIter I = MBB.instr_begin(); I != MBB.instr_end(); ++I) 112 if (I->hasDelaySlot()) { 113 ++FilledSlots; 114 Changed = true; 115 116 InstrIter D; 117 118 if (!DisableDelaySlotFiller && findDelayInstr(MBB, I, D)) { 119 MBB.splice(llvm::next(I), &MBB, D); 120 ++UsefulSlots; 121 } else 122 BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); 123 124 // Record the filler instruction that filled the delay slot. 125 // The instruction after it will be visited in the next iteration. 126 LastFiller = ++I; 127 128 // Set InsideBundle bit so that the machine verifier doesn't expect this 129 // instruction to be a terminator. 130 LastFiller->setIsInsideBundle(); 131 } 132 return Changed; 133 134} 135 136/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 137/// slots in Mips MachineFunctions 138FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 139 return new Filler(tm); 140} 141 142bool Filler::findDelayInstr(MachineBasicBlock &MBB, 143 InstrIter slot, 144 InstrIter &Filler) { 145 SmallSet<unsigned, 32> RegDefs; 146 SmallSet<unsigned, 32> RegUses; 147 148 insertDefsUses(slot, RegDefs, RegUses); 149 150 bool sawLoad = false; 151 bool sawStore = false; 152 153 for (ReverseInstrIter I(slot); I != MBB.instr_rend(); ++I) { 154 // skip debug value 155 if (I->isDebugValue()) 156 continue; 157 158 // Convert to forward iterator. 159 InstrIter FI(llvm::next(I).base()); 160 161 if (I->hasUnmodeledSideEffects() 162 || I->isInlineAsm() 163 || I->isLabel() 164 || FI == LastFiller 165 || I->isPseudo() 166 // 167 // Should not allow: 168 // ERET, DERET or WAIT, PAUSE. Need to add these to instruction 169 // list. TBD. 170 ) 171 break; 172 173 if (delayHasHazard(FI, sawLoad, sawStore, RegDefs, RegUses)) { 174 insertDefsUses(FI, RegDefs, RegUses); 175 continue; 176 } 177 178 Filler = FI; 179 return true; 180 } 181 182 return false; 183} 184 185bool Filler::delayHasHazard(InstrIter candidate, 186 bool &sawLoad, bool &sawStore, 187 SmallSet<unsigned, 32> &RegDefs, 188 SmallSet<unsigned, 32> &RegUses) { 189 if (candidate->isImplicitDef() || candidate->isKill()) 190 return true; 191 192 // Loads or stores cannot be moved past a store to the delay slot 193 // and stores cannot be moved past a load. 194 if (candidate->mayLoad()) { 195 if (sawStore) 196 return true; 197 sawLoad = true; 198 } 199 200 if (candidate->mayStore()) { 201 if (sawStore) 202 return true; 203 sawStore = true; 204 if (sawLoad) 205 return true; 206 } 207 208 assert((!candidate->isCall() && !candidate->isReturn()) && 209 "Cannot put calls or returns in delay slot."); 210 211 for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) { 212 const MachineOperand &MO = candidate->getOperand(i); 213 unsigned Reg; 214 215 if (!MO.isReg() || !(Reg = MO.getReg())) 216 continue; // skip 217 218 if (MO.isDef()) { 219 // check whether Reg is defined or used before delay slot. 220 if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg)) 221 return true; 222 } 223 if (MO.isUse()) { 224 // check whether Reg is defined before delay slot. 225 if (IsRegInSet(RegDefs, Reg)) 226 return true; 227 } 228 } 229 return false; 230} 231 232// Insert Defs and Uses of MI into the sets RegDefs and RegUses. 233void Filler::insertDefsUses(InstrIter MI, 234 SmallSet<unsigned, 32> &RegDefs, 235 SmallSet<unsigned, 32> &RegUses) { 236 // If MI is a call or return, just examine the explicit non-variadic operands. 237 MCInstrDesc MCID = MI->getDesc(); 238 unsigned e = MI->isCall() || MI->isReturn() ? MCID.getNumOperands() : 239 MI->getNumOperands(); 240 241 // Add RA to RegDefs to prevent users of RA from going into delay slot. 242 if (MI->isCall()) 243 RegDefs.insert(Mips::RA); 244 245 for (unsigned i = 0; i != e; ++i) { 246 const MachineOperand &MO = MI->getOperand(i); 247 unsigned Reg; 248 249 if (!MO.isReg() || !(Reg = MO.getReg())) 250 continue; 251 252 if (MO.isDef()) 253 RegDefs.insert(Reg); 254 else if (MO.isUse()) 255 RegUses.insert(Reg); 256 } 257} 258 259//returns true if the Reg or its alias is in the RegSet. 260bool Filler::IsRegInSet(SmallSet<unsigned, 32> &RegSet, unsigned Reg) { 261 // Check Reg and all aliased Registers. 262 for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true); 263 AI.isValid(); ++AI) 264 if (RegSet.count(*AI)) 265 return true; 266 return false; 267} 268