1 //===-- DelaySlotFiller.cpp - SPARC 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 // This is a simple local pass that attempts to fill delay slots with useful 11 // instructions. If no instructions can be moved into the delay slot, then a 12 // NOP is placed. 13 //===----------------------------------------------------------------------===// 14 15 #define DEBUG_TYPE "delay-slot-filler" 16 #include "Sparc.h" 17 #include "llvm/ADT/SmallSet.h" 18 #include "llvm/ADT/Statistic.h" 19 #include "llvm/CodeGen/MachineFunctionPass.h" 20 #include "llvm/CodeGen/MachineInstrBuilder.h" 21 #include "llvm/Support/CommandLine.h" 22 #include "llvm/Target/TargetInstrInfo.h" 23 #include "llvm/Target/TargetMachine.h" 24 #include "llvm/Target/TargetRegisterInfo.h" 25 26 using namespace llvm; 27 28 STATISTIC(FilledSlots, "Number of delay slots filled"); 29 30 static cl::opt<bool> DisableDelaySlotFiller( 31 "disable-sparc-delay-filler", 32 cl::init(false), 33 cl::desc("Disable the Sparc delay slot filler."), 34 cl::Hidden); 35 36 namespace { 37 struct Filler : public MachineFunctionPass { 38 /// Target machine description which we query for reg. names, data 39 /// layout, etc. 40 /// 41 TargetMachine &TM; 42 const TargetInstrInfo *TII; 43 44 static char ID; 45 Filler(TargetMachine &tm) 46 : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } 47 48 virtual const char *getPassName() const { 49 return "SPARC Delay Slot Filler"; 50 } 51 52 bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 53 bool runOnMachineFunction(MachineFunction &F) { 54 bool Changed = false; 55 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 56 FI != FE; ++FI) 57 Changed |= runOnMachineBasicBlock(*FI); 58 return Changed; 59 } 60 61 bool isDelayFiller(MachineBasicBlock &MBB, 62 MachineBasicBlock::iterator candidate); 63 64 void insertCallUses(MachineBasicBlock::iterator MI, 65 SmallSet<unsigned, 32>& RegUses); 66 67 void insertDefsUses(MachineBasicBlock::iterator MI, 68 SmallSet<unsigned, 32>& RegDefs, 69 SmallSet<unsigned, 32>& RegUses); 70 71 bool IsRegInSet(SmallSet<unsigned, 32>& RegSet, 72 unsigned Reg); 73 74 bool delayHasHazard(MachineBasicBlock::iterator candidate, 75 bool &sawLoad, bool &sawStore, 76 SmallSet<unsigned, 32> &RegDefs, 77 SmallSet<unsigned, 32> &RegUses); 78 79 MachineBasicBlock::iterator 80 findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot); 81 82 bool needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize); 83 84 }; 85 char Filler::ID = 0; 86 } // end of anonymous namespace 87 88 /// createSparcDelaySlotFillerPass - Returns a pass that fills in delay 89 /// slots in Sparc MachineFunctions 90 /// 91 FunctionPass *llvm::createSparcDelaySlotFillerPass(TargetMachine &tm) { 92 return new Filler(tm); 93 } 94 95 96 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 97 /// We assume there is only one delay slot per delayed instruction. 98 /// 99 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 100 bool Changed = false; 101 102 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) 103 if (I->hasDelaySlot()) { 104 MachineBasicBlock::iterator D = MBB.end(); 105 MachineBasicBlock::iterator J = I; 106 107 if (!DisableDelaySlotFiller) 108 D = findDelayInstr(MBB, I); 109 110 ++FilledSlots; 111 Changed = true; 112 113 if (D == MBB.end()) 114 BuildMI(MBB, ++J, I->getDebugLoc(), TII->get(SP::NOP)); 115 else 116 MBB.splice(++J, &MBB, D); 117 unsigned structSize = 0; 118 if (needsUnimp(I, structSize)) { 119 MachineBasicBlock::iterator J = I; 120 ++J; //skip the delay filler. 121 BuildMI(MBB, ++J, I->getDebugLoc(), 122 TII->get(SP::UNIMP)).addImm(structSize); 123 } 124 } 125 return Changed; 126 } 127 128 MachineBasicBlock::iterator 129 Filler::findDelayInstr(MachineBasicBlock &MBB, 130 MachineBasicBlock::iterator slot) 131 { 132 SmallSet<unsigned, 32> RegDefs; 133 SmallSet<unsigned, 32> RegUses; 134 bool sawLoad = false; 135 bool sawStore = false; 136 137 MachineBasicBlock::iterator I = slot; 138 139 if (slot->getOpcode() == SP::RET) 140 return MBB.end(); 141 142 if (slot->getOpcode() == SP::RETL) { 143 --I; 144 if (I->getOpcode() != SP::RESTORErr) 145 return MBB.end(); 146 //change retl to ret 147 slot->setDesc(TII->get(SP::RET)); 148 return I; 149 } 150 151 //Call's delay filler can def some of call's uses. 152 if (slot->isCall()) 153 insertCallUses(slot, RegUses); 154 else 155 insertDefsUses(slot, RegDefs, RegUses); 156 157 bool done = false; 158 159 while (!done) { 160 done = (I == MBB.begin()); 161 162 if (!done) 163 --I; 164 165 // skip debug value 166 if (I->isDebugValue()) 167 continue; 168 169 170 if (I->hasUnmodeledSideEffects() 171 || I->isInlineAsm() 172 || I->isLabel() 173 || I->hasDelaySlot() 174 || isDelayFiller(MBB, I)) 175 break; 176 177 if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) { 178 insertDefsUses(I, RegDefs, RegUses); 179 continue; 180 } 181 182 return I; 183 } 184 return MBB.end(); 185 } 186 187 bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate, 188 bool &sawLoad, 189 bool &sawStore, 190 SmallSet<unsigned, 32> &RegDefs, 191 SmallSet<unsigned, 32> &RegUses) 192 { 193 194 if (candidate->isImplicitDef() || candidate->isKill()) 195 return true; 196 197 if (candidate->mayLoad()) { 198 sawLoad = true; 199 if (sawStore) 200 return true; 201 } 202 203 if (candidate->mayStore()) { 204 if (sawStore) 205 return true; 206 sawStore = true; 207 if (sawLoad) 208 return true; 209 } 210 211 for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) { 212 const MachineOperand &MO = candidate->getOperand(i); 213 if (!MO.isReg()) 214 continue; // skip 215 216 unsigned Reg = MO.getReg(); 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 233 void Filler::insertCallUses(MachineBasicBlock::iterator MI, 234 SmallSet<unsigned, 32>& RegUses) 235 { 236 237 switch(MI->getOpcode()) { 238 default: llvm_unreachable("Unknown opcode."); 239 case SP::CALL: break; 240 case SP::JMPLrr: 241 case SP::JMPLri: 242 assert(MI->getNumOperands() >= 2); 243 const MachineOperand &Reg = MI->getOperand(0); 244 assert(Reg.isReg() && "JMPL first operand is not a register."); 245 assert(Reg.isUse() && "JMPL first operand is not a use."); 246 RegUses.insert(Reg.getReg()); 247 248 const MachineOperand &RegOrImm = MI->getOperand(1); 249 if (RegOrImm.isImm()) 250 break; 251 assert(RegOrImm.isReg() && "JMPLrr second operand is not a register."); 252 assert(RegOrImm.isUse() && "JMPLrr second operand is not a use."); 253 RegUses.insert(RegOrImm.getReg()); 254 break; 255 } 256 } 257 258 //Insert Defs and Uses of MI into the sets RegDefs and RegUses. 259 void Filler::insertDefsUses(MachineBasicBlock::iterator MI, 260 SmallSet<unsigned, 32>& RegDefs, 261 SmallSet<unsigned, 32>& RegUses) 262 { 263 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 264 const MachineOperand &MO = MI->getOperand(i); 265 if (!MO.isReg()) 266 continue; 267 268 unsigned Reg = MO.getReg(); 269 if (Reg == 0) 270 continue; 271 if (MO.isDef()) 272 RegDefs.insert(Reg); 273 if (MO.isUse()) 274 RegUses.insert(Reg); 275 276 } 277 } 278 279 //returns true if the Reg or its alias is in the RegSet. 280 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) 281 { 282 // Check Reg and all aliased Registers. 283 for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true); 284 AI.isValid(); ++AI) 285 if (RegSet.count(*AI)) 286 return true; 287 return false; 288 } 289 290 // return true if the candidate is a delay filler. 291 bool Filler::isDelayFiller(MachineBasicBlock &MBB, 292 MachineBasicBlock::iterator candidate) 293 { 294 if (candidate == MBB.begin()) 295 return false; 296 if (candidate->getOpcode() == SP::UNIMP) 297 return true; 298 --candidate; 299 return candidate->hasDelaySlot(); 300 } 301 302 bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize) 303 { 304 if (!I->isCall()) 305 return false; 306 307 unsigned structSizeOpNum = 0; 308 switch (I->getOpcode()) { 309 default: llvm_unreachable("Unknown call opcode."); 310 case SP::CALL: structSizeOpNum = 1; break; 311 case SP::JMPLrr: 312 case SP::JMPLri: structSizeOpNum = 2; break; 313 } 314 315 const MachineOperand &MO = I->getOperand(structSizeOpNum); 316 if (!MO.isImm()) 317 return false; 318 StructSize = MO.getImm(); 319 return true; 320 } 321