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