blob: 1073532c30eb1586f2df946e7bb79527fc226d00 [file] [log] [blame]
Wesley Pecka70f28c2010-02-23 19:15:24 +00001//===-- 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//
Wesley Pecka0603832010-10-27 00:23:01 +000010// 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.
Wesley Pecka70f28c2010-02-23 19:15:24 +000012//
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"
Wesley Peck4e9141f2010-10-21 03:57:26 +000023#include "llvm/Support/CommandLine.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/Support/raw_ostream.h"
Wesley Pecka70f28c2010-02-23 19:15:24 +000027
28using namespace llvm;
29
30STATISTIC(FilledSlots, "Number of delay slots filled");
31
Wesley Peck1e8cdd52010-12-06 21:11:01 +000032namespace llvm {
33cl::opt<bool> DisableDelaySlotFiller(
34 "disable-mblaze-delay-filler",
35 cl::init(false),
36 cl::desc("Disable the MBlaze delay slot filter."),
37 cl::Hidden);
38}
39
Wesley Pecka70f28c2010-02-23 19:15:24 +000040namespace {
41 struct Filler : public MachineFunctionPass {
42
43 TargetMachine &TM;
44 const TargetInstrInfo *TII;
45
46 static char ID;
Wesley Peck0a67d922010-11-08 19:40:01 +000047 Filler(TargetMachine &tm)
Owen Anderson90c579d2010-08-06 18:33:48 +000048 : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { }
Wesley Pecka70f28c2010-02-23 19:15:24 +000049
50 virtual const char *getPassName() const {
51 return "MBlaze 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 };
64 char Filler::ID = 0;
65} // end of anonymous namespace
66
Wesley Peck0a67d922010-11-08 19:40:01 +000067static bool hasImmInstruction(MachineBasicBlock::iterator &candidate) {
Wesley Peck4e9141f2010-10-21 03:57:26 +000068 // Any instruction with an immediate mode operand greater than
69 // 16-bits requires an implicit IMM instruction.
70 unsigned numOper = candidate->getNumOperands();
Wesley Peck0a67d922010-11-08 19:40:01 +000071 for (unsigned op = 0; op < numOper; ++op) {
Wesley Peck1e8cdd52010-12-06 21:11:01 +000072 MachineOperand &mop = candidate->getOperand(op);
73
74 // The operand requires more than 16-bits to represent.
75 if (mop.isImm() && (mop.getImm() < -0x8000 || mop.getImm() > 0x7fff))
76 return true;
77
78 // We must assume that unknown immediate values require more than
79 // 16-bits to represent.
80 if (mop.isGlobal() || mop.isSymbol())
81 return true;
Wesley Peck4e9141f2010-10-21 03:57:26 +000082
83 // FIXME: we could probably check to see if the FP value happens
84 // to not need an IMM instruction. For now we just always
Wesley Peck1e8cdd52010-12-06 21:11:01 +000085 // assume that FP values do.
86 if (mop.isFPImm())
87 return true;
Wesley Peck4e9141f2010-10-21 03:57:26 +000088 }
89
90 return false;
91}
92
Wesley Peck0a67d922010-11-08 19:40:01 +000093static bool delayHasHazard(MachineBasicBlock::iterator &candidate,
94 MachineBasicBlock::iterator &slot) {
Wesley Peck1e8cdd52010-12-06 21:11:01 +000095 // Hazard check
96 MachineBasicBlock::iterator a = candidate;
97 MachineBasicBlock::iterator b = slot;
98 TargetInstrDesc desc = candidate->getDesc();
Wesley Peck4e9141f2010-10-21 03:57:26 +000099
Wesley Peck1e8cdd52010-12-06 21:11:01 +0000100 // MBB layout:-
101 // candidate := a0 = operation(a1, a2)
102 // ...middle bit...
103 // slot := b0 = operation(b1, b2)
104
105 // Possible hazards:-/
106 // 1. a1 or a2 was written during the middle bit
107 // 2. a0 was read or written during the middle bit
108 // 3. a0 is one or more of {b0, b1, b2}
109 // 4. b0 is one or more of {a1, a2}
110 // 5. a accesses memory, and the middle bit
111 // contains a store operation.
112 bool a_is_memory = desc.mayLoad() || desc.mayStore();
113
114 // Check hazards type 1, 2 and 5 by scanning the middle bit
115 MachineBasicBlock::iterator m = a;
116 for (++m; m != b; ++m) {
117 for (unsigned aop = 0, aend = a->getNumOperands(); aop<aend; ++aop) {
118 bool aop_is_reg = a->getOperand(aop).isReg();
119 if (!aop_is_reg) continue;
120
121 bool aop_is_def = a->getOperand(aop).isDef();
122 unsigned aop_reg = a->getOperand(aop).getReg();
123
124 for (unsigned mop = 0, mend = m->getNumOperands(); mop<mend; ++mop) {
125 bool mop_is_reg = m->getOperand(mop).isReg();
126 if (!mop_is_reg) continue;
127
128 bool mop_is_def = m->getOperand(mop).isDef();
129 unsigned mop_reg = m->getOperand(mop).getReg();
130
131 if (aop_is_def && (mop_reg == aop_reg))
132 return true; // Hazard type 2, because aop = a0
133 else if (mop_is_def && (mop_reg == aop_reg))
134 return true; // Hazard type 1, because aop in {a1, a2}
135 }
Wesley Peck4e9141f2010-10-21 03:57:26 +0000136 }
137
Wesley Peck1e8cdd52010-12-06 21:11:01 +0000138 // Check hazard type 5
139 if (a_is_memory && m->getDesc().mayStore())
140 return true;
141 }
Wesley Peck4e9141f2010-10-21 03:57:26 +0000142
Wesley Peck1e8cdd52010-12-06 21:11:01 +0000143 // Check hazard type 3 & 4
144 for (unsigned aop = 0, aend = a->getNumOperands(); aop<aend; ++aop) {
145 if (a->getOperand(aop).isReg()) {
146 unsigned aop_reg = a->getOperand(aop).getReg();
147
148 for (unsigned bop = 0, bend = b->getNumOperands(); bop<bend; ++bop) {
149 if (b->getOperand(bop).isReg() && (!b->getOperand(bop).isImplicit())) {
150 unsigned bop_reg = b->getOperand(bop).getReg();
151 if (aop_reg == bop_reg)
152 return true;
Wesley Peck4e9141f2010-10-21 03:57:26 +0000153 }
Wesley Peck1e8cdd52010-12-06 21:11:01 +0000154 }
155 }
Wesley Peck4e9141f2010-10-21 03:57:26 +0000156 }
157
158 return false;
159}
160
Wesley Peck5437ba42010-11-21 21:36:12 +0000161static bool isDelayFiller(MachineBasicBlock &MBB,
162 MachineBasicBlock::iterator candidate) {
163 if (candidate == MBB.begin())
164 return false;
Wesley Peck4e9141f2010-10-21 03:57:26 +0000165
Wesley Peck5437ba42010-11-21 21:36:12 +0000166 TargetInstrDesc brdesc = (--candidate)->getDesc();
167 return (brdesc.hasDelaySlot());
168}
169
Wesley Peck8f40b242010-12-12 22:22:49 +0000170static bool hasUnknownSideEffects(MachineBasicBlock::iterator &I,
171 TargetInstrDesc &desc) {
172 if (!desc.hasUnmodeledSideEffects())
173 return false;
174
175 unsigned op = I->getOpcode();
176 if (op == MBlaze::ADDK || op == MBlaze::ADDIK ||
177 op == MBlaze::ADDC || op == MBlaze::ADDIC ||
178 op == MBlaze::ADDKC || op == MBlaze::ADDIKC ||
179 op == MBlaze::RSUBK || op == MBlaze::RSUBIK ||
180 op == MBlaze::RSUBC || op == MBlaze::RSUBIC ||
181 op == MBlaze::RSUBKC || op == MBlaze::RSUBIKC)
182 return false;
183
184 return true;
185}
186
Wesley Peck5437ba42010-11-21 21:36:12 +0000187static MachineBasicBlock::iterator
188findDelayInstr(MachineBasicBlock &MBB,MachineBasicBlock::iterator slot) {
189 MachineBasicBlock::iterator I = slot;
190 while (true) {
191 if (I == MBB.begin())
192 break;
193
194 --I;
195 TargetInstrDesc desc = I->getDesc();
Wesley Peck1e8cdd52010-12-06 21:11:01 +0000196 if (desc.hasDelaySlot() || desc.isBranch() || isDelayFiller(MBB,I) ||
197 desc.isCall() || desc.isReturn() || desc.isBarrier() ||
Wesley Peck8f40b242010-12-12 22:22:49 +0000198 hasUnknownSideEffects(I,desc))
Wesley Peck5437ba42010-11-21 21:36:12 +0000199 break;
200
Wesley Peck1e8cdd52010-12-06 21:11:01 +0000201 if (hasImmInstruction(I) || delayHasHazard(I,slot))
Wesley Peck5437ba42010-11-21 21:36:12 +0000202 continue;
203
204 return I;
Wesley Peck4e9141f2010-10-21 03:57:26 +0000205 }
206
Wesley Peck5437ba42010-11-21 21:36:12 +0000207 return MBB.end();
Wesley Peck4e9141f2010-10-21 03:57:26 +0000208}
209
Wesley Pecka70f28c2010-02-23 19:15:24 +0000210/// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
211/// Currently, we fill delay slots with NOPs. We assume there is only one
212/// delay slot per delayed instruction.
213bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) {
214 bool Changed = false;
215 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I)
216 if (I->getDesc().hasDelaySlot()) {
Wesley Peck1e8cdd52010-12-06 21:11:01 +0000217 MachineBasicBlock::iterator D = MBB.end();
Wesley Peck5437ba42010-11-21 21:36:12 +0000218 MachineBasicBlock::iterator J = I;
Wesley Peck4e9141f2010-10-21 03:57:26 +0000219
Wesley Peck1e8cdd52010-12-06 21:11:01 +0000220 if (!DisableDelaySlotFiller)
221 D = findDelayInstr(MBB,I);
222
Wesley Pecka70f28c2010-02-23 19:15:24 +0000223 ++FilledSlots;
224 Changed = true;
Wesley Peck4e9141f2010-10-21 03:57:26 +0000225
Wesley Peck0a67d922010-11-08 19:40:01 +0000226 if (D == MBB.end())
Wesley Peck5437ba42010-11-21 21:36:12 +0000227 BuildMI(MBB, ++J, I->getDebugLoc(), TII->get(MBlaze::NOP));
Wesley Peck4e9141f2010-10-21 03:57:26 +0000228 else
Wesley Peck5437ba42010-11-21 21:36:12 +0000229 MBB.splice(++J, &MBB, D);
Wesley Pecka70f28c2010-02-23 19:15:24 +0000230 }
231 return Changed;
232}
233
234/// createMBlazeDelaySlotFillerPass - Returns a pass that fills in delay
235/// slots in MBlaze MachineFunctions
236FunctionPass *llvm::createMBlazeDelaySlotFillerPass(MBlazeTargetMachine &tm) {
237 return new Filler(tm);
238}
239