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 namespace llvm { 33 cl::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 40 namespace { 41 struct Filler : public MachineFunctionPass { 42 43 TargetMachine &TM; 44 const TargetInstrInfo *TII; 45 46 static char ID; 47 Filler(TargetMachine &tm) 48 : MachineFunctionPass(ID), TM(tm), TII(tm.getInstrInfo()) { } 49 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 67 static bool hasImmInstruction(MachineBasicBlock::iterator &candidate) { 68 // Any instruction with an immediate mode operand greater than 69 // 16-bits requires an implicit IMM instruction. 70 unsigned numOper = candidate->getNumOperands(); 71 for (unsigned op = 0; op < numOper; ++op) { 72 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() || mop.isJTI() || mop.isCPI()) 81 return true; 82 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 85 // assume that FP values do. 86 if (mop.isFPImm()) 87 return true; 88 } 89 90 return false; 91 } 92 93 static unsigned getLastRealOperand(MachineBasicBlock::iterator &instr) { 94 switch (instr->getOpcode()) { 95 default: return instr->getNumOperands(); 96 97 // These instructions have a variable number of operands but the first two 98 // are the "real" operands that we care about during hazard detection. 99 case MBlaze::BRLID: 100 case MBlaze::BRALID: 101 case MBlaze::BRLD: 102 case MBlaze::BRALD: 103 return 2; 104 } 105 } 106 107 static bool delayHasHazard(MachineBasicBlock::iterator &candidate, 108 MachineBasicBlock::iterator &slot) { 109 // Hazard check 110 MachineBasicBlock::iterator a = candidate; 111 MachineBasicBlock::iterator b = slot; 112 MCInstrDesc desc = candidate->getDesc(); 113 114 // MBB layout:- 115 // candidate := a0 = operation(a1, a2) 116 // ...middle bit... 117 // slot := b0 = operation(b1, b2) 118 119 // Possible hazards:-/ 120 // 1. a1 or a2 was written during the middle bit 121 // 2. a0 was read or written during the middle bit 122 // 3. a0 is one or more of {b0, b1, b2} 123 // 4. b0 is one or more of {a1, a2} 124 // 5. a accesses memory, and the middle bit 125 // contains a store operation. 126 bool a_is_memory = desc.mayLoad() || desc.mayStore(); 127 128 // Determine the number of operands in the slot instruction and in the 129 // candidate instruction. 130 const unsigned aend = getLastRealOperand(a); 131 const unsigned bend = getLastRealOperand(b); 132 133 // Check hazards type 1, 2 and 5 by scanning the middle bit 134 MachineBasicBlock::iterator m = a; 135 for (++m; m != b; ++m) { 136 for (unsigned aop = 0; aop<aend; ++aop) { 137 bool aop_is_reg = a->getOperand(aop).isReg(); 138 if (!aop_is_reg) continue; 139 140 bool aop_is_def = a->getOperand(aop).isDef(); 141 unsigned aop_reg = a->getOperand(aop).getReg(); 142 143 const unsigned mend = getLastRealOperand(m); 144 for (unsigned mop = 0; mop<mend; ++mop) { 145 bool mop_is_reg = m->getOperand(mop).isReg(); 146 if (!mop_is_reg) continue; 147 148 bool mop_is_def = m->getOperand(mop).isDef(); 149 unsigned mop_reg = m->getOperand(mop).getReg(); 150 151 if (aop_is_def && (mop_reg == aop_reg)) 152 return true; // Hazard type 2, because aop = a0 153 else if (mop_is_def && (mop_reg == aop_reg)) 154 return true; // Hazard type 1, because aop in {a1, a2} 155 } 156 } 157 158 // Check hazard type 5 159 if (a_is_memory && m->getDesc().mayStore()) 160 return true; 161 } 162 163 // Check hazard type 3 & 4 164 for (unsigned aop = 0; aop<aend; ++aop) { 165 if (a->getOperand(aop).isReg()) { 166 unsigned aop_reg = a->getOperand(aop).getReg(); 167 168 for (unsigned bop = 0; bop<bend; ++bop) { 169 if (b->getOperand(bop).isReg() && !b->getOperand(bop).isImplicit()) { 170 unsigned bop_reg = b->getOperand(bop).getReg(); 171 if (aop_reg == bop_reg) 172 return true; 173 } 174 } 175 } 176 } 177 178 return false; 179 } 180 181 static bool isDelayFiller(MachineBasicBlock &MBB, 182 MachineBasicBlock::iterator candidate) { 183 if (candidate == MBB.begin()) 184 return false; 185 186 MCInstrDesc brdesc = (--candidate)->getDesc(); 187 return (brdesc.hasDelaySlot()); 188 } 189 190 static bool hasUnknownSideEffects(MachineBasicBlock::iterator &I) { 191 if (!I->hasUnmodeledSideEffects()) 192 return false; 193 194 unsigned op = I->getOpcode(); 195 if (op == MBlaze::ADDK || op == MBlaze::ADDIK || 196 op == MBlaze::ADDC || op == MBlaze::ADDIC || 197 op == MBlaze::ADDKC || op == MBlaze::ADDIKC || 198 op == MBlaze::RSUBK || op == MBlaze::RSUBIK || 199 op == MBlaze::RSUBC || op == MBlaze::RSUBIC || 200 op == MBlaze::RSUBKC || op == MBlaze::RSUBIKC) 201 return false; 202 203 return true; 204 } 205 206 static MachineBasicBlock::iterator 207 findDelayInstr(MachineBasicBlock &MBB,MachineBasicBlock::iterator slot) { 208 MachineBasicBlock::iterator I = slot; 209 while (true) { 210 if (I == MBB.begin()) 211 break; 212 213 --I; 214 MCInstrDesc desc = I->getDesc(); 215 if (desc.hasDelaySlot() || desc.isBranch() || isDelayFiller(MBB,I) || 216 desc.isCall() || desc.isReturn() || desc.isBarrier() || 217 hasUnknownSideEffects(I)) 218 break; 219 220 if (hasImmInstruction(I) || delayHasHazard(I,slot)) 221 continue; 222 223 return I; 224 } 225 226 return MBB.end(); 227 } 228 229 /// runOnMachineBasicBlock - Fill in delay slots for the given basic block. 230 /// Currently, we fill delay slots with NOPs. We assume there is only one 231 /// delay slot per delayed instruction. 232 bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { 233 bool Changed = false; 234 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) 235 if (I->getDesc().hasDelaySlot()) { 236 MachineBasicBlock::iterator D = MBB.end(); 237 MachineBasicBlock::iterator J = I; 238 239 if (!DisableDelaySlotFiller) 240 D = findDelayInstr(MBB,I); 241 242 ++FilledSlots; 243 Changed = true; 244 245 if (D == MBB.end()) 246 BuildMI(MBB, ++J, I->getDebugLoc(), TII->get(MBlaze::NOP)); 247 else 248 MBB.splice(++J, &MBB, D); 249 } 250 return Changed; 251 } 252 253 /// createMBlazeDelaySlotFillerPass - Returns a pass that fills in delay 254 /// slots in MBlaze MachineFunctions 255 FunctionPass *llvm::createMBlazeDelaySlotFillerPass(MBlazeTargetMachine &tm) { 256 return new Filler(tm); 257 } 258 259
