LLVM API Documentation
00001 //===-- PPCHazardRecognizers.cpp - PowerPC Hazard Recognizer Impls --------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements hazard recognizers for scheduling on PowerPC processors. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "PPCHazardRecognizers.h" 00015 #include "PPC.h" 00016 #include "PPCInstrInfo.h" 00017 #include "PPCTargetMachine.h" 00018 #include "llvm/CodeGen/ScheduleDAG.h" 00019 #include "llvm/Support/Debug.h" 00020 #include "llvm/Support/ErrorHandling.h" 00021 #include "llvm/Support/raw_ostream.h" 00022 using namespace llvm; 00023 00024 #define DEBUG_TYPE "pre-RA-sched" 00025 00026 bool PPCDispatchGroupSBHazardRecognizer::isLoadAfterStore(SUnit *SU) { 00027 // FIXME: Move this. 00028 if (isBCTRAfterSet(SU)) 00029 return true; 00030 00031 const MCInstrDesc *MCID = DAG->getInstrDesc(SU); 00032 if (!MCID) 00033 return false; 00034 00035 if (!MCID->mayLoad()) 00036 return false; 00037 00038 // SU is a load; for any predecessors in this dispatch group, that are stores, 00039 // and with which we have an ordering dependency, return true. 00040 for (unsigned i = 0, ie = (unsigned) SU->Preds.size(); i != ie; ++i) { 00041 const MCInstrDesc *PredMCID = DAG->getInstrDesc(SU->Preds[i].getSUnit()); 00042 if (!PredMCID || !PredMCID->mayStore()) 00043 continue; 00044 00045 if (!SU->Preds[i].isNormalMemory() && !SU->Preds[i].isBarrier()) 00046 continue; 00047 00048 for (unsigned j = 0, je = CurGroup.size(); j != je; ++j) 00049 if (SU->Preds[i].getSUnit() == CurGroup[j]) 00050 return true; 00051 } 00052 00053 return false; 00054 } 00055 00056 bool PPCDispatchGroupSBHazardRecognizer::isBCTRAfterSet(SUnit *SU) { 00057 const MCInstrDesc *MCID = DAG->getInstrDesc(SU); 00058 if (!MCID) 00059 return false; 00060 00061 if (!MCID->isBranch()) 00062 return false; 00063 00064 // SU is a branch; for any predecessors in this dispatch group, with which we 00065 // have a data dependence and set the counter register, return true. 00066 for (unsigned i = 0, ie = (unsigned) SU->Preds.size(); i != ie; ++i) { 00067 const MCInstrDesc *PredMCID = DAG->getInstrDesc(SU->Preds[i].getSUnit()); 00068 if (!PredMCID || PredMCID->getSchedClass() != PPC::Sched::IIC_SprMTSPR) 00069 continue; 00070 00071 if (SU->Preds[i].isCtrl()) 00072 continue; 00073 00074 for (unsigned j = 0, je = CurGroup.size(); j != je; ++j) 00075 if (SU->Preds[i].getSUnit() == CurGroup[j]) 00076 return true; 00077 } 00078 00079 return false; 00080 } 00081 00082 // FIXME: Remove this when we don't need this: 00083 namespace llvm { namespace PPC { extern int getNonRecordFormOpcode(uint16_t); } } 00084 00085 // FIXME: A lot of code in PPCDispatchGroupSBHazardRecognizer is P7 specific. 00086 00087 bool PPCDispatchGroupSBHazardRecognizer::mustComeFirst(const MCInstrDesc *MCID, 00088 unsigned &NSlots) { 00089 // FIXME: Indirectly, this information is contained in the itinerary, and 00090 // we should derive it from there instead of separately specifying it 00091 // here. 00092 unsigned IIC = MCID->getSchedClass(); 00093 switch (IIC) { 00094 default: 00095 NSlots = 1; 00096 break; 00097 case PPC::Sched::IIC_IntDivW: 00098 case PPC::Sched::IIC_IntDivD: 00099 case PPC::Sched::IIC_LdStLoadUpd: 00100 case PPC::Sched::IIC_LdStLDU: 00101 case PPC::Sched::IIC_LdStLFDU: 00102 case PPC::Sched::IIC_LdStLFDUX: 00103 case PPC::Sched::IIC_LdStLHA: 00104 case PPC::Sched::IIC_LdStLHAU: 00105 case PPC::Sched::IIC_LdStLWA: 00106 case PPC::Sched::IIC_LdStSTDU: 00107 case PPC::Sched::IIC_LdStSTFDU: 00108 NSlots = 2; 00109 break; 00110 case PPC::Sched::IIC_LdStLoadUpdX: 00111 case PPC::Sched::IIC_LdStLDUX: 00112 case PPC::Sched::IIC_LdStLHAUX: 00113 case PPC::Sched::IIC_LdStLWARX: 00114 case PPC::Sched::IIC_LdStLDARX: 00115 case PPC::Sched::IIC_LdStSTDUX: 00116 case PPC::Sched::IIC_LdStSTDCX: 00117 case PPC::Sched::IIC_LdStSTWCX: 00118 case PPC::Sched::IIC_BrMCRX: // mtcr 00119 // FIXME: Add sync/isync (here and in the itinerary). 00120 NSlots = 4; 00121 break; 00122 } 00123 00124 // FIXME: record-form instructions need a different itinerary class. 00125 if (NSlots == 1 && PPC::getNonRecordFormOpcode(MCID->getOpcode()) != -1) 00126 NSlots = 2; 00127 00128 switch (IIC) { 00129 default: 00130 // All multi-slot instructions must come first. 00131 return NSlots > 1; 00132 case PPC::Sched::IIC_BrCR: // cr logicals 00133 case PPC::Sched::IIC_SprMFCR: 00134 case PPC::Sched::IIC_SprMFCRF: 00135 case PPC::Sched::IIC_SprMTSPR: 00136 return true; 00137 } 00138 } 00139 00140 ScheduleHazardRecognizer::HazardType 00141 PPCDispatchGroupSBHazardRecognizer::getHazardType(SUnit *SU, int Stalls) { 00142 if (Stalls == 0 && isLoadAfterStore(SU)) 00143 return NoopHazard; 00144 00145 return ScoreboardHazardRecognizer::getHazardType(SU, Stalls); 00146 } 00147 00148 bool PPCDispatchGroupSBHazardRecognizer::ShouldPreferAnother(SUnit *SU) { 00149 const MCInstrDesc *MCID = DAG->getInstrDesc(SU); 00150 unsigned NSlots; 00151 if (MCID && mustComeFirst(MCID, NSlots) && CurSlots) 00152 return true; 00153 00154 return ScoreboardHazardRecognizer::ShouldPreferAnother(SU); 00155 } 00156 00157 unsigned PPCDispatchGroupSBHazardRecognizer::PreEmitNoops(SUnit *SU) { 00158 // We only need to fill out a maximum of 5 slots here: The 6th slot could 00159 // only be a second branch, and otherwise the next instruction will start a 00160 // new group. 00161 if (isLoadAfterStore(SU) && CurSlots < 6) { 00162 unsigned Directive = 00163 DAG->TM.getSubtarget<PPCSubtarget>().getDarwinDirective(); 00164 // If we're using a special group-terminating nop, then we need only one. 00165 if (Directive == PPC::DIR_PWR6 || Directive == PPC::DIR_PWR7 || 00166 Directive == PPC::DIR_PWR8 ) 00167 return 1; 00168 00169 return 5 - CurSlots; 00170 } 00171 00172 return ScoreboardHazardRecognizer::PreEmitNoops(SU); 00173 } 00174 00175 void PPCDispatchGroupSBHazardRecognizer::EmitInstruction(SUnit *SU) { 00176 const MCInstrDesc *MCID = DAG->getInstrDesc(SU); 00177 if (MCID) { 00178 if (CurSlots == 5 || (MCID->isBranch() && CurBranches == 1)) { 00179 CurGroup.clear(); 00180 CurSlots = CurBranches = 0; 00181 } else { 00182 DEBUG(dbgs() << "**** Adding to dispatch group: SU(" << 00183 SU->NodeNum << "): "); 00184 DEBUG(DAG->dumpNode(SU)); 00185 00186 unsigned NSlots; 00187 bool MustBeFirst = mustComeFirst(MCID, NSlots); 00188 00189 // If this instruction must come first, but does not, then it starts a 00190 // new group. 00191 if (MustBeFirst && CurSlots) { 00192 CurSlots = CurBranches = 0; 00193 CurGroup.clear(); 00194 } 00195 00196 CurSlots += NSlots; 00197 CurGroup.push_back(SU); 00198 00199 if (MCID->isBranch()) 00200 ++CurBranches; 00201 } 00202 } 00203 00204 return ScoreboardHazardRecognizer::EmitInstruction(SU); 00205 } 00206 00207 void PPCDispatchGroupSBHazardRecognizer::AdvanceCycle() { 00208 return ScoreboardHazardRecognizer::AdvanceCycle(); 00209 } 00210 00211 void PPCDispatchGroupSBHazardRecognizer::RecedeCycle() { 00212 llvm_unreachable("Bottom-up scheduling not supported"); 00213 } 00214 00215 void PPCDispatchGroupSBHazardRecognizer::Reset() { 00216 CurGroup.clear(); 00217 CurSlots = CurBranches = 0; 00218 return ScoreboardHazardRecognizer::Reset(); 00219 } 00220 00221 void PPCDispatchGroupSBHazardRecognizer::EmitNoop() { 00222 unsigned Directive = 00223 DAG->TM.getSubtarget<PPCSubtarget>().getDarwinDirective(); 00224 // If the group has now filled all of its slots, or if we're using a special 00225 // group-terminating nop, the group is complete. 00226 if (Directive == PPC::DIR_PWR6 || Directive == PPC::DIR_PWR7 || 00227 Directive == PPC::DIR_PWR8 || CurSlots == 6) { 00228 CurGroup.clear(); 00229 CurSlots = CurBranches = 0; 00230 } else { 00231 CurGroup.push_back(nullptr); 00232 ++CurSlots; 00233 } 00234 } 00235 00236 //===----------------------------------------------------------------------===// 00237 // PowerPC 970 Hazard Recognizer 00238 // 00239 // This models the dispatch group formation of the PPC970 processor. Dispatch 00240 // groups are bundles of up to five instructions that can contain various mixes 00241 // of instructions. The PPC970 can dispatch a peak of 4 non-branch and one 00242 // branch instruction per-cycle. 00243 // 00244 // There are a number of restrictions to dispatch group formation: some 00245 // instructions can only be issued in the first slot of a dispatch group, & some 00246 // instructions fill an entire dispatch group. Additionally, only branches can 00247 // issue in the 5th (last) slot. 00248 // 00249 // Finally, there are a number of "structural" hazards on the PPC970. These 00250 // conditions cause large performance penalties due to misprediction, recovery, 00251 // and replay logic that has to happen. These cases include setting a CTR and 00252 // branching through it in the same dispatch group, and storing to an address, 00253 // then loading from the same address within a dispatch group. To avoid these 00254 // conditions, we insert no-op instructions when appropriate. 00255 // 00256 // FIXME: This is missing some significant cases: 00257 // 1. Modeling of microcoded instructions. 00258 // 2. Handling of serialized operations. 00259 // 3. Handling of the esoteric cases in "Resource-based Instruction Grouping". 00260 // 00261 00262 PPCHazardRecognizer970::PPCHazardRecognizer970(const ScheduleDAG &DAG) 00263 : DAG(DAG) { 00264 EndDispatchGroup(); 00265 } 00266 00267 void PPCHazardRecognizer970::EndDispatchGroup() { 00268 DEBUG(errs() << "=== Start of dispatch group\n"); 00269 NumIssued = 0; 00270 00271 // Structural hazard info. 00272 HasCTRSet = false; 00273 NumStores = 0; 00274 } 00275 00276 00277 PPCII::PPC970_Unit 00278 PPCHazardRecognizer970::GetInstrType(unsigned Opcode, 00279 bool &isFirst, bool &isSingle, 00280 bool &isCracked, 00281 bool &isLoad, bool &isStore) { 00282 const MCInstrDesc &MCID = DAG.TII->get(Opcode); 00283 00284 isLoad = MCID.mayLoad(); 00285 isStore = MCID.mayStore(); 00286 00287 uint64_t TSFlags = MCID.TSFlags; 00288 00289 isFirst = TSFlags & PPCII::PPC970_First; 00290 isSingle = TSFlags & PPCII::PPC970_Single; 00291 isCracked = TSFlags & PPCII::PPC970_Cracked; 00292 return (PPCII::PPC970_Unit)(TSFlags & PPCII::PPC970_Mask); 00293 } 00294 00295 /// isLoadOfStoredAddress - If we have a load from the previously stored pointer 00296 /// as indicated by StorePtr1/StorePtr2/StoreSize, return true. 00297 bool PPCHazardRecognizer970:: 00298 isLoadOfStoredAddress(uint64_t LoadSize, int64_t LoadOffset, 00299 const Value *LoadValue) const { 00300 for (unsigned i = 0, e = NumStores; i != e; ++i) { 00301 // Handle exact and commuted addresses. 00302 if (LoadValue == StoreValue[i] && LoadOffset == StoreOffset[i]) 00303 return true; 00304 00305 // Okay, we don't have an exact match, if this is an indexed offset, see if 00306 // we have overlap (which happens during fp->int conversion for example). 00307 if (StoreValue[i] == LoadValue) { 00308 // Okay the base pointers match, so we have [c1+r] vs [c2+r]. Check 00309 // to see if the load and store actually overlap. 00310 if (StoreOffset[i] < LoadOffset) { 00311 if (int64_t(StoreOffset[i]+StoreSize[i]) > LoadOffset) return true; 00312 } else { 00313 if (int64_t(LoadOffset+LoadSize) > StoreOffset[i]) return true; 00314 } 00315 } 00316 } 00317 return false; 00318 } 00319 00320 /// getHazardType - We return hazard for any non-branch instruction that would 00321 /// terminate the dispatch group. We turn NoopHazard for any 00322 /// instructions that wouldn't terminate the dispatch group that would cause a 00323 /// pipeline flush. 00324 ScheduleHazardRecognizer::HazardType PPCHazardRecognizer970:: 00325 getHazardType(SUnit *SU, int Stalls) { 00326 assert(Stalls == 0 && "PPC hazards don't support scoreboard lookahead"); 00327 00328 MachineInstr *MI = SU->getInstr(); 00329 00330 if (MI->isDebugValue()) 00331 return NoHazard; 00332 00333 unsigned Opcode = MI->getOpcode(); 00334 bool isFirst, isSingle, isCracked, isLoad, isStore; 00335 PPCII::PPC970_Unit InstrType = 00336 GetInstrType(Opcode, isFirst, isSingle, isCracked, 00337 isLoad, isStore); 00338 if (InstrType == PPCII::PPC970_Pseudo) return NoHazard; 00339 00340 // We can only issue a PPC970_First/PPC970_Single instruction (such as 00341 // crand/mtspr/etc) if this is the first cycle of the dispatch group. 00342 if (NumIssued != 0 && (isFirst || isSingle)) 00343 return Hazard; 00344 00345 // If this instruction is cracked into two ops by the decoder, we know that 00346 // it is not a branch and that it cannot issue if 3 other instructions are 00347 // already in the dispatch group. 00348 if (isCracked && NumIssued > 2) 00349 return Hazard; 00350 00351 switch (InstrType) { 00352 default: llvm_unreachable("Unknown instruction type!"); 00353 case PPCII::PPC970_FXU: 00354 case PPCII::PPC970_LSU: 00355 case PPCII::PPC970_FPU: 00356 case PPCII::PPC970_VALU: 00357 case PPCII::PPC970_VPERM: 00358 // We can only issue a branch as the last instruction in a group. 00359 if (NumIssued == 4) return Hazard; 00360 break; 00361 case PPCII::PPC970_CRU: 00362 // We can only issue a CR instruction in the first two slots. 00363 if (NumIssued >= 2) return Hazard; 00364 break; 00365 case PPCII::PPC970_BRU: 00366 break; 00367 } 00368 00369 // Do not allow MTCTR and BCTRL to be in the same dispatch group. 00370 if (HasCTRSet && Opcode == PPC::BCTRL) 00371 return NoopHazard; 00372 00373 // If this is a load following a store, make sure it's not to the same or 00374 // overlapping address. 00375 if (isLoad && NumStores && !MI->memoperands_empty()) { 00376 MachineMemOperand *MO = *MI->memoperands_begin(); 00377 if (isLoadOfStoredAddress(MO->getSize(), 00378 MO->getOffset(), MO->getValue())) 00379 return NoopHazard; 00380 } 00381 00382 return NoHazard; 00383 } 00384 00385 void PPCHazardRecognizer970::EmitInstruction(SUnit *SU) { 00386 MachineInstr *MI = SU->getInstr(); 00387 00388 if (MI->isDebugValue()) 00389 return; 00390 00391 unsigned Opcode = MI->getOpcode(); 00392 bool isFirst, isSingle, isCracked, isLoad, isStore; 00393 PPCII::PPC970_Unit InstrType = 00394 GetInstrType(Opcode, isFirst, isSingle, isCracked, 00395 isLoad, isStore); 00396 if (InstrType == PPCII::PPC970_Pseudo) return; 00397 00398 // Update structural hazard information. 00399 if (Opcode == PPC::MTCTR || Opcode == PPC::MTCTR8) HasCTRSet = true; 00400 00401 // Track the address stored to. 00402 if (isStore && NumStores < 4 && !MI->memoperands_empty()) { 00403 MachineMemOperand *MO = *MI->memoperands_begin(); 00404 StoreSize[NumStores] = MO->getSize(); 00405 StoreOffset[NumStores] = MO->getOffset(); 00406 StoreValue[NumStores] = MO->getValue(); 00407 ++NumStores; 00408 } 00409 00410 if (InstrType == PPCII::PPC970_BRU || isSingle) 00411 NumIssued = 4; // Terminate a d-group. 00412 ++NumIssued; 00413 00414 // If this instruction is cracked into two ops by the decoder, remember that 00415 // we issued two pieces. 00416 if (isCracked) 00417 ++NumIssued; 00418 00419 if (NumIssued == 5) 00420 EndDispatchGroup(); 00421 } 00422 00423 void PPCHazardRecognizer970::AdvanceCycle() { 00424 assert(NumIssued < 5 && "Illegal dispatch group!"); 00425 ++NumIssued; 00426 if (NumIssued == 5) 00427 EndDispatchGroup(); 00428 } 00429 00430 void PPCHazardRecognizer970::Reset() { 00431 EndDispatchGroup(); 00432 } 00433