MipsDelaySlotFiller.cpp revision 243830
1234353Sdim//===-- DelaySlotFiller.cpp - Mips Delay Slot Filler ----------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10226633Sdim// Simple pass to fills delay slots with useful instructions. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#define DEBUG_TYPE "delay-slot-filler" 15193323Sed 16193323Sed#include "Mips.h" 17193323Sed#include "MipsTargetMachine.h" 18193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 19193323Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 20226633Sdim#include "llvm/Support/CommandLine.h" 21226633Sdim#include "llvm/Target/TargetMachine.h" 22193323Sed#include "llvm/Target/TargetInstrInfo.h" 23226633Sdim#include "llvm/Target/TargetRegisterInfo.h" 24226633Sdim#include "llvm/ADT/SmallSet.h" 25193323Sed#include "llvm/ADT/Statistic.h" 26193323Sed 27193323Sedusing namespace llvm; 28193323Sed 29193323SedSTATISTIC(FilledSlots, "Number of delay slots filled"); 30226633SdimSTATISTIC(UsefulSlots, "Number of delay slots filled with instructions that" 31226633Sdim " are not NOP."); 32193323Sed 33243830Sdimstatic cl::opt<bool> DisableDelaySlotFiller( 34243830Sdim "disable-mips-delay-filler", 35226633Sdim cl::init(false), 36243830Sdim cl::desc("Disable the delay slot filler, which attempts to fill the Mips" 37243830Sdim "delay slots with useful instructions."), 38226633Sdim cl::Hidden); 39226633Sdim 40239462Sdim// This option can be used to silence complaints by machine verifier passes. 41239462Sdimstatic cl::opt<bool> SkipDelaySlotFiller( 42239462Sdim "skip-mips-delay-filler", 43239462Sdim cl::init(false), 44239462Sdim cl::desc("Skip MIPS' delay slot filling pass."), 45239462Sdim cl::Hidden); 46239462Sdim 47193323Sednamespace { 48193323Sed struct Filler : public MachineFunctionPass { 49239462Sdim typedef MachineBasicBlock::instr_iterator InstrIter; 50239462Sdim typedef MachineBasicBlock::reverse_instr_iterator ReverseInstrIter; 51193323Sed 52193323Sed TargetMachine &TM; 53193323Sed const TargetInstrInfo *TII; 54239462Sdim InstrIter LastFiller; 55193323Sed 56193323Sed static char ID; 57218893Sdim Filler(TargetMachine &tm) 58212904Sdim : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } 59193323Sed 60193323Sed virtual const char *getPassName() const { 61193323Sed return "Mips Delay Slot Filler"; 62193323Sed } 63193323Sed 64193323Sed bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 65193323Sed bool runOnMachineFunction(MachineFunction &F) { 66239462Sdim if (SkipDelaySlotFiller) 67239462Sdim return false; 68239462Sdim 69193323Sed bool Changed = false; 70193323Sed for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 71193323Sed FI != FE; ++FI) 72193323Sed Changed |= runOnMachineBasicBlock(*FI); 73193323Sed return Changed; 74193323Sed } 75193323Sed 76226633Sdim bool isDelayFiller(MachineBasicBlock &MBB, 77239462Sdim InstrIter candidate); 78226633Sdim 79239462Sdim void insertCallUses(InstrIter MI, 80239462Sdim SmallSet<unsigned, 32> &RegDefs, 81239462Sdim SmallSet<unsigned, 32> &RegUses); 82226633Sdim 83239462Sdim void insertDefsUses(InstrIter MI, 84239462Sdim SmallSet<unsigned, 32> &RegDefs, 85239462Sdim SmallSet<unsigned, 32> &RegUses); 86226633Sdim 87239462Sdim bool IsRegInSet(SmallSet<unsigned, 32> &RegSet, 88226633Sdim unsigned Reg); 89226633Sdim 90239462Sdim bool delayHasHazard(InstrIter candidate, 91226633Sdim bool &sawLoad, bool &sawStore, 92226633Sdim SmallSet<unsigned, 32> &RegDefs, 93226633Sdim SmallSet<unsigned, 32> &RegUses); 94226633Sdim 95226633Sdim bool 96239462Sdim findDelayInstr(MachineBasicBlock &MBB, InstrIter slot, 97239462Sdim InstrIter &Filler); 98226633Sdim 99226633Sdim 100193323Sed }; 101193323Sed char Filler::ID = 0; 102193323Sed} // end of anonymous namespace 103193323Sed 104193323Sed/// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 105226633Sdim/// We assume there is only one delay slot per delayed instruction. 106193323Sedbool Filler:: 107226633SdimrunOnMachineBasicBlock(MachineBasicBlock &MBB) { 108193323Sed bool Changed = false; 109239462Sdim LastFiller = MBB.instr_end(); 110226633Sdim 111239462Sdim for (InstrIter I = MBB.instr_begin(); I != MBB.instr_end(); ++I) 112234353Sdim if (I->hasDelaySlot()) { 113193323Sed ++FilledSlots; 114193323Sed Changed = true; 115218893Sdim 116239462Sdim InstrIter D; 117226633Sdim 118243830Sdim // Delay slot filling is disabled at -O0. 119243830Sdim if (!DisableDelaySlotFiller && (TM.getOptLevel() != CodeGenOpt::None) && 120243830Sdim findDelayInstr(MBB, I, D)) { 121226633Sdim MBB.splice(llvm::next(I), &MBB, D); 122226633Sdim ++UsefulSlots; 123234353Sdim } else 124226633Sdim BuildMI(MBB, llvm::next(I), I->getDebugLoc(), TII->get(Mips::NOP)); 125226633Sdim 126226633Sdim // Record the filler instruction that filled the delay slot. 127226633Sdim // The instruction after it will be visited in the next iteration. 128226633Sdim LastFiller = ++I; 129239462Sdim 130239462Sdim // Set InsideBundle bit so that the machine verifier doesn't expect this 131239462Sdim // instruction to be a terminator. 132239462Sdim LastFiller->setIsInsideBundle(); 133226633Sdim } 134193323Sed return Changed; 135226633Sdim 136193323Sed} 137193323Sed 138193323Sed/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay 139193323Sed/// slots in Mips MachineFunctions 140193323SedFunctionPass *llvm::createMipsDelaySlotFillerPass(MipsTargetMachine &tm) { 141193323Sed return new Filler(tm); 142193323Sed} 143193323Sed 144226633Sdimbool Filler::findDelayInstr(MachineBasicBlock &MBB, 145239462Sdim InstrIter slot, 146239462Sdim InstrIter &Filler) { 147226633Sdim SmallSet<unsigned, 32> RegDefs; 148226633Sdim SmallSet<unsigned, 32> RegUses; 149226633Sdim 150226633Sdim insertDefsUses(slot, RegDefs, RegUses); 151226633Sdim 152226633Sdim bool sawLoad = false; 153226633Sdim bool sawStore = false; 154226633Sdim 155239462Sdim for (ReverseInstrIter I(slot); I != MBB.instr_rend(); ++I) { 156226633Sdim // skip debug value 157226633Sdim if (I->isDebugValue()) 158226633Sdim continue; 159226633Sdim 160226633Sdim // Convert to forward iterator. 161239462Sdim InstrIter FI(llvm::next(I).base()); 162226633Sdim 163226633Sdim if (I->hasUnmodeledSideEffects() 164226633Sdim || I->isInlineAsm() 165226633Sdim || I->isLabel() 166226633Sdim || FI == LastFiller 167234353Sdim || I->isPseudo() 168226633Sdim // 169226633Sdim // Should not allow: 170226633Sdim // ERET, DERET or WAIT, PAUSE. Need to add these to instruction 171226633Sdim // list. TBD. 172226633Sdim ) 173226633Sdim break; 174226633Sdim 175226633Sdim if (delayHasHazard(FI, sawLoad, sawStore, RegDefs, RegUses)) { 176226633Sdim insertDefsUses(FI, RegDefs, RegUses); 177226633Sdim continue; 178226633Sdim } 179226633Sdim 180226633Sdim Filler = FI; 181226633Sdim return true; 182226633Sdim } 183226633Sdim 184226633Sdim return false; 185226633Sdim} 186226633Sdim 187239462Sdimbool Filler::delayHasHazard(InstrIter candidate, 188234353Sdim bool &sawLoad, bool &sawStore, 189226633Sdim SmallSet<unsigned, 32> &RegDefs, 190226633Sdim SmallSet<unsigned, 32> &RegUses) { 191226633Sdim if (candidate->isImplicitDef() || candidate->isKill()) 192226633Sdim return true; 193226633Sdim 194226633Sdim // Loads or stores cannot be moved past a store to the delay slot 195234353Sdim // and stores cannot be moved past a load. 196234353Sdim if (candidate->mayLoad()) { 197226633Sdim if (sawStore) 198226633Sdim return true; 199226633Sdim sawLoad = true; 200226633Sdim } 201226633Sdim 202234353Sdim if (candidate->mayStore()) { 203226633Sdim if (sawStore) 204226633Sdim return true; 205226633Sdim sawStore = true; 206226633Sdim if (sawLoad) 207226633Sdim return true; 208226633Sdim } 209226633Sdim 210234353Sdim assert((!candidate->isCall() && !candidate->isReturn()) && 211226633Sdim "Cannot put calls or returns in delay slot."); 212226633Sdim 213226633Sdim for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) { 214226633Sdim const MachineOperand &MO = candidate->getOperand(i); 215226633Sdim unsigned Reg; 216226633Sdim 217226633Sdim if (!MO.isReg() || !(Reg = MO.getReg())) 218226633Sdim continue; // skip 219226633Sdim 220226633Sdim if (MO.isDef()) { 221226633Sdim // check whether Reg is defined or used before delay slot. 222226633Sdim if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg)) 223226633Sdim return true; 224226633Sdim } 225226633Sdim if (MO.isUse()) { 226226633Sdim // check whether Reg is defined before delay slot. 227226633Sdim if (IsRegInSet(RegDefs, Reg)) 228226633Sdim return true; 229226633Sdim } 230226633Sdim } 231226633Sdim return false; 232226633Sdim} 233226633Sdim 234226633Sdim// Insert Defs and Uses of MI into the sets RegDefs and RegUses. 235239462Sdimvoid Filler::insertDefsUses(InstrIter MI, 236239462Sdim SmallSet<unsigned, 32> &RegDefs, 237239462Sdim SmallSet<unsigned, 32> &RegUses) { 238226633Sdim // If MI is a call or return, just examine the explicit non-variadic operands. 239226633Sdim MCInstrDesc MCID = MI->getDesc(); 240234353Sdim unsigned e = MI->isCall() || MI->isReturn() ? MCID.getNumOperands() : 241234353Sdim MI->getNumOperands(); 242234353Sdim 243234353Sdim // Add RA to RegDefs to prevent users of RA from going into delay slot. 244234353Sdim if (MI->isCall()) 245226633Sdim RegDefs.insert(Mips::RA); 246226633Sdim 247226633Sdim for (unsigned i = 0; i != e; ++i) { 248226633Sdim const MachineOperand &MO = MI->getOperand(i); 249226633Sdim unsigned Reg; 250226633Sdim 251226633Sdim if (!MO.isReg() || !(Reg = MO.getReg())) 252226633Sdim continue; 253226633Sdim 254226633Sdim if (MO.isDef()) 255226633Sdim RegDefs.insert(Reg); 256226633Sdim else if (MO.isUse()) 257226633Sdim RegUses.insert(Reg); 258226633Sdim } 259226633Sdim} 260226633Sdim 261226633Sdim//returns true if the Reg or its alias is in the RegSet. 262239462Sdimbool Filler::IsRegInSet(SmallSet<unsigned, 32> &RegSet, unsigned Reg) { 263239462Sdim // Check Reg and all aliased Registers. 264239462Sdim for (MCRegAliasIterator AI(Reg, TM.getRegisterInfo(), true); 265239462Sdim AI.isValid(); ++AI) 266239462Sdim if (RegSet.count(*AI)) 267226633Sdim return true; 268226633Sdim return false; 269226633Sdim} 270