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; 45 Filler(TargetMachine &tm) 46 : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } 47 48 virtual const char *getPassName() const { 49 return "MBlaze Delay Slot Filler"; 50 } 51 52 bool runOnMachineBasicBlock(MachineBasicBlock &MBB); 53 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 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 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 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 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 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 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. 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 251 FunctionPass *llvm::createMBlazeDelaySlotFillerPass(MBlazeTargetMachine &tm) { 252 return new Filler(tm); 253 } 254 255