DelaySlotFiller.cpp revision f152fe8d487c46873bbdd4abab43200f783e978b
1e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor//===-- DelaySlotFiller.cpp - SPARC delay slot filler ---------------------===// 2e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor// 3e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor// The LLVM Compiler Infrastructure 4e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor// 5e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor// This file is distributed under the University of Illinois Open Source 6e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor// License. See LICENSE.TXT for details. 7e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor// 8e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor//===----------------------------------------------------------------------===// 9e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor// 10e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor// This is a simple local pass that attempts to fill delay slots with useful 11e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor// instructions. If no instructions can be moved into the delay slot, then a 12e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor// NOP is placed. 13e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor//===----------------------------------------------------------------------===// 14e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor 15e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor#define DEBUG_TYPE "delay-slot-filler" 16e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor#include "Sparc.h" 17e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor#include "llvm/CodeGen/MachineFunctionPass.h" 18e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor#include "llvm/CodeGen/MachineInstrBuilder.h" 19e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor#include "llvm/Support/CommandLine.h" 20e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor#include "llvm/Target/TargetMachine.h" 21e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor#include "llvm/Target/TargetInstrInfo.h" 22e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor#include "llvm/Target/TargetRegisterInfo.h" 23e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor#include "llvm/ADT/SmallSet.h" 24e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor#include "llvm/ADT/Statistic.h" 25e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor 26e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregorusing namespace llvm; 27e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor 28e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas GregorSTATISTIC(FilledSlots, "Number of delay slots filled"); 29e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor 30e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregorstatic cl::opt<bool> DisableDelaySlotFiller( 31e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor "disable-sparc-delay-filler", 32e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor cl::init(false), 33e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor cl::desc("Disable the Sparc delay slot filler."), 34e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor cl::Hidden); 35e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor 36e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregornamespace { 37e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor struct Filler : public MachineFunctionPass { 38e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor /// Target machine description which we query for reg. names, data 39e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor /// layout, etc. 40e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor /// 41e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor TargetMachine &TM; 42e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor const TargetInstrInfo *TII; 43e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor 44e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor static char ID; 45e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor Filler(TargetMachine &tm) 46e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } 47e7450f5dbd5bed63b8ef9db86350a8fc3db011e8Douglas Gregor 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->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->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 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->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 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 // 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. 291bool 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 302bool 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