lib/Target/PowerPC/PPCHazardRecognizers.cpp

   1 //===-- PPCHazardRecognizers.cpp - PowerPC Hazard Recognizer Impls --------===//
   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 // This file implements hazard recognizers for scheduling on PowerPC processors.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "pre-RA-sched"
  15 #include "PPCHazardRecognizers.h"
  16 #include "PPC.h"
  17 #include "PPCInstrInfo.h"
  18 #include "PPCTargetMachine.h"
  19 #include "llvm/CodeGen/ScheduleDAG.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/ErrorHandling.h"
  22 #include "llvm/Support/raw_ostream.h"
  23 using namespace llvm;
  24
  25 bool PPCDispatchGroupSBHazardRecognizer::isLoadAfterStore(SUnit *SU) {
  26   // FIXME: Move this.
  27   if (isBCTRAfterSet(SU))
  28     return true;
  29
  30   const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
  31   if (!MCID)
  32     return false;
  33
  34   if (!MCID->mayLoad())
  35     return false;
  36
  37   // SU is a load; for any predecessors in this dispatch group, that are stores,
  38   // and with which we have an ordering dependency, return true.
  39   for (unsigned i = 0, ie = (unsigned) SU->Preds.size(); i != ie; ++i) {
  40     const MCInstrDesc *PredMCID = DAG->getInstrDesc(SU->Preds[i].getSUnit());
  41     if (!PredMCID || !PredMCID->mayStore())
  42       continue;
  43
  44     if (!SU->Preds[i].isNormalMemory() && !SU->Preds[i].isBarrier())
  45       continue;
  46
  47     for (unsigned j = 0, je = CurGroup.size(); j != je; ++j)
  48       if (SU->Preds[i].getSUnit() == CurGroup[j])
  49         return true;
  50   }
  51
  52   return false;
  53 }
  54
  55 bool PPCDispatchGroupSBHazardRecognizer::isBCTRAfterSet(SUnit *SU) {
  56   const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
  57   if (!MCID)
  58     return false;
  59
  60   if (!MCID->isBranch())
  61     return false;
  62
  63   // SU is a branch; for any predecessors in this dispatch group, with which we
  64   // have a data dependence and set the counter register, return true.
  65   for (unsigned i = 0, ie = (unsigned) SU->Preds.size(); i != ie; ++i) {
  66     const MCInstrDesc *PredMCID = DAG->getInstrDesc(SU->Preds[i].getSUnit());
  67     if (!PredMCID || PredMCID->getSchedClass() != PPC::Sched::IIC_SprMTSPR)
  68       continue;
  69
  70     if (SU->Preds[i].isCtrl())
  71       continue;
  72
  73     for (unsigned j = 0, je = CurGroup.size(); j != je; ++j)
  74       if (SU->Preds[i].getSUnit() == CurGroup[j])
  75         return true;
  76   }
  77
  78   return false;
  79 }
  80
  81 // FIXME: Remove this when we don't need this:
  82 namespace llvm { namespace PPC { extern int getNonRecordFormOpcode(uint16_t); } }
  83
  84 // FIXME: A lot of code in PPCDispatchGroupSBHazardRecognizer is P7 specific.
  85
  86 bool PPCDispatchGroupSBHazardRecognizer::mustComeFirst(const MCInstrDesc *MCID,
  87                                                        unsigned &NSlots) {
  88   // FIXME: Indirectly, this information is contained in the itinerary, and
  89   // we should derive it from there instead of separately specifying it
  90   // here.
  91   unsigned IIC = MCID->getSchedClass();
  92   switch (IIC) {
  93   default:
  94     NSlots = 1;
  95     break;
  96   case PPC::Sched::IIC_IntDivW:
  97   case PPC::Sched::IIC_IntDivD:
  98   case PPC::Sched::IIC_LdStLoadUpd:
  99   case PPC::Sched::IIC_LdStLDU:
 100   case PPC::Sched::IIC_LdStLFDU:
 101   case PPC::Sched::IIC_LdStLFDUX:
 102   case PPC::Sched::IIC_LdStLHA:
 103   case PPC::Sched::IIC_LdStLHAU:
 104   case PPC::Sched::IIC_LdStLWA:
 105   case PPC::Sched::IIC_LdStSTDU:
 106   case PPC::Sched::IIC_LdStSTFDU:
 107     NSlots = 2;
 108     break;
 109   case PPC::Sched::IIC_LdStLoadUpdX:
 110   case PPC::Sched::IIC_LdStLDUX:
 111   case PPC::Sched::IIC_LdStLHAUX:
 112   case PPC::Sched::IIC_LdStLWARX:
 113   case PPC::Sched::IIC_LdStLDARX:
 114   case PPC::Sched::IIC_LdStSTDUX:
 115   case PPC::Sched::IIC_LdStSTDCX:
 116   case PPC::Sched::IIC_LdStSTWCX:
 117   case PPC::Sched::IIC_BrMCRX: // mtcr
 118   // FIXME: Add sync/isync (here and in the itinerary).
 119     NSlots = 4;
 120     break;
 121   }
 122
 123   // FIXME: record-form instructions need a different itinerary class.
 124   if (NSlots == 1 && PPC::getNonRecordFormOpcode(MCID->getOpcode()) != -1)
 125     NSlots = 2;
 126
 127   switch (IIC) {
 128   default:
 129     // All multi-slot instructions must come first.
 130     return NSlots > 1;
 131   case PPC::Sched::IIC_BrCR: // cr logicals
 132   case PPC::Sched::IIC_SprMFCR:
 133   case PPC::Sched::IIC_SprMFCRF:
 134   case PPC::Sched::IIC_SprMTSPR:
 135     return true;
 136   }
 137 }
 138
 139 ScheduleHazardRecognizer::HazardType
 140 PPCDispatchGroupSBHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
 141   if (Stalls == 0 && isLoadAfterStore(SU))
 142     return NoopHazard;
 143
 144   return ScoreboardHazardRecognizer::getHazardType(SU, Stalls);
 145 }
 146
 147 bool PPCDispatchGroupSBHazardRecognizer::ShouldPreferAnother(SUnit *SU) {
 148   const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
 149   unsigned NSlots;
 150   if (MCID && mustComeFirst(MCID, NSlots) && CurSlots)
 151     return true;
 152
 153   return ScoreboardHazardRecognizer::ShouldPreferAnother(SU);
 154 }
 155
 156 unsigned PPCDispatchGroupSBHazardRecognizer::PreEmitNoops(SUnit *SU) {
 157   // We only need to fill out a maximum of 5 slots here: The 6th slot could
 158   // only be a second branch, and otherwise the next instruction will start a
 159   // new group.
 160   if (isLoadAfterStore(SU) && CurSlots < 6) {
 161     unsigned Directive =
 162       DAG->TM.getSubtarget<PPCSubtarget>().getDarwinDirective();
 163     // If we're using a special group-terminating nop, then we need only one.
 164     if (Directive == PPC::DIR_PWR6 || Directive == PPC::DIR_PWR7)
 165       return 1;
 166
 167     return 5 - CurSlots;
 168   }
 169
 170   return ScoreboardHazardRecognizer::PreEmitNoops(SU);
 171 }
 172
 173 void PPCDispatchGroupSBHazardRecognizer::EmitInstruction(SUnit *SU) {
 174   const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
 175   if (MCID) {
 176     if (CurSlots == 5 || (MCID->isBranch() && CurBranches == 1)) {
 177       CurGroup.clear();
 178       CurSlots = CurBranches = 0;
 179     } else {
 180       DEBUG(dbgs() << "**** Adding to dispatch group: SU(" <<
 181                       SU->NodeNum << "): ");
 182       DEBUG(DAG->dumpNode(SU));
 183
 184       unsigned NSlots;
 185       bool MustBeFirst = mustComeFirst(MCID, NSlots);
 186
 187       // If this instruction must come first, but does not, then it starts a
 188       // new group.
 189       if (MustBeFirst && CurSlots) {
 190         CurSlots = CurBranches = 0;
 191         CurGroup.clear();
 192       }
 193
 194       CurSlots += NSlots;
 195       CurGroup.push_back(SU);
 196
 197       if (MCID->isBranch())
 198         ++CurBranches;
 199     }
 200   }
 201
 202   return ScoreboardHazardRecognizer::EmitInstruction(SU);
 203 }
 204
 205 void PPCDispatchGroupSBHazardRecognizer::AdvanceCycle() {
 206   return ScoreboardHazardRecognizer::AdvanceCycle();
 207 }
 208
 209 void PPCDispatchGroupSBHazardRecognizer::RecedeCycle() {
 210   llvm_unreachable("Bottom-up scheduling not supported");
 211 }
 212
 213 void PPCDispatchGroupSBHazardRecognizer::Reset() {
 214   CurGroup.clear();
 215   CurSlots = CurBranches = 0;
 216   return ScoreboardHazardRecognizer::Reset();
 217 }
 218
 219 void PPCDispatchGroupSBHazardRecognizer::EmitNoop() {
 220   unsigned Directive =
 221     DAG->TM.getSubtarget<PPCSubtarget>().getDarwinDirective();
 222   // If the group has now filled all of its slots, or if we're using a special
 223   // group-terminating nop, the group is complete.
 224   if (Directive == PPC::DIR_PWR6 || Directive == PPC::DIR_PWR7 ||
 225       CurSlots == 6)  {
 226     CurGroup.clear();
 227     CurSlots = CurBranches = 0;
 228   } else {
 229     CurGroup.push_back(0);
 230     ++CurSlots;
 231   }
 232 }
 233
 234 //===----------------------------------------------------------------------===//
 235 // PowerPC 970 Hazard Recognizer
 236 //
 237 // This models the dispatch group formation of the PPC970 processor.  Dispatch
 238 // groups are bundles of up to five instructions that can contain various mixes
 239 // of instructions.  The PPC970 can dispatch a peak of 4 non-branch and one
 240 // branch instruction per-cycle.
 241 //
 242 // There are a number of restrictions to dispatch group formation: some
 243 // instructions can only be issued in the first slot of a dispatch group, & some
 244 // instructions fill an entire dispatch group.  Additionally, only branches can
 245 // issue in the 5th (last) slot.
 246 //
 247 // Finally, there are a number of "structural" hazards on the PPC970.  These
 248 // conditions cause large performance penalties due to misprediction, recovery,
 249 // and replay logic that has to happen.  These cases include setting a CTR and
 250 // branching through it in the same dispatch group, and storing to an address,
 251 // then loading from the same address within a dispatch group.  To avoid these
 252 // conditions, we insert no-op instructions when appropriate.
 253 //
 254 // FIXME: This is missing some significant cases:
 255 //   1. Modeling of microcoded instructions.
 256 //   2. Handling of serialized operations.
 257 //   3. Handling of the esoteric cases in "Resource-based Instruction Grouping".
 258 //
 259
 260 PPCHazardRecognizer970::PPCHazardRecognizer970(const TargetMachine &TM)
 261   : TM(TM) {
 262   EndDispatchGroup();
 263 }
 264
 265 void PPCHazardRecognizer970::EndDispatchGroup() {
 266   DEBUG(errs() << "=== Start of dispatch group\n");
 267   NumIssued = 0;
 268
 269   // Structural hazard info.
 270   HasCTRSet = false;
 271   NumStores = 0;
 272 }
 273
 274
 275 PPCII::PPC970_Unit
 276 PPCHazardRecognizer970::GetInstrType(unsigned Opcode,
 277                                      bool &isFirst, bool &isSingle,
 278                                      bool &isCracked,
 279                                      bool &isLoad, bool &isStore) {
 280   const MCInstrDesc &MCID = TM.getInstrInfo()->get(Opcode);
 281
 282   isLoad  = MCID.mayLoad();
 283   isStore = MCID.mayStore();
 284
 285   uint64_t TSFlags = MCID.TSFlags;
 286
 287   isFirst   = TSFlags & PPCII::PPC970_First;
 288   isSingle  = TSFlags & PPCII::PPC970_Single;
 289   isCracked = TSFlags & PPCII::PPC970_Cracked;
 290   return (PPCII::PPC970_Unit)(TSFlags & PPCII::PPC970_Mask);
 291 }
 292
 293 /// isLoadOfStoredAddress - If we have a load from the previously stored pointer
 294 /// as indicated by StorePtr1/StorePtr2/StoreSize, return true.
 295 bool PPCHazardRecognizer970::
 296 isLoadOfStoredAddress(uint64_t LoadSize, int64_t LoadOffset,
 297   const Value *LoadValue) const {
 298   for (unsigned i = 0, e = NumStores; i != e; ++i) {
 299     // Handle exact and commuted addresses.
 300     if (LoadValue == StoreValue[i] && LoadOffset == StoreOffset[i])
 301       return true;
 302
 303     // Okay, we don't have an exact match, if this is an indexed offset, see if
 304     // we have overlap (which happens during fp->int conversion for example).
 305     if (StoreValue[i] == LoadValue) {
 306       // Okay the base pointers match, so we have [c1+r] vs [c2+r].  Check
 307       // to see if the load and store actually overlap.
 308       if (StoreOffset[i] < LoadOffset) {
 309         if (int64_t(StoreOffset[i]+StoreSize[i]) > LoadOffset) return true;
 310       } else {
 311         if (int64_t(LoadOffset+LoadSize) > StoreOffset[i]) return true;
 312       }
 313     }
 314   }
 315   return false;
 316 }
 317
 318 /// getHazardType - We return hazard for any non-branch instruction that would
 319 /// terminate the dispatch group.  We turn NoopHazard for any
 320 /// instructions that wouldn't terminate the dispatch group that would cause a
 321 /// pipeline flush.
 322 ScheduleHazardRecognizer::HazardType PPCHazardRecognizer970::
 323 getHazardType(SUnit *SU, int Stalls) {
 324   assert(Stalls == 0 && "PPC hazards don't support scoreboard lookahead");
 325
 326   MachineInstr *MI = SU->getInstr();
 327
 328   if (MI->isDebugValue())
 329     return NoHazard;
 330
 331   unsigned Opcode = MI->getOpcode();
 332   bool isFirst, isSingle, isCracked, isLoad, isStore;
 333   PPCII::PPC970_Unit InstrType =
 334     GetInstrType(Opcode, isFirst, isSingle, isCracked,
 335                  isLoad, isStore);
 336   if (InstrType == PPCII::PPC970_Pseudo) return NoHazard;
 337
 338   // We can only issue a PPC970_First/PPC970_Single instruction (such as
 339   // crand/mtspr/etc) if this is the first cycle of the dispatch group.
 340   if (NumIssued != 0 && (isFirst || isSingle))
 341     return Hazard;
 342
 343   // If this instruction is cracked into two ops by the decoder, we know that
 344   // it is not a branch and that it cannot issue if 3 other instructions are
 345   // already in the dispatch group.
 346   if (isCracked && NumIssued > 2)
 347     return Hazard;
 348
 349   switch (InstrType) {
 350   default: llvm_unreachable("Unknown instruction type!");
 351   case PPCII::PPC970_FXU:
 352   case PPCII::PPC970_LSU:
 353   case PPCII::PPC970_FPU:
 354   case PPCII::PPC970_VALU:
 355   case PPCII::PPC970_VPERM:
 356     // We can only issue a branch as the last instruction in a group.
 357     if (NumIssued == 4) return Hazard;
 358     break;
 359   case PPCII::PPC970_CRU:
 360     // We can only issue a CR instruction in the first two slots.
 361     if (NumIssued >= 2) return Hazard;
 362     break;
 363   case PPCII::PPC970_BRU:
 364     break;
 365   }
 366
 367   // Do not allow MTCTR and BCTRL to be in the same dispatch group.
 368   if (HasCTRSet && Opcode == PPC::BCTRL)
 369     return NoopHazard;
 370
 371   // If this is a load following a store, make sure it's not to the same or
 372   // overlapping address.
 373   if (isLoad && NumStores && !MI->memoperands_empty()) {
 374     MachineMemOperand *MO = *MI->memoperands_begin();
 375     if (isLoadOfStoredAddress(MO->getSize(),
 376                               MO->getOffset(), MO->getValue()))
 377       return NoopHazard;
 378   }
 379
 380   return NoHazard;
 381 }
 382
 383 void PPCHazardRecognizer970::EmitInstruction(SUnit *SU) {
 384   MachineInstr *MI = SU->getInstr();
 385
 386   if (MI->isDebugValue())
 387     return;
 388
 389   unsigned Opcode = MI->getOpcode();
 390   bool isFirst, isSingle, isCracked, isLoad, isStore;
 391   PPCII::PPC970_Unit InstrType =
 392     GetInstrType(Opcode, isFirst, isSingle, isCracked,
 393                  isLoad, isStore);
 394   if (InstrType == PPCII::PPC970_Pseudo) return;
 395
 396   // Update structural hazard information.
 397   if (Opcode == PPC::MTCTR || Opcode == PPC::MTCTR8) HasCTRSet = true;
 398
 399   // Track the address stored to.
 400   if (isStore && NumStores < 4 && !MI->memoperands_empty()) {
 401     MachineMemOperand *MO = *MI->memoperands_begin();
 402     StoreSize[NumStores] = MO->getSize();
 403     StoreOffset[NumStores] = MO->getOffset();
 404     StoreValue[NumStores] = MO->getValue();
 405     ++NumStores;
 406   }
 407
 408   if (InstrType == PPCII::PPC970_BRU || isSingle)
 409     NumIssued = 4;  // Terminate a d-group.
 410   ++NumIssued;
 411
 412   // If this instruction is cracked into two ops by the decoder, remember that
 413   // we issued two pieces.
 414   if (isCracked)
 415     ++NumIssued;
 416
 417   if (NumIssued == 5)
 418     EndDispatchGroup();
 419 }
 420
 421 void PPCHazardRecognizer970::AdvanceCycle() {
 422   assert(NumIssued < 5 && "Illegal dispatch group!");
 423   ++NumIssued;
 424   if (NumIssued == 5)
 425     EndDispatchGroup();
 426 }
 427
 428 void PPCHazardRecognizer970::Reset() {
 429   EndDispatchGroup();
 430 }
 431