xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp (revision ccb59683b98360afaf5b5bb641a68fea22c68d0b)
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 
14 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
15 #include "llvm/ADT/IntEqClasses.h"
16 #include "llvm/ADT/MapVector.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/SparseSet.h"
19 #include "llvm/ADT/iterator_range.h"
20 #include "llvm/Analysis/AliasAnalysis.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/LiveIntervals.h"
23 #include "llvm/CodeGen/LivePhysRegs.h"
24 #include "llvm/CodeGen/MachineBasicBlock.h"
25 #include "llvm/CodeGen/MachineFrameInfo.h"
26 #include "llvm/CodeGen/MachineFunction.h"
27 #include "llvm/CodeGen/MachineInstr.h"
28 #include "llvm/CodeGen/MachineInstrBundle.h"
29 #include "llvm/CodeGen/MachineMemOperand.h"
30 #include "llvm/CodeGen/MachineOperand.h"
31 #include "llvm/CodeGen/MachineRegisterInfo.h"
32 #include "llvm/CodeGen/PseudoSourceValue.h"
33 #include "llvm/CodeGen/RegisterPressure.h"
34 #include "llvm/CodeGen/ScheduleDAG.h"
35 #include "llvm/CodeGen/ScheduleDFS.h"
36 #include "llvm/CodeGen/SlotIndexes.h"
37 #include "llvm/CodeGen/TargetRegisterInfo.h"
38 #include "llvm/CodeGen/TargetSubtargetInfo.h"
39 #include "llvm/Config/llvm-config.h"
40 #include "llvm/IR/Constants.h"
41 #include "llvm/IR/Function.h"
42 #include "llvm/IR/Type.h"
43 #include "llvm/IR/Value.h"
44 #include "llvm/MC/LaneBitmask.h"
45 #include "llvm/MC/MCRegisterInfo.h"
46 #include "llvm/Support/Casting.h"
47 #include "llvm/Support/CommandLine.h"
48 #include "llvm/Support/Compiler.h"
49 #include "llvm/Support/Debug.h"
50 #include "llvm/Support/ErrorHandling.h"
51 #include "llvm/Support/Format.h"
52 #include "llvm/Support/raw_ostream.h"
53 #include <algorithm>
54 #include <cassert>
55 #include <iterator>
56 #include <string>
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 
82 static cl::opt<unsigned> ReductionSize(
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(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 
107 ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
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.
124 static bool getUnderlyingObjectsForInstr(const MachineInstr *MI,
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.push_back(UnderlyingObjectsVector::value_type(PSV, MayAlias));
151       } else if (const Value *V = MMO->getValue()) {
152         SmallVector<Value *, 4> Objs;
153         if (!getUnderlyingObjectsForCodeGen(V, Objs))
154           return false;
155 
156         for (Value *V : Objs) {
157           assert(isIdentifiedObject(V));
158           Objects.push_back(UnderlyingObjectsVector::value_type(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 
174 void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) {
175   BB = bb;
176 }
177 
178 void ScheduleDAGInstrs::finishBlock() {
179   // Subclasses should no longer refer to the old block.
180   BB = nullptr;
181 }
182 
183 void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb,
184                                     MachineBasicBlock::iterator begin,
185                                     MachineBasicBlock::iterator end,
186                                     unsigned regioninstrs) {
187   assert(bb == BB && "startBlock should set BB");
188   RegionBegin = begin;
189   RegionEnd = end;
190   NumRegionInstrs = regioninstrs;
191 }
192 
193 void ScheduleDAGInstrs::exitRegion() {
194   // Nothing to do.
195 }
196 
197 void ScheduleDAGInstrs::addSchedBarrierDeps() {
198   MachineInstr *ExitMI =
199       RegionEnd != BB->end()
200           ? &*skipDebugInstructionsBackward(RegionEnd, RegionBegin)
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();
208       if (Register::isPhysicalRegister(Reg)) {
209         Uses.insert(PhysRegSUOper(&ExitSU, -1, Reg));
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.
234   const TargetSubtargetInfo &ST = MF.getSubtarget();
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) {
268         Dep.setLatency(SchedModel.computeOperandLatency(SU->getInstr(), OperIdx,
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.
287   if (MRI.isConstantPhysReg(Reg))
288     return;
289 
290   const TargetSubtargetInfo &ST = MF.getSubtarget();
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.
343       Reg2SUnitsMap::RangePair P = Defs.equal_range(Reg);
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 
359 LaneBitmask ScheduleDAGInstrs::getLaneMaskForMO(const MachineOperand &MO) const
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();
370   return TRI->getSubRegIndexLaneMask(SubReg);
371 }
372 
373 bool ScheduleDAGInstrs::deadDefHasNoUse(const MachineOperand &MO) {
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.
423     const TargetSubtargetInfo &ST = MF.getSubtarget();
424     for (VReg2SUnitOperIdxMultiMap::iterator I = CurrentVRegUses.find(Reg),
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);
437         Dep.setLatency(SchedModel.computeOperandLatency(MI, OperIdx, Use,
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
449         I = CurrentVRegUses.erase(I);
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;
465   for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg),
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.
513   LaneBitmask LaneMask = TrackLaneMasks ? getLaneMaskForMO(MO)
514                                         : LaneBitmask::getAll();
515   CurrentVRegUses.insert(VReg2SUnitOperIdx(Reg, LaneMask, OperIdx, SU));
516 
517   // Add antidependences to the following defs of the vreg.
518   for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg),
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 
538 void ScheduleDAGInstrs::addChainDependency (SUnit *SUa, SUnit *SUb,
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.
559 void ScheduleDAGInstrs::initSUnits() {
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 
564   for (MachineInstr &MI : make_range(RegionBegin, RegionEnd)) {
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.
585     if (SchedModel.hasInstrSchedModel()) {
586       const MCSchedClassDesc *SC = getSchedClass(SU);
587       for (const MCWriteProcResEntry &PRE :
588            make_range(SchedModel.getWriteProcResBegin(SC),
589                       SchedModel.getWriteProcResEnd(SC))) {
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().
617   ValueType &operator[](const SUList &Key) {
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() {
640     MapVector<ValueType, SUList>::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 
660 void ScheduleDAGInstrs::addChainDependencies(SUnit *SU,
661                                              Value2SUsMap &Val2SUsMap) {
662   for (auto &I : Val2SUsMap)
663     addChainDependencies(SU, I.second,
664                          Val2SUsMap.getTrueMemOrderLatency());
665 }
666 
667 void ScheduleDAGInstrs::addChainDependencies(SUnit *SU,
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 
676 void ScheduleDAGInstrs::addBarrierChain(Value2SUsMap &map) {
677   assert(BarrierChain != nullptr);
678 
679   for (auto &I : map) {
680     SUList &sus = I.second;
681     for (auto *SU : sus)
682       SU->addPredBarrier(BarrierChain);
683   }
684   map.clear();
685 }
686 
687 void ScheduleDAGInstrs::insertBarrierChain(Value2SUsMap &map) {
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 
720 void ScheduleDAGInstrs::buildSchedGraph(AAResults *AA,
721                                         RegPressureTracker *RPTracker,
722                                         PressureDiffs *PDiffs,
723                                         LiveIntervals *LIS,
724                                         bool TrackLaneMasks) {
725   const TargetSubtargetInfo &ST = MF.getSubtarget();
726   bool UseAA = EnableAASchedMI.getNumOccurrences() > 0 ? EnableAASchedMI
727                                                        : ST.useAA();
728   AAForDep = UseAA ? AA : nullptr;
729 
730   BarrierChain = nullptr;
731 
732   this->TrackLaneMasks = TrackLaneMasks;
733   MISUnitMap.clear();
734   ScheduleDAG::clearDAG();
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");
777   Defs.setUniverse(TRI->getNumRegs());
778   Uses.setUniverse(TRI->getNumRegs());
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.
788   addSchedBarrierDeps();
789 
790   // Walk the list of instructions, from bottom moving up.
791   MachineInstr *DbgMI = nullptr;
792   for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin;
793        MII != MIE; --MII) {
794     MachineInstr &MI = *std::prev(MII);
795     if (DbgMI) {
796       DbgValues.push_back(std::make_pair(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();
842       if (Register::isPhysicalRegister(Reg)) {
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();
859       if (Register::isPhysicalRegister(Reg)) {
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)
887         BarrierChain->addPredBarrier(SU);
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)
907         BarrierChain->addPredBarrier(SU);
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)
925       BarrierChain->addPredBarrier(SU);
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.
930     UnderlyingObjectsVector Objs;
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.
966         addChainDependencies(SU, Loads, UnknownValue);
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();
1010   CurrentVRegDefs.clear();
1011   CurrentVRegUses.clear();
1012 
1013   Topo.MarkDirty();
1014 }
1015 
1016 raw_ostream &llvm::operator<<(raw_ostream &OS, const PseudoSourceValue* PSV) {
1017   PSV->printCustom(OS);
1018   return OS;
1019 }
1020 
1021 void ScheduleDAGInstrs::Value2SUsMap::dump() {
1022   for (auto &Itr : *this) {
1023     if (Itr.first.is<const Value*>()) {
1024       const Value *V = Itr.first.get<const Value*>();
1025       if (isa<UndefValue>(V))
1026         dbgs() << "Unknown";
1027       else
1028         V->printAsOperand(dbgs());
1029     }
1030     else if (Itr.first.is<const PseudoSourceValue*>())
1031       dbgs() <<  Itr.first.get<const PseudoSourceValue*>();
1032     else
1033       llvm_unreachable("Unknown Value type.");
1034 
1035     dbgs() << " : ";
1036     dumpSUList(Itr.second);
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 (auto &I : stores)
1049     for (auto *SU : I.second)
1050       NodeNums.push_back(SU->NodeNum);
1051   for (auto &I : loads)
1052     for (auto *SU : I.second)
1053       NodeNums.push_back(SU->NodeNum);
1054   llvm::sort(NodeNums);
1055 
1056   // The N last elements in NodeNums will be removed, and the SU with
1057   // the lowest NodeNum of them will become the new BarrierChain to
1058   // let the not yet seen SUs have a dependency to the removed SUs.
1059   assert(N <= NodeNums.size());
1060   SUnit *newBarrierChain = &SUnits[*(NodeNums.end() - N)];
1061   if (BarrierChain) {
1062     // The aliasing and non-aliasing maps reduce independently of each
1063     // other, but share a common BarrierChain. Check if the
1064     // newBarrierChain is above the former one. If it is not, it may
1065     // introduce a loop to use newBarrierChain, so keep the old one.
1066     if (newBarrierChain->NodeNum < BarrierChain->NodeNum) {
1067       BarrierChain->addPredBarrier(newBarrierChain);
1068       BarrierChain = newBarrierChain;
1069       LLVM_DEBUG(dbgs() << "Inserting new barrier chain: SU("
1070                         << BarrierChain->NodeNum << ").\n";);
1071     }
1072     else
1073       LLVM_DEBUG(dbgs() << "Keeping old barrier chain: SU("
1074                         << BarrierChain->NodeNum << ").\n";);
1075   }
1076   else
1077     BarrierChain = newBarrierChain;
1078 
1079   insertBarrierChain(stores);
1080   insertBarrierChain(loads);
1081 
1082   LLVM_DEBUG(dbgs() << "After reduction:\nStoring SUnits:\n"; stores.dump();
1083              dbgs() << "Loading SUnits:\n"; loads.dump());
1084 }
1085 
1086 static void toggleKills(const MachineRegisterInfo &MRI, LivePhysRegs &LiveRegs,
1087                         MachineInstr &MI, bool addToLiveRegs) {
1088   for (MachineOperand &MO : MI.operands()) {
1089     if (!MO.isReg() || !MO.readsReg())
1090       continue;
1091     Register Reg = MO.getReg();
1092     if (!Reg)
1093       continue;
1094 
1095     // Things that are available after the instruction are killed by it.
1096     bool IsKill = LiveRegs.available(MRI, Reg);
1097     MO.setIsKill(IsKill);
1098     if (addToLiveRegs)
1099       LiveRegs.addReg(Reg);
1100   }
1101 }
1102 
1103 void ScheduleDAGInstrs::fixupKills(MachineBasicBlock &MBB) {
1104   LLVM_DEBUG(dbgs() << "Fixup kills for " << printMBBReference(MBB) << '\n');
1105 
1106   LiveRegs.init(*TRI);
1107   LiveRegs.addLiveOuts(MBB);
1108 
1109   // Examine block from end to start...
1110   for (MachineInstr &MI : llvm::reverse(MBB)) {
1111     if (MI.isDebugOrPseudoInstr())
1112       continue;
1113 
1114     // Update liveness.  Registers that are defed but not used in this
1115     // instruction are now dead. Mark register and all subregs as they
1116     // are completely defined.
1117     for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
1118       const MachineOperand &MO = *O;
1119       if (MO.isReg()) {
1120         if (!MO.isDef())
1121           continue;
1122         Register Reg = MO.getReg();
1123         if (!Reg)
1124           continue;
1125         LiveRegs.removeReg(Reg);
1126       } else if (MO.isRegMask()) {
1127         LiveRegs.removeRegsInMask(MO);
1128       }
1129     }
1130 
1131     // If there is a bundle header fix it up first.
1132     if (!MI.isBundled()) {
1133       toggleKills(MRI, LiveRegs, MI, true);
1134     } else {
1135       MachineBasicBlock::instr_iterator Bundle = MI.getIterator();
1136       if (MI.isBundle())
1137         toggleKills(MRI, LiveRegs, MI, false);
1138 
1139       // Some targets make the (questionable) assumtion that the instructions
1140       // inside the bundle are ordered and consequently only the last use of
1141       // a register inside the bundle can kill it.
1142       MachineBasicBlock::instr_iterator I = std::next(Bundle);
1143       while (I->isBundledWithSucc())
1144         ++I;
1145       do {
1146         if (!I->isDebugOrPseudoInstr())
1147           toggleKills(MRI, LiveRegs, *I, true);
1148         --I;
1149       } while (I != Bundle);
1150     }
1151   }
1152 }
1153 
1154 void ScheduleDAGInstrs::dumpNode(const SUnit &SU) const {
1155 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1156   dumpNodeName(SU);
1157   dbgs() << ": ";
1158   SU.getInstr()->dump();
1159 #endif
1160 }
1161 
1162 void ScheduleDAGInstrs::dump() const {
1163 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1164   if (EntrySU.getInstr() != nullptr)
1165     dumpNodeAll(EntrySU);
1166   for (const SUnit &SU : SUnits)
1167     dumpNodeAll(SU);
1168   if (ExitSU.getInstr() != nullptr)
1169     dumpNodeAll(ExitSU);
1170 #endif
1171 }
1172 
1173 std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
1174   std::string s;
1175   raw_string_ostream oss(s);
1176   if (SU == &EntrySU)
1177     oss << "<entry>";
1178   else if (SU == &ExitSU)
1179     oss << "<exit>";
1180   else
1181     SU->getInstr()->print(oss, /*IsStandalone=*/true);
1182   return oss.str();
1183 }
1184 
1185 /// Return the basic block label. It is not necessarilly unique because a block
1186 /// contains multiple scheduling regions. But it is fine for visualization.
1187 std::string ScheduleDAGInstrs::getDAGName() const {
1188   return "dag." + BB->getFullName();
1189 }
1190 
1191 bool ScheduleDAGInstrs::canAddEdge(SUnit *SuccSU, SUnit *PredSU) {
1192   return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
1193 }
1194 
1195 bool ScheduleDAGInstrs::addEdge(SUnit *SuccSU, const SDep &PredDep) {
1196   if (SuccSU != &ExitSU) {
1197     // Do not use WillCreateCycle, it assumes SD scheduling.
1198     // If Pred is reachable from Succ, then the edge creates a cycle.
1199     if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
1200       return false;
1201     Topo.AddPredQueued(SuccSU, PredDep.getSUnit());
1202   }
1203   SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial());
1204   // Return true regardless of whether a new edge needed to be inserted.
1205   return true;
1206 }
1207 
1208 //===----------------------------------------------------------------------===//
1209 // SchedDFSResult Implementation
1210 //===----------------------------------------------------------------------===//
1211 
1212 namespace llvm {
1213 
1214 /// Internal state used to compute SchedDFSResult.
1215 class SchedDFSImpl {
1216   SchedDFSResult &R;
1217 
1218   /// Join DAG nodes into equivalence classes by their subtree.
1219   IntEqClasses SubtreeClasses;
1220   /// List PredSU, SuccSU pairs that represent data edges between subtrees.
1221   std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs;
1222 
1223   struct RootData {
1224     unsigned NodeID;
1225     unsigned ParentNodeID;  ///< Parent node (member of the parent subtree).
1226     unsigned SubInstrCount = 0; ///< Instr count in this tree only, not
1227                                 /// children.
1228 
1229     RootData(unsigned id): NodeID(id),
1230                            ParentNodeID(SchedDFSResult::InvalidSubtreeID) {}
1231 
1232     unsigned getSparseSetIndex() const { return NodeID; }
1233   };
1234 
1235   SparseSet<RootData> RootSet;
1236 
1237 public:
1238   SchedDFSImpl(SchedDFSResult &r): R(r), SubtreeClasses(R.DFSNodeData.size()) {
1239     RootSet.setUniverse(R.DFSNodeData.size());
1240   }
1241 
1242   /// Returns true if this node been visited by the DFS traversal.
1243   ///
1244   /// During visitPostorderNode the Node's SubtreeID is assigned to the Node
1245   /// ID. Later, SubtreeID is updated but remains valid.
1246   bool isVisited(const SUnit *SU) const {
1247     return R.DFSNodeData[SU->NodeNum].SubtreeID
1248       != SchedDFSResult::InvalidSubtreeID;
1249   }
1250 
1251   /// Initializes this node's instruction count. We don't need to flag the node
1252   /// visited until visitPostorder because the DAG cannot have cycles.
1253   void visitPreorder(const SUnit *SU) {
1254     R.DFSNodeData[SU->NodeNum].InstrCount =
1255       SU->getInstr()->isTransient() ? 0 : 1;
1256   }
1257 
1258   /// Called once for each node after all predecessors are visited. Revisit this
1259   /// node's predecessors and potentially join them now that we know the ILP of
1260   /// the other predecessors.
1261   void visitPostorderNode(const SUnit *SU) {
1262     // Mark this node as the root of a subtree. It may be joined with its
1263     // successors later.
1264     R.DFSNodeData[SU->NodeNum].SubtreeID = SU->NodeNum;
1265     RootData RData(SU->NodeNum);
1266     RData.SubInstrCount = SU->getInstr()->isTransient() ? 0 : 1;
1267 
1268     // If any predecessors are still in their own subtree, they either cannot be
1269     // joined or are large enough to remain separate. If this parent node's
1270     // total instruction count is not greater than a child subtree by at least
1271     // the subtree limit, then try to join it now since splitting subtrees is
1272     // only useful if multiple high-pressure paths are possible.
1273     unsigned InstrCount = R.DFSNodeData[SU->NodeNum].InstrCount;
1274     for (const SDep &PredDep : SU->Preds) {
1275       if (PredDep.getKind() != SDep::Data)
1276         continue;
1277       unsigned PredNum = PredDep.getSUnit()->NodeNum;
1278       if ((InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit)
1279         joinPredSubtree(PredDep, SU, /*CheckLimit=*/false);
1280 
1281       // Either link or merge the TreeData entry from the child to the parent.
1282       if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1283         // If the predecessor's parent is invalid, this is a tree edge and the
1284         // current node is the parent.
1285         if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1286           RootSet[PredNum].ParentNodeID = SU->NodeNum;
1287       }
1288       else if (RootSet.count(PredNum)) {
1289         // The predecessor is not a root, but is still in the root set. This
1290         // must be the new parent that it was just joined to. Note that
1291         // RootSet[PredNum].ParentNodeID may either be invalid or may still be
1292         // set to the original parent.
1293         RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1294         RootSet.erase(PredNum);
1295       }
1296     }
1297     RootSet[SU->NodeNum] = RData;
1298   }
1299 
1300   /// Called once for each tree edge after calling visitPostOrderNode on
1301   /// the predecessor. Increment the parent node's instruction count and
1302   /// preemptively join this subtree to its parent's if it is small enough.
1303   void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ) {
1304     R.DFSNodeData[Succ->NodeNum].InstrCount
1305       += R.DFSNodeData[PredDep.getSUnit()->NodeNum].InstrCount;
1306     joinPredSubtree(PredDep, Succ);
1307   }
1308 
1309   /// Adds a connection for cross edges.
1310   void visitCrossEdge(const SDep &PredDep, const SUnit *Succ) {
1311     ConnectionPairs.push_back(std::make_pair(PredDep.getSUnit(), Succ));
1312   }
1313 
1314   /// Sets each node's subtree ID to the representative ID and record
1315   /// connections between trees.
1316   void finalize() {
1317     SubtreeClasses.compress();
1318     R.DFSTreeData.resize(SubtreeClasses.getNumClasses());
1319     assert(SubtreeClasses.getNumClasses() == RootSet.size()
1320            && "number of roots should match trees");
1321     for (const RootData &Root : RootSet) {
1322       unsigned TreeID = SubtreeClasses[Root.NodeID];
1323       if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1324         R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID];
1325       R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount;
1326       // Note that SubInstrCount may be greater than InstrCount if we joined
1327       // subtrees across a cross edge. InstrCount will be attributed to the
1328       // original parent, while SubInstrCount will be attributed to the joined
1329       // parent.
1330     }
1331     R.SubtreeConnections.resize(SubtreeClasses.getNumClasses());
1332     R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses());
1333     LLVM_DEBUG(dbgs() << R.getNumSubtrees() << " subtrees:\n");
1334     for (unsigned Idx = 0, End = R.DFSNodeData.size(); Idx != End; ++Idx) {
1335       R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx];
1336       LLVM_DEBUG(dbgs() << "  SU(" << Idx << ") in tree "
1337                         << R.DFSNodeData[Idx].SubtreeID << '\n');
1338     }
1339     for (const std::pair<const SUnit*, const SUnit*> &P : ConnectionPairs) {
1340       unsigned PredTree = SubtreeClasses[P.first->NodeNum];
1341       unsigned SuccTree = SubtreeClasses[P.second->NodeNum];
1342       if (PredTree == SuccTree)
1343         continue;
1344       unsigned Depth = P.first->getDepth();
1345       addConnection(PredTree, SuccTree, Depth);
1346       addConnection(SuccTree, PredTree, Depth);
1347     }
1348   }
1349 
1350 protected:
1351   /// Joins the predecessor subtree with the successor that is its DFS parent.
1352   /// Applies some heuristics before joining.
1353   bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ,
1354                        bool CheckLimit = true) {
1355     assert(PredDep.getKind() == SDep::Data && "Subtrees are for data edges");
1356 
1357     // Check if the predecessor is already joined.
1358     const SUnit *PredSU = PredDep.getSUnit();
1359     unsigned PredNum = PredSU->NodeNum;
1360     if (R.DFSNodeData[PredNum].SubtreeID != PredNum)
1361       return false;
1362 
1363     // Four is the magic number of successors before a node is considered a
1364     // pinch point.
1365     unsigned NumDataSucs = 0;
1366     for (const SDep &SuccDep : PredSU->Succs) {
1367       if (SuccDep.getKind() == SDep::Data) {
1368         if (++NumDataSucs >= 4)
1369           return false;
1370       }
1371     }
1372     if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit)
1373       return false;
1374     R.DFSNodeData[PredNum].SubtreeID = Succ->NodeNum;
1375     SubtreeClasses.join(Succ->NodeNum, PredNum);
1376     return true;
1377   }
1378 
1379   /// Called by finalize() to record a connection between trees.
1380   void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth) {
1381     if (!Depth)
1382       return;
1383 
1384     do {
1385       SmallVectorImpl<SchedDFSResult::Connection> &Connections =
1386         R.SubtreeConnections[FromTree];
1387       for (SchedDFSResult::Connection &C : Connections) {
1388         if (C.TreeID == ToTree) {
1389           C.Level = std::max(C.Level, Depth);
1390           return;
1391         }
1392       }
1393       Connections.push_back(SchedDFSResult::Connection(ToTree, Depth));
1394       FromTree = R.DFSTreeData[FromTree].ParentTreeID;
1395     } while (FromTree != SchedDFSResult::InvalidSubtreeID);
1396   }
1397 };
1398 
1399 } // end namespace llvm
1400 
1401 namespace {
1402 
1403 /// Manage the stack used by a reverse depth-first search over the DAG.
1404 class SchedDAGReverseDFS {
1405   std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack;
1406 
1407 public:
1408   bool isComplete() const { return DFSStack.empty(); }
1409 
1410   void follow(const SUnit *SU) {
1411     DFSStack.push_back(std::make_pair(SU, SU->Preds.begin()));
1412   }
1413   void advance() { ++DFSStack.back().second; }
1414 
1415   const SDep *backtrack() {
1416     DFSStack.pop_back();
1417     return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second);
1418   }
1419 
1420   const SUnit *getCurr() const { return DFSStack.back().first; }
1421 
1422   SUnit::const_pred_iterator getPred() const { return DFSStack.back().second; }
1423 
1424   SUnit::const_pred_iterator getPredEnd() const {
1425     return getCurr()->Preds.end();
1426   }
1427 };
1428 
1429 } // end anonymous namespace
1430 
1431 static bool hasDataSucc(const SUnit *SU) {
1432   for (const SDep &SuccDep : SU->Succs) {
1433     if (SuccDep.getKind() == SDep::Data &&
1434         !SuccDep.getSUnit()->isBoundaryNode())
1435       return true;
1436   }
1437   return false;
1438 }
1439 
1440 /// Computes an ILP metric for all nodes in the subDAG reachable via depth-first
1441 /// search from this root.
1442 void SchedDFSResult::compute(ArrayRef<SUnit> SUnits) {
1443   if (!IsBottomUp)
1444     llvm_unreachable("Top-down ILP metric is unimplemented");
1445 
1446   SchedDFSImpl Impl(*this);
1447   for (const SUnit &SU : SUnits) {
1448     if (Impl.isVisited(&SU) || hasDataSucc(&SU))
1449       continue;
1450 
1451     SchedDAGReverseDFS DFS;
1452     Impl.visitPreorder(&SU);
1453     DFS.follow(&SU);
1454     while (true) {
1455       // Traverse the leftmost path as far as possible.
1456       while (DFS.getPred() != DFS.getPredEnd()) {
1457         const SDep &PredDep = *DFS.getPred();
1458         DFS.advance();
1459         // Ignore non-data edges.
1460         if (PredDep.getKind() != SDep::Data
1461             || PredDep.getSUnit()->isBoundaryNode()) {
1462           continue;
1463         }
1464         // An already visited edge is a cross edge, assuming an acyclic DAG.
1465         if (Impl.isVisited(PredDep.getSUnit())) {
1466           Impl.visitCrossEdge(PredDep, DFS.getCurr());
1467           continue;
1468         }
1469         Impl.visitPreorder(PredDep.getSUnit());
1470         DFS.follow(PredDep.getSUnit());
1471       }
1472       // Visit the top of the stack in postorder and backtrack.
1473       const SUnit *Child = DFS.getCurr();
1474       const SDep *PredDep = DFS.backtrack();
1475       Impl.visitPostorderNode(Child);
1476       if (PredDep)
1477         Impl.visitPostorderEdge(*PredDep, DFS.getCurr());
1478       if (DFS.isComplete())
1479         break;
1480     }
1481   }
1482   Impl.finalize();
1483 }
1484 
1485 /// The root of the given SubtreeID was just scheduled. For all subtrees
1486 /// connected to this tree, record the depth of the connection so that the
1487 /// nearest connected subtrees can be prioritized.
1488 void SchedDFSResult::scheduleTree(unsigned SubtreeID) {
1489   for (const Connection &C : SubtreeConnections[SubtreeID]) {
1490     SubtreeConnectLevels[C.TreeID] =
1491       std::max(SubtreeConnectLevels[C.TreeID], C.Level);
1492     LLVM_DEBUG(dbgs() << "  Tree: " << C.TreeID << " @"
1493                       << SubtreeConnectLevels[C.TreeID] << '\n');
1494   }
1495 }
1496 
1497 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1498 LLVM_DUMP_METHOD void ILPValue::print(raw_ostream &OS) const {
1499   OS << InstrCount << " / " << Length << " = ";
1500   if (!Length)
1501     OS << "BADILP";
1502   else
1503     OS << format("%g", ((double)InstrCount / Length));
1504 }
1505 
1506 LLVM_DUMP_METHOD void ILPValue::dump() const {
1507   dbgs() << *this << '\n';
1508 }
1509 
1510 namespace llvm {
1511 
1512 LLVM_DUMP_METHOD
1513 raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val) {
1514   Val.print(OS);
1515   return OS;
1516 }
1517 
1518 } // end namespace llvm
1519 
1520 #endif
1521