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 27using namespace llvm; 28 29STATISTIC(FilledSlots, "Number of delay slots filled"); 30STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 31 " are not NOP."); 32 33static 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 39namespace { 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. 93bool Filler:: 94runOnMachineBasicBlock(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 122FunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 123 return new Filler(tm); 124} 125 126bool Filler::findDelayInstr(MachineBasicBlock &MBB, 127 MachineBasicBlock::iterator slot, 128 MachineBasicBlock::iterator &Filler) { 129 SmallSet<unsigned, 32> RegDefs; 130 SmallSet<unsigned, 32> RegUses; 131 132 insertDefsUses(slot, RegDefs, RegUses); 133 134 bool sawLoad = false; 135 bool sawStore = false; 136 137 for (MachineBasicBlock::reverse_iterator I(slot); I != MBB.rend(); ++I) { 138 // skip debug value 139 if (I->isDebugValue()) 140 continue; 141 142 // Convert to forward iterator. 143 MachineBasicBlock::iterator FI(llvm::next(I).base()); 144 145 if (I->hasUnmodeledSideEffects() 146 || I->isInlineAsm() 147 || I->isLabel() 148 || FI == LastFiller 149 || I->getDesc().isPseudo() 150 // 151 // Should not allow: 152 // ERET, DERET or WAIT, PAUSE. Need to add these to instruction 153 // list. TBD. 154 ) 155 break; 156 157 if (delayHasHazard(FI, sawLoad, sawStore, RegDefs, RegUses)) { 158 insertDefsUses(FI, RegDefs, RegUses); 159 continue; 160 } 161 162 Filler = FI; 163 return true; 164 } 165 166 return false; 167} 168 169bool 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 MCInstrDesc MCID = candidate->getDesc(); 178 // Loads or stores cannot be moved past a store to the delay slot 179 // and stores cannot be moved past a load. 180 if (MCID.mayLoad()) { 181 if (sawStore) 182 return true; 183 sawLoad = true; 184 } 185 186 if (MCID.mayStore()) { 187 if (sawStore) 188 return true; 189 sawStore = true; 190 if (sawLoad) 191 return true; 192 } 193 194 assert((!MCID.isCall() && !MCID.isReturn()) && 195 "Cannot put calls or returns in delay slot."); 196 197 for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) { 198 const MachineOperand &MO = candidate->getOperand(i); 199 unsigned Reg; 200 201 if (!MO.isReg() || !(Reg = MO.getReg())) 202 continue; // skip 203 204 if (MO.isDef()) { 205 // check whether Reg is defined or used before delay slot. 206 if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg)) 207 return true; 208 } 209 if (MO.isUse()) { 210 // check whether Reg is defined before delay slot. 211 if (IsRegInSet(RegDefs, Reg)) 212 return true; 213 } 214 } 215 return false; 216} 217 218// Insert Defs and Uses of MI into the sets RegDefs and RegUses. 219void Filler::insertDefsUses(MachineBasicBlock::iterator MI, 220 SmallSet<unsigned, 32>& RegDefs, 221 SmallSet<unsigned, 32>& RegUses) { 222 // If MI is a call or return, just examine the explicit non-variadic operands. 223 MCInstrDesc MCID = MI->getDesc(); 224 unsigned e = MCID.isCall() || MCID.isReturn() ? MCID.getNumOperands() : 225 MI->getNumOperands(); 226 227 // Add RA to RegDefs to prevent users of RA from going into delay slot. 228 if (MCID.isCall()) 229 RegDefs.insert(Mips::RA); 230 231 for (unsigned i = 0; i != e; ++i) { 232 const MachineOperand &MO = MI->getOperand(i); 233 unsigned Reg; 234 235 if (!MO.isReg() || !(Reg = MO.getReg())) 236 continue; 237 238 if (MO.isDef()) 239 RegDefs.insert(Reg); 240 else if (MO.isUse()) 241 RegUses.insert(Reg); 242 } 243} 244 245//returns true if the Reg or its alias is in the RegSet. 246bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) { 247 if (RegSet.count(Reg)) 248 return true; 249 // check Aliased Registers 250 for (const unsigned *Alias = TM.getRegisterInfo()->getAliasSet(Reg); 251 *Alias; ++Alias) 252 if (RegSet.count(*Alias)) 253 return true; 254 255 return false; 256} 257