LLVM  16.0.0git
ScheduleDAGInstrs.cpp
Go to the documentation of this file.
1 //===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===//
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 /// \file This implements the ScheduleDAGInstrs class, which implements
10 /// re-scheduling of MachineInstrs.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 
16 #include "llvm/ADT/IntEqClasses.h"
17 #include "llvm/ADT/MapVector.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/SparseSet.h"
40 #include "llvm/Config/llvm-config.h"
41 #include "llvm/IR/Constants.h"
42 #include "llvm/IR/Function.h"
43 #include "llvm/IR/Type.h"
44 #include "llvm/IR/Value.h"
45 #include "llvm/MC/LaneBitmask.h"
46 #include "llvm/MC/MCRegisterInfo.h"
47 #include "llvm/Support/Casting.h"
49 #include "llvm/Support/Compiler.h"
50 #include "llvm/Support/Debug.h"
52 #include "llvm/Support/Format.h"
54 #include <algorithm>
55 #include <cassert>
56 #include <iterator>
57 #include <utility>
58 #include <vector>
59 
60 using namespace llvm;
61 
62 #define DEBUG_TYPE "machine-scheduler"
63 
64 static cl::opt<bool>
65  EnableAASchedMI("enable-aa-sched-mi", cl::Hidden,
66  cl::desc("Enable use of AA during MI DAG construction"));
67 
68 static cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden,
69  cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"));
70 
71 // Note: the two options below might be used in tuning compile time vs
72 // output quality. Setting HugeRegion so large that it will never be
73 // reached means best-effort, but may be slow.
74 
75 // When Stores and Loads maps (or NonAliasStores and NonAliasLoads)
76 // together hold this many SUs, a reduction of maps will be done.
77 static cl::opt<unsigned> HugeRegion("dag-maps-huge-region", cl::Hidden,
78  cl::init(1000), cl::desc("The limit to use while constructing the DAG "
79  "prior to scheduling, at which point a trade-off "
80  "is made to avoid excessive compile time."));
81 
83  "dag-maps-reduction-size", cl::Hidden,
84  cl::desc("A huge scheduling region will have maps reduced by this many "
85  "nodes at a time. Defaults to HugeRegion / 2."));
86 
87 static unsigned getReductionSize() {
88  // Always reduce a huge region with half of the elements, except
89  // when user sets this number explicitly.
90  if (ReductionSize.getNumOccurrences() == 0)
91  return HugeRegion / 2;
92  return ReductionSize;
93 }
94 
95 static void dumpSUList(const ScheduleDAGInstrs::SUList &L) {
96 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
97  dbgs() << "{ ";
98  for (const SUnit *SU : L) {
99  dbgs() << "SU(" << SU->NodeNum << ")";
100  if (SU != L.back())
101  dbgs() << ", ";
102  }
103  dbgs() << "}\n";
104 #endif
105 }
106 
108  const MachineLoopInfo *mli,
109  bool RemoveKillFlags)
110  : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()),
111  RemoveKillFlags(RemoveKillFlags),
112  UnknownValue(UndefValue::get(
113  Type::getVoidTy(mf.getFunction().getContext()))), Topo(SUnits, &ExitSU) {
114  DbgValues.clear();
115 
116  const TargetSubtargetInfo &ST = mf.getSubtarget();
117  SchedModel.init(&ST);
118 }
119 
120 /// If this machine instr has memory reference information and it can be
121 /// tracked to a normal reference to a known object, return the Value
122 /// for that object. This function returns false the memory location is
123 /// unknown or may alias anything.
125  const MachineFrameInfo &MFI,
126  UnderlyingObjectsVector &Objects,
127  const DataLayout &DL) {
128  auto AllMMOsOkay = [&]() {
129  for (const MachineMemOperand *MMO : MI->memoperands()) {
130  // TODO: Figure out whether isAtomic is really necessary (see D57601).
131  if (MMO->isVolatile() || MMO->isAtomic())
132  return false;
133 
134  if (const PseudoSourceValue *PSV = MMO->getPseudoValue()) {
135  // Function that contain tail calls don't have unique PseudoSourceValue
136  // objects. Two PseudoSourceValues might refer to the same or
137  // overlapping locations. The client code calling this function assumes
138  // this is not the case. So return a conservative answer of no known
139  // object.
140  if (MFI.hasTailCall())
141  return false;
142 
143  // For now, ignore PseudoSourceValues which may alias LLVM IR values
144  // because the code that uses this function has no way to cope with
145  // such aliases.
146  if (PSV->isAliased(&MFI))
147  return false;
148 
149  bool MayAlias = PSV->mayAlias(&MFI);
150  Objects.emplace_back(PSV, MayAlias);
151  } else if (const Value *V = MMO->getValue()) {
153  if (!getUnderlyingObjectsForCodeGen(V, Objs))
154  return false;
155 
156  for (Value *V : Objs) {
158  Objects.emplace_back(V, true);
159  }
160  } else
161  return false;
162  }
163  return true;
164  };
165 
166  if (!AllMMOsOkay()) {
167  Objects.clear();
168  return false;
169  }
170 
171  return true;
172 }
173 
175  BB = bb;
176 }
177 
179  // Subclasses should no longer refer to the old block.
180  BB = nullptr;
181 }
182 
186  unsigned regioninstrs) {
187  assert(bb == BB && "startBlock should set BB");
188  RegionBegin = begin;
189  RegionEnd = end;
190  NumRegionInstrs = regioninstrs;
191 }
192 
194  // Nothing to do.
195 }
196 
198  MachineInstr *ExitMI =
199  RegionEnd != BB->end()
201  : nullptr;
202  ExitSU.setInstr(ExitMI);
203  // Add dependencies on the defs and uses of the instruction.
204  if (ExitMI) {
205  for (const MachineOperand &MO : ExitMI->operands()) {
206  if (!MO.isReg() || MO.isDef()) continue;
207  Register Reg = MO.getReg();
210  } else if (Register::isVirtualRegister(Reg) && MO.readsReg()) {
211  addVRegUseDeps(&ExitSU, ExitMI->getOperandNo(&MO));
212  }
213  }
214  }
215  if (!ExitMI || (!ExitMI->isCall() && !ExitMI->isBarrier())) {
216  // For others, e.g. fallthrough, conditional branch, assume the exit
217  // uses all the registers that are livein to the successor blocks.
218  for (const MachineBasicBlock *Succ : BB->successors()) {
219  for (const auto &LI : Succ->liveins()) {
220  if (!Uses.contains(LI.PhysReg))
221  Uses.insert(PhysRegSUOper(&ExitSU, -1, LI.PhysReg));
222  }
223  }
224  }
225 }
226 
227 /// MO is an operand of SU's instruction that defines a physical register. Adds
228 /// data dependencies from SU to any uses of the physical register.
229 void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) {
230  const MachineOperand &MO = SU->getInstr()->getOperand(OperIdx);
231  assert(MO.isDef() && "expect physreg def");
232 
233  // Ask the target if address-backscheduling is desirable, and if so how much.
235 
236  // Only use any non-zero latency for real defs/uses, in contrast to
237  // "fake" operands added by regalloc.
238  const MCInstrDesc *DefMIDesc = &SU->getInstr()->getDesc();
239  bool ImplicitPseudoDef = (OperIdx >= DefMIDesc->getNumOperands() &&
240  !DefMIDesc->hasImplicitDefOfPhysReg(MO.getReg()));
241  for (MCRegAliasIterator Alias(MO.getReg(), TRI, true);
242  Alias.isValid(); ++Alias) {
243  for (Reg2SUnitsMap::iterator I = Uses.find(*Alias); I != Uses.end(); ++I) {
244  SUnit *UseSU = I->SU;
245  if (UseSU == SU)
246  continue;
247 
248  // Adjust the dependence latency using operand def/use information,
249  // then allow the target to perform its own adjustments.
250  int UseOp = I->OpIdx;
251  MachineInstr *RegUse = nullptr;
252  SDep Dep;
253  if (UseOp < 0)
254  Dep = SDep(SU, SDep::Artificial);
255  else {
256  // Set the hasPhysRegDefs only for physreg defs that have a use within
257  // the scheduling region.
258  SU->hasPhysRegDefs = true;
259  Dep = SDep(SU, SDep::Data, *Alias);
260  RegUse = UseSU->getInstr();
261  }
262  const MCInstrDesc *UseMIDesc =
263  (RegUse ? &UseSU->getInstr()->getDesc() : nullptr);
264  bool ImplicitPseudoUse =
265  (UseMIDesc && UseOp >= ((int)UseMIDesc->getNumOperands()) &&
266  !UseMIDesc->hasImplicitUseOfPhysReg(*Alias));
267  if (!ImplicitPseudoDef && !ImplicitPseudoUse) {
269  RegUse, UseOp));
270  } else {
271  Dep.setLatency(0);
272  }
273  ST.adjustSchedDependency(SU, OperIdx, UseSU, UseOp, Dep);
274  UseSU->addPred(Dep);
275  }
276  }
277 }
278 
279 /// Adds register dependencies (data, anti, and output) from this SUnit
280 /// to following instructions in the same scheduling region that depend the
281 /// physical register referenced at OperIdx.
282 void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) {
283  MachineInstr *MI = SU->getInstr();
284  MachineOperand &MO = MI->getOperand(OperIdx);
285  Register Reg = MO.getReg();
286  // We do not need to track any dependencies for constant registers.
288  return;
289 
291 
292  // Optionally add output and anti dependencies. For anti
293  // dependencies we use a latency of 0 because for a multi-issue
294  // target we want to allow the defining instruction to issue
295  // in the same cycle as the using instruction.
296  // TODO: Using a latency of 1 here for output dependencies assumes
297  // there's no cost for reusing registers.
298  SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
299  for (MCRegAliasIterator Alias(Reg, TRI, true); Alias.isValid(); ++Alias) {
300  if (!Defs.contains(*Alias))
301  continue;
302  for (Reg2SUnitsMap::iterator I = Defs.find(*Alias); I != Defs.end(); ++I) {
303  SUnit *DefSU = I->SU;
304  if (DefSU == &ExitSU)
305  continue;
306  if (DefSU != SU &&
307  (Kind != SDep::Output || !MO.isDead() ||
308  !DefSU->getInstr()->registerDefIsDead(*Alias))) {
309  SDep Dep(SU, Kind, /*Reg=*/*Alias);
310  if (Kind != SDep::Anti)
311  Dep.setLatency(
312  SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()));
313  ST.adjustSchedDependency(SU, OperIdx, DefSU, I->OpIdx, Dep);
314  DefSU->addPred(Dep);
315  }
316  }
317  }
318 
319  if (!MO.isDef()) {
320  SU->hasPhysRegUses = true;
321  // Either insert a new Reg2SUnits entry with an empty SUnits list, or
322  // retrieve the existing SUnits list for this register's uses.
323  // Push this SUnit on the use list.
324  Uses.insert(PhysRegSUOper(SU, OperIdx, Reg));
325  if (RemoveKillFlags)
326  MO.setIsKill(false);
327  } else {
328  addPhysRegDataDeps(SU, OperIdx);
329 
330  // Clear previous uses and defs of this register and its subergisters.
331  for (MCSubRegIterator SubReg(Reg, TRI, true); SubReg.isValid(); ++SubReg) {
332  if (Uses.contains(*SubReg))
333  Uses.eraseAll(*SubReg);
334  if (!MO.isDead())
335  Defs.eraseAll(*SubReg);
336  }
337  if (MO.isDead() && SU->isCall) {
338  // Calls will not be reordered because of chain dependencies (see
339  // below). Since call operands are dead, calls may continue to be added
340  // to the DefList making dependence checking quadratic in the size of
341  // the block. Instead, we leave only one call at the back of the
342  // DefList.
344  Reg2SUnitsMap::iterator B = P.first;
345  Reg2SUnitsMap::iterator I = P.second;
346  for (bool isBegin = I == B; !isBegin; /* empty */) {
347  isBegin = (--I) == B;
348  if (!I->SU->isCall)
349  break;
350  I = Defs.erase(I);
351  }
352  }
353 
354  // Defs are pushed in the order they are visited and never reordered.
355  Defs.insert(PhysRegSUOper(SU, OperIdx, Reg));
356  }
357 }
358 
360 {
361  Register Reg = MO.getReg();
362  // No point in tracking lanemasks if we don't have interesting subregisters.
363  const TargetRegisterClass &RC = *MRI.getRegClass(Reg);
364  if (!RC.HasDisjunctSubRegs)
365  return LaneBitmask::getAll();
366 
367  unsigned SubReg = MO.getSubReg();
368  if (SubReg == 0)
369  return RC.getLaneMask();
371 }
372 
374  auto RegUse = CurrentVRegUses.find(MO.getReg());
375  if (RegUse == CurrentVRegUses.end())
376  return true;
377  return (RegUse->LaneMask & getLaneMaskForMO(MO)).none();
378 }
379 
380 /// Adds register output and data dependencies from this SUnit to instructions
381 /// that occur later in the same scheduling region if they read from or write to
382 /// the virtual register defined at OperIdx.
383 ///
384 /// TODO: Hoist loop induction variable increments. This has to be
385 /// reevaluated. Generally, IV scheduling should be done before coalescing.
386 void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) {
387  MachineInstr *MI = SU->getInstr();
388  MachineOperand &MO = MI->getOperand(OperIdx);
389  Register Reg = MO.getReg();
390 
391  LaneBitmask DefLaneMask;
392  LaneBitmask KillLaneMask;
393  if (TrackLaneMasks) {
394  bool IsKill = MO.getSubReg() == 0 || MO.isUndef();
395  DefLaneMask = getLaneMaskForMO(MO);
396  // If we have a <read-undef> flag, none of the lane values comes from an
397  // earlier instruction.
398  KillLaneMask = IsKill ? LaneBitmask::getAll() : DefLaneMask;
399 
400  if (MO.getSubReg() != 0 && MO.isUndef()) {
401  // There may be other subregister defs on the same instruction of the same
402  // register in later operands. The lanes of other defs will now be live
403  // after this instruction, so these should not be treated as killed by the
404  // instruction even though they appear to be killed in this one operand.
405  for (const MachineOperand &OtherMO :
406  llvm::drop_begin(MI->operands(), OperIdx + 1))
407  if (OtherMO.isReg() && OtherMO.isDef() && OtherMO.getReg() == Reg)
408  KillLaneMask &= ~getLaneMaskForMO(OtherMO);
409  }
410 
411  // Clear undef flag, we'll re-add it later once we know which subregister
412  // Def is first.
413  MO.setIsUndef(false);
414  } else {
415  DefLaneMask = LaneBitmask::getAll();
416  KillLaneMask = LaneBitmask::getAll();
417  }
418 
419  if (MO.isDead()) {
420  assert(deadDefHasNoUse(MO) && "Dead defs should have no uses");
421  } else {
422  // Add data dependence to all uses we found so far.
425  E = CurrentVRegUses.end(); I != E; /*empty*/) {
426  LaneBitmask LaneMask = I->LaneMask;
427  // Ignore uses of other lanes.
428  if ((LaneMask & KillLaneMask).none()) {
429  ++I;
430  continue;
431  }
432 
433  if ((LaneMask & DefLaneMask).any()) {
434  SUnit *UseSU = I->SU;
435  MachineInstr *Use = UseSU->getInstr();
436  SDep Dep(SU, SDep::Data, Reg);
438  I->OperandIndex));
439  ST.adjustSchedDependency(SU, OperIdx, UseSU, I->OperandIndex, Dep);
440  UseSU->addPred(Dep);
441  }
442 
443  LaneMask &= ~KillLaneMask;
444  // If we found a Def for all lanes of this use, remove it from the list.
445  if (LaneMask.any()) {
446  I->LaneMask = LaneMask;
447  ++I;
448  } else
450  }
451  }
452 
453  // Shortcut: Singly defined vregs do not have output/anti dependencies.
454  if (MRI.hasOneDef(Reg))
455  return;
456 
457  // Add output dependence to the next nearest defs of this vreg.
458  //
459  // Unless this definition is dead, the output dependence should be
460  // transitively redundant with antidependencies from this definition's
461  // uses. We're conservative for now until we have a way to guarantee the uses
462  // are not eliminated sometime during scheduling. The output dependence edge
463  // is also useful if output latency exceeds def-use latency.
464  LaneBitmask LaneMask = DefLaneMask;
466  CurrentVRegDefs.end())) {
467  // Ignore defs for other lanes.
468  if ((V2SU.LaneMask & LaneMask).none())
469  continue;
470  // Add an output dependence.
471  SUnit *DefSU = V2SU.SU;
472  // Ignore additional defs of the same lanes in one instruction. This can
473  // happen because lanemasks are shared for targets with too many
474  // subregisters. We also use some representration tricks/hacks where we
475  // add super-register defs/uses, to imply that although we only access parts
476  // of the reg we care about the full one.
477  if (DefSU == SU)
478  continue;
479  SDep Dep(SU, SDep::Output, Reg);
480  Dep.setLatency(
481  SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()));
482  DefSU->addPred(Dep);
483 
484  // Update current definition. This can get tricky if the def was about a
485  // bigger lanemask before. We then have to shrink it and create a new
486  // VReg2SUnit for the non-overlapping part.
487  LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
488  LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
489  V2SU.SU = SU;
490  V2SU.LaneMask = OverlapMask;
491  if (NonOverlapMask.any())
492  CurrentVRegDefs.insert(VReg2SUnit(Reg, NonOverlapMask, DefSU));
493  }
494  // If there was no CurrentVRegDefs entry for some lanes yet, create one.
495  if (LaneMask.any())
496  CurrentVRegDefs.insert(VReg2SUnit(Reg, LaneMask, SU));
497 }
498 
499 /// Adds a register data dependency if the instruction that defines the
500 /// virtual register used at OperIdx is mapped to an SUnit. Add a register
501 /// antidependency from this SUnit to instructions that occur later in the same
502 /// scheduling region if they write the virtual register.
503 ///
504 /// TODO: Handle ExitSU "uses" properly.
505 void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
506  const MachineInstr *MI = SU->getInstr();
507  assert(!MI->isDebugOrPseudoInstr());
508 
509  const MachineOperand &MO = MI->getOperand(OperIdx);
510  Register Reg = MO.getReg();
511 
512  // Remember the use. Data dependencies will be added when we find the def.
515  CurrentVRegUses.insert(VReg2SUnitOperIdx(Reg, LaneMask, OperIdx, SU));
516 
517  // Add antidependences to the following defs of the vreg.
519  CurrentVRegDefs.end())) {
520  // Ignore defs for unrelated lanes.
521  LaneBitmask PrevDefLaneMask = V2SU.LaneMask;
522  if ((PrevDefLaneMask & LaneMask).none())
523  continue;
524  if (V2SU.SU == SU)
525  continue;
526 
527  V2SU.SU->addPred(SDep(SU, SDep::Anti, Reg));
528  }
529 }
530 
531 /// Returns true if MI is an instruction we are unable to reason about
532 /// (like a call or something with unmodeled side effects).
533 static inline bool isGlobalMemoryObject(MachineInstr *MI) {
534  return MI->isCall() || MI->hasUnmodeledSideEffects() ||
535  (MI->hasOrderedMemoryRef() && !MI->isDereferenceableInvariantLoad());
536 }
537 
539  unsigned Latency) {
540  if (SUa->getInstr()->mayAlias(AAForDep, *SUb->getInstr(), UseTBAA)) {
541  SDep Dep(SUa, SDep::MayAliasMem);
542  Dep.setLatency(Latency);
543  SUb->addPred(Dep);
544  }
545 }
546 
547 /// Creates an SUnit for each real instruction, numbered in top-down
548 /// topological order. The instruction order A < B, implies that no edge exists
549 /// from B to A.
550 ///
551 /// Map each real instruction to its SUnit.
552 ///
553 /// After initSUnits, the SUnits vector cannot be resized and the scheduler may
554 /// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs
555 /// instead of pointers.
556 ///
557 /// MachineScheduler relies on initSUnits numbering the nodes by their order in
558 /// the original instruction list.
560  // We'll be allocating one SUnit for each real instruction in the region,
561  // which is contained within a basic block.
562  SUnits.reserve(NumRegionInstrs);
563 
565  if (MI.isDebugOrPseudoInstr())
566  continue;
567 
568  SUnit *SU = newSUnit(&MI);
569  MISUnitMap[&MI] = SU;
570 
571  SU->isCall = MI.isCall();
572  SU->isCommutable = MI.isCommutable();
573 
574  // Assign the Latency field of SU using target-provided information.
575  SU->Latency = SchedModel.computeInstrLatency(SU->getInstr());
576 
577  // If this SUnit uses a reserved or unbuffered resource, mark it as such.
578  //
579  // Reserved resources block an instruction from issuing and stall the
580  // entire pipeline. These are identified by BufferSize=0.
581  //
582  // Unbuffered resources prevent execution of subsequent instructions that
583  // require the same resources. This is used for in-order execution pipelines
584  // within an out-of-order core. These are identified by BufferSize=1.
586  const MCSchedClassDesc *SC = getSchedClass(SU);
587  for (const MCWriteProcResEntry &PRE :
590  switch (SchedModel.getProcResource(PRE.ProcResourceIdx)->BufferSize) {
591  case 0:
592  SU->hasReservedResource = true;
593  break;
594  case 1:
595  SU->isUnbuffered = true;
596  break;
597  default:
598  break;
599  }
600  }
601  }
602  }
603 }
604 
605 class ScheduleDAGInstrs::Value2SUsMap : public MapVector<ValueType, SUList> {
606  /// Current total number of SUs in map.
607  unsigned NumNodes = 0;
608 
609  /// 1 for loads, 0 for stores. (see comment in SUList)
610  unsigned TrueMemOrderLatency;
611 
612 public:
613  Value2SUsMap(unsigned lat = 0) : TrueMemOrderLatency(lat) {}
614 
615  /// To keep NumNodes up to date, insert() is used instead of
616  /// this operator w/ push_back().
618  llvm_unreachable("Don't use. Use insert() instead."); };
619 
620  /// Adds SU to the SUList of V. If Map grows huge, reduce its size by calling
621  /// reduce().
622  void inline insert(SUnit *SU, ValueType V) {
623  MapVector::operator[](V).push_back(SU);
624  NumNodes++;
625  }
626 
627  /// Clears the list of SUs mapped to V.
628  void inline clearList(ValueType V) {
629  iterator Itr = find(V);
630  if (Itr != end()) {
631  assert(NumNodes >= Itr->second.size());
632  NumNodes -= Itr->second.size();
633 
634  Itr->second.clear();
635  }
636  }
637 
638  /// Clears map from all contents.
639  void clear() {
641  NumNodes = 0;
642  }
643 
644  unsigned inline size() const { return NumNodes; }
645 
646  /// Counts the number of SUs in this map after a reduction.
647  void reComputeSize() {
648  NumNodes = 0;
649  for (auto &I : *this)
650  NumNodes += I.second.size();
651  }
652 
653  unsigned inline getTrueMemOrderLatency() const {
654  return TrueMemOrderLatency;
655  }
656 
657  void dump();
658 };
659 
661  Value2SUsMap &Val2SUsMap) {
662  for (auto &I : Val2SUsMap)
663  addChainDependencies(SU, I.second,
664  Val2SUsMap.getTrueMemOrderLatency());
665 }
666 
668  Value2SUsMap &Val2SUsMap,
669  ValueType V) {
670  Value2SUsMap::iterator Itr = Val2SUsMap.find(V);
671  if (Itr != Val2SUsMap.end())
672  addChainDependencies(SU, Itr->second,
673  Val2SUsMap.getTrueMemOrderLatency());
674 }
675 
677  assert(BarrierChain != nullptr);
678 
679  for (auto &[V, SUs] : map) {
680  (void)V;
681  for (auto *SU : SUs)
682  SU->addPredBarrier(BarrierChain);
683  }
684  map.clear();
685 }
686 
688  assert(BarrierChain != nullptr);
689 
690  // Go through all lists of SUs.
691  for (Value2SUsMap::iterator I = map.begin(), EE = map.end(); I != EE;) {
692  Value2SUsMap::iterator CurrItr = I++;
693  SUList &sus = CurrItr->second;
694  SUList::iterator SUItr = sus.begin(), SUEE = sus.end();
695  for (; SUItr != SUEE; ++SUItr) {
696  // Stop on BarrierChain or any instruction above it.
697  if ((*SUItr)->NodeNum <= BarrierChain->NodeNum)
698  break;
699 
700  (*SUItr)->addPredBarrier(BarrierChain);
701  }
702 
703  // Remove also the BarrierChain from list if present.
704  if (SUItr != SUEE && *SUItr == BarrierChain)
705  SUItr++;
706 
707  // Remove all SUs that are now successors of BarrierChain.
708  if (SUItr != sus.begin())
709  sus.erase(sus.begin(), SUItr);
710  }
711 
712  // Remove all entries with empty su lists.
713  map.remove_if([&](std::pair<ValueType, SUList> &mapEntry) {
714  return (mapEntry.second.empty()); });
715 
716  // Recompute the size of the map (NumNodes).
717  map.reComputeSize();
718 }
719 
721  RegPressureTracker *RPTracker,
722  PressureDiffs *PDiffs,
723  LiveIntervals *LIS,
724  bool TrackLaneMasks) {
727  : ST.useAA();
728  AAForDep = UseAA ? AA : nullptr;
729 
730  BarrierChain = nullptr;
731 
732  this->TrackLaneMasks = TrackLaneMasks;
733  MISUnitMap.clear();
735 
736  // Create an SUnit for each real instruction.
737  initSUnits();
738 
739  if (PDiffs)
740  PDiffs->init(SUnits.size());
741 
742  // We build scheduling units by walking a block's instruction list
743  // from bottom to top.
744 
745  // Each MIs' memory operand(s) is analyzed to a list of underlying
746  // objects. The SU is then inserted in the SUList(s) mapped from the
747  // Value(s). Each Value thus gets mapped to lists of SUs depending
748  // on it, stores and loads kept separately. Two SUs are trivially
749  // non-aliasing if they both depend on only identified Values and do
750  // not share any common Value.
751  Value2SUsMap Stores, Loads(1 /*TrueMemOrderLatency*/);
752 
753  // Certain memory accesses are known to not alias any SU in Stores
754  // or Loads, and have therefore their own 'NonAlias'
755  // domain. E.g. spill / reload instructions never alias LLVM I/R
756  // Values. It would be nice to assume that this type of memory
757  // accesses always have a proper memory operand modelling, and are
758  // therefore never unanalyzable, but this is conservatively not
759  // done.
760  Value2SUsMap NonAliasStores, NonAliasLoads(1 /*TrueMemOrderLatency*/);
761 
762  // Track all instructions that may raise floating-point exceptions.
763  // These do not depend on one other (or normal loads or stores), but
764  // must not be rescheduled across global barriers. Note that we don't
765  // really need a "map" here since we don't track those MIs by value;
766  // using the same Value2SUsMap data type here is simply a matter of
767  // convenience.
768  Value2SUsMap FPExceptions;
769 
770  // Remove any stale debug info; sometimes BuildSchedGraph is called again
771  // without emitting the info from the previous call.
772  DbgValues.clear();
773  FirstDbgValue = nullptr;
774 
775  assert(Defs.empty() && Uses.empty() &&
776  "Only BuildGraph should update Defs/Uses");
779 
780  assert(CurrentVRegDefs.empty() && "nobody else should use CurrentVRegDefs");
781  assert(CurrentVRegUses.empty() && "nobody else should use CurrentVRegUses");
782  unsigned NumVirtRegs = MRI.getNumVirtRegs();
783  CurrentVRegDefs.setUniverse(NumVirtRegs);
784  CurrentVRegUses.setUniverse(NumVirtRegs);
785 
786  // Model data dependencies between instructions being scheduled and the
787  // ExitSU.
789 
790  // Walk the list of instructions, from bottom moving up.
791  MachineInstr *DbgMI = nullptr;
793  MII != MIE; --MII) {
794  MachineInstr &MI = *std::prev(MII);
795  if (DbgMI) {
796  DbgValues.emplace_back(DbgMI, &MI);
797  DbgMI = nullptr;
798  }
799 
800  if (MI.isDebugValue() || MI.isDebugPHI()) {
801  DbgMI = &MI;
802  continue;
803  }
804 
805  if (MI.isDebugLabel() || MI.isDebugRef() || MI.isPseudoProbe())
806  continue;
807 
808  SUnit *SU = MISUnitMap[&MI];
809  assert(SU && "No SUnit mapped to this MI");
810 
811  if (RPTracker) {
812  RegisterOperands RegOpers;
813  RegOpers.collect(MI, *TRI, MRI, TrackLaneMasks, false);
814  if (TrackLaneMasks) {
815  SlotIndex SlotIdx = LIS->getInstructionIndex(MI);
816  RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx);
817  }
818  if (PDiffs != nullptr)
819  PDiffs->addInstruction(SU->NodeNum, RegOpers, MRI);
820 
821  if (RPTracker->getPos() == RegionEnd || &*RPTracker->getPos() != &MI)
822  RPTracker->recedeSkipDebugValues();
823  assert(&*RPTracker->getPos() == &MI && "RPTracker in sync");
824  RPTracker->recede(RegOpers);
825  }
826 
827  assert(
828  (CanHandleTerminators || (!MI.isTerminator() && !MI.isPosition())) &&
829  "Cannot schedule terminators or labels!");
830 
831  // Add register-based dependencies (data, anti, and output).
832  // For some instructions (calls, returns, inline-asm, etc.) there can
833  // be explicit uses and implicit defs, in which case the use will appear
834  // on the operand list before the def. Do two passes over the operand
835  // list to make sure that defs are processed before any uses.
836  bool HasVRegDef = false;
837  for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) {
838  const MachineOperand &MO = MI.getOperand(j);
839  if (!MO.isReg() || !MO.isDef())
840  continue;
841  Register Reg = MO.getReg();
843  addPhysRegDeps(SU, j);
844  } else if (Register::isVirtualRegister(Reg)) {
845  HasVRegDef = true;
846  addVRegDefDeps(SU, j);
847  }
848  }
849  // Now process all uses.
850  for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) {
851  const MachineOperand &MO = MI.getOperand(j);
852  // Only look at use operands.
853  // We do not need to check for MO.readsReg() here because subsequent
854  // subregister defs will get output dependence edges and need no
855  // additional use dependencies.
856  if (!MO.isReg() || !MO.isUse())
857  continue;
858  Register Reg = MO.getReg();
860  addPhysRegDeps(SU, j);
861  } else if (Register::isVirtualRegister(Reg) && MO.readsReg()) {
862  addVRegUseDeps(SU, j);
863  }
864  }
865 
866  // If we haven't seen any uses in this scheduling region, create a
867  // dependence edge to ExitSU to model the live-out latency. This is required
868  // for vreg defs with no in-region use, and prefetches with no vreg def.
869  //
870  // FIXME: NumDataSuccs would be more precise than NumSuccs here. This
871  // check currently relies on being called before adding chain deps.
872  if (SU->NumSuccs == 0 && SU->Latency > 1 && (HasVRegDef || MI.mayLoad())) {
873  SDep Dep(SU, SDep::Artificial);
874  Dep.setLatency(SU->Latency - 1);
875  ExitSU.addPred(Dep);
876  }
877 
878  // Add memory dependencies (Note: isStoreToStackSlot and
879  // isLoadFromStackSLot are not usable after stack slots are lowered to
880  // actual addresses).
881 
882  // This is a barrier event that acts as a pivotal node in the DAG.
883  if (isGlobalMemoryObject(&MI)) {
884 
885  // Become the barrier chain.
886  if (BarrierChain)
888  BarrierChain = SU;
889 
890  LLVM_DEBUG(dbgs() << "Global memory object and new barrier chain: SU("
891  << BarrierChain->NodeNum << ").\n";);
892 
893  // Add dependencies against everything below it and clear maps.
894  addBarrierChain(Stores);
895  addBarrierChain(Loads);
896  addBarrierChain(NonAliasStores);
897  addBarrierChain(NonAliasLoads);
898  addBarrierChain(FPExceptions);
899 
900  continue;
901  }
902 
903  // Instructions that may raise FP exceptions may not be moved
904  // across any global barriers.
905  if (MI.mayRaiseFPException()) {
906  if (BarrierChain)
908 
909  FPExceptions.insert(SU, UnknownValue);
910 
911  if (FPExceptions.size() >= HugeRegion) {
912  LLVM_DEBUG(dbgs() << "Reducing FPExceptions map.\n";);
913  Value2SUsMap empty;
914  reduceHugeMemNodeMaps(FPExceptions, empty, getReductionSize());
915  }
916  }
917 
918  // If it's not a store or a variant load, we're done.
919  if (!MI.mayStore() &&
920  !(MI.mayLoad() && !MI.isDereferenceableInvariantLoad()))
921  continue;
922 
923  // Always add dependecy edge to BarrierChain if present.
924  if (BarrierChain)
926 
927  // Find the underlying objects for MI. The Objs vector is either
928  // empty, or filled with the Values of memory locations which this
929  // SU depends on.
931  bool ObjsFound = getUnderlyingObjectsForInstr(&MI, MFI, Objs,
932  MF.getDataLayout());
933 
934  if (MI.mayStore()) {
935  if (!ObjsFound) {
936  // An unknown store depends on all stores and loads.
937  addChainDependencies(SU, Stores);
938  addChainDependencies(SU, NonAliasStores);
939  addChainDependencies(SU, Loads);
940  addChainDependencies(SU, NonAliasLoads);
941 
942  // Map this store to 'UnknownValue'.
943  Stores.insert(SU, UnknownValue);
944  } else {
945  // Add precise dependencies against all previously seen memory
946  // accesses mapped to the same Value(s).
947  for (const UnderlyingObject &UnderlObj : Objs) {
948  ValueType V = UnderlObj.getValue();
949  bool ThisMayAlias = UnderlObj.mayAlias();
950 
951  // Add dependencies to previous stores and loads mapped to V.
952  addChainDependencies(SU, (ThisMayAlias ? Stores : NonAliasStores), V);
953  addChainDependencies(SU, (ThisMayAlias ? Loads : NonAliasLoads), V);
954  }
955  // Update the store map after all chains have been added to avoid adding
956  // self-loop edge if multiple underlying objects are present.
957  for (const UnderlyingObject &UnderlObj : Objs) {
958  ValueType V = UnderlObj.getValue();
959  bool ThisMayAlias = UnderlObj.mayAlias();
960 
961  // Map this store to V.
962  (ThisMayAlias ? Stores : NonAliasStores).insert(SU, V);
963  }
964  // The store may have dependencies to unanalyzable loads and
965  // stores.
967  addChainDependencies(SU, Stores, UnknownValue);
968  }
969  } else { // SU is a load.
970  if (!ObjsFound) {
971  // An unknown load depends on all stores.
972  addChainDependencies(SU, Stores);
973  addChainDependencies(SU, NonAliasStores);
974 
975  Loads.insert(SU, UnknownValue);
976  } else {
977  for (const UnderlyingObject &UnderlObj : Objs) {
978  ValueType V = UnderlObj.getValue();
979  bool ThisMayAlias = UnderlObj.mayAlias();
980 
981  // Add precise dependencies against all previously seen stores
982  // mapping to the same Value(s).
983  addChainDependencies(SU, (ThisMayAlias ? Stores : NonAliasStores), V);
984 
985  // Map this load to V.
986  (ThisMayAlias ? Loads : NonAliasLoads).insert(SU, V);
987  }
988  // The load may have dependencies to unanalyzable stores.
989  addChainDependencies(SU, Stores, UnknownValue);
990  }
991  }
992 
993  // Reduce maps if they grow huge.
994  if (Stores.size() + Loads.size() >= HugeRegion) {
995  LLVM_DEBUG(dbgs() << "Reducing Stores and Loads maps.\n";);
996  reduceHugeMemNodeMaps(Stores, Loads, getReductionSize());
997  }
998  if (NonAliasStores.size() + NonAliasLoads.size() >= HugeRegion) {
999  LLVM_DEBUG(
1000  dbgs() << "Reducing NonAliasStores and NonAliasLoads maps.\n";);
1001  reduceHugeMemNodeMaps(NonAliasStores, NonAliasLoads, getReductionSize());
1002  }
1003  }
1004 
1005  if (DbgMI)
1006  FirstDbgValue = DbgMI;
1007 
1008  Defs.clear();
1009  Uses.clear();
1012 
1013  Topo.MarkDirty();
1014 }
1015 
1017  PSV->printCustom(OS);
1018  return OS;
1019 }
1020 
1022  for (const auto &[ValType, SUs] : *this) {
1023  if (ValType.is<const Value*>()) {
1024  const Value *V = ValType.get<const Value*>();
1025  if (isa<UndefValue>(V))
1026  dbgs() << "Unknown";
1027  else
1028  V->printAsOperand(dbgs());
1029  }
1030  else if (ValType.is<const PseudoSourceValue*>())
1031  dbgs() << ValType.get<const PseudoSourceValue*>();
1032  else
1033  llvm_unreachable("Unknown Value type.");
1034 
1035  dbgs() << " : ";
1036  dumpSUList(SUs);
1037  }
1038 }
1039 
1040 void ScheduleDAGInstrs::reduceHugeMemNodeMaps(Value2SUsMap &stores,
1041  Value2SUsMap &loads, unsigned N) {
1042  LLVM_DEBUG(dbgs() << "Before reduction:\nStoring SUnits:\n"; stores.dump();
1043  dbgs() << "Loading SUnits:\n"; loads.dump());
1044 
1045  // Insert all SU's NodeNums into a vector and sort it.
1046  std::vector<unsigned> NodeNums;
1047  NodeNums.reserve(stores.size() + loads.size());
1048  for (const auto &[V, SUs] : stores) {
1049  (void)V;
1050  for (const auto *SU : SUs)
1051  NodeNums.push_back(SU->NodeNum);
1052  }
1053  for (const auto &[V, SUs] : loads) {
1054  (void)V;
1055  for (const auto *SU : SUs)
1056  NodeNums.push_back(SU->NodeNum);
1057  }
1058  llvm::sort(NodeNums);
1059 
1060  // The N last elements in NodeNums will be removed, and the SU with
1061  // the lowest NodeNum of them will become the new BarrierChain to
1062  // let the not yet seen SUs have a dependency to the removed SUs.
1063  assert(N <= NodeNums.size());
1064  SUnit *newBarrierChain = &SUnits[*(NodeNums.end() - N)];
1065  if (BarrierChain) {
1066  // The aliasing and non-aliasing maps reduce independently of each
1067  // other, but share a common BarrierChain. Check if the
1068  // newBarrierChain is above the former one. If it is not, it may
1069  // introduce a loop to use newBarrierChain, so keep the old one.
1070  if (newBarrierChain->NodeNum < BarrierChain->NodeNum) {
1071  BarrierChain->addPredBarrier(newBarrierChain);
1072  BarrierChain = newBarrierChain;
1073  LLVM_DEBUG(dbgs() << "Inserting new barrier chain: SU("
1074  << BarrierChain->NodeNum << ").\n";);
1075  }
1076  else
1077  LLVM_DEBUG(dbgs() << "Keeping old barrier chain: SU("
1078  << BarrierChain->NodeNum << ").\n";);
1079  }
1080  else
1081  BarrierChain = newBarrierChain;
1082 
1083  insertBarrierChain(stores);
1084  insertBarrierChain(loads);
1085 
1086  LLVM_DEBUG(dbgs() << "After reduction:\nStoring SUnits:\n"; stores.dump();
1087  dbgs() << "Loading SUnits:\n"; loads.dump());
1088 }
1089 
1090 static void toggleKills(const MachineRegisterInfo &MRI, LivePhysRegs &LiveRegs,
1091  MachineInstr &MI, bool addToLiveRegs) {
1092  for (MachineOperand &MO : MI.operands()) {
1093  if (!MO.isReg() || !MO.readsReg())
1094  continue;
1095  Register Reg = MO.getReg();
1096  if (!Reg)
1097  continue;
1098 
1099  // Things that are available after the instruction are killed by it.
1100  bool IsKill = LiveRegs.available(MRI, Reg);
1101  MO.setIsKill(IsKill);
1102  if (addToLiveRegs)
1103  LiveRegs.addReg(Reg);
1104  }
1105 }
1106 
1107 void ScheduleDAGInstrs::fixupKills(MachineBasicBlock &MBB) {
1108  LLVM_DEBUG(dbgs() << "Fixup kills for " << printMBBReference(MBB) << '\n');
1109 
1110  LiveRegs.init(*TRI);
1111  LiveRegs.addLiveOuts(MBB);
1112 
1113  // Examine block from end to start...
1114  for (MachineInstr &MI : llvm::reverse(MBB)) {
1115  if (MI.isDebugOrPseudoInstr())
1116  continue;
1117 
1118  // Update liveness. Registers that are defed but not used in this
1119  // instruction are now dead. Mark register and all subregs as they
1120  // are completely defined.
1121  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
1122  const MachineOperand &MO = *O;
1123  if (MO.isReg()) {
1124  if (!MO.isDef())
1125  continue;
1126  Register Reg = MO.getReg();
1127  if (!Reg)
1128  continue;
1129  LiveRegs.removeReg(Reg);
1130  } else if (MO.isRegMask()) {
1131  LiveRegs.removeRegsInMask(MO);
1132  }
1133  }
1134 
1135  // If there is a bundle header fix it up first.
1136  if (!MI.isBundled()) {
1137  toggleKills(MRI, LiveRegs, MI, true);
1138  } else {
1139  MachineBasicBlock::instr_iterator Bundle = MI.getIterator();
1140  if (MI.isBundle())
1141  toggleKills(MRI, LiveRegs, MI, false);
1142 
1143  // Some targets make the (questionable) assumtion that the instructions
1144  // inside the bundle are ordered and consequently only the last use of
1145  // a register inside the bundle can kill it.
1146  MachineBasicBlock::instr_iterator I = std::next(Bundle);
1147  while (I->isBundledWithSucc())
1148  ++I;
1149  do {
1150  if (!I->isDebugOrPseudoInstr())
1151  toggleKills(MRI, LiveRegs, *I, true);
1152  --I;
1153  } while (I != Bundle);
1154  }
1155  }
1156 }
1157 
1158 void ScheduleDAGInstrs::dumpNode(const SUnit &SU) const {
1159 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1160  dumpNodeName(SU);
1161  dbgs() << ": ";
1162  SU.getInstr()->dump();
1163 #endif
1164 }
1165 
1167 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1168  if (EntrySU.getInstr() != nullptr)
1169  dumpNodeAll(EntrySU);
1170  for (const SUnit &SU : SUnits)
1171  dumpNodeAll(SU);
1172  if (ExitSU.getInstr() != nullptr)
1173  dumpNodeAll(ExitSU);
1174 #endif
1175 }
1176 
1177 std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
1178  std::string s;
1179  raw_string_ostream oss(s);
1180  if (SU == &EntrySU)
1181  oss << "<entry>";
1182  else if (SU == &ExitSU)
1183  oss << "<exit>";
1184  else
1185  SU->getInstr()->print(oss, /*IsStandalone=*/true);
1186  return oss.str();
1187 }
1188 
1189 /// Return the basic block label. It is not necessarilly unique because a block
1190 /// contains multiple scheduling regions. But it is fine for visualization.
1191 std::string ScheduleDAGInstrs::getDAGName() const {
1192  return "dag." + BB->getFullName();
1193 }
1194 
1195 bool ScheduleDAGInstrs::canAddEdge(SUnit *SuccSU, SUnit *PredSU) {
1196  return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
1197 }
1198 
1199 bool ScheduleDAGInstrs::addEdge(SUnit *SuccSU, const SDep &PredDep) {
1200  if (SuccSU != &ExitSU) {
1201  // Do not use WillCreateCycle, it assumes SD scheduling.
1202  // If Pred is reachable from Succ, then the edge creates a cycle.
1203  if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
1204  return false;
1205  Topo.AddPredQueued(SuccSU, PredDep.getSUnit());
1206  }
1207  SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial());
1208  // Return true regardless of whether a new edge needed to be inserted.
1209  return true;
1210 }
1211 
1212 //===----------------------------------------------------------------------===//
1213 // SchedDFSResult Implementation
1214 //===----------------------------------------------------------------------===//
1215 
1216 namespace llvm {
1217 
1218 /// Internal state used to compute SchedDFSResult.
1220  SchedDFSResult &R;
1221 
1222  /// Join DAG nodes into equivalence classes by their subtree.
1223  IntEqClasses SubtreeClasses;
1224  /// List PredSU, SuccSU pairs that represent data edges between subtrees.
1225  std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs;
1226 
1227  struct RootData {
1228  unsigned NodeID;
1229  unsigned ParentNodeID; ///< Parent node (member of the parent subtree).
1230  unsigned SubInstrCount = 0; ///< Instr count in this tree only, not
1231  /// children.
1232 
1233  RootData(unsigned id): NodeID(id),
1234  ParentNodeID(SchedDFSResult::InvalidSubtreeID) {}
1235 
1236  unsigned getSparseSetIndex() const { return NodeID; }
1237  };
1238 
1239  SparseSet<RootData> RootSet;
1240 
1241 public:
1242  SchedDFSImpl(SchedDFSResult &r): R(r), SubtreeClasses(R.DFSNodeData.size()) {
1243  RootSet.setUniverse(R.DFSNodeData.size());
1244  }
1245 
1246  /// Returns true if this node been visited by the DFS traversal.
1247  ///
1248  /// During visitPostorderNode the Node's SubtreeID is assigned to the Node
1249  /// ID. Later, SubtreeID is updated but remains valid.
1250  bool isVisited(const SUnit *SU) const {
1251  return R.DFSNodeData[SU->NodeNum].SubtreeID
1252  != SchedDFSResult::InvalidSubtreeID;
1253  }
1254 
1255  /// Initializes this node's instruction count. We don't need to flag the node
1256  /// visited until visitPostorder because the DAG cannot have cycles.
1257  void visitPreorder(const SUnit *SU) {
1258  R.DFSNodeData[SU->NodeNum].InstrCount =
1259  SU->getInstr()->isTransient() ? 0 : 1;
1260  }
1261 
1262  /// Called once for each node after all predecessors are visited. Revisit this
1263  /// node's predecessors and potentially join them now that we know the ILP of
1264  /// the other predecessors.
1265  void visitPostorderNode(const SUnit *SU) {
1266  // Mark this node as the root of a subtree. It may be joined with its
1267  // successors later.
1268  R.DFSNodeData[SU->NodeNum].SubtreeID = SU->NodeNum;
1269  RootData RData(SU->NodeNum);
1270  RData.SubInstrCount = SU->getInstr()->isTransient() ? 0 : 1;
1271 
1272  // If any predecessors are still in their own subtree, they either cannot be
1273  // joined or are large enough to remain separate. If this parent node's
1274  // total instruction count is not greater than a child subtree by at least
1275  // the subtree limit, then try to join it now since splitting subtrees is
1276  // only useful if multiple high-pressure paths are possible.
1277  unsigned InstrCount = R.DFSNodeData[SU->NodeNum].InstrCount;
1278  for (const SDep &PredDep : SU->Preds) {
1279  if (PredDep.getKind() != SDep::Data)
1280  continue;
1281  unsigned PredNum = PredDep.getSUnit()->NodeNum;
1282  if ((InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit)
1283  joinPredSubtree(PredDep, SU, /*CheckLimit=*/false);
1284 
1285  // Either link or merge the TreeData entry from the child to the parent.
1286  if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1287  // If the predecessor's parent is invalid, this is a tree edge and the
1288  // current node is the parent.
1289  if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1290  RootSet[PredNum].ParentNodeID = SU->NodeNum;
1291  }
1292  else if (RootSet.count(PredNum)) {
1293  // The predecessor is not a root, but is still in the root set. This
1294  // must be the new parent that it was just joined to. Note that
1295  // RootSet[PredNum].ParentNodeID may either be invalid or may still be
1296  // set to the original parent.
1297  RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1298  RootSet.erase(PredNum);
1299  }
1300  }
1301  RootSet[SU->NodeNum] = RData;
1302  }
1303 
1304  /// Called once for each tree edge after calling visitPostOrderNode on
1305  /// the predecessor. Increment the parent node's instruction count and
1306  /// preemptively join this subtree to its parent's if it is small enough.
1307  void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ) {
1308  R.DFSNodeData[Succ->NodeNum].InstrCount
1309  += R.DFSNodeData[PredDep.getSUnit()->NodeNum].InstrCount;
1310  joinPredSubtree(PredDep, Succ);
1311  }
1312 
1313  /// Adds a connection for cross edges.
1314  void visitCrossEdge(const SDep &PredDep, const SUnit *Succ) {
1315  ConnectionPairs.emplace_back(PredDep.getSUnit(), Succ);
1316  }
1317 
1318  /// Sets each node's subtree ID to the representative ID and record
1319  /// connections between trees.
1320  void finalize() {
1321  SubtreeClasses.compress();
1322  R.DFSTreeData.resize(SubtreeClasses.getNumClasses());
1323  assert(SubtreeClasses.getNumClasses() == RootSet.size()
1324  && "number of roots should match trees");
1325  for (const RootData &Root : RootSet) {
1326  unsigned TreeID = SubtreeClasses[Root.NodeID];
1327  if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1328  R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID];
1329  R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount;
1330  // Note that SubInstrCount may be greater than InstrCount if we joined
1331  // subtrees across a cross edge. InstrCount will be attributed to the
1332  // original parent, while SubInstrCount will be attributed to the joined
1333  // parent.
1334  }
1335  R.SubtreeConnections.resize(SubtreeClasses.getNumClasses());
1336  R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses());
1337  LLVM_DEBUG(dbgs() << R.getNumSubtrees() << " subtrees:\n");
1338  for (unsigned Idx = 0, End = R.DFSNodeData.size(); Idx != End; ++Idx) {
1339  R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx];
1340  LLVM_DEBUG(dbgs() << " SU(" << Idx << ") in tree "
1341  << R.DFSNodeData[Idx].SubtreeID << '\n');
1342  }
1343  for (const auto &[Pred, Succ] : ConnectionPairs) {
1344  unsigned PredTree = SubtreeClasses[Pred->NodeNum];
1345  unsigned SuccTree = SubtreeClasses[Succ->NodeNum];
1346  if (PredTree == SuccTree)
1347  continue;
1348  unsigned Depth = Pred->getDepth();
1349  addConnection(PredTree, SuccTree, Depth);
1350  addConnection(SuccTree, PredTree, Depth);
1351  }
1352  }
1353 
1354 protected:
1355  /// Joins the predecessor subtree with the successor that is its DFS parent.
1356  /// Applies some heuristics before joining.
1357  bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ,
1358  bool CheckLimit = true) {
1359  assert(PredDep.getKind() == SDep::Data && "Subtrees are for data edges");
1360 
1361  // Check if the predecessor is already joined.
1362  const SUnit *PredSU = PredDep.getSUnit();
1363  unsigned PredNum = PredSU->NodeNum;
1364  if (R.DFSNodeData[PredNum].SubtreeID != PredNum)
1365  return false;
1366 
1367  // Four is the magic number of successors before a node is considered a
1368  // pinch point.
1369  unsigned NumDataSucs = 0;
1370  for (const SDep &SuccDep : PredSU->Succs) {
1371  if (SuccDep.getKind() == SDep::Data) {
1372  if (++NumDataSucs >= 4)
1373  return false;
1374  }
1375  }
1376  if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit)
1377  return false;
1378  R.DFSNodeData[PredNum].SubtreeID = Succ->NodeNum;
1379  SubtreeClasses.join(Succ->NodeNum, PredNum);
1380  return true;
1381  }
1382 
1383  /// Called by finalize() to record a connection between trees.
1384  void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth) {
1385  if (!Depth)
1386  return;
1387 
1388  do {
1390  R.SubtreeConnections[FromTree];
1391  for (SchedDFSResult::Connection &C : Connections) {
1392  if (C.TreeID == ToTree) {
1393  C.Level = std::max(C.Level, Depth);
1394  return;
1395  }
1396  }
1397  Connections.push_back(SchedDFSResult::Connection(ToTree, Depth));
1398  FromTree = R.DFSTreeData[FromTree].ParentTreeID;
1399  } while (FromTree != SchedDFSResult::InvalidSubtreeID);
1400  }
1401 };
1402 
1403 } // end namespace llvm
1404 
1405 namespace {
1406 
1407 /// Manage the stack used by a reverse depth-first search over the DAG.
1408 class SchedDAGReverseDFS {
1409  std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack;
1410 
1411 public:
1412  bool isComplete() const { return DFSStack.empty(); }
1413 
1414  void follow(const SUnit *SU) {
1415  DFSStack.emplace_back(SU, SU->Preds.begin());
1416  }
1417  void advance() { ++DFSStack.back().second; }
1418 
1419  const SDep *backtrack() {
1420  DFSStack.pop_back();
1421  return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second);
1422  }
1423 
1424  const SUnit *getCurr() const { return DFSStack.back().first; }
1425 
1426  SUnit::const_pred_iterator getPred() const { return DFSStack.back().second; }
1427 
1428  SUnit::const_pred_iterator getPredEnd() const {
1429  return getCurr()->Preds.end();
1430  }
1431 };
1432 
1433 } // end anonymous namespace
1434 
1435 static bool hasDataSucc(const SUnit *SU) {
1436  for (const SDep &SuccDep : SU->Succs) {
1437  if (SuccDep.getKind() == SDep::Data &&
1438  !SuccDep.getSUnit()->isBoundaryNode())
1439  return true;
1440  }
1441  return false;
1442 }
1443 
1444 /// Computes an ILP metric for all nodes in the subDAG reachable via depth-first
1445 /// search from this root.
1446 void SchedDFSResult::compute(ArrayRef<SUnit> SUnits) {
1447  if (!IsBottomUp)
1448  llvm_unreachable("Top-down ILP metric is unimplemented");
1449 
1450  SchedDFSImpl Impl(*this);
1451  for (const SUnit &SU : SUnits) {
1452  if (Impl.isVisited(&SU) || hasDataSucc(&SU))
1453  continue;
1454 
1455  SchedDAGReverseDFS DFS;
1456  Impl.visitPreorder(&SU);
1457  DFS.follow(&SU);
1458  while (true) {
1459  // Traverse the leftmost path as far as possible.
1460  while (DFS.getPred() != DFS.getPredEnd()) {
1461  const SDep &PredDep = *DFS.getPred();
1462  DFS.advance();
1463  // Ignore non-data edges.
1464  if (PredDep.getKind() != SDep::Data
1465  || PredDep.getSUnit()->isBoundaryNode()) {
1466  continue;
1467  }
1468  // An already visited edge is a cross edge, assuming an acyclic DAG.
1469  if (Impl.isVisited(PredDep.getSUnit())) {
1470  Impl.visitCrossEdge(PredDep, DFS.getCurr());
1471  continue;
1472  }
1473  Impl.visitPreorder(PredDep.getSUnit());
1474  DFS.follow(PredDep.getSUnit());
1475  }
1476  // Visit the top of the stack in postorder and backtrack.
1477  const SUnit *Child = DFS.getCurr();
1478  const SDep *PredDep = DFS.backtrack();
1479  Impl.visitPostorderNode(Child);
1480  if (PredDep)
1481  Impl.visitPostorderEdge(*PredDep, DFS.getCurr());
1482  if (DFS.isComplete())
1483  break;
1484  }
1485  }
1486  Impl.finalize();
1487 }
1488 
1489 /// The root of the given SubtreeID was just scheduled. For all subtrees
1490 /// connected to this tree, record the depth of the connection so that the
1491 /// nearest connected subtrees can be prioritized.
1492 void SchedDFSResult::scheduleTree(unsigned SubtreeID) {
1493  for (const Connection &C : SubtreeConnections[SubtreeID]) {
1494  SubtreeConnectLevels[C.TreeID] =
1495  std::max(SubtreeConnectLevels[C.TreeID], C.Level);
1496  LLVM_DEBUG(dbgs() << " Tree: " << C.TreeID << " @"
1497  << SubtreeConnectLevels[C.TreeID] << '\n');
1498  }
1499 }
1500 
1501 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1503  OS << InstrCount << " / " << Length << " = ";
1504  if (!Length)
1505  OS << "BADILP";
1506  else
1507  OS << format("%g", ((double)InstrCount / Length));
1508 }
1509 
1511  dbgs() << *this << '\n';
1512 }
1513 
1514 namespace llvm {
1515 
1518  Val.print(OS);
1519  return OS;
1520 }
1521 
1522 } // end namespace llvm
1523 
1524 #endif
llvm::ScheduleDAGInstrs::initSUnits
void initSUnits()
Creates an SUnit for each real instruction, numbered in top-down topological order.
Definition: ScheduleDAGInstrs.cpp:559
llvm::ScheduleDAGInstrs::FirstDbgValue
MachineInstr * FirstDbgValue
Definition: ScheduleDAGInstrs.h:250
llvm::MapVector< ValueType, SUList >::iterator
typename std::vector< std::pair< ValueType, SUList >> ::iterator iterator
Definition: MapVector.h:50
llvm::LaneBitmask
Definition: LaneBitmask.h:40
llvm::SparseMultiSet::setUniverse
void setUniverse(unsigned U)
Set the universe size which determines the largest key the set can hold.
Definition: SparseMultiSet.h:202
llvm::ScheduleDAG::MRI
MachineRegisterInfo & MRI
Virtual/real register map.
Definition: ScheduleDAG.h:560
llvm::TargetSchedModel::getWriteProcResBegin
ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const
Definition: TargetSchedule.h:133
llvm::MCProcResourceDesc::BufferSize
int BufferSize
Definition: MCSchedule.h:48
ScheduleDAG.h
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
llvm::MachineInstr::getOperandNo
unsigned getOperandNo(const_mop_iterator I) const
Returns the number of the operand iterator I points to.
Definition: MachineInstr.h:706
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::MapVector::remove_if
void remove_if(Predicate Pred)
Remove the elements that match the predicate.
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:387
llvm::ScheduleDAGInstrs::addBarrierChain
void addBarrierChain(Value2SUsMap &map)
Adds barrier chain edges from all SUs in map, and then clear the map.
Definition: ScheduleDAGInstrs.cpp:676
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::LivePhysRegs::addReg
void addReg(MCPhysReg Reg)
Adds a physical register and all its sub-registers to the set.
Definition: LivePhysRegs.h:81
getUnderlyingObjectsForInstr
static bool getUnderlyingObjectsForInstr(const MachineInstr *MI, const MachineFrameInfo &MFI, UnderlyingObjectsVector &Objects, const DataLayout &DL)
If this machine instr has memory reference information and it can be tracked to a normal reference to...
Definition: ScheduleDAGInstrs.cpp:124
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::TargetRegisterClass::getLaneMask
LaneBitmask getLaneMask() const
Returns the combination of all lane masks of register in this class.
Definition: TargetRegisterInfo.h:209
llvm::SDep::Artificial
@ Artificial
Arbitrary strong DAG edge (no real dependence).
Definition: ScheduleDAG.h:72
isGlobalMemoryObject
static bool isGlobalMemoryObject(MachineInstr *MI)
Returns true if MI is an instruction we are unable to reason about (like a call or something with unm...
Definition: ScheduleDAGInstrs.cpp:533
ReductionSize
static cl::opt< unsigned > ReductionSize("dag-maps-reduction-size", cl::Hidden, cl::desc("A huge scheduling region will have maps reduced by this many " "nodes at a time. Defaults to HugeRegion / 2."))
llvm::ScheduleDAGInstrs::CurrentVRegUses
VReg2SUnitOperIdxMultiMap CurrentVRegUses
Tracks the last instructions in this region using each virtual register.
Definition: ScheduleDAGInstrs.h:176
llvm::Latency
@ Latency
Definition: SIMachineScheduler.h:34
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
getFunction
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:236
llvm::ScheduleDAGInstrs::buildSchedGraph
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
Definition: ScheduleDAGInstrs.cpp:720
llvm::ScheduleDAGInstrs::begin
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
Definition: ScheduleDAGInstrs.h:278
llvm::SparseMultiSet::find
iterator find(const KeyT &Key)
Find an element by its key.
Definition: SparseMultiSet.h:375
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::RegisterOperands
List of registers defined and used by a machine instruction.
Definition: RegisterPressure.h:166
llvm::UnderlyingObject
Definition: ScheduleDAGInstrs.h:109
ScheduleDAGInstrs.h
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:629
addEdge
static void addEdge(SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK)
Definition: LazyCallGraph.cpp:60
llvm::MachineOperand::setIsKill
void setIsKill(bool Val=true)
Definition: MachineOperand.h:509
llvm::MapVector::clear
void clear()
Definition: MapVector.h:89
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
hasDataSucc
static bool hasDataSucc(const SUnit *SU)
Definition: ScheduleDAGInstrs.cpp:1435
llvm::ScheduleDAGInstrs::Value2SUsMap::size
unsigned size() const
Definition: ScheduleDAGInstrs.cpp:644
llvm::ScheduleDAGInstrs::Value2SUsMap::clear
void clear()
Clears map from all contents.
Definition: ScheduleDAGInstrs.cpp:639
llvm::ScheduleDAGInstrs::NumRegionInstrs
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
Definition: ScheduleDAGInstrs.h:155
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:118
llvm::SchedDFSImpl
Internal state used to compute SchedDFSResult.
Definition: ScheduleDAGInstrs.cpp:1219
llvm::SparseMultiSet::clear
void clear()
Clears the set.
Definition: SparseMultiSet.h:342
ErrorHandling.h
llvm::MCRegisterInfo::getNumRegs
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Definition: MCRegisterInfo.h:491
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
MapVector.h
llvm::SUnit::const_pred_iterator
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
Definition: ScheduleDAG.h:261
llvm::SDep::Anti
@ Anti
A register anti-dependence (aka WAR).
Definition: ScheduleDAG.h:54
llvm::SUnit::isCommutable
bool isCommutable
Is a commutable instruction.
Definition: ScheduleDAG.h:278
llvm::SchedDFSImpl::addConnection
void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth)
Called by finalize() to record a connection between trees.
Definition: ScheduleDAGInstrs.cpp:1384
ValueTracking.h
llvm::SUnit::isCall
bool isCall
Is a function call.
Definition: ScheduleDAG.h:275
MachineBasicBlock.h
llvm::LivePhysRegs
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
stores
hexagon widen stores
Definition: HexagonStoreWidening.cpp:118
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::ScheduleDAGInstrs::Topo
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
Definition: ScheduleDAGInstrs.h:242
llvm::ScheduleDAGInstrs::SUList
std::list< SUnit * > SUList
A list of SUnits, used in Value2SUsMap, during DAG construction.
Definition: ScheduleDAGInstrs.h:191
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
InstrCount
static unsigned InstrCount
Definition: DFAPacketizer.cpp:53
llvm::TargetSchedModel::computeOutputLatency
unsigned computeOutputLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *DepMI) const
Output dependency latency of a pair of defs of the same register.
Definition: TargetSchedule.cpp:274
llvm::SDep::Kind
Kind
These are the different kinds of scheduling dependencies.
Definition: ScheduleDAG.h:52
IntEqClasses.h
llvm::SparseMultiSet::eraseAll
void eraseAll(const KeyT &K)
Erase all elements with the given key.
Definition: SparseMultiSet.h:482
llvm::RegPressureTracker
Track the current register pressure at some position in the instruction stream, and remember the high...
Definition: RegisterPressure.h:357
llvm::MachineInstr::getDesc
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:513
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::MachineMemOperand
A description of a memory reference used in the backend.
Definition: MachineMemOperand.h:127
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::ScheduleDAGInstrs::Value2SUsMap::insert
void insert(SUnit *SU, ValueType V)
Adds SU to the SUList of V.
Definition: ScheduleDAGInstrs.cpp:622
llvm::ScheduleDAGInstrs::startBlock
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
Definition: ScheduleDAGInstrs.cpp:174
llvm::SUnit::Succs
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
llvm::PressureDiffs
Array of PressureDiffs.
Definition: RegisterPressure.h:197
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:770
llvm::SchedDFSImpl::SchedDFSImpl
SchedDFSImpl(SchedDFSResult &r)
Definition: ScheduleDAGInstrs.cpp:1242
llvm::ScheduleDAGInstrs::getLaneMaskForMO
LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const
Returns a mask for which lanes get read/written by the given (register) machine operand.
Definition: ScheduleDAGInstrs.cpp:359
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::MCWriteProcResEntry
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
Definition: MCSchedule.h:63
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
toggleKills
static void toggleKills(const MachineRegisterInfo &MRI, LivePhysRegs &LiveRegs, MachineInstr &MI, bool addToLiveRegs)
Definition: ScheduleDAGInstrs.cpp:1090
llvm::ScheduleDAGInstrs::SchedModel
TargetSchedModel SchedModel
TargetSchedModel provides an interface to the machine model.
Definition: ScheduleDAGInstrs.h:126
Format.h
llvm::PressureDiffs::init
void init(unsigned N)
Initialize an array of N PressureDiffs.
Definition: RegisterPressure.cpp:648
HugeRegion
static cl::opt< unsigned > HugeRegion("dag-maps-huge-region", cl::Hidden, cl::init(1000), cl::desc("The limit to use while constructing the DAG " "prior to scheduling, at which point a trade-off " "is made to avoid excessive compile time."))
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::IntEqClasses::join
unsigned join(unsigned a, unsigned b)
Join the equivalence classes of a and b.
Definition: IntEqClasses.cpp:32
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
llvm::ScheduleDAGInstrs::end
MachineBasicBlock::iterator end() const
Returns an iterator to the bottom of the current scheduling region.
Definition: ScheduleDAGInstrs.h:281
llvm::LegalityPredicates::any
Predicate any(Predicate P0, Predicate P1)
True iff P0 or P1 are true.
Definition: LegalizerInfo.h:241
llvm::ScheduleDAGInstrs::Value2SUsMap::clearList
void clearList(ValueType V)
Clears the list of SUs mapped to V.
Definition: ScheduleDAGInstrs.cpp:628
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
RegisterPressure.h
llvm::LiveIntervals::getInstructionIndex
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
Definition: LiveIntervals.h:220
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
llvm::TargetSchedModel::getProcResource
const MCProcResourceDesc * getProcResource(unsigned PIdx) const
Get a processor resource by ID for convenience.
Definition: TargetSchedule.h:117
MachineRegisterInfo.h
llvm::ScheduleDAGInstrs::Value2SUsMap::reComputeSize
void reComputeSize()
Counts the number of SUs in this map after a reduction.
Definition: ScheduleDAGInstrs.cpp:647
AliasAnalysis.h
llvm::SDep::isArtificial
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
Definition: ScheduleDAG.h:200
llvm::TargetSchedModel::init
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
Definition: TargetSchedule.cpp:47
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::PressureDiffs::addInstruction
void addInstruction(unsigned Idx, const RegisterOperands &RegOpers, const MachineRegisterInfo &MRI)
Record pressure difference induced by the given operand list to node with index Idx.
Definition: RegisterPressure.cpp:659
llvm::ScheduleDAGTopologicalSort::MarkDirty
void MarkDirty()
Mark the ordering as temporarily broken, after a new node has been added.
Definition: ScheduleDAG.h:767
llvm::SparseSet::size
size_type size() const
size - Returns the number of elements in the set.
Definition: SparseSet.h:190
llvm::get
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
Definition: PointerIntPair.h:234
llvm::SparseMultiSet< PhysRegSUOper, identity< unsigned >, uint16_t >::RangePair
std::pair< iterator, iterator > RangePair
Definition: SparseMultiSet.h:315
CommandLine.h
llvm::SUnit::isBoundaryNode
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
Definition: ScheduleDAG.h:344
bb
< i1 > br i1 label label bb bb
Definition: README.txt:978
llvm::ScheduleDAGInstrs::ScheduleDAGInstrs
ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo *mli, bool RemoveKillFlags=false)
Definition: ScheduleDAGInstrs.cpp:107
llvm::MapVector::begin
iterator begin()
Definition: MapVector.h:70
llvm::ScheduleDAGInstrs::addChainDependencies
void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency)
Adds dependencies as needed from all SUs in list to SU.
Definition: ScheduleDAGInstrs.h:211
llvm::MachineInstr::isCall
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:872
llvm::ScheduleDAGInstrs::addVRegDefDeps
void addVRegDefDeps(SUnit *SU, unsigned OperIdx)
Adds register output and data dependencies from this SUnit to instructions that occur later in the sa...
Definition: ScheduleDAGInstrs.cpp:386
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:420
Constants.h
llvm::SUnit::isUnbuffered
bool isUnbuffered
Uses an unbuffered resource.
Definition: ScheduleDAG.h:288
llvm::TargetRegisterInfo::getSubRegIndexLaneMask
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
Definition: TargetRegisterInfo.h:380
llvm::AAResults
Definition: AliasAnalysis.h:294
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::ScheduleDAGInstrs::addSchedBarrierDeps
void addSchedBarrierDeps()
Adds dependencies from instructions in the current list of instructions being scheduled to scheduling...
Definition: ScheduleDAGInstrs.cpp:197
llvm::ScheduleDAGInstrs::UnknownValue
UndefValue * UnknownValue
For an unanalyzable memory access, this Value is used in maps.
Definition: ScheduleDAGInstrs.h:237
llvm::PhysRegSUOper
Record a physical register access.
Definition: ScheduleDAGInstrs.h:77
llvm::SUnit::Latency
unsigned short Latency
Node latency.
Definition: ScheduleDAG.h:273
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:369
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
llvm::ScheduleDAGInstrs::CanHandleTerminators
bool CanHandleTerminators
The standard DAG builder does not normally include terminators as DAG nodes because it does not creat...
Definition: ScheduleDAGInstrs.h:137
llvm::ScheduleDAGInstrs::exitRegion
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
Definition: ScheduleDAGInstrs.cpp:193
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::ScheduleDAGInstrs::BarrierChain
SUnit * BarrierChain
Remember a generic side-effecting instruction as we proceed.
Definition: ScheduleDAGInstrs.h:183
llvm::SUnit::NodeNum
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
llvm::MCSchedClassDesc
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition: MCSchedule.h:109
llvm::SparseMultiSet::empty
bool empty() const
Returns true if the set is empty.
Definition: SparseMultiSet.h:328
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::MachineInstr::mayAlias
bool mayAlias(AAResults *AA, const MachineInstr &Other, bool UseTBAA) const
Returns true if this instruction's memory access aliases the memory access of Other.
Definition: MachineInstr.cpp:1322
llvm::ScheduleDAGInstrs::addPhysRegDeps
void addPhysRegDeps(SUnit *SU, unsigned OperIdx)
Adds register dependencies (data, anti, and output) from this SUnit to following instructions in the ...
Definition: ScheduleDAGInstrs.cpp:282
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:45
llvm::ILPValue
Represent the ILP of the subDAG rooted at a DAG node.
Definition: ScheduleDFS.h:34
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
dumpSUList
static void dumpSUList(const ScheduleDAGInstrs::SUList &L)
Definition: ScheduleDAGInstrs.cpp:95
PseudoSourceValue.h
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:197
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::SUnit::setInstr
void setInstr(MachineInstr *MI)
Assigns the instruction for the SUnit.
Definition: ScheduleDAG.h:366
MachineInstrBundle.h
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
llvm::cl::Option::getNumOccurrences
int getNumOccurrences() const
Definition: CommandLine.h:402
llvm::SDep::Output
@ Output
A register output-dependence (aka WAW).
Definition: ScheduleDAG.h:55
llvm::SDep::Data
@ Data
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:53
llvm::wasm::ValType
ValType
Definition: Wasm.h:424
llvm::ScheduleDAGInstrs::RegionEnd
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
Definition: ScheduleDAGInstrs.h:152
llvm::TargetSchedModel::getWriteProcResEnd
ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const
Definition: TargetSchedule.h:137
llvm::PseudoSourceValue
Special value supplied for machine level alias analysis.
Definition: PseudoSourceValue.h:35
none
@ none
Definition: HWAddressSanitizer.cpp:188
llvm::ILPValue::print
void print(raw_ostream &OS) const
Definition: ScheduleDAGInstrs.cpp:1502
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
llvm::VReg2SUnit
An individual mapping from virtual register number to SUnit.
Definition: ScheduleDAGInstrs.h:53
llvm::MapVector::operator[]
ValueT & operator[](const KeyT &Key)
Definition: MapVector.h:99
Type.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::RegisterOperands::collect
void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, bool TrackLaneMasks, bool IgnoreDead)
Analyze the given instruction MI and fill in the Uses, Defs and DeadDefs list based on the MachineOpe...
Definition: RegisterPressure.cpp:570
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:647
llvm::MCInstrDesc::hasImplicitDefOfPhysReg
bool hasImplicitDefOfPhysReg(unsigned Reg, const MCRegisterInfo *MRI=nullptr) const
Return true if this instruction implicitly defines the specified physical register.
Definition: MCInstrDesc.cpp:32
llvm::ScheduleDAGInstrs::Value2SUsMap::Value2SUsMap
Value2SUsMap(unsigned lat=0)
Definition: ScheduleDAGInstrs.cpp:613
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1682
llvm::SparseMultiSet::end
iterator end()
Returns an iterator past this container.
Definition: SparseMultiSet.h:319
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:660
llvm::RegPressureTracker::recedeSkipDebugValues
void recedeSkipDebugValues()
Recede until we find an instruction which is not a DebugValue.
Definition: RegisterPressure.cpp:853
llvm::cl::opt< bool >
llvm::SparseMultiSet::insert
iterator insert(const ValueT &Val)
Insert a new element at the tail of the subset list.
Definition: SparseMultiSet.h:419
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
llvm::MachineOperand::isUndef
bool isUndef() const
Definition: MachineOperand.h:394
llvm::MapVector< ValueType, SUList >::find
iterator find(const ValueType &Key)
Definition: MapVector.h:148
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
LiveIntervals.h
getReductionSize
static unsigned getReductionSize()
Definition: ScheduleDAGInstrs.cpp:87
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
s
multiplies can be turned into SHL s
Definition: README.txt:370
llvm::IntEqClasses::compress
void compress()
compress - Compress equivalence classes by numbering them 0 .
Definition: IntEqClasses.cpp:60
llvm::LivePhysRegs::available
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
Definition: LivePhysRegs.cpp:141
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:384
llvm::TargetRegisterClass::HasDisjunctSubRegs
const bool HasDisjunctSubRegs
Whether the class supports two (or more) disjunct subregister indices.
Definition: TargetRegisterInfo.h:66
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::SUnit::getInstr
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
llvm::LaneBitmask::any
constexpr bool any() const
Definition: LaneBitmask.h:53
llvm::UndefValue
'undef' values are things that do not have specified contents.
Definition: Constants.h:1356
llvm::SparseMultiSet< PhysRegSUOper, identity< unsigned >, uint16_t >::iterator
iterator_base< SparseMultiSet * > iterator
Definition: SparseMultiSet.h:311
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:446
MCRegisterInfo.h
llvm::SDep::MayAliasMem
@ MayAliasMem
Nonvolatile load/Store instructions that may alias.
Definition: ScheduleDAG.h:70
size
i< reg-> size
Definition: README.txt:166
llvm::ScheduleDAGInstrs::Defs
Reg2SUnitsMap Defs
Defs, Uses - Remember where defs and uses of each register are as we iterate upward through the instr...
Definition: ScheduleDAGInstrs.h:168
llvm::SchedDFSImpl::visitPostorderEdge
void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ)
Called once for each tree edge after calling visitPostOrderNode on the predecessor.
Definition: ScheduleDAGInstrs.cpp:1307
llvm::ScheduleDAGInstrs::MFI
const MachineFrameInfo & MFI
Definition: ScheduleDAGInstrs.h:123
llvm::SchedDFSImpl::joinPredSubtree
bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ, bool CheckLimit=true)
Joins the predecessor subtree with the successor that is its DFS parent.
Definition: ScheduleDAGInstrs.cpp:1357
llvm::SparseSet::setUniverse
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition: SparseSet.h:155
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
llvm::SUnit::hasPhysRegUses
bool hasPhysRegUses
Has physreg uses.
Definition: ScheduleDAG.h:279
llvm::SchedDFSImpl::finalize
void finalize()
Sets each node's subtree ID to the representative ID and record connections between trees.
Definition: ScheduleDAGInstrs.cpp:1320
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SchedDFSImpl::visitPostorderNode
void visitPostorderNode(const SUnit *SU)
Called once for each node after all predecessors are visited.
Definition: ScheduleDAGInstrs.cpp:1265
llvm::SchedDFSImpl::visitPreorder
void visitPreorder(const SUnit *SU)
Initializes this node's instruction count.
Definition: ScheduleDAGInstrs.cpp:1257
llvm::ScheduleDAGInstrs::TrackLaneMasks
bool TrackLaneMasks
Whether lane masks should get tracked.
Definition: ScheduleDAGInstrs.h:140
llvm::getUnderlyingObjectsForCodeGen
bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)
This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
Definition: ValueTracking.cpp:4622
iterator_range.h
llvm::MachineOperand::isRegMask
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Definition: MachineOperand.h:344
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineRegisterInfo::hasOneDef
bool hasOneDef(Register RegNo) const
Return true if there is exactly one operand defining the specified register.
Definition: MachineRegisterInfo.h:452
llvm::ScheduleDAGInstrs::DbgValues
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
Definition: ScheduleDAGInstrs.h:249
llvm::TargetSchedModel::computeOperandLatency
unsigned computeOperandLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *UseMI, unsigned UseOperIdx) const
Compute operand latency based on the available machine model.
Definition: TargetSchedule.cpp:168
UseTBAA
static cl::opt< bool > UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"))
llvm::Value::printAsOperand
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:4758
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::MachineInstr::dump
void dump() const
Definition: MachineInstr.cpp:1525
llvm::SparseMultiSet::equal_range
RangePair equal_range(const KeyT &K)
The bounds of the range of items sharing Key K.
Definition: SparseMultiSet.h:411
llvm::ScheduleDAG
Definition: ScheduleDAG.h:554
llvm::SparseMultiSet::contains
bool contains(const KeyT &Key) const
Returns true if this set contains an element identified by Key.
Definition: SparseMultiSet.h:395
llvm::ScheduleDAG::TRI
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:558
llvm::VReg2SUnitOperIdx
Mapping from virtual register to SUnit including an operand index.
Definition: ScheduleDAGInstrs.h:67
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
llvm::SDep::getSUnit
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:396
llvm::ScheduleDAG::MF
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:559
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::SparseMultiSet::erase
iterator erase(iterator I)
Erases an existing element identified by a valid iterator.
Definition: SparseMultiSet.h:466
llvm::MachineOperand::setIsUndef
void setIsUndef(bool Val=true)
Definition: MachineOperand.h:520
Compiler.h
TargetSubtargetInfo.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::MachineInstr::print
void print(raw_ostream &OS, bool IsStandalone=true, bool SkipOpers=false, bool SkipDebugLoc=false, bool AddNewLine=true, const TargetInstrInfo *TII=nullptr) const
Print this MI to OS.
Definition: MachineInstr.cpp:1562
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
llvm::format
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
llvm::RegPressureTracker::getPos
MachineBasicBlock::const_iterator getPos() const
Get the MI position corresponding to this register pressure.
Definition: RegisterPressure.h:413
llvm::ScheduleDAGInstrs::getSchedClass
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
Definition: ScheduleDAGInstrs.h:266
SparseSet.h
llvm::ScheduleDAGInstrs::Value2SUsMap::dump
void dump()
Definition: ScheduleDAGInstrs.cpp:1021
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:62
llvm::ScheduleDAGInstrs::MISUnitMap
DenseMap< MachineInstr *, SUnit * > MISUnitMap
After calling BuildSchedGraph, each machine instruction in the current scheduling region is mapped to...
Definition: ScheduleDAGInstrs.h:159
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::PointerUnion< const Value *, const PseudoSourceValue * >
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::ScheduleDAGInstrs::enterRegion
virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)
Initialize the DAG and common scheduler state for a new scheduling region.
Definition: ScheduleDAGInstrs.cpp:183
llvm::MachineOperand::getSubReg
unsigned getSubReg() const
Definition: MachineOperand.h:364
llvm::ScheduleDAGInstrs::addChainDependency
void addChainDependency(SUnit *SUa, SUnit *SUb, unsigned Latency=0)
Adds a chain edge between SUa and SUb, but only if both AAResults and Target fail to deny the depende...
Definition: ScheduleDAGInstrs.cpp:538
llvm::MapVector< ValueType, SUList >::end
iterator end()
Definition: MapVector.h:72
llvm::ScheduleDAGInstrs::Value2SUsMap::getTrueMemOrderLatency
unsigned getTrueMemOrderLatency() const
Definition: ScheduleDAGInstrs.cpp:653
llvm::ScheduleDAGInstrs::newSUnit
SUnit * newSUnit(MachineInstr *MI)
Creates a new SUnit and return a ptr to it.
Definition: ScheduleDAGInstrs.h:380
llvm::MachineRegisterInfo::isConstantPhysReg
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
Definition: MachineRegisterInfo.cpp:515
llvm::ScheduleDAGInstrs::RemoveKillFlags
bool RemoveKillFlags
True if the DAG builder should remove kill flags (in preparation for rescheduling).
Definition: ScheduleDAGInstrs.h:130
llvm::SDep
Scheduling dependency.
Definition: ScheduleDAG.h:49
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::ScheduleDAGInstrs::AAForDep
AAResults * AAForDep
Definition: ScheduleDAGInstrs.h:178
j
return j(j<< 16)
llvm::AArch64::Alias
StringRef Alias
Definition: AArch64TargetParser.h:141
llvm::ScheduleDAG::SUnits
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:561
EnableAASchedMI
static cl::opt< bool > EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, cl::desc("Enable use of AA during MI DAG construction"))
llvm::ScheduleDAGInstrs::RegionBegin
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
Definition: ScheduleDAGInstrs.h:149
llvm::isIdentifiedObject
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
Definition: AliasAnalysis.cpp:891
llvm::MachineOperand::readsReg
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
Definition: MachineOperand.h:457
llvm::SUnit::NumSuccs
unsigned NumSuccs
Definition: ScheduleDAG.h:267
llvm::MCInstrDesc::hasImplicitUseOfPhysReg
bool hasImplicitUseOfPhysReg(unsigned Reg) const
Return true if this instruction implicitly uses the specified physical register.
Definition: MCInstrDesc.h:601
llvm::ConstMIBundleOperands
ConstMIBundleOperands - Iterate over all operands in a const bundle of machine instructions.
Definition: MachineInstrBundle.h:185
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
MachineFrameInfo.h
llvm::SDep::setLatency
void setLatency(unsigned Lat)
Sets the latency for this edge.
Definition: ScheduleDAG.h:147
Casting.h
Function.h
llvm::SparseSet::count
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise.
Definition: SparseSet.h:240
llvm::SchedDFSResult
Compute the values of each DAG node for various metrics during DFS.
Definition: ScheduleDFS.h:65
llvm::ScheduleDAGInstrs::Value2SUsMap
Definition: ScheduleDAGInstrs.cpp:605
llvm::ScheduleDAGInstrs::deadDefHasNoUse
bool deadDefHasNoUse(const MachineOperand &MO)
Returns true if the def register in MO has no uses.
Definition: ScheduleDAGInstrs.cpp:373
llvm::SUnit::addPred
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
Definition: ScheduleDAG.cpp:107
llvm::SparseSet::erase
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:288
llvm::SUnit::hasPhysRegDefs
bool hasPhysRegDefs
Has physreg defs that are being used.
Definition: ScheduleDAG.h:280
llvm::LiveIntervals
Definition: LiveIntervals.h:53
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::SUnit::addPredBarrier
bool addPredBarrier(SUnit *SU)
Adds a barrier edge to SU by calling addPred(), with latency 0 generally or latency 1 for a store fol...
Definition: ScheduleDAG.h:384
llvm::ScheduleDAGInstrs::Uses
Reg2SUnitsMap Uses
Definition: ScheduleDAGInstrs.h:169
llvm::SDep::getKind
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Definition: ScheduleDAG.h:486
llvm::RegisterOperands::adjustLaneLiveness
void adjustLaneLiveness(const LiveIntervals &LIS, const MachineRegisterInfo &MRI, SlotIndex Pos, MachineInstr *AddFlagsMI=nullptr)
Use liveness information to find out which uses/defs are partially undefined/dead and adjust the Regi...
Definition: RegisterPressure.cpp:601
llvm::ScheduleDAGInstrs::BB
MachineBasicBlock * BB
The block in which to insert instructions.
Definition: ScheduleDAGInstrs.h:146
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:597
llvm::ScheduleDAGInstrs::Value2SUsMap::operator[]
ValueType & operator[](const SUList &Key)
To keep NumNodes up to date, insert() is used instead of this operator w/ push_back().
Definition: ScheduleDAGInstrs.cpp:617
llvm::MachineFrameInfo
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
Definition: MachineFrameInfo.h:106
llvm::SUnit::hasReservedResource
bool hasReservedResource
Uses a reserved resource.
Definition: ScheduleDAG.h:289
llvm::skipDebugInstructionsBackward
IterT skipDebugInstructionsBackward(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It until it points to a non-debug instruction or to Begin and return the resulting iterator...
Definition: MachineBasicBlock.h:1301
SmallVector.h
UseAA
static cl::opt< bool > UseAA("aarch64-use-aa", cl::init(true), cl::desc("Enable the use of AA during codegen."))
llvm::ScheduleDAGInstrs::finishBlock
virtual void finishBlock()
Cleans up after scheduling in the given block.
Definition: ScheduleDAGInstrs.cpp:178
llvm::ScheduleDAGInstrs::addPhysRegDataDeps
void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx)
MO is an operand of SU's instruction that defines a physical register.
Definition: ScheduleDAGInstrs.cpp:229
ScheduleDFS.h
llvm::ScheduleDAGInstrs::CurrentVRegDefs
VReg2SUnitMultiMap CurrentVRegDefs
Tracks the last instruction(s) in this region defining each virtual register.
Definition: ScheduleDAGInstrs.h:174
N
#define N
llvm::ScheduleDAGInstrs::addVRegUseDeps
void addVRegUseDeps(SUnit *SU, unsigned OperIdx)
Adds a register data dependency if the instruction that defines the virtual register used at OperIdx ...
Definition: ScheduleDAGInstrs.cpp:505
LaneBitmask.h
llvm::MachineFunction::getDataLayout
const DataLayout & getDataLayout() const
Return the DataLayout attached to the Module associated to this MF.
Definition: MachineFunction.cpp:285
llvm::IntEqClasses::getNumClasses
unsigned getNumClasses() const
getNumClasses - Return the number of equivalence classes after compress() was called.
Definition: IntEqClasses.h:72
llvm::MachineInstr::isTransient
bool isTransient() const
Return true if this is a transient instruction that is either very likely to be eliminated during reg...
Definition: MachineInstr.h:1363
llvm::SchedDFSImpl::visitCrossEdge
void visitCrossEdge(const SDep &PredDep, const SUnit *Succ)
Adds a connection for cross edges.
Definition: ScheduleDAGInstrs.cpp:1314
MachineMemOperand.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
MachineOperand.h
llvm::SparseSet< RootData >
llvm::SchedDFSImpl::isVisited
bool isVisited(const SUnit *SU) const
Returns true if this node been visited by the DFS traversal.
Definition: ScheduleDAGInstrs.cpp:1250
llvm::SUnit::Preds
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:256
llvm::SUnit
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::IntEqClasses
Definition: IntEqClasses.h:28
llvm::MachineFrameInfo::hasTailCall
bool hasTailCall() const
Returns true if the function contains a tail call.
Definition: MachineFrameInfo.h:638
SlotIndexes.h
llvm::cl::desc
Definition: CommandLine.h:412
llvm::ScheduleDAGInstrs::insertBarrierChain
void insertBarrierChain(Value2SUsMap &map)
Inserts a barrier chain in a huge region, far below current SU.
Definition: ScheduleDAGInstrs.cpp:687
raw_ostream.h
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
MachineFunction.h
llvm::MachineInstr::registerDefIsDead
bool registerDefIsDead(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Returns true if the register is dead in this machine instruction.
Definition: MachineInstr.h:1436
llvm::MachineInstrBundleIterator< MachineInstr >
Value.h
llvm::raw_string_ostream::str
std::string & str()
Returns the string's reference.
Definition: raw_ostream.h:647
llvm::MachineInstr::isBarrier
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
Definition: MachineInstr.h:887
llvm::ScheduleDAGInstrs::reduceHugeMemNodeMaps
void reduceHugeMemNodeMaps(Value2SUsMap &stores, Value2SUsMap &loads, unsigned N)
Reduces maps in FIFO order, by N SUs.
Definition: ScheduleDAGInstrs.cpp:1040
llvm::ScheduleDAG::clearDAG
void clearDAG()
Clears the DAG state (between regions).
Definition: ScheduleDAG.cpp:64
llvm::MCInstrDesc::getNumOperands
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:230
llvm::MachineInstr::operands
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:641
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
TargetRegisterInfo.h
llvm::RegPressureTracker::recede
void recede(SmallVectorImpl< RegisterMaskPair > *LiveUses=nullptr)
Recede across the previous instruction.
Definition: RegisterPressure.cpp:874
Debug.h
llvm::ScheduleDAG::ExitSU
SUnit ExitSU
Special node for the region exit.
Definition: ScheduleDAG.h:563
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:311
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
SubReg
unsigned SubReg
Definition: AArch64AdvSIMDScalarPass.cpp:104
llvm::TargetSchedModel::hasInstrSchedModel
bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model.
Definition: TargetSchedule.cpp:39
llvm::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:788
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
LivePhysRegs.h