DelaySlotFiller.cpp revision 71e39dac0ce9676dd3d0a92164167e18499d40fa
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/CodeGen/MachineFunctionPass.h" 18#include "llvm/CodeGen/MachineInstrBuilder.h" 19#include "llvm/Support/CommandLine.h" 20#include "llvm/Target/TargetMachine.h" 21#include "llvm/Target/TargetInstrInfo.h" 22#include "llvm/Target/TargetRegisterInfo.h" 23#include "llvm/ADT/SmallSet.h" 24#include "llvm/ADT/Statistic.h" 25 26using namespace llvm; 27 28STATISTIC(FilledSlots, "Number of delay slots filled"); 29 30static 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 36namespace { 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 83 }; 84 char Filler::ID = 0; 85} // end of anonymous namespace 86 87/// createSparcDelaySlotFillerPass - Returns a pass that fills in delay 88/// slots in Sparc MachineFunctions 89/// 90FunctionPass *llvm::createSparcDelaySlotFillerPass(TargetMachine &tm) { 91 return new Filler(tm); 92} 93 94/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 95/// We assume there is only one delay slot per delayed instruction. 96/// 97bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 98 bool Changed = false; 99 100 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) 101 if (I->getDesc().hasDelaySlot()) { 102 MachineBasicBlock::iterator D = MBB.end(); 103 MachineBasicBlock::iterator J = I; 104 105 if (!DisableDelaySlotFiller) 106 D = findDelayInstr(MBB, I); 107 108 ++FilledSlots; 109 Changed = true; 110 111 if (D == MBB.end()) 112 BuildMI(MBB, ++J, I->getDebugLoc(), TII->get(SP::NOP)); 113 else 114 MBB.splice(++J, &MBB, D); 115 } 116 return Changed; 117} 118 119MachineBasicBlock::iterator 120Filler::findDelayInstr(MachineBasicBlock &MBB, 121 MachineBasicBlock::iterator slot) 122{ 123 SmallSet<unsigned, 32> RegDefs; 124 SmallSet<unsigned, 32> RegUses; 125 bool sawLoad = false; 126 bool sawStore = false; 127 128 MachineBasicBlock::iterator I = slot; 129 130 if (slot->getOpcode() == SP::RET) 131 return MBB.end(); 132 133 if (slot->getOpcode() == SP::RETL) { 134 --I; 135 if (I->getOpcode() != SP::RESTORErr) 136 return MBB.end(); 137 //change retl to ret 138 slot->setDesc(TII->get(SP::RET)); 139 return I; 140 } 141 142 //Call's delay filler can def some of call's uses. 143 if (slot->getDesc().isCall()) 144 insertCallUses(slot, RegUses); 145 else 146 insertDefsUses(slot, RegDefs, RegUses); 147 148 bool done = false; 149 150 while (!done) { 151 done = (I == MBB.begin()); 152 153 if (!done) 154 --I; 155 156 // skip debug value 157 if (I->isDebugValue()) 158 continue; 159 160 161 if (I->hasUnmodeledSideEffects() 162 || I->isInlineAsm() 163 || I->isLabel() 164 || I->getDesc().hasDelaySlot() 165 || isDelayFiller(MBB, I)) 166 break; 167 168 if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) { 169 insertDefsUses(I, RegDefs, RegUses); 170 continue; 171 } 172 173 return I; 174 } 175 return MBB.end(); 176} 177 178bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate, 179 bool &sawLoad, 180 bool &sawStore, 181 SmallSet<unsigned, 32> &RegDefs, 182 SmallSet<unsigned, 32> &RegUses) 183{ 184 185 if (candidate->getDesc().mayLoad()) { 186 sawLoad = true; 187 if (sawStore) 188 return true; 189 } 190 191 if (candidate->getDesc().mayStore()) { 192 if (sawStore) 193 return true; 194 sawStore = true; 195 if (sawLoad) 196 return true; 197 } 198 199 for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) { 200 const MachineOperand &MO = candidate->getOperand(i); 201 if (!MO.isReg()) 202 continue; // skip 203 204 unsigned Reg = MO.getReg(); 205 206 if (MO.isDef()) { 207 //check whether Reg is defined or used before delay slot. 208 if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg)) 209 return true; 210 } 211 if (MO.isUse()) { 212 //check whether Reg is defined before delay slot. 213 if (IsRegInSet(RegDefs, Reg)) 214 return true; 215 } 216 } 217 return false; 218} 219 220 221void Filler::insertCallUses(MachineBasicBlock::iterator MI, 222 SmallSet<unsigned, 32>& RegUses) 223{ 224 225 switch(MI->getOpcode()) { 226 default: llvm_unreachable("Unknown opcode."); 227 case SP::CALL: break; 228 case SP::JMPLrr: 229 case SP::JMPLri: 230 assert(MI->getNumOperands() >= 2); 231 const MachineOperand &Reg = MI->getOperand(0); 232 assert(Reg.isReg() && "JMPL first operand is not a register."); 233 assert(Reg.isUse() && "JMPL first operand is not a use."); 234 RegUses.insert(Reg.getReg()); 235 236 const MachineOperand &RegOrImm = MI->getOperand(1); 237 if (RegOrImm.isImm()) 238 break; 239 assert(RegOrImm.isReg() && "JMPLrr second operand is not a register."); 240 assert(RegOrImm.isUse() && "JMPLrr second operand is not a use."); 241 RegUses.insert(RegOrImm.getReg()); 242 break; 243 } 244} 245 246//Insert Defs and Uses of MI into the sets RegDefs and RegUses. 247void Filler::insertDefsUses(MachineBasicBlock::iterator MI, 248 SmallSet<unsigned, 32>& RegDefs, 249 SmallSet<unsigned, 32>& RegUses) 250{ 251 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 252 const MachineOperand &MO = MI->getOperand(i); 253 if (!MO.isReg()) 254 continue; 255 256 unsigned Reg = MO.getReg(); 257 if (Reg == 0) 258 continue; 259 if (MO.isDef()) 260 RegDefs.insert(Reg); 261 if (MO.isUse()) 262 RegUses.insert(Reg); 263 264 } 265} 266 267//returns true if the Reg or its alias is in the RegSet. 268bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) 269{ 270 if (RegSet.count(Reg)) 271 return true; 272 // check Aliased Registers 273 for (const unsigned *Alias = TM.getRegisterInfo()->getAliasSet(Reg); 274 *Alias; ++ Alias) 275 if (RegSet.count(*Alias)) 276 return true; 277 278 return false; 279} 280 281// return true if the candidate is a delay filler. 282bool Filler::isDelayFiller(MachineBasicBlock &MBB, 283 MachineBasicBlock::iterator candidate) 284{ 285 if (candidate == MBB.begin()) 286 return false; 287 const TargetInstrDesc &prevdesc = (--candidate)->getDesc(); 288 return prevdesc.hasDelaySlot(); 289} 290