LLVM API Documentation

PPCHazardRecognizers.cpp
Go to the documentation of this file.
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