1 //===-- DelaySlotFiller.cpp - Mips delay slot filler ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Simple pass to fills delay slots with useful instructions.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "delay-slot-filler"
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"
29 STATISTIC(FilledSlots, "Number of delay slots filled");
31 static cl::opt<bool> EnableDelaySlotFiller(
32 "enable-mips-delay-filler",
34 cl::desc("Fill the Mips delay slots useful instructions."),
38 struct Filler : public MachineFunctionPass {
41 const TargetInstrInfo *TII;
44 Filler(TargetMachine &tm)
45 : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { }
47 virtual const char *getPassName() const {
48 return "Mips Delay Slot Filler";
51 bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
52 bool runOnMachineFunction(MachineFunction &F) {
54 for (MachineFunction::iterator FI = F.begin(), FE = F.end();
56 Changed |= runOnMachineBasicBlock(*FI);
60 bool isDelayFiller(MachineBasicBlock &MBB,
61 MachineBasicBlock::iterator candidate);
63 void insertCallUses(MachineBasicBlock::iterator MI,
64 SmallSet<unsigned, 32>& RegDefs,
65 SmallSet<unsigned, 32>& RegUses);
67 void insertDefsUses(MachineBasicBlock::iterator MI,
68 SmallSet<unsigned, 32>& RegDefs,
69 SmallSet<unsigned, 32>& RegUses);
71 bool IsRegInSet(SmallSet<unsigned, 32>& RegSet,
74 bool delayHasHazard(MachineBasicBlock::iterator candidate,
75 bool &sawLoad, bool &sawStore,
76 SmallSet<unsigned, 32> &RegDefs,
77 SmallSet<unsigned, 32> &RegUses);
79 MachineBasicBlock::iterator
80 findDelayInstr(MachineBasicBlock &MBB, MachineBasicBlock::iterator slot);
85 } // end of anonymous namespace
87 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
88 /// We assume there is only one delay slot per delayed instruction.
90 runOnMachineBasicBlock(MachineBasicBlock &MBB) {
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;
97 if (EnableDelaySlotFiller)
98 D = findDelayInstr(MBB, I);
104 BuildMI(MBB, ++J, I->getDebugLoc(), TII->get(Mips::NOP));
106 MBB.splice(++J, &MBB, D);
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);
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;
126 MachineBasicBlock::iterator I = slot;
128 // Call's delay filler can def some of call's uses.
129 if (slot->getDesc().isCall())
130 insertCallUses(slot, RegDefs, RegUses);
132 insertDefsUses(slot, RegDefs, RegUses);
137 done = (I == MBB.begin());
143 if (I->isDebugValue())
146 if (I->hasUnmodeledSideEffects()
149 || I->getDesc().hasDelaySlot()
150 || isDelayFiller(MBB, I)
151 || I->getDesc().isPseudo()
154 // ERET, DERET or WAIT, PAUSE. Need to add these to instruction
159 if (delayHasHazard(I, sawLoad, sawStore, RegDefs, RegUses)) {
160 insertDefsUses(I, RegDefs, RegUses);
169 bool Filler::delayHasHazard(MachineBasicBlock::iterator candidate,
172 SmallSet<unsigned, 32> &RegDefs,
173 SmallSet<unsigned, 32> &RegUses) {
174 if (candidate->isImplicitDef() || candidate->isKill())
177 // Loads or stores cannot be moved past a store to the delay slot
178 // and stores cannot be moved past a load.
179 if (candidate->getDesc().mayLoad()) {
185 if (candidate->getDesc().mayStore()) {
193 for (unsigned i = 0, e = candidate->getNumOperands(); i!= e; ++i) {
194 const MachineOperand &MO = candidate->getOperand(i);
198 unsigned Reg = MO.getReg();
201 // check whether Reg is defined or used before delay slot.
202 if (IsRegInSet(RegDefs, Reg) || IsRegInSet(RegUses, Reg))
206 // check whether Reg is defined before delay slot.
207 if (IsRegInSet(RegDefs, Reg))
214 void Filler::insertCallUses(MachineBasicBlock::iterator MI,
215 SmallSet<unsigned, 32>& RegDefs,
216 SmallSet<unsigned, 32>& RegUses) {
217 switch(MI->getOpcode()) {
218 default: llvm_unreachable("Unknown opcode.");
223 assert(MI->getNumOperands() >= 1);
224 const MachineOperand &Reg = MI->getOperand(0);
225 assert(Reg.isReg() && "JALR first operand is not a register.");
226 RegUses.insert(Reg.getReg());
232 // Insert Defs and Uses of MI into the sets RegDefs and RegUses.
233 void Filler::insertDefsUses(MachineBasicBlock::iterator MI,
234 SmallSet<unsigned, 32>& RegDefs,
235 SmallSet<unsigned, 32>& RegUses) {
236 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
237 const MachineOperand &MO = MI->getOperand(i);
241 unsigned Reg = MO.getReg();
251 //returns true if the Reg or its alias is in the RegSet.
252 bool Filler::IsRegInSet(SmallSet<unsigned, 32>& RegSet, unsigned Reg) {
253 if (RegSet.count(Reg))
255 // check Aliased Registers
256 for (const unsigned *Alias = TM.getRegisterInfo()->getAliasSet(Reg);
258 if (RegSet.count(*Alias))
264 // return true if the candidate is a delay filler.
265 bool Filler::isDelayFiller(MachineBasicBlock &MBB,
266 MachineBasicBlock::iterator candidate) {
267 if (candidate == MBB.begin())
269 const MCInstrDesc &prevdesc = (--candidate)->getDesc();
270 return prevdesc.hasDelaySlot();