LLVM  9.0.0svn
PPCHazardRecognizers.cpp
Go to the documentation of this file.
1 //===-- PPCHazardRecognizers.cpp - PowerPC Hazard Recognizer Impls --------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements hazard recognizers for scheduling on PowerPC processors.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "PPCHazardRecognizers.h"
14 #include "PPC.h"
15 #include "PPCInstrInfo.h"
16 #include "PPCTargetMachine.h"
18 #include "llvm/Support/Debug.h"
21 using namespace llvm;
22 
23 #define DEBUG_TYPE "pre-RA-sched"
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_LdStSTU:
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_LdStSTUX:
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 
141  if (Stalls == 0 && isLoadAfterStore(SU))
142  return NoopHazard;
143 
145 }
146 
148  const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
149  unsigned NSlots;
150  if (MCID && mustComeFirst(MCID, NSlots) && CurSlots)
151  return true;
152 
154 }
155 
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->MF.getSubtarget<PPCSubtarget>().getDarwinDirective();
163  // If we're using a special group-terminating nop, then we need only one.
164  // FIXME: the same for P9 as previous gen until POWER9 scheduling is ready
165  if (Directive == PPC::DIR_PWR6 || Directive == PPC::DIR_PWR7 ||
166  Directive == PPC::DIR_PWR8 || Directive == PPC::DIR_PWR9)
167  return 1;
168 
169  return 5 - CurSlots;
170  }
171 
173 }
174 
176  const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
177  if (MCID) {
178  if (CurSlots == 5 || (MCID->isBranch() && CurBranches == 1)) {
179  CurGroup.clear();
180  CurSlots = CurBranches = 0;
181  } else {
182  LLVM_DEBUG(dbgs() << "**** Adding to dispatch group: ");
183  LLVM_DEBUG(DAG->dumpNode(*SU));
184 
185  unsigned NSlots;
186  bool MustBeFirst = mustComeFirst(MCID, NSlots);
187 
188  // If this instruction must come first, but does not, then it starts a
189  // new group.
190  if (MustBeFirst && CurSlots) {
191  CurSlots = CurBranches = 0;
192  CurGroup.clear();
193  }
194 
195  CurSlots += NSlots;
196  CurGroup.push_back(SU);
197 
198  if (MCID->isBranch())
199  ++CurBranches;
200  }
201  }
202 
204 }
205 
208 }
209 
211  llvm_unreachable("Bottom-up scheduling not supported");
212 }
213 
215  CurGroup.clear();
216  CurSlots = CurBranches = 0;
218 }
219 
221  unsigned Directive =
222  DAG->MF.getSubtarget<PPCSubtarget>().getDarwinDirective();
223  // If the group has now filled all of its slots, or if we're using a special
224  // group-terminating nop, the group is complete.
225  // FIXME: the same for P9 as previous gen until POWER9 scheduling is ready
226  if (Directive == PPC::DIR_PWR6 || Directive == PPC::DIR_PWR7 ||
227  Directive == PPC::DIR_PWR8 || Directive == PPC::DIR_PWR9 ||
228  CurSlots == 6) {
229  CurGroup.clear();
230  CurSlots = CurBranches = 0;
231  } else {
232  CurGroup.push_back(nullptr);
233  ++CurSlots;
234  }
235 }
236 
237 //===----------------------------------------------------------------------===//
238 // PowerPC 970 Hazard Recognizer
239 //
240 // This models the dispatch group formation of the PPC970 processor. Dispatch
241 // groups are bundles of up to five instructions that can contain various mixes
242 // of instructions. The PPC970 can dispatch a peak of 4 non-branch and one
243 // branch instruction per-cycle.
244 //
245 // There are a number of restrictions to dispatch group formation: some
246 // instructions can only be issued in the first slot of a dispatch group, & some
247 // instructions fill an entire dispatch group. Additionally, only branches can
248 // issue in the 5th (last) slot.
249 //
250 // Finally, there are a number of "structural" hazards on the PPC970. These
251 // conditions cause large performance penalties due to misprediction, recovery,
252 // and replay logic that has to happen. These cases include setting a CTR and
253 // branching through it in the same dispatch group, and storing to an address,
254 // then loading from the same address within a dispatch group. To avoid these
255 // conditions, we insert no-op instructions when appropriate.
256 //
257 // FIXME: This is missing some significant cases:
258 // 1. Modeling of microcoded instructions.
259 // 2. Handling of serialized operations.
260 // 3. Handling of the esoteric cases in "Resource-based Instruction Grouping".
261 //
262 
264  : DAG(DAG) {
265  EndDispatchGroup();
266 }
267 
268 void PPCHazardRecognizer970::EndDispatchGroup() {
269  LLVM_DEBUG(errs() << "=== Start of dispatch group\n");
270  NumIssued = 0;
271 
272  // Structural hazard info.
273  HasCTRSet = false;
274  NumStores = 0;
275 }
276 
277 
279 PPCHazardRecognizer970::GetInstrType(unsigned Opcode,
280  bool &isFirst, bool &isSingle,
281  bool &isCracked,
282  bool &isLoad, bool &isStore) {
283  const MCInstrDesc &MCID = DAG.TII->get(Opcode);
284 
285  isLoad = MCID.mayLoad();
286  isStore = MCID.mayStore();
287 
288  uint64_t TSFlags = MCID.TSFlags;
289 
290  isFirst = TSFlags & PPCII::PPC970_First;
291  isSingle = TSFlags & PPCII::PPC970_Single;
292  isCracked = TSFlags & PPCII::PPC970_Cracked;
293  return (PPCII::PPC970_Unit)(TSFlags & PPCII::PPC970_Mask);
294 }
295 
296 /// isLoadOfStoredAddress - If we have a load from the previously stored pointer
297 /// as indicated by StorePtr1/StorePtr2/StoreSize, return true.
298 bool PPCHazardRecognizer970::
299 isLoadOfStoredAddress(uint64_t LoadSize, int64_t LoadOffset,
300  const Value *LoadValue) const {
301  for (unsigned i = 0, e = NumStores; i != e; ++i) {
302  // Handle exact and commuted addresses.
303  if (LoadValue == StoreValue[i] && LoadOffset == StoreOffset[i])
304  return true;
305 
306  // Okay, we don't have an exact match, if this is an indexed offset, see if
307  // we have overlap (which happens during fp->int conversion for example).
308  if (StoreValue[i] == LoadValue) {
309  // Okay the base pointers match, so we have [c1+r] vs [c2+r]. Check
310  // to see if the load and store actually overlap.
311  if (StoreOffset[i] < LoadOffset) {
312  if (int64_t(StoreOffset[i]+StoreSize[i]) > LoadOffset) return true;
313  } else {
314  if (int64_t(LoadOffset+LoadSize) > StoreOffset[i]) return true;
315  }
316  }
317  }
318  return false;
319 }
320 
321 /// getHazardType - We return hazard for any non-branch instruction that would
322 /// terminate the dispatch group. We turn NoopHazard for any
323 /// instructions that wouldn't terminate the dispatch group that would cause a
324 /// pipeline flush.
326 getHazardType(SUnit *SU, int Stalls) {
327  assert(Stalls == 0 && "PPC hazards don't support scoreboard lookahead");
328 
329  MachineInstr *MI = SU->getInstr();
330 
331  if (MI->isDebugInstr())
332  return NoHazard;
333 
334  unsigned Opcode = MI->getOpcode();
335  bool isFirst, isSingle, isCracked, isLoad, isStore;
337  GetInstrType(Opcode, isFirst, isSingle, isCracked,
338  isLoad, isStore);
339  if (InstrType == PPCII::PPC970_Pseudo) return NoHazard;
340 
341  // We can only issue a PPC970_First/PPC970_Single instruction (such as
342  // crand/mtspr/etc) if this is the first cycle of the dispatch group.
343  if (NumIssued != 0 && (isFirst || isSingle))
344  return Hazard;
345 
346  // If this instruction is cracked into two ops by the decoder, we know that
347  // it is not a branch and that it cannot issue if 3 other instructions are
348  // already in the dispatch group.
349  if (isCracked && NumIssued > 2)
350  return Hazard;
351 
352  switch (InstrType) {
353  default: llvm_unreachable("Unknown instruction type!");
354  case PPCII::PPC970_FXU:
355  case PPCII::PPC970_LSU:
356  case PPCII::PPC970_FPU:
357  case PPCII::PPC970_VALU:
358  case PPCII::PPC970_VPERM:
359  // We can only issue a branch as the last instruction in a group.
360  if (NumIssued == 4) return Hazard;
361  break;
362  case PPCII::PPC970_CRU:
363  // We can only issue a CR instruction in the first two slots.
364  if (NumIssued >= 2) return Hazard;
365  break;
366  case PPCII::PPC970_BRU:
367  break;
368  }
369 
370  // Do not allow MTCTR and BCTRL to be in the same dispatch group.
371  if (HasCTRSet && Opcode == PPC::BCTRL)
372  return NoopHazard;
373 
374  // If this is a load following a store, make sure it's not to the same or
375  // overlapping address.
376  if (isLoad && NumStores && !MI->memoperands_empty()) {
378  if (isLoadOfStoredAddress(MO->getSize(),
379  MO->getOffset(), MO->getValue()))
380  return NoopHazard;
381  }
382 
383  return NoHazard;
384 }
385 
387  MachineInstr *MI = SU->getInstr();
388 
389  if (MI->isDebugInstr())
390  return;
391 
392  unsigned Opcode = MI->getOpcode();
393  bool isFirst, isSingle, isCracked, isLoad, isStore;
395  GetInstrType(Opcode, isFirst, isSingle, isCracked,
396  isLoad, isStore);
397  if (InstrType == PPCII::PPC970_Pseudo) return;
398 
399  // Update structural hazard information.
400  if (Opcode == PPC::MTCTR || Opcode == PPC::MTCTR8) HasCTRSet = true;
401 
402  // Track the address stored to.
403  if (isStore && NumStores < 4 && !MI->memoperands_empty()) {
405  StoreSize[NumStores] = MO->getSize();
406  StoreOffset[NumStores] = MO->getOffset();
407  StoreValue[NumStores] = MO->getValue();
408  ++NumStores;
409  }
410 
411  if (InstrType == PPCII::PPC970_BRU || isSingle)
412  NumIssued = 4; // Terminate a d-group.
413  ++NumIssued;
414 
415  // If this instruction is cracked into two ops by the decoder, remember that
416  // we issued two pieces.
417  if (isCracked)
418  ++NumIssued;
419 
420  if (NumIssued == 5)
421  EndDispatchGroup();
422 }
423 
425  assert(NumIssued < 5 && "Illegal dispatch group!");
426  ++NumIssued;
427  if (NumIssued == 5)
428  EndDispatchGroup();
429 }
430 
432  EndDispatchGroup();
433 }
434 
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
int getNonRecordFormOpcode(uint16_t)
PPCHazardRecognizer970(const ScheduleDAG &DAG)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
void RecedeCycle() override
RecedeCycle - This callback is invoked whenever the next bottom-up instruction to be scheduled cannot...
unsigned PreEmitNoops(SUnit *SU) override
PreEmitNoops - This callback is invoked prior to emitting an instruction.
uint64_t getSize() const
Return the size in bytes of the memory reference.
These are the various PPC970 execution unit pipelines.
Definition: PPCInstrInfo.h:54
CHAIN,FLAG = BCTRL(CHAIN, INFLAG) - Directly corresponds to a BCTRL instruction.
bool mayLoad() const
Return true if this instruction could possibly read memory.
Definition: MCInstrDesc.h:398
PPC970_Single - This instruction starts a new dispatch group and terminates it, so it will be the sol...
Definition: PPCInstrInfo.h:40
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:256
bool isBranch() const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MCInstrDesc.h:276
A description of a memory reference used in the backend.
static bool isLoad(int Opcode)
HazardType getHazardType(SUnit *SU, int Stalls) override
getHazardType - We return hazard for any non-branch instruction that would terminate the dispatch gro...
const MCInstrDesc * getInstrDesc(const SUnit *SU) const
Returns the MCInstrDesc of this SUnit.
Definition: ScheduleDAG.h:581
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:408
void EmitInstruction(SUnit *SU) override
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
PPC970_Cracked - This instruction is cracked into two pieces, requiring two dispatch pipes to be avai...
Definition: PPCInstrInfo.h:44
static bool isStore(int Opcode)
void AdvanceCycle() override
AdvanceCycle - This callback is invoked whenever the next top-down instruction to be scheduled cannot...
void EmitNoop() override
EmitNoop - This callback is invoked when a noop was added to the instruction stream.
const Value * getValue() const
Return the base address of the memory access.
unsigned getSchedClass() const
Return the scheduling class for this instruction.
Definition: MCInstrDesc.h:576
void Reset() override
Reset - This callback is invoked when a new block of instructions is about to be schedule.
HazardType getHazardType(SUnit *SU, int Stalls) override
getHazardType - Return the hazard type of emitting this node.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
InstrType
Represents how an instruction should be mapped by the outliner.
CHAIN,FLAG = MTCTR(VAL, CHAIN[, INFLAG]) - Directly corresponds to a MTCTR instruction.
void EmitInstruction(SUnit *SU) override
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
virtual bool ShouldPreferAnother(SUnit *)
ShouldPreferAnother - This callback may be invoked if getHazardType returns NoHazard.
bool isDebugInstr() const
Definition: MachineInstr.h:998
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void Reset() override
Reset - This callback is invoked when a new block of instructions is about to be schedule.
void AdvanceCycle() override
AdvanceCycle - This callback is invoked whenever the next top-down instruction to be scheduled cannot...
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:533
void Reset() override
Reset - This callback is invoked when a new block of instructions is about to be schedule.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
virtual unsigned PreEmitNoops(SUnit *)
PreEmitNoops - This callback is invoked prior to emitting an instruction.
bool mayStore() const
Return true if this instruction could possibly modify memory.
Definition: MCInstrDesc.h:404
bool ShouldPreferAnother(SUnit *SU) override
ShouldPreferAnother - This callback may be invoked if getHazardType returns NoHazard.
Representation of each machine instruction.
Definition: MachineInstr.h:63
void AdvanceCycle() override
AdvanceCycle - This callback is invoked whenever the next top-down instruction to be scheduled cannot...
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:558
bool memoperands_empty() const
Return true if we don&#39;t have any memory operands which described the memory access done by this instr...
Definition: MachineInstr.h:545
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
int64_t getOffset() const
For normal values, this is a byte offset added to the base address.
LLVM Value Representation.
Definition: Value.h:72
void EmitInstruction(SUnit *SU) override
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
unsigned getOpcode() const
Return the opcode number for this descriptor.
Definition: MCInstrDesc.h:203
IRTranslator LLVM IR MI
PPC970_First - This instruction starts a new dispatch group, so it will always be the first one in th...
Definition: PPCInstrInfo.h:36
#define LLVM_DEBUG(X)
Definition: Debug.h:122
HazardType getHazardType(SUnit *SU, int Stalls) override
getHazardType - Return the hazard type of emitting this node.
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242