1 //===-- DelaySlotFiller.cpp - MBlaze 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 // A pass that attempts to fill instructions with delay slots. If no
11 // instructions can be moved into the delay slot then a NOP is placed there.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #define DEBUG_TYPE "delay-slot-filler"
16
17 #include "MBlaze.h"
18 #include "MBlazeTargetMachine.h"
19 #include "llvm/CodeGen/MachineFunctionPass.h"
20 #include "llvm/CodeGen/MachineInstrBuilder.h"
21 #include "llvm/Target/TargetInstrInfo.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/Support/CommandLine.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/ErrorHandling.h"
26 #include "llvm/Support/raw_ostream.h"
27
28 using namespace llvm;
29
30 STATISTIC(FilledSlots, "Number of delay slots filled");
31
32 static cl::opt<bool> MBDisableDelaySlotFiller(
33 "disable-mblaze-delay-filler",
34 cl::init(false),
35 cl::desc("Disable the MBlaze delay slot filter."),
36 cl::Hidden);
37
38 namespace {
39 struct Filler : public MachineFunctionPass {
40
41 TargetMachine &TM;
42 const TargetInstrInfo *TII;
43
44 static char ID;
Filler__anon55d02d020111::Filler45 Filler(TargetMachine &tm)
46 : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { }
47
getPassName__anon55d02d020111::Filler48 virtual const char *getPassName() const {
49 return "MBlaze Delay Slot Filler";
50 }
51
52 bool runOnMachineBasicBlock(MachineBasicBlock &MBB);
runOnMachineFunction__anon55d02d020111::Filler53 bool runOnMachineFunction(MachineFunction &F) {
54 bool Changed = false;
55 for (MachineFunction::iterator FI = F.begin(), FE = F.end();
56 FI != FE; ++FI)
57 Changed |= runOnMachineBasicBlock(*FI);
58 return Changed;
59 }
60
61 };
62 char Filler::ID = 0;
63 } // end of anonymous namespace
64
hasImmInstruction(MachineBasicBlock::iterator & candidate)65 static bool hasImmInstruction(MachineBasicBlock::iterator &candidate) {
66 // Any instruction with an immediate mode operand greater than
67 // 16-bits requires an implicit IMM instruction.
68 unsigned numOper = candidate->getNumOperands();
69 for (unsigned op = 0; op < numOper; ++op) {
70 MachineOperand &mop = candidate->getOperand(op);
71
72 // The operand requires more than 16-bits to represent.
73 if (mop.isImm() && (mop.getImm() < -0x8000 || mop.getImm() > 0x7fff))
74 return true;
75
76 // We must assume that unknown immediate values require more than
77 // 16-bits to represent.
78 if (mop.isGlobal() || mop.isSymbol() || mop.isJTI() || mop.isCPI())
79 return true;
80
81 // FIXME: we could probably check to see if the FP value happens
82 // to not need an IMM instruction. For now we just always
83 // assume that FP values do.
84 if (mop.isFPImm())
85 return true;
86 }
87
88 return false;
89 }
90
getLastRealOperand(MachineBasicBlock::iterator & instr)91 static unsigned getLastRealOperand(MachineBasicBlock::iterator &instr) {
92 switch (instr->getOpcode()) {
93 default: return instr->getNumOperands();
94
95 // These instructions have a variable number of operands but the first two
96 // are the "real" operands that we care about during hazard detection.
97 case MBlaze::BRLID:
98 case MBlaze::BRALID:
99 case MBlaze::BRLD:
100 case MBlaze::BRALD:
101 return 2;
102 }
103 }
104
delayHasHazard(MachineBasicBlock::iterator & candidate,MachineBasicBlock::iterator & slot)105 static bool delayHasHazard(MachineBasicBlock::iterator &candidate,
106 MachineBasicBlock::iterator &slot) {
107 // Hazard check
108 MachineBasicBlock::iterator a = candidate;
109 MachineBasicBlock::iterator b = slot;
110
111 // MBB layout:-
112 // candidate := a0 = operation(a1, a2)
113 // ...middle bit...
114 // slot := b0 = operation(b1, b2)
115
116 // Possible hazards:-/
117 // 1. a1 or a2 was written during the middle bit
118 // 2. a0 was read or written during the middle bit
119 // 3. a0 is one or more of {b0, b1, b2}
120 // 4. b0 is one or more of {a1, a2}
121 // 5. a accesses memory, and the middle bit
122 // contains a store operation.
123 bool a_is_memory = candidate->mayLoad() || candidate->mayStore();
124
125 // Determine the number of operands in the slot instruction and in the
126 // candidate instruction.
127 const unsigned aend = getLastRealOperand(a);
128 const unsigned bend = getLastRealOperand(b);
129
130 // Check hazards type 1, 2 and 5 by scanning the middle bit
131 MachineBasicBlock::iterator m = a;
132 for (++m; m != b; ++m) {
133 for (unsigned aop = 0; aop<aend; ++aop) {
134 bool aop_is_reg = a->getOperand(aop).isReg();
135 if (!aop_is_reg) continue;
136
137 bool aop_is_def = a->getOperand(aop).isDef();
138 unsigned aop_reg = a->getOperand(aop).getReg();
139
140 const unsigned mend = getLastRealOperand(m);
141 for (unsigned mop = 0; mop<mend; ++mop) {
142 bool mop_is_reg = m->getOperand(mop).isReg();
143 if (!mop_is_reg) continue;
144
145 bool mop_is_def = m->getOperand(mop).isDef();
146 unsigned mop_reg = m->getOperand(mop).getReg();
147
148 if (aop_is_def && (mop_reg == aop_reg))
149 return true; // Hazard type 2, because aop = a0
150 else if (mop_is_def && (mop_reg == aop_reg))
151 return true; // Hazard type 1, because aop in {a1, a2}
152 }
153 }
154
155 // Check hazard type 5
156 if (a_is_memory && m->mayStore())
157 return true;
158 }
159
160 // Check hazard type 3 & 4
161 for (unsigned aop = 0; aop<aend; ++aop) {
162 if (a->getOperand(aop).isReg()) {
163 unsigned aop_reg = a->getOperand(aop).getReg();
164
165 for (unsigned bop = 0; bop<bend; ++bop) {
166 if (b->getOperand(bop).isReg() && !b->getOperand(bop).isImplicit()) {
167 unsigned bop_reg = b->getOperand(bop).getReg();
168 if (aop_reg == bop_reg)
169 return true;
170 }
171 }
172 }
173 }
174
175 return false;
176 }
177
isDelayFiller(MachineBasicBlock & MBB,MachineBasicBlock::iterator candidate)178 static bool isDelayFiller(MachineBasicBlock &MBB,
179 MachineBasicBlock::iterator candidate) {
180 if (candidate == MBB.begin())
181 return false;
182
183 --candidate;
184 return (candidate->hasDelaySlot());
185 }
186
hasUnknownSideEffects(MachineBasicBlock::iterator & I)187 static bool hasUnknownSideEffects(MachineBasicBlock::iterator &I) {
188 if (!I->hasUnmodeledSideEffects())
189 return false;
190
191 unsigned op = I->getOpcode();
192 if (op == MBlaze::ADDK || op == MBlaze::ADDIK ||
193 op == MBlaze::ADDC || op == MBlaze::ADDIC ||
194 op == MBlaze::ADDKC || op == MBlaze::ADDIKC ||
195 op == MBlaze::RSUBK || op == MBlaze::RSUBIK ||
196 op == MBlaze::RSUBC || op == MBlaze::RSUBIC ||
197 op == MBlaze::RSUBKC || op == MBlaze::RSUBIKC)
198 return false;
199
200 return true;
201 }
202
203 static MachineBasicBlock::iterator
findDelayInstr(MachineBasicBlock & MBB,MachineBasicBlock::iterator slot)204 findDelayInstr(MachineBasicBlock &MBB,MachineBasicBlock::iterator slot) {
205 MachineBasicBlock::iterator I = slot;
206 while (true) {
207 if (I == MBB.begin())
208 break;
209
210 --I;
211 if (I->hasDelaySlot() || I->isBranch() || isDelayFiller(MBB,I) ||
212 I->isCall() || I->isReturn() || I->isBarrier() ||
213 hasUnknownSideEffects(I))
214 break;
215
216 if (hasImmInstruction(I) || delayHasHazard(I,slot))
217 continue;
218
219 return I;
220 }
221
222 return MBB.end();
223 }
224
225 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
226 /// Currently, we fill delay slots with NOPs. We assume there is only one
227 /// delay slot per delayed instruction.
runOnMachineBasicBlock(MachineBasicBlock & MBB)228 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
229 bool Changed = false;
230 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I)
231 if (I->hasDelaySlot()) {
232 MachineBasicBlock::iterator D = MBB.end();
233 MachineBasicBlock::iterator J = I;
234
235 if (!MBDisableDelaySlotFiller)
236 D = findDelayInstr(MBB,I);
237
238 ++FilledSlots;
239 Changed = true;
240
241 if (D == MBB.end())
242 BuildMI(MBB, ++J, I->getDebugLoc(), TII->get(MBlaze::NOP));
243 else
244 MBB.splice(++J, &MBB, D);
245 }
246 return Changed;
247 }
248
249 /// createMBlazeDelaySlotFillerPass - Returns a pass that fills in delay
250 /// slots in MBlaze MachineFunctions
createMBlazeDelaySlotFillerPass(MBlazeTargetMachine & tm)251 FunctionPass *llvm::createMBlazeDelaySlotFillerPass(MBlazeTargetMachine &tm) {
252 return new Filler(tm);
253 }
254
255