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 45 static char ID; 46 Filler(TargetMachine &tm) 47 : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } 48 49 virtual const char *getPassName() const { 50 return "Mips Delay Slot Filler"; 51 } 52 53 bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 54 bool runOnMachineFunction(MachineFunction &F) { 55 bool Changed = false; 56 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 57 FI != FE; ++FI) 58 Changed |= runOnMachineBasicBlock(*FI); 59 return Changed; 60 } 61 62 bool isDelayFiller(MachineBasicBlock &MBB, 63 MachineBasicBlock::iterator candidate); 64 65 void insertCallUses(MachineBasicBlock::iterator MI, 66 SmallSet<unsigned, 32>& RegDefs, 67 SmallSet<unsigned, 32>& RegUses); 68 69 void insertDefsUses(MachineBasicBlock::iterator MI, 70 SmallSet<unsigned, 32>& RegDefs, 71 SmallSet<unsigned, 32>& RegUses); 72 73 bool IsRegInSet(SmallSet<unsigned, 32>& RegSet, 74 unsigned Reg); 75 76 bool delayHasHazard(MachineBasicBlock::iterator candidate, 77 bool &sawLoad, bool &sawStore, 78 SmallSet<unsigned, 32> &RegDefs, 79 SmallSet<unsigned, 32> &RegUses); 80 81 bool 82 findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot, 83 MachineBasicBlock::iterator &Filler); 84 85 86 }; 87 char Filler::ID = 0; 88 } // end of anonymous namespace 89 90 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 91 /// We assume there is only one delay slot per delayed instruction. 92 bool Filler:: 93 runOnMachineBasicBlock(MachineBasicBlock &MBB) { 94 bool Changed = false; 95 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) 96 if (I->getDesc().hasDelaySlot()) { 97 ++FilledSlots; 98 Changed = true; 99 100 MachineBasicBlock::iterator D; 101 102 if (EnableDelaySlotFiller && findDelayInstr(MBB, I, D)) { 103 MBB.splice(llvm::next(I), &MBB, D); 104 ++UsefulSlots; 105 } 106 else 107 BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); 108 109 ++I; // Skip instruction that has just been moved to delay slot. 110 } 111 return Changed; 112 113 } 114 115 /// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 116 /// slots in Mips MachineFunctions 117 FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 118 return new Filler(tm); 119 } 120 121 bool Filler::findDelayInstr(MachineBasicBlock &MBB, 122 MachineBasicBlock::iterator slot, 123 MachineBasicBlock::iterator &Filler) { 124 SmallSet<unsigned, 32> RegDefs; 125 SmallSet<unsigned, 32> RegUses; 126 bool sawLoad = false; 127 bool sawStore = false; 128 129 MachineBasicBlock::iterator I = slot; 130 131 // Call's delay filler can def some of call's uses. 132 if (slot->getDesc().isCall()) 133 insertCallUses(slot, RegDefs, RegUses); 134 else 135 insertDefsUses(slot, RegDefs, RegUses); 136 137 bool done = false; 138 139 while (!done) { 140 done = (I == MBB.begin()); 141 142 if (!done) 143 --I; 144 145 // skip debug value 146 if (I->isDebugValue()) 147 continue; 148 149 if (I->hasUnmodeledSideEffects() 150 || I->isInlineAsm() 151 || I->isLabel() 152 || isDelayFiller(MBB, I) 153 || I->getDesc().isPseudo() 154 // 155 // Should not allow: 156 // ERET, DERET or WAIT, PAUSE. Need to add these to instruction 157 // list. TBD. 158 ) 159 break; 160 161 if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) { 162 insertDefsUses(I, RegDefs, RegUses); 163 continue; 164 } 165 166 Filler = I; 167 return true; 168 } 169 170 return false; 171 } 172 173 bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate, 174 bool &sawLoad, 175 bool &sawStore, 176 SmallSet<unsigned, 32> &RegDefs, 177 SmallSet<unsigned, 32> &RegUses) { 178 if (candidate->isImplicitDef() || candidate->isKill()) 179 return true; 180 181 // Loads or stores cannot be moved past a store to the delay slot 182 // and stores cannot be moved past a load. 183 if (candidate->getDesc().mayLoad()) { 184 if (sawStore) 185 return true; 186 sawLoad = true; 187 } 188 189 if (candidate->getDesc().mayStore()) { 190 if (sawStore) 191 return true; 192 sawStore = true; 193 if (sawLoad) 194 return true; 195 } 196 197 for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) { 198 const MachineOperand &MO = candidate->getOperand(i); 199 if (!MO.isReg()) 200 continue; // skip 201 202 unsigned Reg = MO.getReg(); 203 204 if (MO.isDef()) { 205 // check whether Reg is defined or used before delay slot. 206 if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg)) 207 return true; 208 } 209 if (MO.isUse()) { 210 // check whether Reg is defined before delay slot. 211 if (IsRegInSet(RegDefs, Reg)) 212 return true; 213 } 214 } 215 return false; 216 } 217 218 void Filler::insertCallUses(MachineBasicBlock::iterator MI, 219 SmallSet<unsigned, 32>& RegDefs, 220 SmallSet<unsigned, 32>& RegUses) { 221 switch(MI->getOpcode()) { 222 default: llvm_unreachable("Unknown opcode."); 223 case Mips::JAL: 224 RegDefs.insert(31); 225 break; 226 case Mips::JALR: 227 assert(MI->getNumOperands() >= 1); 228 const MachineOperand &Reg = MI->getOperand(0); 229 assert(Reg.isReg() && "JALR first operand is not a register."); 230 RegUses.insert(Reg.getReg()); 231 RegDefs.insert(31); 232 break; 233 } 234 } 235 236 // Insert Defs and Uses of MI into the sets RegDefs and RegUses. 237 void Filler::insertDefsUses(MachineBasicBlock::iterator MI, 238 SmallSet<unsigned, 32>& RegDefs, 239 SmallSet<unsigned, 32>& RegUses) { 240 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 241 const MachineOperand &MO = MI->getOperand(i); 242 if (!MO.isReg()) 243 continue; 244 245 unsigned Reg = MO.getReg(); 246 if (Reg == 0) 247 continue; 248 if (MO.isDef()) 249 RegDefs.insert(Reg); 250 if (MO.isUse()) 251 RegUses.insert(Reg); 252 } 253 } 254 255 //returns true if the Reg or its alias is in the RegSet. 256 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) { 257 if (RegSet.count(Reg)) 258 return true; 259 // check Aliased Registers 260 for (const unsigned *Alias = TM.getRegisterInfo()->getAliasSet(Reg); 261 *Alias; ++Alias) 262 if (RegSet.count(*Alias)) 263 return true; 264 265 return false; 266 } 267 268 // return true if the candidate is a delay filler. 269 bool Filler::isDelayFiller(MachineBasicBlock &MBB, 270 MachineBasicBlock::iterator candidate) { 271 if (candidate == MBB.begin()) 272 return false; 273 const MCInstrDesc &prevdesc = (--candidate)->getDesc(); 274 return prevdesc.hasDelaySlot(); 275 } 276