DelaySlotFiller.cpp revision e837dead3c8dc3445ef6a0e2322179c57e264a13
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===-- DelaySlotFiller.cpp - SPARC delay slot filler ---------------------===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is a simple local pass that attempts to fill delay slots with useful 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// instructions. If no instructions can be moved into the delay slot, then a 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// NOP is placed. 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_TYPE "delay-slot-filler" 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "Sparc.h" 17c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/CodeGen/MachineFunctionPass.h" 18c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/CodeGen/MachineInstrBuilder.h" 19c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Support/CommandLine.h" 20cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)#include "llvm/Target/TargetMachine.h" 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Target/TargetInstrInfo.h" 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Target/TargetRegisterInfo.h" 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/SmallSet.h" 24cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)#include "llvm/ADT/Statistic.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace llvm; 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 28cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)STATISTIC(FilledSlots, "Number of delay slots filled"); 29cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static cl::opt<bool> DisableDelaySlotFiller( 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "disable-sparc-delay-filler", 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cl::init(false), 33cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) cl::desc("Disable the Sparc delay slot filler."), 34cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) cl::Hidden); 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct Filler : public MachineFunctionPass { 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// Target machine description which we query for reg. names, data 395f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) /// 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/// 91FunctionPass *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/// 99bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 100 bool Changed = false; 101 102 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) 103 if (I->getDesc().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 128MachineBasicBlock::iterator 129Filler::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->getDesc().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->getDesc().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 187bool 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->getDesc().mayLoad()) { 198 sawLoad = true; 199 if (sawStore) 200 return true; 201 } 202 203 if (candidate->getDesc().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 233void 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. 259void 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. 280bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) 281{ 282 if (RegSet.count(Reg)) 283 return true; 284 // check Aliased Registers 285 for (const unsigned *Alias = TM.getRegisterInfo()->getAliasSet(Reg); 286 *Alias; ++ Alias) 287 if (RegSet.count(*Alias)) 288 return true; 289 290 return false; 291} 292 293// return true if the candidate is a delay filler. 294bool Filler::isDelayFiller(MachineBasicBlock &MBB, 295 MachineBasicBlock::iterator candidate) 296{ 297 if (candidate == MBB.begin()) 298 return false; 299 if (candidate->getOpcode() == SP::UNIMP) 300 return true; 301 const MCInstrDesc &prevdesc = (--candidate)->getDesc(); 302 return prevdesc.hasDelaySlot(); 303} 304 305bool Filler::needsUnimp(MachineBasicBlock::iterator I, unsigned &StructSize) 306{ 307 if (!I->getDesc().isCall()) 308 return false; 309 310 unsigned structSizeOpNum = 0; 311 switch (I->getOpcode()) { 312 default: llvm_unreachable("Unknown call opcode."); 313 case SP::CALL: structSizeOpNum = 1; break; 314 case SP::JMPLrr: 315 case SP::JMPLri: structSizeOpNum = 2; break; 316 } 317 318 const MachineOperand &MO = I->getOperand(structSizeOpNum); 319 if (!MO.isImm()) 320 return false; 321 StructSize = MO.getImm(); 322 return true; 323} 324