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 27 using namespace llvm; 28 29 STATISTIC(FilledSlots, "Number of delay slots filled"); 30 STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 31 " are not NOP."); 32 33 static 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 namespace { 40 struct Filler : public MachineFunctionPass { 41 42 TargetMachine &TM; 43 const TargetInstrInfo *TII; 44 MachineBasicBlock::iterator LastFiller; 45 46 static char ID; 47 Filler(TargetMachine &tm) 48 : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } 49 50 virtual const char *getPassName() const { 51 return "Mips Delay Slot Filler"; 52 } 53 54 bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 55 bool runOnMachineFunction(MachineFunction &F) { 56 bool Changed = false; 57 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 58 FI != FE; ++FI) 59 Changed |= runOnMachineBasicBlock(*FI); 60 return Changed; 61 } 62 63 bool isDelayFiller(MachineBasicBlock &MBB, 64 MachineBasicBlock::iterator candidate); 65 66 void insertCallUses(MachineBasicBlock::iterator MI, 67 SmallSet<unsigned, 32>& RegDefs, 68 SmallSet<unsigned, 32>& RegUses); 69 70 void insertDefsUses(MachineBasicBlock::iterator MI, 71 SmallSet<unsigned, 32>& RegDefs, 72 SmallSet<unsigned, 32>& RegUses); 73 74 bool IsRegInSet(SmallSet<unsigned, 32>& RegSet, 75 unsigned Reg); 76 77 bool delayHasHazard(MachineBasicBlock::iterator candidate, 78 bool &sawLoad, bool &sawStore, 79 SmallSet<unsigned, 32> &RegDefs, 80 SmallSet<unsigned, 32> &RegUses); 81 82 bool 83 findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot, 84 MachineBasicBlock::iterator &Filler); 85 86 87 }; 88 char Filler::ID = 0; 89 } // end of anonymous namespace 90 91 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 92 /// We assume there is only one delay slot per delayed instruction. 93 bool Filler:: 94 runOnMachineBasicBlock(MachineBasicBlock &MBB) { 95 bool Changed = false; 96 LastFiller = MBB.end(); 97 98 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) 99 if (I->hasDelaySlot()) { 100 ++FilledSlots; 101 Changed = true; 102 103 MachineBasicBlock::iterator D; 104 105 if (EnableDelaySlotFiller && findDelayInstr(MBB, I, D)) { 106 MBB.splice(llvm::next(I), &MBB, D); 107 ++UsefulSlots; 108 } else 109 BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); 110 111 // Record the filler instruction that filled the delay slot. 112 // The instruction after it will be visited in the next iteration. 113 LastFiller = ++I; 114 } 115 return Changed; 116 117 } 118 119 /// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 120 /// slots in Mips MachineFunctions 121 FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 122 return new Filler(tm); 123 } 124 125 bool Filler::findDelayInstr(MachineBasicBlock &MBB, 126 MachineBasicBlock::iterator slot, 127 MachineBasicBlock::iterator &Filler) { 128 SmallSet<unsigned, 32> RegDefs; 129 SmallSet<unsigned, 32> RegUses; 130 131 insertDefsUses(slot, RegDefs, RegUses); 132 133 bool sawLoad = false; 134 bool sawStore = false; 135 136 for (MachineBasicBlock::reverse_iterator I(slot); I != MBB.rend(); ++I) { 137 // skip debug value 138 if (I->isDebugValue()) 139 continue; 140 141 // Convert to forward iterator. 142 MachineBasicBlock::iterator FI(llvm::next(I).base()); 143 144 if (I->hasUnmodeledSideEffects() 145 || I->isInlineAsm() 146 || I->isLabel() 147 || FI == LastFiller 148 || I->isPseudo() 149 // 150 // Should not allow: 151 // ERET, DERET or WAIT, PAUSE. Need to add these to instruction 152 // list. TBD. 153 ) 154 break; 155 156 if (delayHasHazard(FI, sawLoad, sawStore, RegDefs, RegUses)) { 157 insertDefsUses(FI, RegDefs, RegUses); 158 continue; 159 } 160 161 Filler = FI; 162 return true; 163 } 164 165 return false; 166 } 167 168 bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate, 169 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. 216 void 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. 243 bool 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
