contrib/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp

   1 //===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements the ScheduleDAGInstrs class, which implements re-scheduling
  11 // of MachineInstrs.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
  16 #include "llvm/ADT/IntEqClasses.h"
  17 #include "llvm/ADT/SmallPtrSet.h"
  18 #include "llvm/ADT/SmallSet.h"
  19 #include "llvm/Analysis/AliasAnalysis.h"
  20 #include "llvm/Analysis/ValueTracking.h"
  21 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  22 #include "llvm/CodeGen/MachineFunctionPass.h"
  23 #include "llvm/CodeGen/MachineFrameInfo.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineMemOperand.h"
  26 #include "llvm/CodeGen/MachineRegisterInfo.h"
  27 #include "llvm/CodeGen/PseudoSourceValue.h"
  28 #include "llvm/CodeGen/RegisterPressure.h"
  29 #include "llvm/CodeGen/ScheduleDFS.h"
  30 #include "llvm/IR/Function.h"
  31 #include "llvm/IR/Type.h"
  32 #include "llvm/IR/Operator.h"
  33 #include "llvm/Support/CommandLine.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/Format.h"
  36 #include "llvm/Support/raw_ostream.h"
  37 #include "llvm/Target/TargetInstrInfo.h"
  38 #include "llvm/Target/TargetMachine.h"
  39 #include "llvm/Target/TargetRegisterInfo.h"
  40 #include "llvm/Target/TargetSubtargetInfo.h"
  41
  42 using namespace llvm;
  43
  44 #define DEBUG_TYPE "misched"
  45
  46 static cl::opt<bool> EnableAASchedMI("enable-aa-sched-mi", cl::Hidden,
  47     cl::ZeroOrMore, cl::init(false),
  48     cl::desc("Enable use of AA during MI DAG construction"));
  49
  50 static cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden,
  51     cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"));
  52
  53 // Note: the two options below might be used in tuning compile time vs
  54 // output quality. Setting HugeRegion so large that it will never be
  55 // reached means best-effort, but may be slow.
  56
  57 // When Stores and Loads maps (or NonAliasStores and NonAliasLoads)
  58 // together hold this many SUs, a reduction of maps will be done.
  59 static cl::opt<unsigned> HugeRegion("dag-maps-huge-region", cl::Hidden,
  60     cl::init(1000), cl::desc("The limit to use while constructing the DAG "
  61                              "prior to scheduling, at which point a trade-off "
  62                              "is made to avoid excessive compile time."));
  63
  64 static cl::opt<unsigned> ReductionSize(
  65     "dag-maps-reduction-size", cl::Hidden,
  66     cl::desc("A huge scheduling region will have maps reduced by this many "
  67              "nodes at a time. Defaults to HugeRegion / 2."));
  68
  69 static unsigned getReductionSize() {
  70   // Always reduce a huge region with half of the elements, except
  71   // when user sets this number explicitly.
  72   if (ReductionSize.getNumOccurrences() == 0)
  73     return HugeRegion / 2;
  74   return ReductionSize;
  75 }
  76
  77 static void dumpSUList(ScheduleDAGInstrs::SUList &L) {
  78 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  79   dbgs() << "{ ";
  80   for (auto *su : L) {
  81     dbgs() << "SU(" << su->NodeNum << ")";
  82     if (su != L.back())
  83       dbgs() << ", ";
  84   }
  85   dbgs() << "}\n";
  86 #endif
  87 }
  88
  89 ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
  90                                      const MachineLoopInfo *mli,
  91                                      bool RemoveKillFlags)
  92     : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()),
  93       RemoveKillFlags(RemoveKillFlags), CanHandleTerminators(false),
  94       TrackLaneMasks(false), AAForDep(nullptr), BarrierChain(nullptr),
  95       UnknownValue(UndefValue::get(
  96                      Type::getVoidTy(mf.getFunction()->getContext()))),
  97       FirstDbgValue(nullptr) {
  98   DbgValues.clear();
  99
 100   const TargetSubtargetInfo &ST = mf.getSubtarget();
 101   SchedModel.init(ST.getSchedModel(), &ST, TII);
 102 }
 103
 104 /// getUnderlyingObjectFromInt - This is the function that does the work of
 105 /// looking through basic ptrtoint+arithmetic+inttoptr sequences.
 106 static const Value *getUnderlyingObjectFromInt(const Value *V) {
 107   do {
 108     if (const Operator *U = dyn_cast<Operator>(V)) {
 109       // If we find a ptrtoint, we can transfer control back to the
 110       // regular getUnderlyingObjectFromInt.
 111       if (U->getOpcode() == Instruction::PtrToInt)
 112         return U->getOperand(0);
 113       // If we find an add of a constant, a multiplied value, or a phi, it's
 114       // likely that the other operand will lead us to the base
 115       // object. We don't have to worry about the case where the
 116       // object address is somehow being computed by the multiply,
 117       // because our callers only care when the result is an
 118       // identifiable object.
 119       if (U->getOpcode() != Instruction::Add ||
 120           (!isa<ConstantInt>(U->getOperand(1)) &&
 121            Operator::getOpcode(U->getOperand(1)) != Instruction::Mul &&
 122            !isa<PHINode>(U->getOperand(1))))
 123         return V;
 124       V = U->getOperand(0);
 125     } else {
 126       return V;
 127     }
 128     assert(V->getType()->isIntegerTy() && "Unexpected operand type!");
 129   } while (1);
 130 }
 131
 132 /// getUnderlyingObjects - This is a wrapper around GetUnderlyingObjects
 133 /// and adds support for basic ptrtoint+arithmetic+inttoptr sequences.
 134 static void getUnderlyingObjects(const Value *V,
 135                                  SmallVectorImpl<Value *> &Objects,
 136                                  const DataLayout &DL) {
 137   SmallPtrSet<const Value *, 16> Visited;
 138   SmallVector<const Value *, 4> Working(1, V);
 139   do {
 140     V = Working.pop_back_val();
 141
 142     SmallVector<Value *, 4> Objs;
 143     GetUnderlyingObjects(const_cast<Value *>(V), Objs, DL);
 144
 145     for (SmallVectorImpl<Value *>::iterator I = Objs.begin(), IE = Objs.end();
 146          I != IE; ++I) {
 147       V = *I;
 148       if (!Visited.insert(V).second)
 149         continue;
 150       if (Operator::getOpcode(V) == Instruction::IntToPtr) {
 151         const Value *O =
 152           getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0));
 153         if (O->getType()->isPointerTy()) {
 154           Working.push_back(O);
 155           continue;
 156         }
 157       }
 158       Objects.push_back(const_cast<Value *>(V));
 159     }
 160   } while (!Working.empty());
 161 }
 162
 163 /// getUnderlyingObjectsForInstr - If this machine instr has memory reference
 164 /// information and it can be tracked to a normal reference to a known
 165 /// object, return the Value for that object.
 166 static void getUnderlyingObjectsForInstr(const MachineInstr *MI,
 167                                          const MachineFrameInfo *MFI,
 168                                          UnderlyingObjectsVector &Objects,
 169                                          const DataLayout &DL) {
 170   auto allMMOsOkay = [&]() {
 171     for (const MachineMemOperand *MMO : MI->memoperands()) {
 172       if (MMO->isVolatile())
 173         return false;
 174
 175       if (const PseudoSourceValue *PSV = MMO->getPseudoValue()) {
 176         // Function that contain tail calls don't have unique PseudoSourceValue
 177         // objects. Two PseudoSourceValues might refer to the same or
 178         // overlapping locations. The client code calling this function assumes
 179         // this is not the case. So return a conservative answer of no known
 180         // object.
 181         if (MFI->hasTailCall())
 182           return false;
 183
 184         // For now, ignore PseudoSourceValues which may alias LLVM IR values
 185         // because the code that uses this function has no way to cope with
 186         // such aliases.
 187         if (PSV->isAliased(MFI))
 188           return false;
 189
 190         bool MayAlias = PSV->mayAlias(MFI);
 191         Objects.push_back(UnderlyingObjectsVector::value_type(PSV, MayAlias));
 192       } else if (const Value *V = MMO->getValue()) {
 193         SmallVector<Value *, 4> Objs;
 194         getUnderlyingObjects(V, Objs, DL);
 195
 196         for (Value *V : Objs) {
 197           if (!isIdentifiedObject(V))
 198             return false;
 199
 200           Objects.push_back(UnderlyingObjectsVector::value_type(V, true));
 201         }
 202       } else
 203         return false;
 204     }
 205     return true;
 206   };
 207
 208   if (!allMMOsOkay())
 209     Objects.clear();
 210 }
 211
 212 void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) {
 213   BB = bb;
 214 }
 215
 216 void ScheduleDAGInstrs::finishBlock() {
 217   // Subclasses should no longer refer to the old block.
 218   BB = nullptr;
 219 }
 220
 221 /// Initialize the DAG and common scheduler state for the current scheduling
 222 /// region. This does not actually create the DAG, only clears it. The
 223 /// scheduling driver may call BuildSchedGraph multiple times per scheduling
 224 /// region.
 225 void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb,
 226                                     MachineBasicBlock::iterator begin,
 227                                     MachineBasicBlock::iterator end,
 228                                     unsigned regioninstrs) {
 229   assert(bb == BB && "startBlock should set BB");
 230   RegionBegin = begin;
 231   RegionEnd = end;
 232   NumRegionInstrs = regioninstrs;
 233 }
 234
 235 /// Close the current scheduling region. Don't clear any state in case the
 236 /// driver wants to refer to the previous scheduling region.
 237 void ScheduleDAGInstrs::exitRegion() {
 238   // Nothing to do.
 239 }
 240
 241 /// addSchedBarrierDeps - Add dependencies from instructions in the current
 242 /// list of instructions being scheduled to scheduling barrier by adding
 243 /// the exit SU to the register defs and use list. This is because we want to
 244 /// make sure instructions which define registers that are either used by
 245 /// the terminator or are live-out are properly scheduled. This is
 246 /// especially important when the definition latency of the return value(s)
 247 /// are too high to be hidden by the branch or when the liveout registers
 248 /// used by instructions in the fallthrough block.
 249 void ScheduleDAGInstrs::addSchedBarrierDeps() {
 250   MachineInstr *ExitMI = RegionEnd != BB->end() ? &*RegionEnd : nullptr;
 251   ExitSU.setInstr(ExitMI);
 252   bool AllDepKnown = ExitMI &&
 253     (ExitMI->isCall() || ExitMI->isBarrier());
 254   if (ExitMI && AllDepKnown) {
 255     // If it's a call or a barrier, add dependencies on the defs and uses of
 256     // instruction.
 257     for (unsigned i = 0, e = ExitMI->getNumOperands(); i != e; ++i) {
 258       const MachineOperand &MO = ExitMI->getOperand(i);
 259       if (!MO.isReg() || MO.isDef()) continue;
 260       unsigned Reg = MO.getReg();
 261       if (Reg == 0) continue;
 262
 263       if (TRI->isPhysicalRegister(Reg))
 264         Uses.insert(PhysRegSUOper(&ExitSU, -1, Reg));
 265       else if (MO.readsReg()) // ignore undef operands
 266         addVRegUseDeps(&ExitSU, i);
 267     }
 268   } else {
 269     // For others, e.g. fallthrough, conditional branch, assume the exit
 270     // uses all the registers that are livein to the successor blocks.
 271     assert(Uses.empty() && "Uses in set before adding deps?");
 272     for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
 273            SE = BB->succ_end(); SI != SE; ++SI)
 274       for (const auto &LI : (*SI)->liveins()) {
 275         if (!Uses.contains(LI.PhysReg))
 276           Uses.insert(PhysRegSUOper(&ExitSU, -1, LI.PhysReg));
 277       }
 278   }
 279 }
 280
 281 /// MO is an operand of SU's instruction that defines a physical register. Add
 282 /// data dependencies from SU to any uses of the physical register.
 283 void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) {
 284   const MachineOperand &MO = SU->getInstr()->getOperand(OperIdx);
 285   assert(MO.isDef() && "expect physreg def");
 286
 287   // Ask the target if address-backscheduling is desirable, and if so how much.
 288   const TargetSubtargetInfo &ST = MF.getSubtarget();
 289
 290   for (MCRegAliasIterator Alias(MO.getReg(), TRI, true);
 291        Alias.isValid(); ++Alias) {
 292     if (!Uses.contains(*Alias))
 293       continue;
 294     for (Reg2SUnitsMap::iterator I = Uses.find(*Alias); I != Uses.end(); ++I) {
 295       SUnit *UseSU = I->SU;
 296       if (UseSU == SU)
 297         continue;
 298
 299       // Adjust the dependence latency using operand def/use information,
 300       // then allow the target to perform its own adjustments.
 301       int UseOp = I->OpIdx;
 302       MachineInstr *RegUse = nullptr;
 303       SDep Dep;
 304       if (UseOp < 0)
 305         Dep = SDep(SU, SDep::Artificial);
 306       else {
 307         // Set the hasPhysRegDefs only for physreg defs that have a use within
 308         // the scheduling region.
 309         SU->hasPhysRegDefs = true;
 310         Dep = SDep(SU, SDep::Data, *Alias);
 311         RegUse = UseSU->getInstr();
 312       }
 313       Dep.setLatency(
 314         SchedModel.computeOperandLatency(SU->getInstr(), OperIdx, RegUse,
 315                                          UseOp));
 316
 317       ST.adjustSchedDependency(SU, UseSU, Dep);
 318       UseSU->addPred(Dep);
 319     }
 320   }
 321 }
 322
 323 /// addPhysRegDeps - Add register dependencies (data, anti, and output) from
 324 /// this SUnit to following instructions in the same scheduling region that
 325 /// depend the physical register referenced at OperIdx.
 326 void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) {
 327   MachineInstr *MI = SU->getInstr();
 328   MachineOperand &MO = MI->getOperand(OperIdx);
 329
 330   // Optionally add output and anti dependencies. For anti
 331   // dependencies we use a latency of 0 because for a multi-issue
 332   // target we want to allow the defining instruction to issue
 333   // in the same cycle as the using instruction.
 334   // TODO: Using a latency of 1 here for output dependencies assumes
 335   //       there's no cost for reusing registers.
 336   SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
 337   for (MCRegAliasIterator Alias(MO.getReg(), TRI, true);
 338        Alias.isValid(); ++Alias) {
 339     if (!Defs.contains(*Alias))
 340       continue;
 341     for (Reg2SUnitsMap::iterator I = Defs.find(*Alias); I != Defs.end(); ++I) {
 342       SUnit *DefSU = I->SU;
 343       if (DefSU == &ExitSU)
 344         continue;
 345       if (DefSU != SU &&
 346           (Kind != SDep::Output || !MO.isDead() ||
 347            !DefSU->getInstr()->registerDefIsDead(*Alias))) {
 348         if (Kind == SDep::Anti)
 349           DefSU->addPred(SDep(SU, Kind, /*Reg=*/*Alias));
 350         else {
 351           SDep Dep(SU, Kind, /*Reg=*/*Alias);
 352           Dep.setLatency(
 353             SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()));
 354           DefSU->addPred(Dep);
 355         }
 356       }
 357     }
 358   }
 359
 360   if (!MO.isDef()) {
 361     SU->hasPhysRegUses = true;
 362     // Either insert a new Reg2SUnits entry with an empty SUnits list, or
 363     // retrieve the existing SUnits list for this register's uses.
 364     // Push this SUnit on the use list.
 365     Uses.insert(PhysRegSUOper(SU, OperIdx, MO.getReg()));
 366     if (RemoveKillFlags)
 367       MO.setIsKill(false);
 368   }
 369   else {
 370     addPhysRegDataDeps(SU, OperIdx);
 371     unsigned Reg = MO.getReg();
 372
 373     // clear this register's use list
 374     if (Uses.contains(Reg))
 375       Uses.eraseAll(Reg);
 376
 377     if (!MO.isDead()) {
 378       Defs.eraseAll(Reg);
 379     } else if (SU->isCall) {
 380       // Calls will not be reordered because of chain dependencies (see
 381       // below). Since call operands are dead, calls may continue to be added
 382       // to the DefList making dependence checking quadratic in the size of
 383       // the block. Instead, we leave only one call at the back of the
 384       // DefList.
 385       Reg2SUnitsMap::RangePair P = Defs.equal_range(Reg);
 386       Reg2SUnitsMap::iterator B = P.first;
 387       Reg2SUnitsMap::iterator I = P.second;
 388       for (bool isBegin = I == B; !isBegin; /* empty */) {
 389         isBegin = (--I) == B;
 390         if (!I->SU->isCall)
 391           break;
 392         I = Defs.erase(I);
 393       }
 394     }
 395
 396     // Defs are pushed in the order they are visited and never reordered.
 397     Defs.insert(PhysRegSUOper(SU, OperIdx, Reg));
 398   }
 399 }
 400
 401 LaneBitmask ScheduleDAGInstrs::getLaneMaskForMO(const MachineOperand &MO) const
 402 {
 403   unsigned Reg = MO.getReg();
 404   // No point in tracking lanemasks if we don't have interesting subregisters.
 405   const TargetRegisterClass &RC = *MRI.getRegClass(Reg);
 406   if (!RC.HasDisjunctSubRegs)
 407     return ~0u;
 408
 409   unsigned SubReg = MO.getSubReg();
 410   if (SubReg == 0)
 411     return RC.getLaneMask();
 412   return TRI->getSubRegIndexLaneMask(SubReg);
 413 }
 414
 415 /// addVRegDefDeps - Add register output and data dependencies from this SUnit
 416 /// to instructions that occur later in the same scheduling region if they read
 417 /// from or write to the virtual register defined at OperIdx.
 418 ///
 419 /// TODO: Hoist loop induction variable increments. This has to be
 420 /// reevaluated. Generally, IV scheduling should be done before coalescing.
 421 void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) {
 422   MachineInstr *MI = SU->getInstr();
 423   MachineOperand &MO = MI->getOperand(OperIdx);
 424   unsigned Reg = MO.getReg();
 425
 426   LaneBitmask DefLaneMask;
 427   LaneBitmask KillLaneMask;
 428   if (TrackLaneMasks) {
 429     bool IsKill = MO.getSubReg() == 0 || MO.isUndef();
 430     DefLaneMask = getLaneMaskForMO(MO);
 431     // If we have a <read-undef> flag, none of the lane values comes from an
 432     // earlier instruction.
 433     KillLaneMask = IsKill ? ~0u : DefLaneMask;
 434
 435     // Clear undef flag, we'll re-add it later once we know which subregister
 436     // Def is first.
 437     MO.setIsUndef(false);
 438   } else {
 439     DefLaneMask = ~0u;
 440     KillLaneMask = ~0u;
 441   }
 442
 443   if (MO.isDead()) {
 444     assert(CurrentVRegUses.find(Reg) == CurrentVRegUses.end() &&
 445            "Dead defs should have no uses");
 446   } else {
 447     // Add data dependence to all uses we found so far.
 448     const TargetSubtargetInfo &ST = MF.getSubtarget();
 449     for (VReg2SUnitOperIdxMultiMap::iterator I = CurrentVRegUses.find(Reg),
 450          E = CurrentVRegUses.end(); I != E; /*empty*/) {
 451       LaneBitmask LaneMask = I->LaneMask;
 452       // Ignore uses of other lanes.
 453       if ((LaneMask & KillLaneMask) == 0) {
 454         ++I;
 455         continue;
 456       }
 457
 458       if ((LaneMask & DefLaneMask) != 0) {
 459         SUnit *UseSU = I->SU;
 460         MachineInstr *Use = UseSU->getInstr();
 461         SDep Dep(SU, SDep::Data, Reg);
 462         Dep.setLatency(SchedModel.computeOperandLatency(MI, OperIdx, Use,
 463                                                         I->OperandIndex));
 464         ST.adjustSchedDependency(SU, UseSU, Dep);
 465         UseSU->addPred(Dep);
 466       }
 467
 468       LaneMask &= ~KillLaneMask;
 469       // If we found a Def for all lanes of this use, remove it from the list.
 470       if (LaneMask != 0) {
 471         I->LaneMask = LaneMask;
 472         ++I;
 473       } else
 474         I = CurrentVRegUses.erase(I);
 475     }
 476   }
 477
 478   // Shortcut: Singly defined vregs do not have output/anti dependencies.
 479   if (MRI.hasOneDef(Reg))
 480     return;
 481
 482   // Add output dependence to the next nearest defs of this vreg.
 483   //
 484   // Unless this definition is dead, the output dependence should be
 485   // transitively redundant with antidependencies from this definition's
 486   // uses. We're conservative for now until we have a way to guarantee the uses
 487   // are not eliminated sometime during scheduling. The output dependence edge
 488   // is also useful if output latency exceeds def-use latency.
 489   LaneBitmask LaneMask = DefLaneMask;
 490   for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg),
 491                                      CurrentVRegDefs.end())) {
 492     // Ignore defs for other lanes.
 493     if ((V2SU.LaneMask & LaneMask) == 0)
 494       continue;
 495     // Add an output dependence.
 496     SUnit *DefSU = V2SU.SU;
 497     // Ignore additional defs of the same lanes in one instruction. This can
 498     // happen because lanemasks are shared for targets with too many
 499     // subregisters. We also use some representration tricks/hacks where we
 500     // add super-register defs/uses, to imply that although we only access parts
 501     // of the reg we care about the full one.
 502     if (DefSU == SU)
 503       continue;
 504     SDep Dep(SU, SDep::Output, Reg);
 505     Dep.setLatency(
 506       SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()));
 507     DefSU->addPred(Dep);
 508
 509     // Update current definition. This can get tricky if the def was about a
 510     // bigger lanemask before. We then have to shrink it and create a new
 511     // VReg2SUnit for the non-overlapping part.
 512     LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
 513     LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
 514     V2SU.SU = SU;
 515     V2SU.LaneMask = OverlapMask;
 516     if (NonOverlapMask != 0)
 517       CurrentVRegDefs.insert(VReg2SUnit(Reg, NonOverlapMask, DefSU));
 518   }
 519   // If there was no CurrentVRegDefs entry for some lanes yet, create one.
 520   if (LaneMask != 0)
 521     CurrentVRegDefs.insert(VReg2SUnit(Reg, LaneMask, SU));
 522 }
 523
 524 /// addVRegUseDeps - Add a register data dependency if the instruction that
 525 /// defines the virtual register used at OperIdx is mapped to an SUnit. Add a
 526 /// register antidependency from this SUnit to instructions that occur later in
 527 /// the same scheduling region if they write the virtual register.
 528 ///
 529 /// TODO: Handle ExitSU "uses" properly.
 530 void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) {
 531   const MachineInstr *MI = SU->getInstr();
 532   const MachineOperand &MO = MI->getOperand(OperIdx);
 533   unsigned Reg = MO.getReg();
 534
 535   // Remember the use. Data dependencies will be added when we find the def.
 536   LaneBitmask LaneMask = TrackLaneMasks ? getLaneMaskForMO(MO) : ~0u;
 537   CurrentVRegUses.insert(VReg2SUnitOperIdx(Reg, LaneMask, OperIdx, SU));
 538
 539   // Add antidependences to the following defs of the vreg.
 540   for (VReg2SUnit &V2SU : make_range(CurrentVRegDefs.find(Reg),
 541                                      CurrentVRegDefs.end())) {
 542     // Ignore defs for unrelated lanes.
 543     LaneBitmask PrevDefLaneMask = V2SU.LaneMask;
 544     if ((PrevDefLaneMask & LaneMask) == 0)
 545       continue;
 546     if (V2SU.SU == SU)
 547       continue;
 548
 549     V2SU.SU->addPred(SDep(SU, SDep::Anti, Reg));
 550   }
 551 }
 552
 553 /// Return true if MI is an instruction we are unable to reason about
 554 /// (like a call or something with unmodeled side effects).
 555 static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) {
 556   return MI->isCall() || MI->hasUnmodeledSideEffects() ||
 557          (MI->hasOrderedMemoryRef() && !MI->isInvariantLoad(AA));
 558 }
 559
 560 /// This returns true if the two MIs need a chain edge between them.
 561 /// This is called on normal stores and loads.
 562 static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI,
 563                              const DataLayout &DL, MachineInstr *MIa,
 564                              MachineInstr *MIb) {
 565   const MachineFunction *MF = MIa->getParent()->getParent();
 566   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
 567
 568   assert ((MIa->mayStore() || MIb->mayStore()) &&
 569           "Dependency checked between two loads");
 570
 571   // Let the target decide if memory accesses cannot possibly overlap.
 572   if (TII->areMemAccessesTriviallyDisjoint(*MIa, *MIb, AA))
 573     return false;
 574
 575   // To this point analysis is generic. From here on we do need AA.
 576   if (!AA)
 577     return true;
 578
 579   // FIXME: Need to handle multiple memory operands to support all targets.
 580   if (!MIa->hasOneMemOperand() || !MIb->hasOneMemOperand())
 581     return true;
 582
 583   MachineMemOperand *MMOa = *MIa->memoperands_begin();
 584   MachineMemOperand *MMOb = *MIb->memoperands_begin();
 585
 586   if (!MMOa->getValue() || !MMOb->getValue())
 587     return true;
 588
 589   // The following interface to AA is fashioned after DAGCombiner::isAlias
 590   // and operates with MachineMemOperand offset with some important
 591   // assumptions:
 592   //   - LLVM fundamentally assumes flat address spaces.
 593   //   - MachineOperand offset can *only* result from legalization and
 594   //     cannot affect queries other than the trivial case of overlap
 595   //     checking.
 596   //   - These offsets never wrap and never step outside
 597   //     of allocated objects.
 598   //   - There should never be any negative offsets here.
 599   //
 600   // FIXME: Modify API to hide this math from "user"
 601   // FIXME: Even before we go to AA we can reason locally about some
 602   // memory objects. It can save compile time, and possibly catch some
 603   // corner cases not currently covered.
 604
 605   assert ((MMOa->getOffset() >= 0) && "Negative MachineMemOperand offset");
 606   assert ((MMOb->getOffset() >= 0) && "Negative MachineMemOperand offset");
 607
 608   int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset());
 609   int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() - MinOffset;
 610   int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() - MinOffset;
 611
 612   AliasResult AAResult =
 613       AA->alias(MemoryLocation(MMOa->getValue(), Overlapa,
 614                                UseTBAA ? MMOa->getAAInfo() : AAMDNodes()),
 615                 MemoryLocation(MMOb->getValue(), Overlapb,
 616                                UseTBAA ? MMOb->getAAInfo() : AAMDNodes()));
 617
 618   return (AAResult != NoAlias);
 619 }
 620
 621 /// Check whether two objects need a chain edge and add it if needed.
 622 void ScheduleDAGInstrs::addChainDependency (SUnit *SUa, SUnit *SUb,
 623                                             unsigned Latency) {
 624   if (MIsNeedChainEdge(AAForDep, MFI, MF.getDataLayout(), SUa->getInstr(),
 625                        SUb->getInstr())) {
 626     SDep Dep(SUa, SDep::MayAliasMem);
 627     Dep.setLatency(Latency);
 628     SUb->addPred(Dep);
 629   }
 630 }
 631
 632 /// Create an SUnit for each real instruction, numbered in top-down topological
 633 /// order. The instruction order A < B, implies that no edge exists from B to A.
 634 ///
 635 /// Map each real instruction to its SUnit.
 636 ///
 637 /// After initSUnits, the SUnits vector cannot be resized and the scheduler may
 638 /// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs
 639 /// instead of pointers.
 640 ///
 641 /// MachineScheduler relies on initSUnits numbering the nodes by their order in
 642 /// the original instruction list.
 643 void ScheduleDAGInstrs::initSUnits() {
 644   // We'll be allocating one SUnit for each real instruction in the region,
 645   // which is contained within a basic block.
 646   SUnits.reserve(NumRegionInstrs);
 647
 648   for (MachineInstr &MI : llvm::make_range(RegionBegin, RegionEnd)) {
 649     if (MI.isDebugValue())
 650       continue;
 651
 652     SUnit *SU = newSUnit(&MI);
 653     MISUnitMap[&MI] = SU;
 654
 655     SU->isCall = MI.isCall();
 656     SU->isCommutable = MI.isCommutable();
 657
 658     // Assign the Latency field of SU using target-provided information.
 659     SU->Latency = SchedModel.computeInstrLatency(SU->getInstr());
 660
 661     // If this SUnit uses a reserved or unbuffered resource, mark it as such.
 662     //
 663     // Reserved resources block an instruction from issuing and stall the
 664     // entire pipeline. These are identified by BufferSize=0.
 665     //
 666     // Unbuffered resources prevent execution of subsequent instructions that
 667     // require the same resources. This is used for in-order execution pipelines
 668     // within an out-of-order core. These are identified by BufferSize=1.
 669     if (SchedModel.hasInstrSchedModel()) {
 670       const MCSchedClassDesc *SC = getSchedClass(SU);
 671       for (TargetSchedModel::ProcResIter
 672              PI = SchedModel.getWriteProcResBegin(SC),
 673              PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) {
 674         switch (SchedModel.getProcResource(PI->ProcResourceIdx)->BufferSize) {
 675         case 0:
 676           SU->hasReservedResource = true;
 677           break;
 678         case 1:
 679           SU->isUnbuffered = true;
 680           break;
 681         default:
 682           break;
 683         }
 684       }
 685     }
 686   }
 687 }
 688
 689 void ScheduleDAGInstrs::collectVRegUses(SUnit *SU) {
 690   const MachineInstr *MI = SU->getInstr();
 691   for (const MachineOperand &MO : MI->operands()) {
 692     if (!MO.isReg())
 693       continue;
 694     if (!MO.readsReg())
 695       continue;
 696     if (TrackLaneMasks && !MO.isUse())
 697       continue;
 698
 699     unsigned Reg = MO.getReg();
 700     if (!TargetRegisterInfo::isVirtualRegister(Reg))
 701       continue;
 702
 703     // Ignore re-defs.
 704     if (TrackLaneMasks) {
 705       bool FoundDef = false;
 706       for (const MachineOperand &MO2 : MI->operands()) {
 707         if (MO2.isReg() && MO2.isDef() && MO2.getReg() == Reg && !MO2.isDead()) {
 708           FoundDef = true;
 709           break;
 710         }
 711       }
 712       if (FoundDef)
 713         continue;
 714     }
 715
 716     // Record this local VReg use.
 717     VReg2SUnitMultiMap::iterator UI = VRegUses.find(Reg);
 718     for (; UI != VRegUses.end(); ++UI) {
 719       if (UI->SU == SU)
 720         break;
 721     }
 722     if (UI == VRegUses.end())
 723       VRegUses.insert(VReg2SUnit(Reg, 0, SU));
 724   }
 725 }
 726
 727 class ScheduleDAGInstrs::Value2SUsMap : public MapVector<ValueType, SUList> {
 728
 729   /// Current total number of SUs in map.
 730   unsigned NumNodes;
 731
 732   /// 1 for loads, 0 for stores. (see comment in SUList)
 733   unsigned TrueMemOrderLatency;
 734 public:
 735
 736   Value2SUsMap(unsigned lat = 0) : NumNodes(0), TrueMemOrderLatency(lat) {}
 737
 738   /// To keep NumNodes up to date, insert() is used instead of
 739   /// this operator w/ push_back().
 740   ValueType &operator[](const SUList &Key) {
 741     llvm_unreachable("Don't use. Use insert() instead."); };
 742
 743   /// Add SU to the SUList of V. If Map grows huge, reduce its size
 744   /// by calling reduce().
 745   void inline insert(SUnit *SU, ValueType V) {
 746     MapVector::operator[](V).push_back(SU);
 747     NumNodes++;
 748   }
 749
 750   /// Clears the list of SUs mapped to V.
 751   void inline clearList(ValueType V) {
 752     iterator Itr = find(V);
 753     if (Itr != end()) {
 754       assert (NumNodes >= Itr->second.size());
 755       NumNodes -= Itr->second.size();
 756
 757       Itr->second.clear();
 758     }
 759   }
 760
 761   /// Clears map from all contents.
 762   void clear() {
 763     MapVector<ValueType, SUList>::clear();
 764     NumNodes = 0;
 765   }
 766
 767   unsigned inline size() const { return NumNodes; }
 768
 769   /// Count the number of SUs in this map after a reduction.
 770   void reComputeSize(void) {
 771     NumNodes = 0;
 772     for (auto &I : *this)
 773       NumNodes += I.second.size();
 774   }
 775
 776   unsigned inline getTrueMemOrderLatency() const {
 777     return TrueMemOrderLatency;
 778   }
 779
 780   void dump();
 781 };
 782
 783 void ScheduleDAGInstrs::addChainDependencies(SUnit *SU,
 784                                              Value2SUsMap &Val2SUsMap) {
 785   for (auto &I : Val2SUsMap)
 786     addChainDependencies(SU, I.second,
 787                          Val2SUsMap.getTrueMemOrderLatency());
 788 }
 789
 790 void ScheduleDAGInstrs::addChainDependencies(SUnit *SU,
 791                                              Value2SUsMap &Val2SUsMap,
 792                                              ValueType V) {
 793   Value2SUsMap::iterator Itr = Val2SUsMap.find(V);
 794   if (Itr != Val2SUsMap.end())
 795     addChainDependencies(SU, Itr->second,
 796                          Val2SUsMap.getTrueMemOrderLatency());
 797 }
 798
 799 void ScheduleDAGInstrs::addBarrierChain(Value2SUsMap &map) {
 800   assert (BarrierChain != nullptr);
 801
 802   for (auto &I : map) {
 803     SUList &sus = I.second;
 804     for (auto *SU : sus)
 805       SU->addPredBarrier(BarrierChain);
 806   }
 807   map.clear();
 808 }
 809
 810 void ScheduleDAGInstrs::insertBarrierChain(Value2SUsMap &map) {
 811   assert (BarrierChain != nullptr);
 812
 813   // Go through all lists of SUs.
 814   for (Value2SUsMap::iterator I = map.begin(), EE = map.end(); I != EE;) {
 815     Value2SUsMap::iterator CurrItr = I++;
 816     SUList &sus = CurrItr->second;
 817     SUList::iterator SUItr = sus.begin(), SUEE = sus.end();
 818     for (; SUItr != SUEE; ++SUItr) {
 819       // Stop on BarrierChain or any instruction above it.
 820       if ((*SUItr)->NodeNum <= BarrierChain->NodeNum)
 821         break;
 822
 823       (*SUItr)->addPredBarrier(BarrierChain);
 824     }
 825
 826     // Remove also the BarrierChain from list if present.
 827     if (SUItr != SUEE && *SUItr == BarrierChain)
 828       SUItr++;
 829
 830     // Remove all SUs that are now successors of BarrierChain.
 831     if (SUItr != sus.begin())
 832       sus.erase(sus.begin(), SUItr);
 833   }
 834
 835   // Remove all entries with empty su lists.
 836   map.remove_if([&](std::pair<ValueType, SUList> &mapEntry) {
 837       return (mapEntry.second.empty()); });
 838
 839   // Recompute the size of the map (NumNodes).
 840   map.reComputeSize();
 841 }
 842
 843 /// If RegPressure is non-null, compute register pressure as a side effect. The
 844 /// DAG builder is an efficient place to do it because it already visits
 845 /// operands.
 846 void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA,
 847                                         RegPressureTracker *RPTracker,
 848                                         PressureDiffs *PDiffs,
 849                                         LiveIntervals *LIS,
 850                                         bool TrackLaneMasks) {
 851   const TargetSubtargetInfo &ST = MF.getSubtarget();
 852   bool UseAA = EnableAASchedMI.getNumOccurrences() > 0 ? EnableAASchedMI
 853                                                        : ST.useAA();
 854   AAForDep = UseAA ? AA : nullptr;
 855
 856   BarrierChain = nullptr;
 857
 858   this->TrackLaneMasks = TrackLaneMasks;
 859   MISUnitMap.clear();
 860   ScheduleDAG::clearDAG();
 861
 862   // Create an SUnit for each real instruction.
 863   initSUnits();
 864
 865   if (PDiffs)
 866     PDiffs->init(SUnits.size());
 867
 868   // We build scheduling units by walking a block's instruction list
 869   // from bottom to top.
 870
 871   // Each MIs' memory operand(s) is analyzed to a list of underlying
 872   // objects. The SU is then inserted in the SUList(s) mapped from the
 873   // Value(s). Each Value thus gets mapped to lists of SUs depending
 874   // on it, stores and loads kept separately. Two SUs are trivially
 875   // non-aliasing if they both depend on only identified Values and do
 876   // not share any common Value.
 877   Value2SUsMap Stores, Loads(1 /*TrueMemOrderLatency*/);
 878
 879   // Certain memory accesses are known to not alias any SU in Stores
 880   // or Loads, and have therefore their own 'NonAlias'
 881   // domain. E.g. spill / reload instructions never alias LLVM I/R
 882   // Values. It would be nice to assume that this type of memory
 883   // accesses always have a proper memory operand modelling, and are
 884   // therefore never unanalyzable, but this is conservatively not
 885   // done.
 886   Value2SUsMap NonAliasStores, NonAliasLoads(1 /*TrueMemOrderLatency*/);
 887
 888   // Remove any stale debug info; sometimes BuildSchedGraph is called again
 889   // without emitting the info from the previous call.
 890   DbgValues.clear();
 891   FirstDbgValue = nullptr;
 892
 893   assert(Defs.empty() && Uses.empty() &&
 894          "Only BuildGraph should update Defs/Uses");
 895   Defs.setUniverse(TRI->getNumRegs());
 896   Uses.setUniverse(TRI->getNumRegs());
 897
 898   assert(CurrentVRegDefs.empty() && "nobody else should use CurrentVRegDefs");
 899   assert(CurrentVRegUses.empty() && "nobody else should use CurrentVRegUses");
 900   unsigned NumVirtRegs = MRI.getNumVirtRegs();
 901   CurrentVRegDefs.setUniverse(NumVirtRegs);
 902   CurrentVRegUses.setUniverse(NumVirtRegs);
 903
 904   VRegUses.clear();
 905   VRegUses.setUniverse(NumVirtRegs);
 906
 907   // Model data dependencies between instructions being scheduled and the
 908   // ExitSU.
 909   addSchedBarrierDeps();
 910
 911   // Walk the list of instructions, from bottom moving up.
 912   MachineInstr *DbgMI = nullptr;
 913   for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin;
 914        MII != MIE; --MII) {
 915     MachineInstr &MI = *std::prev(MII);
 916     if (DbgMI) {
 917       DbgValues.push_back(std::make_pair(DbgMI, &MI));
 918       DbgMI = nullptr;
 919     }
 920
 921     if (MI.isDebugValue()) {
 922       DbgMI = &MI;
 923       continue;
 924     }
 925     SUnit *SU = MISUnitMap[&MI];
 926     assert(SU && "No SUnit mapped to this MI");
 927
 928     if (RPTracker) {
 929       collectVRegUses(SU);
 930
 931       RegisterOperands RegOpers;
 932       RegOpers.collect(MI, *TRI, MRI, TrackLaneMasks, false);
 933       if (TrackLaneMasks) {
 934         SlotIndex SlotIdx = LIS->getInstructionIndex(MI);
 935         RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx);
 936       }
 937       if (PDiffs != nullptr)
 938         PDiffs->addInstruction(SU->NodeNum, RegOpers, MRI);
 939
 940       RPTracker->recedeSkipDebugValues();
 941       assert(&*RPTracker->getPos() == &MI && "RPTracker in sync");
 942       RPTracker->recede(RegOpers);
 943     }
 944
 945     assert(
 946         (CanHandleTerminators || (!MI.isTerminator() && !MI.isPosition())) &&
 947         "Cannot schedule terminators or labels!");
 948
 949     // Add register-based dependencies (data, anti, and output).
 950     // For some instructions (calls, returns, inline-asm, etc.) there can
 951     // be explicit uses and implicit defs, in which case the use will appear
 952     // on the operand list before the def. Do two passes over the operand
 953     // list to make sure that defs are processed before any uses.
 954     bool HasVRegDef = false;
 955     for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) {
 956       const MachineOperand &MO = MI.getOperand(j);
 957       if (!MO.isReg() || !MO.isDef())
 958         continue;
 959       unsigned Reg = MO.getReg();
 960       if (Reg == 0)
 961         continue;
 962
 963       if (TRI->isPhysicalRegister(Reg))
 964         addPhysRegDeps(SU, j);
 965       else {
 966         HasVRegDef = true;
 967         addVRegDefDeps(SU, j);
 968       }
 969     }
 970     // Now process all uses.
 971     for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) {
 972       const MachineOperand &MO = MI.getOperand(j);
 973       // Only look at use operands.
 974       // We do not need to check for MO.readsReg() here because subsequent
 975       // subregister defs will get output dependence edges and need no
 976       // additional use dependencies.
 977       if (!MO.isReg() || !MO.isUse())
 978         continue;
 979       unsigned Reg = MO.getReg();
 980       if (Reg == 0)
 981         continue;
 982
 983       if (TRI->isPhysicalRegister(Reg))
 984         addPhysRegDeps(SU, j);
 985       else if (MO.readsReg()) // ignore undef operands
 986         addVRegUseDeps(SU, j);
 987     }
 988
 989     // If we haven't seen any uses in this scheduling region, create a
 990     // dependence edge to ExitSU to model the live-out latency. This is required
 991     // for vreg defs with no in-region use, and prefetches with no vreg def.
 992     //
 993     // FIXME: NumDataSuccs would be more precise than NumSuccs here. This
 994     // check currently relies on being called before adding chain deps.
 995     if (SU->NumSuccs == 0 && SU->Latency > 1 && (HasVRegDef || MI.mayLoad())) {
 996       SDep Dep(SU, SDep::Artificial);
 997       Dep.setLatency(SU->Latency - 1);
 998       ExitSU.addPred(Dep);
 999     }
1000
1001     // Add memory dependencies (Note: isStoreToStackSlot and
1002     // isLoadFromStackSLot are not usable after stack slots are lowered to
1003     // actual addresses).
1004
1005     // This is a barrier event that acts as a pivotal node in the DAG.
1006     if (isGlobalMemoryObject(AA, &MI)) {
1007
1008       // Become the barrier chain.
1009       if (BarrierChain)
1010         BarrierChain->addPredBarrier(SU);
1011       BarrierChain = SU;
1012
1013       DEBUG(dbgs() << "Global memory object and new barrier chain: SU("
1014             << BarrierChain->NodeNum << ").\n";);
1015
1016       // Add dependencies against everything below it and clear maps.
1017       addBarrierChain(Stores);
1018       addBarrierChain(Loads);
1019       addBarrierChain(NonAliasStores);
1020       addBarrierChain(NonAliasLoads);
1021
1022       continue;
1023     }
1024
1025     // If it's not a store or a variant load, we're done.
1026     if (!MI.mayStore() && !(MI.mayLoad() && !MI.isInvariantLoad(AA)))
1027       continue;
1028
1029     // Always add dependecy edge to BarrierChain if present.
1030     if (BarrierChain)
1031       BarrierChain->addPredBarrier(SU);
1032
1033     // Find the underlying objects for MI. The Objs vector is either
1034     // empty, or filled with the Values of memory locations which this
1035     // SU depends on. An empty vector means the memory location is
1036     // unknown, and may alias anything.
1037     UnderlyingObjectsVector Objs;
1038     getUnderlyingObjectsForInstr(&MI, MFI, Objs, MF.getDataLayout());
1039
1040     if (MI.mayStore()) {
1041       if (Objs.empty()) {
1042         // An unknown store depends on all stores and loads.
1043         addChainDependencies(SU, Stores);
1044         addChainDependencies(SU, NonAliasStores);
1045         addChainDependencies(SU, Loads);
1046         addChainDependencies(SU, NonAliasLoads);
1047
1048         // Map this store to 'UnknownValue'.
1049         Stores.insert(SU, UnknownValue);
1050       } else {
1051         // Add precise dependencies against all previously seen memory
1052         // accesses mapped to the same Value(s).
1053         for (const UnderlyingObject &UnderlObj : Objs) {
1054           ValueType V = UnderlObj.getValue();
1055           bool ThisMayAlias = UnderlObj.mayAlias();
1056
1057           // Add dependencies to previous stores and loads mapped to V.
1058           addChainDependencies(SU, (ThisMayAlias ? Stores : NonAliasStores), V);
1059           addChainDependencies(SU, (ThisMayAlias ? Loads : NonAliasLoads), V);
1060         }
1061         // Update the store map after all chains have been added to avoid adding
1062         // self-loop edge if multiple underlying objects are present.
1063         for (const UnderlyingObject &UnderlObj : Objs) {
1064           ValueType V = UnderlObj.getValue();
1065           bool ThisMayAlias = UnderlObj.mayAlias();
1066
1067           // Map this store to V.
1068           (ThisMayAlias ? Stores : NonAliasStores).insert(SU, V);
1069         }
1070         // The store may have dependencies to unanalyzable loads and
1071         // stores.
1072         addChainDependencies(SU, Loads, UnknownValue);
1073         addChainDependencies(SU, Stores, UnknownValue);
1074       }
1075     } else { // SU is a load.
1076       if (Objs.empty()) {
1077         // An unknown load depends on all stores.
1078         addChainDependencies(SU, Stores);
1079         addChainDependencies(SU, NonAliasStores);
1080
1081         Loads.insert(SU, UnknownValue);
1082       } else {
1083         for (const UnderlyingObject &UnderlObj : Objs) {
1084           ValueType V = UnderlObj.getValue();
1085           bool ThisMayAlias = UnderlObj.mayAlias();
1086
1087           // Add precise dependencies against all previously seen stores
1088           // mapping to the same Value(s).
1089           addChainDependencies(SU, (ThisMayAlias ? Stores : NonAliasStores), V);
1090
1091           // Map this load to V.
1092           (ThisMayAlias ? Loads : NonAliasLoads).insert(SU, V);
1093         }
1094         // The load may have dependencies to unanalyzable stores.
1095         addChainDependencies(SU, Stores, UnknownValue);
1096       }
1097     }
1098
1099     // Reduce maps if they grow huge.
1100     if (Stores.size() + Loads.size() >= HugeRegion) {
1101       DEBUG(dbgs() << "Reducing Stores and Loads maps.\n";);
1102       reduceHugeMemNodeMaps(Stores, Loads, getReductionSize());
1103     }
1104     if (NonAliasStores.size() + NonAliasLoads.size() >= HugeRegion) {
1105       DEBUG(dbgs() << "Reducing NonAliasStores and NonAliasLoads maps.\n";);
1106       reduceHugeMemNodeMaps(NonAliasStores, NonAliasLoads, getReductionSize());
1107     }
1108   }
1109
1110   if (DbgMI)
1111     FirstDbgValue = DbgMI;
1112
1113   Defs.clear();
1114   Uses.clear();
1115   CurrentVRegDefs.clear();
1116   CurrentVRegUses.clear();
1117 }
1118
1119 raw_ostream &llvm::operator<<(raw_ostream &OS, const PseudoSourceValue* PSV) {
1120   PSV->printCustom(OS);
1121   return OS;
1122 }
1123
1124 void ScheduleDAGInstrs::Value2SUsMap::dump() {
1125   for (auto &Itr : *this) {
1126     if (Itr.first.is<const Value*>()) {
1127       const Value *V = Itr.first.get<const Value*>();
1128       if (isa<UndefValue>(V))
1129         dbgs() << "Unknown";
1130       else
1131         V->printAsOperand(dbgs());
1132     }
1133     else if (Itr.first.is<const PseudoSourceValue*>())
1134       dbgs() <<  Itr.first.get<const PseudoSourceValue*>();
1135     else
1136       llvm_unreachable("Unknown Value type.");
1137
1138     dbgs() << " : ";
1139     dumpSUList(Itr.second);
1140   }
1141 }
1142
1143 /// Reduce maps in FIFO order, by N SUs. This is better than turning
1144 /// every Nth memory SU into BarrierChain in buildSchedGraph(), since
1145 /// it avoids unnecessary edges between seen SUs above the new
1146 /// BarrierChain, and those below it.
1147 void ScheduleDAGInstrs::reduceHugeMemNodeMaps(Value2SUsMap &stores,
1148                                               Value2SUsMap &loads, unsigned N) {
1149   DEBUG(dbgs() << "Before reduction:\nStoring SUnits:\n";
1150         stores.dump();
1151         dbgs() << "Loading SUnits:\n";
1152         loads.dump());
1153
1154   // Insert all SU's NodeNums into a vector and sort it.
1155   std::vector<unsigned> NodeNums;
1156   NodeNums.reserve(stores.size() + loads.size());
1157   for (auto &I : stores)
1158     for (auto *SU : I.second)
1159       NodeNums.push_back(SU->NodeNum);
1160   for (auto &I : loads)
1161     for (auto *SU : I.second)
1162       NodeNums.push_back(SU->NodeNum);
1163   std::sort(NodeNums.begin(), NodeNums.end());
1164
1165   // The N last elements in NodeNums will be removed, and the SU with
1166   // the lowest NodeNum of them will become the new BarrierChain to
1167   // let the not yet seen SUs have a dependency to the removed SUs.
1168   assert (N <= NodeNums.size());
1169   SUnit *newBarrierChain = &SUnits[*(NodeNums.end() - N)];
1170   if (BarrierChain) {
1171     // The aliasing and non-aliasing maps reduce independently of each
1172     // other, but share a common BarrierChain. Check if the
1173     // newBarrierChain is above the former one. If it is not, it may
1174     // introduce a loop to use newBarrierChain, so keep the old one.
1175     if (newBarrierChain->NodeNum < BarrierChain->NodeNum) {
1176       BarrierChain->addPredBarrier(newBarrierChain);
1177       BarrierChain = newBarrierChain;
1178       DEBUG(dbgs() << "Inserting new barrier chain: SU("
1179             << BarrierChain->NodeNum << ").\n";);
1180     }
1181     else
1182       DEBUG(dbgs() << "Keeping old barrier chain: SU("
1183             << BarrierChain->NodeNum << ").\n";);
1184   }
1185   else
1186     BarrierChain = newBarrierChain;
1187
1188   insertBarrierChain(stores);
1189   insertBarrierChain(loads);
1190
1191   DEBUG(dbgs() << "After reduction:\nStoring SUnits:\n";
1192         stores.dump();
1193         dbgs() << "Loading SUnits:\n";
1194         loads.dump());
1195 }
1196
1197 /// \brief Initialize register live-range state for updating kills.
1198 void ScheduleDAGInstrs::startBlockForKills(MachineBasicBlock *BB) {
1199   // Start with no live registers.
1200   LiveRegs.reset();
1201
1202   // Examine the live-in regs of all successors.
1203   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
1204        SE = BB->succ_end(); SI != SE; ++SI) {
1205     for (const auto &LI : (*SI)->liveins()) {
1206       // Repeat, for reg and all subregs.
1207       for (MCSubRegIterator SubRegs(LI.PhysReg, TRI, /*IncludeSelf=*/true);
1208            SubRegs.isValid(); ++SubRegs)
1209         LiveRegs.set(*SubRegs);
1210     }
1211   }
1212 }
1213
1214 /// \brief If we change a kill flag on the bundle instruction implicit register
1215 /// operands, then we also need to propagate that to any instructions inside
1216 /// the bundle which had the same kill state.
1217 static void toggleBundleKillFlag(MachineInstr *MI, unsigned Reg,
1218                                  bool NewKillState,
1219                                  const TargetRegisterInfo *TRI) {
1220   if (MI->getOpcode() != TargetOpcode::BUNDLE)
1221     return;
1222
1223   // Walk backwards from the last instruction in the bundle to the first.
1224   // Once we set a kill flag on an instruction, we bail out, as otherwise we
1225   // might set it on too many operands.  We will clear as many flags as we
1226   // can though.
1227   MachineBasicBlock::instr_iterator Begin = MI->getIterator();
1228   MachineBasicBlock::instr_iterator End = getBundleEnd(*MI);
1229   while (Begin != End) {
1230     if (NewKillState) {
1231       if ((--End)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
1232          return;
1233     } else
1234         (--End)->clearRegisterKills(Reg, TRI);
1235   }
1236 }
1237
1238 bool ScheduleDAGInstrs::toggleKillFlag(MachineInstr *MI, MachineOperand &MO) {
1239   // Setting kill flag...
1240   if (!MO.isKill()) {
1241     MO.setIsKill(true);
1242     toggleBundleKillFlag(MI, MO.getReg(), true, TRI);
1243     return false;
1244   }
1245
1246   // If MO itself is live, clear the kill flag...
1247   if (LiveRegs.test(MO.getReg())) {
1248     MO.setIsKill(false);
1249     toggleBundleKillFlag(MI, MO.getReg(), false, TRI);
1250     return false;
1251   }
1252
1253   // If any subreg of MO is live, then create an imp-def for that
1254   // subreg and keep MO marked as killed.
1255   MO.setIsKill(false);
1256   toggleBundleKillFlag(MI, MO.getReg(), false, TRI);
1257   bool AllDead = true;
1258   const unsigned SuperReg = MO.getReg();
1259   MachineInstrBuilder MIB(MF, MI);
1260   for (MCSubRegIterator SubRegs(SuperReg, TRI); SubRegs.isValid(); ++SubRegs) {
1261     if (LiveRegs.test(*SubRegs)) {
1262       MIB.addReg(*SubRegs, RegState::ImplicitDefine);
1263       AllDead = false;
1264     }
1265   }
1266
1267   if(AllDead) {
1268     MO.setIsKill(true);
1269     toggleBundleKillFlag(MI, MO.getReg(), true, TRI);
1270   }
1271   return false;
1272 }
1273
1274 // FIXME: Reuse the LivePhysRegs utility for this.
1275 void ScheduleDAGInstrs::fixupKills(MachineBasicBlock *MBB) {
1276   DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n');
1277
1278   LiveRegs.resize(TRI->getNumRegs());
1279   BitVector killedRegs(TRI->getNumRegs());
1280
1281   startBlockForKills(MBB);
1282
1283   // Examine block from end to start...
1284   unsigned Count = MBB->size();
1285   for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin();
1286        I != E; --Count) {
1287     MachineInstr &MI = *--I;
1288     if (MI.isDebugValue())
1289       continue;
1290
1291     // Update liveness.  Registers that are defed but not used in this
1292     // instruction are now dead. Mark register and all subregs as they
1293     // are completely defined.
1294     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1295       MachineOperand &MO = MI.getOperand(i);
1296       if (MO.isRegMask())
1297         LiveRegs.clearBitsNotInMask(MO.getRegMask());
1298       if (!MO.isReg()) continue;
1299       unsigned Reg = MO.getReg();
1300       if (Reg == 0) continue;
1301       if (!MO.isDef()) continue;
1302       // Ignore two-addr defs.
1303       if (MI.isRegTiedToUseOperand(i)) continue;
1304
1305       // Repeat for reg and all subregs.
1306       for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
1307            SubRegs.isValid(); ++SubRegs)
1308         LiveRegs.reset(*SubRegs);
1309     }
1310
1311     // Examine all used registers and set/clear kill flag. When a
1312     // register is used multiple times we only set the kill flag on
1313     // the first use. Don't set kill flags on undef operands.
1314     killedRegs.reset();
1315     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1316       MachineOperand &MO = MI.getOperand(i);
1317       if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue;
1318       unsigned Reg = MO.getReg();
1319       if ((Reg == 0) || MRI.isReserved(Reg)) continue;
1320
1321       bool kill = false;
1322       if (!killedRegs.test(Reg)) {
1323         kill = true;
1324         // A register is not killed if any subregs are live...
1325         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) {
1326           if (LiveRegs.test(*SubRegs)) {
1327             kill = false;
1328             break;
1329           }
1330         }
1331
1332         // If subreg is not live, then register is killed if it became
1333         // live in this instruction
1334         if (kill)
1335           kill = !LiveRegs.test(Reg);
1336       }
1337
1338       if (MO.isKill() != kill) {
1339         DEBUG(dbgs() << "Fixing " << MO << " in ");
1340         // Warning: toggleKillFlag may invalidate MO.
1341         toggleKillFlag(&MI, MO);
1342         DEBUG(MI.dump());
1343         DEBUG({
1344           if (MI.getOpcode() == TargetOpcode::BUNDLE) {
1345             MachineBasicBlock::instr_iterator Begin = MI.getIterator();
1346             MachineBasicBlock::instr_iterator End = getBundleEnd(MI);
1347             while (++Begin != End)
1348               DEBUG(Begin->dump());
1349           }
1350         });
1351       }
1352
1353       killedRegs.set(Reg);
1354     }
1355
1356     // Mark any used register (that is not using undef) and subregs as
1357     // now live...
1358     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1359       MachineOperand &MO = MI.getOperand(i);
1360       if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue;
1361       unsigned Reg = MO.getReg();
1362       if ((Reg == 0) || MRI.isReserved(Reg)) continue;
1363
1364       for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
1365            SubRegs.isValid(); ++SubRegs)
1366         LiveRegs.set(*SubRegs);
1367     }
1368   }
1369 }
1370
1371 void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
1372 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1373   SU->getInstr()->dump();
1374 #endif
1375 }
1376
1377 std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
1378   std::string s;
1379   raw_string_ostream oss(s);
1380   if (SU == &EntrySU)
1381     oss << "<entry>";
1382   else if (SU == &ExitSU)
1383     oss << "<exit>";
1384   else
1385     SU->getInstr()->print(oss, /*SkipOpers=*/true);
1386   return oss.str();
1387 }
1388
1389 /// Return the basic block label. It is not necessarilly unique because a block
1390 /// contains multiple scheduling regions. But it is fine for visualization.
1391 std::string ScheduleDAGInstrs::getDAGName() const {
1392   return "dag." + BB->getFullName();
1393 }
1394
1395 //===----------------------------------------------------------------------===//
1396 // SchedDFSResult Implementation
1397 //===----------------------------------------------------------------------===//
1398
1399 namespace llvm {
1400 /// \brief Internal state used to compute SchedDFSResult.
1401 class SchedDFSImpl {
1402   SchedDFSResult &R;
1403
1404   /// Join DAG nodes into equivalence classes by their subtree.
1405   IntEqClasses SubtreeClasses;
1406   /// List PredSU, SuccSU pairs that represent data edges between subtrees.
1407   std::vector<std::pair<const SUnit*, const SUnit*> > ConnectionPairs;
1408
1409   struct RootData {
1410     unsigned NodeID;
1411     unsigned ParentNodeID;  // Parent node (member of the parent subtree).
1412     unsigned SubInstrCount; // Instr count in this tree only, not children.
1413
1414     RootData(unsigned id): NodeID(id),
1415                            ParentNodeID(SchedDFSResult::InvalidSubtreeID),
1416                            SubInstrCount(0) {}
1417
1418     unsigned getSparseSetIndex() const { return NodeID; }
1419   };
1420
1421   SparseSet<RootData> RootSet;
1422
1423 public:
1424   SchedDFSImpl(SchedDFSResult &r): R(r), SubtreeClasses(R.DFSNodeData.size()) {
1425     RootSet.setUniverse(R.DFSNodeData.size());
1426   }
1427
1428   /// Return true if this node been visited by the DFS traversal.
1429   ///
1430   /// During visitPostorderNode the Node's SubtreeID is assigned to the Node
1431   /// ID. Later, SubtreeID is updated but remains valid.
1432   bool isVisited(const SUnit *SU) const {
1433     return R.DFSNodeData[SU->NodeNum].SubtreeID
1434       != SchedDFSResult::InvalidSubtreeID;
1435   }
1436
1437   /// Initialize this node's instruction count. We don't need to flag the node
1438   /// visited until visitPostorder because the DAG cannot have cycles.
1439   void visitPreorder(const SUnit *SU) {
1440     R.DFSNodeData[SU->NodeNum].InstrCount =
1441       SU->getInstr()->isTransient() ? 0 : 1;
1442   }
1443
1444   /// Called once for each node after all predecessors are visited. Revisit this
1445   /// node's predecessors and potentially join them now that we know the ILP of
1446   /// the other predecessors.
1447   void visitPostorderNode(const SUnit *SU) {
1448     // Mark this node as the root of a subtree. It may be joined with its
1449     // successors later.
1450     R.DFSNodeData[SU->NodeNum].SubtreeID = SU->NodeNum;
1451     RootData RData(SU->NodeNum);
1452     RData.SubInstrCount = SU->getInstr()->isTransient() ? 0 : 1;
1453
1454     // If any predecessors are still in their own subtree, they either cannot be
1455     // joined or are large enough to remain separate. If this parent node's
1456     // total instruction count is not greater than a child subtree by at least
1457     // the subtree limit, then try to join it now since splitting subtrees is
1458     // only useful if multiple high-pressure paths are possible.
1459     unsigned InstrCount = R.DFSNodeData[SU->NodeNum].InstrCount;
1460     for (SUnit::const_pred_iterator
1461            PI = SU->Preds.begin(), PE = SU->Preds.end(); PI != PE; ++PI) {
1462       if (PI->getKind() != SDep::Data)
1463         continue;
1464       unsigned PredNum = PI->getSUnit()->NodeNum;
1465       if ((InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit)
1466         joinPredSubtree(*PI, SU, /*CheckLimit=*/false);
1467
1468       // Either link or merge the TreeData entry from the child to the parent.
1469       if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1470         // If the predecessor's parent is invalid, this is a tree edge and the
1471         // current node is the parent.
1472         if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1473           RootSet[PredNum].ParentNodeID = SU->NodeNum;
1474       }
1475       else if (RootSet.count(PredNum)) {
1476         // The predecessor is not a root, but is still in the root set. This
1477         // must be the new parent that it was just joined to. Note that
1478         // RootSet[PredNum].ParentNodeID may either be invalid or may still be
1479         // set to the original parent.
1480         RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1481         RootSet.erase(PredNum);
1482       }
1483     }
1484     RootSet[SU->NodeNum] = RData;
1485   }
1486
1487   /// Called once for each tree edge after calling visitPostOrderNode on the
1488   /// predecessor. Increment the parent node's instruction count and
1489   /// preemptively join this subtree to its parent's if it is small enough.
1490   void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ) {
1491     R.DFSNodeData[Succ->NodeNum].InstrCount
1492       += R.DFSNodeData[PredDep.getSUnit()->NodeNum].InstrCount;
1493     joinPredSubtree(PredDep, Succ);
1494   }
1495
1496   /// Add a connection for cross edges.
1497   void visitCrossEdge(const SDep &PredDep, const SUnit *Succ) {
1498     ConnectionPairs.push_back(std::make_pair(PredDep.getSUnit(), Succ));
1499   }
1500
1501   /// Set each node's subtree ID to the representative ID and record connections
1502   /// between trees.
1503   void finalize() {
1504     SubtreeClasses.compress();
1505     R.DFSTreeData.resize(SubtreeClasses.getNumClasses());
1506     assert(SubtreeClasses.getNumClasses() == RootSet.size()
1507            && "number of roots should match trees");
1508     for (SparseSet<RootData>::const_iterator
1509            RI = RootSet.begin(), RE = RootSet.end(); RI != RE; ++RI) {
1510       unsigned TreeID = SubtreeClasses[RI->NodeID];
1511       if (RI->ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1512         R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[RI->ParentNodeID];
1513       R.DFSTreeData[TreeID].SubInstrCount = RI->SubInstrCount;
1514       // Note that SubInstrCount may be greater than InstrCount if we joined
1515       // subtrees across a cross edge. InstrCount will be attributed to the
1516       // original parent, while SubInstrCount will be attributed to the joined
1517       // parent.
1518     }
1519     R.SubtreeConnections.resize(SubtreeClasses.getNumClasses());
1520     R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses());
1521     DEBUG(dbgs() << R.getNumSubtrees() << " subtrees:\n");
1522     for (unsigned Idx = 0, End = R.DFSNodeData.size(); Idx != End; ++Idx) {
1523       R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx];
1524       DEBUG(dbgs() << "  SU(" << Idx << ") in tree "
1525             << R.DFSNodeData[Idx].SubtreeID << '\n');
1526     }
1527     for (std::vector<std::pair<const SUnit*, const SUnit*> >::const_iterator
1528            I = ConnectionPairs.begin(), E = ConnectionPairs.end();
1529          I != E; ++I) {
1530       unsigned PredTree = SubtreeClasses[I->first->NodeNum];
1531       unsigned SuccTree = SubtreeClasses[I->second->NodeNum];
1532       if (PredTree == SuccTree)
1533         continue;
1534       unsigned Depth = I->first->getDepth();
1535       addConnection(PredTree, SuccTree, Depth);
1536       addConnection(SuccTree, PredTree, Depth);
1537     }
1538   }
1539
1540 protected:
1541   /// Join the predecessor subtree with the successor that is its DFS
1542   /// parent. Apply some heuristics before joining.
1543   bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ,
1544                        bool CheckLimit = true) {
1545     assert(PredDep.getKind() == SDep::Data && "Subtrees are for data edges");
1546
1547     // Check if the predecessor is already joined.
1548     const SUnit *PredSU = PredDep.getSUnit();
1549     unsigned PredNum = PredSU->NodeNum;
1550     if (R.DFSNodeData[PredNum].SubtreeID != PredNum)
1551       return false;
1552
1553     // Four is the magic number of successors before a node is considered a
1554     // pinch point.
1555     unsigned NumDataSucs = 0;
1556     for (SUnit::const_succ_iterator SI = PredSU->Succs.begin(),
1557            SE = PredSU->Succs.end(); SI != SE; ++SI) {
1558       if (SI->getKind() == SDep::Data) {
1559         if (++NumDataSucs >= 4)
1560           return false;
1561       }
1562     }
1563     if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit)
1564       return false;
1565     R.DFSNodeData[PredNum].SubtreeID = Succ->NodeNum;
1566     SubtreeClasses.join(Succ->NodeNum, PredNum);
1567     return true;
1568   }
1569
1570   /// Called by finalize() to record a connection between trees.
1571   void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth) {
1572     if (!Depth)
1573       return;
1574
1575     do {
1576       SmallVectorImpl<SchedDFSResult::Connection> &Connections =
1577         R.SubtreeConnections[FromTree];
1578       for (SmallVectorImpl<SchedDFSResult::Connection>::iterator
1579              I = Connections.begin(), E = Connections.end(); I != E; ++I) {
1580         if (I->TreeID == ToTree) {
1581           I->Level = std::max(I->Level, Depth);
1582           return;
1583         }
1584       }
1585       Connections.push_back(SchedDFSResult::Connection(ToTree, Depth));
1586       FromTree = R.DFSTreeData[FromTree].ParentTreeID;
1587     } while (FromTree != SchedDFSResult::InvalidSubtreeID);
1588   }
1589 };
1590 } // namespace llvm
1591
1592 namespace {
1593 /// \brief Manage the stack used by a reverse depth-first search over the DAG.
1594 class SchedDAGReverseDFS {
1595   std::vector<std::pair<const SUnit*, SUnit::const_pred_iterator> > DFSStack;
1596 public:
1597   bool isComplete() const { return DFSStack.empty(); }
1598
1599   void follow(const SUnit *SU) {
1600     DFSStack.push_back(std::make_pair(SU, SU->Preds.begin()));
1601   }
1602   void advance() { ++DFSStack.back().second; }
1603
1604   const SDep *backtrack() {
1605     DFSStack.pop_back();
1606     return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second);
1607   }
1608
1609   const SUnit *getCurr() const { return DFSStack.back().first; }
1610
1611   SUnit::const_pred_iterator getPred() const { return DFSStack.back().second; }
1612
1613   SUnit::const_pred_iterator getPredEnd() const {
1614     return getCurr()->Preds.end();
1615   }
1616 };
1617 } // anonymous
1618
1619 static bool hasDataSucc(const SUnit *SU) {
1620   for (SUnit::const_succ_iterator
1621          SI = SU->Succs.begin(), SE = SU->Succs.end(); SI != SE; ++SI) {
1622     if (SI->getKind() == SDep::Data && !SI->getSUnit()->isBoundaryNode())
1623       return true;
1624   }
1625   return false;
1626 }
1627
1628 /// Compute an ILP metric for all nodes in the subDAG reachable via depth-first
1629 /// search from this root.
1630 void SchedDFSResult::compute(ArrayRef<SUnit> SUnits) {
1631   if (!IsBottomUp)
1632     llvm_unreachable("Top-down ILP metric is unimplemnted");
1633
1634   SchedDFSImpl Impl(*this);
1635   for (ArrayRef<SUnit>::const_iterator
1636          SI = SUnits.begin(), SE = SUnits.end(); SI != SE; ++SI) {
1637     const SUnit *SU = &*SI;
1638     if (Impl.isVisited(SU) || hasDataSucc(SU))
1639       continue;
1640
1641     SchedDAGReverseDFS DFS;
1642     Impl.visitPreorder(SU);
1643     DFS.follow(SU);
1644     for (;;) {
1645       // Traverse the leftmost path as far as possible.
1646       while (DFS.getPred() != DFS.getPredEnd()) {
1647         const SDep &PredDep = *DFS.getPred();
1648         DFS.advance();
1649         // Ignore non-data edges.
1650         if (PredDep.getKind() != SDep::Data
1651             || PredDep.getSUnit()->isBoundaryNode()) {
1652           continue;
1653         }
1654         // An already visited edge is a cross edge, assuming an acyclic DAG.
1655         if (Impl.isVisited(PredDep.getSUnit())) {
1656           Impl.visitCrossEdge(PredDep, DFS.getCurr());
1657           continue;
1658         }
1659         Impl.visitPreorder(PredDep.getSUnit());
1660         DFS.follow(PredDep.getSUnit());
1661       }
1662       // Visit the top of the stack in postorder and backtrack.
1663       const SUnit *Child = DFS.getCurr();
1664       const SDep *PredDep = DFS.backtrack();
1665       Impl.visitPostorderNode(Child);
1666       if (PredDep)
1667         Impl.visitPostorderEdge(*PredDep, DFS.getCurr());
1668       if (DFS.isComplete())
1669         break;
1670     }
1671   }
1672   Impl.finalize();
1673 }
1674
1675 /// The root of the given SubtreeID was just scheduled. For all subtrees
1676 /// connected to this tree, record the depth of the connection so that the
1677 /// nearest connected subtrees can be prioritized.
1678 void SchedDFSResult::scheduleTree(unsigned SubtreeID) {
1679   for (SmallVectorImpl<Connection>::const_iterator
1680          I = SubtreeConnections[SubtreeID].begin(),
1681          E = SubtreeConnections[SubtreeID].end(); I != E; ++I) {
1682     SubtreeConnectLevels[I->TreeID] =
1683       std::max(SubtreeConnectLevels[I->TreeID], I->Level);
1684     DEBUG(dbgs() << "  Tree: " << I->TreeID
1685           << " @" << SubtreeConnectLevels[I->TreeID] << '\n');
1686   }
1687 }
1688
1689 LLVM_DUMP_METHOD
1690 void ILPValue::print(raw_ostream &OS) const {
1691   OS << InstrCount << " / " << Length << " = ";
1692   if (!Length)
1693     OS << "BADILP";
1694   else
1695     OS << format("%g", ((double)InstrCount / Length));
1696 }
1697
1698 LLVM_DUMP_METHOD
1699 void ILPValue::dump() const {
1700   dbgs() << *this << '\n';
1701 }
1702
1703 namespace llvm {
1704
1705 LLVM_DUMP_METHOD
1706 raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val) {
1707   Val.print(OS);
1708   return OS;
1709 }
1710
1711 } // namespace llvm