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