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