diff options
| author | orivej <[email protected]> | 2022-02-10 16:45:01 +0300 | 
|---|---|---|
| committer | Daniil Cherednik <[email protected]> | 2022-02-10 16:45:01 +0300 | 
| commit | 2d37894b1b037cf24231090eda8589bbb44fb6fc (patch) | |
| tree | be835aa92c6248212e705f25388ebafcf84bc7a1 /contrib/libs/llvm12/lib/CodeGen/MachineScheduler.cpp | |
| parent | 718c552901d703c502ccbefdfc3c9028d608b947 (diff) | |
Restoring authorship annotation for <[email protected]>. Commit 2 of 2.
Diffstat (limited to 'contrib/libs/llvm12/lib/CodeGen/MachineScheduler.cpp')
| -rw-r--r-- | contrib/libs/llvm12/lib/CodeGen/MachineScheduler.cpp | 7456 | 
1 files changed, 3728 insertions, 3728 deletions
diff --git a/contrib/libs/llvm12/lib/CodeGen/MachineScheduler.cpp b/contrib/libs/llvm12/lib/CodeGen/MachineScheduler.cpp index 48d9e5c2232..8d51bb26103 100644 --- a/contrib/libs/llvm12/lib/CodeGen/MachineScheduler.cpp +++ b/contrib/libs/llvm12/lib/CodeGen/MachineScheduler.cpp @@ -1,134 +1,134 @@ -//===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===//  -//  -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.  -// See https://llvm.org/LICENSE.txt for license information.  -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception  -//  -//===----------------------------------------------------------------------===//  -//  -// MachineScheduler schedules machine instructions after phi elimination. It  -// preserves LiveIntervals so it can be invoked before register allocation.  -//  -//===----------------------------------------------------------------------===//  -  -#include "llvm/CodeGen/MachineScheduler.h"  -#include "llvm/ADT/ArrayRef.h"  -#include "llvm/ADT/BitVector.h"  -#include "llvm/ADT/DenseMap.h"  -#include "llvm/ADT/PriorityQueue.h"  -#include "llvm/ADT/STLExtras.h"  -#include "llvm/ADT/SmallVector.h"  +//===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// MachineScheduler schedules machine instructions after phi elimination. It +// preserves LiveIntervals so it can be invoked before register allocation. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/MachineScheduler.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PriorityQueue.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h"  #include "llvm/ADT/Statistic.h" -#include "llvm/ADT/iterator_range.h"  -#include "llvm/Analysis/AliasAnalysis.h"  -#include "llvm/CodeGen/LiveInterval.h"  -#include "llvm/CodeGen/LiveIntervals.h"  -#include "llvm/CodeGen/MachineBasicBlock.h"  -#include "llvm/CodeGen/MachineDominators.h"  -#include "llvm/CodeGen/MachineFunction.h"  -#include "llvm/CodeGen/MachineFunctionPass.h"  -#include "llvm/CodeGen/MachineInstr.h"  -#include "llvm/CodeGen/MachineLoopInfo.h"  -#include "llvm/CodeGen/MachineOperand.h"  -#include "llvm/CodeGen/MachinePassRegistry.h"  -#include "llvm/CodeGen/MachineRegisterInfo.h"  -#include "llvm/CodeGen/Passes.h"  -#include "llvm/CodeGen/RegisterClassInfo.h"  -#include "llvm/CodeGen/RegisterPressure.h"  -#include "llvm/CodeGen/ScheduleDAG.h"  -#include "llvm/CodeGen/ScheduleDAGInstrs.h"  -#include "llvm/CodeGen/ScheduleDAGMutation.h"  -#include "llvm/CodeGen/ScheduleDFS.h"  -#include "llvm/CodeGen/ScheduleHazardRecognizer.h"  -#include "llvm/CodeGen/SlotIndexes.h"  -#include "llvm/CodeGen/TargetFrameLowering.h"  -#include "llvm/CodeGen/TargetInstrInfo.h"  -#include "llvm/CodeGen/TargetLowering.h"  -#include "llvm/CodeGen/TargetPassConfig.h"  -#include "llvm/CodeGen/TargetRegisterInfo.h"  -#include "llvm/CodeGen/TargetSchedule.h"  -#include "llvm/CodeGen/TargetSubtargetInfo.h"  -#include "llvm/Config/llvm-config.h"  -#include "llvm/InitializePasses.h"  -#include "llvm/MC/LaneBitmask.h"  -#include "llvm/Pass.h"  -#include "llvm/Support/CommandLine.h"  -#include "llvm/Support/Compiler.h"  -#include "llvm/Support/Debug.h"  -#include "llvm/Support/ErrorHandling.h"  -#include "llvm/Support/GraphWriter.h"  -#include "llvm/Support/MachineValueType.h"  -#include "llvm/Support/raw_ostream.h"  -#include <algorithm>  -#include <cassert>  -#include <cstdint>  -#include <iterator>  -#include <limits>  -#include <memory>  -#include <string>  -#include <tuple>  -#include <utility>  -#include <vector>  -  -using namespace llvm;  -  -#define DEBUG_TYPE "machine-scheduler"  -  +#include "llvm/ADT/iterator_range.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/LiveIntervals.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/MachinePassRegistry.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/CodeGen/RegisterPressure.h" +#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include "llvm/CodeGen/ScheduleDAGMutation.h" +#include "llvm/CodeGen/ScheduleDFS.h" +#include "llvm/CodeGen/ScheduleHazardRecognizer.h" +#include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/CodeGen/TargetFrameLowering.h" +#include "llvm/CodeGen/TargetInstrInfo.h" +#include "llvm/CodeGen/TargetLowering.h" +#include "llvm/CodeGen/TargetPassConfig.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" +#include "llvm/CodeGen/TargetSchedule.h" +#include "llvm/CodeGen/TargetSubtargetInfo.h" +#include "llvm/Config/llvm-config.h" +#include "llvm/InitializePasses.h" +#include "llvm/MC/LaneBitmask.h" +#include "llvm/Pass.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/GraphWriter.h" +#include "llvm/Support/MachineValueType.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <cassert> +#include <cstdint> +#include <iterator> +#include <limits> +#include <memory> +#include <string> +#include <tuple> +#include <utility> +#include <vector> + +using namespace llvm; + +#define DEBUG_TYPE "machine-scheduler" +  STATISTIC(NumClustered, "Number of load/store pairs clustered"); -namespace llvm {  -  -cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden,  -                           cl::desc("Force top-down list scheduling"));  -cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden,  -                            cl::desc("Force bottom-up list scheduling"));  -cl::opt<bool>  -DumpCriticalPathLength("misched-dcpl", cl::Hidden,  -                       cl::desc("Print critical path length to stdout"));  -  -cl::opt<bool> VerifyScheduling(  -    "verify-misched", cl::Hidden,  -    cl::desc("Verify machine instrs before and after machine scheduling"));  -  -} // end namespace llvm  -  -#ifndef NDEBUG  -static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden,  -  cl::desc("Pop up a window to show MISched dags after they are processed"));  -  -/// In some situations a few uninteresting nodes depend on nearly all other  -/// nodes in the graph, provide a cutoff to hide them.  -static cl::opt<unsigned> ViewMISchedCutoff("view-misched-cutoff", cl::Hidden,  -  cl::desc("Hide nodes with more predecessor/successor than cutoff"));  -  -static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden,  -  cl::desc("Stop scheduling after N instructions"), cl::init(~0U));  -  -static cl::opt<std::string> SchedOnlyFunc("misched-only-func", cl::Hidden,  -  cl::desc("Only schedule this function"));  -static cl::opt<unsigned> SchedOnlyBlock("misched-only-block", cl::Hidden,  -                                        cl::desc("Only schedule this MBB#"));  -static cl::opt<bool> PrintDAGs("misched-print-dags", cl::Hidden,  -                              cl::desc("Print schedule DAGs"));  -#else  -static const bool ViewMISchedDAGs = false;  -static const bool PrintDAGs = false;  -#endif // NDEBUG  -  -/// Avoid quadratic complexity in unusually large basic blocks by limiting the  -/// size of the ready lists.  -static cl::opt<unsigned> ReadyListLimit("misched-limit", cl::Hidden,  -  cl::desc("Limit ready list to N instructions"), cl::init(256));  -  -static cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden,  -  cl::desc("Enable register pressure scheduling."), cl::init(true));  -  -static cl::opt<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden,  -  cl::desc("Enable cyclic critical path analysis."), cl::init(true));  -  -static cl::opt<bool> EnableMemOpCluster("misched-cluster", cl::Hidden,  -                                        cl::desc("Enable memop clustering."),  -                                        cl::init(true));  +namespace llvm { + +cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden, +                           cl::desc("Force top-down list scheduling")); +cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden, +                            cl::desc("Force bottom-up list scheduling")); +cl::opt<bool> +DumpCriticalPathLength("misched-dcpl", cl::Hidden, +                       cl::desc("Print critical path length to stdout")); + +cl::opt<bool> VerifyScheduling( +    "verify-misched", cl::Hidden, +    cl::desc("Verify machine instrs before and after machine scheduling")); + +} // end namespace llvm + +#ifndef NDEBUG +static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden, +  cl::desc("Pop up a window to show MISched dags after they are processed")); + +/// In some situations a few uninteresting nodes depend on nearly all other +/// nodes in the graph, provide a cutoff to hide them. +static cl::opt<unsigned> ViewMISchedCutoff("view-misched-cutoff", cl::Hidden, +  cl::desc("Hide nodes with more predecessor/successor than cutoff")); + +static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden, +  cl::desc("Stop scheduling after N instructions"), cl::init(~0U)); + +static cl::opt<std::string> SchedOnlyFunc("misched-only-func", cl::Hidden, +  cl::desc("Only schedule this function")); +static cl::opt<unsigned> SchedOnlyBlock("misched-only-block", cl::Hidden, +                                        cl::desc("Only schedule this MBB#")); +static cl::opt<bool> PrintDAGs("misched-print-dags", cl::Hidden, +                              cl::desc("Print schedule DAGs")); +#else +static const bool ViewMISchedDAGs = false; +static const bool PrintDAGs = false; +#endif // NDEBUG + +/// Avoid quadratic complexity in unusually large basic blocks by limiting the +/// size of the ready lists. +static cl::opt<unsigned> ReadyListLimit("misched-limit", cl::Hidden, +  cl::desc("Limit ready list to N instructions"), cl::init(256)); + +static cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden, +  cl::desc("Enable register pressure scheduling."), cl::init(true)); + +static cl::opt<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden, +  cl::desc("Enable cyclic critical path analysis."), cl::init(true)); + +static cl::opt<bool> EnableMemOpCluster("misched-cluster", cl::Hidden, +                                        cl::desc("Enable memop clustering."), +                                        cl::init(true));  static cl::opt<bool>      ForceFastCluster("force-fast-cluster", cl::Hidden,                       cl::desc("Switch to fast cluster algorithm with the lost " @@ -138,108 +138,108 @@ static cl::opt<unsigned>      FastClusterThreshold("fast-cluster-threshold", cl::Hidden,                           cl::desc("The threshold for fast cluster"),                           cl::init(1000)); -  -// DAG subtrees must have at least this many nodes.  -static const unsigned MinSubtreeSize = 8;  -  -// Pin the vtables to this file.  -void MachineSchedStrategy::anchor() {}  -  -void ScheduleDAGMutation::anchor() {}  -  -//===----------------------------------------------------------------------===//  -// Machine Instruction Scheduling Pass and Registry  -//===----------------------------------------------------------------------===//  -  -MachineSchedContext::MachineSchedContext() {  -  RegClassInfo = new RegisterClassInfo();  -}  -  -MachineSchedContext::~MachineSchedContext() {  -  delete RegClassInfo;  -}  -  -namespace {  -  -/// Base class for a machine scheduler class that can run at any point.  -class MachineSchedulerBase : public MachineSchedContext,  -                             public MachineFunctionPass {  -public:  -  MachineSchedulerBase(char &ID): MachineFunctionPass(ID) {}  -  -  void print(raw_ostream &O, const Module* = nullptr) const override;  -  -protected:  -  void scheduleRegions(ScheduleDAGInstrs &Scheduler, bool FixKillFlags);  -};  -  -/// MachineScheduler runs after coalescing and before register allocation.  -class MachineScheduler : public MachineSchedulerBase {  -public:  -  MachineScheduler();  -  -  void getAnalysisUsage(AnalysisUsage &AU) const override;  -  -  bool runOnMachineFunction(MachineFunction&) override;  -  -  static char ID; // Class identification, replacement for typeinfo  -  -protected:  -  ScheduleDAGInstrs *createMachineScheduler();  -};  -  -/// PostMachineScheduler runs after shortly before code emission.  -class PostMachineScheduler : public MachineSchedulerBase {  -public:  -  PostMachineScheduler();  -  -  void getAnalysisUsage(AnalysisUsage &AU) const override;  -  -  bool runOnMachineFunction(MachineFunction&) override;  -  -  static char ID; // Class identification, replacement for typeinfo  -  -protected:  -  ScheduleDAGInstrs *createPostMachineScheduler();  -};  -  -} // end anonymous namespace  -  -char MachineScheduler::ID = 0;  -  -char &llvm::MachineSchedulerID = MachineScheduler::ID;  -  -INITIALIZE_PASS_BEGIN(MachineScheduler, DEBUG_TYPE,  -                      "Machine Instruction Scheduler", false, false)  -INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)  -INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)  -INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)  -INITIALIZE_PASS_DEPENDENCY(SlotIndexes)  -INITIALIZE_PASS_DEPENDENCY(LiveIntervals)  -INITIALIZE_PASS_END(MachineScheduler, DEBUG_TYPE,  -                    "Machine Instruction Scheduler", false, false)  -  -MachineScheduler::MachineScheduler() : MachineSchedulerBase(ID) {  -  initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());  -}  -  -void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {  -  AU.setPreservesCFG();  -  AU.addRequired<MachineDominatorTree>();  -  AU.addRequired<MachineLoopInfo>();  -  AU.addRequired<AAResultsWrapperPass>();  -  AU.addRequired<TargetPassConfig>();  -  AU.addRequired<SlotIndexes>();  -  AU.addPreserved<SlotIndexes>();  -  AU.addRequired<LiveIntervals>();  -  AU.addPreserved<LiveIntervals>();  -  MachineFunctionPass::getAnalysisUsage(AU);  -}  -  -char PostMachineScheduler::ID = 0;  -  -char &llvm::PostMachineSchedulerID = PostMachineScheduler::ID;  -  + +// DAG subtrees must have at least this many nodes. +static const unsigned MinSubtreeSize = 8; + +// Pin the vtables to this file. +void MachineSchedStrategy::anchor() {} + +void ScheduleDAGMutation::anchor() {} + +//===----------------------------------------------------------------------===// +// Machine Instruction Scheduling Pass and Registry +//===----------------------------------------------------------------------===// + +MachineSchedContext::MachineSchedContext() { +  RegClassInfo = new RegisterClassInfo(); +} + +MachineSchedContext::~MachineSchedContext() { +  delete RegClassInfo; +} + +namespace { + +/// Base class for a machine scheduler class that can run at any point. +class MachineSchedulerBase : public MachineSchedContext, +                             public MachineFunctionPass { +public: +  MachineSchedulerBase(char &ID): MachineFunctionPass(ID) {} + +  void print(raw_ostream &O, const Module* = nullptr) const override; + +protected: +  void scheduleRegions(ScheduleDAGInstrs &Scheduler, bool FixKillFlags); +}; + +/// MachineScheduler runs after coalescing and before register allocation. +class MachineScheduler : public MachineSchedulerBase { +public: +  MachineScheduler(); + +  void getAnalysisUsage(AnalysisUsage &AU) const override; + +  bool runOnMachineFunction(MachineFunction&) override; + +  static char ID; // Class identification, replacement for typeinfo + +protected: +  ScheduleDAGInstrs *createMachineScheduler(); +}; + +/// PostMachineScheduler runs after shortly before code emission. +class PostMachineScheduler : public MachineSchedulerBase { +public: +  PostMachineScheduler(); + +  void getAnalysisUsage(AnalysisUsage &AU) const override; + +  bool runOnMachineFunction(MachineFunction&) override; + +  static char ID; // Class identification, replacement for typeinfo + +protected: +  ScheduleDAGInstrs *createPostMachineScheduler(); +}; + +} // end anonymous namespace + +char MachineScheduler::ID = 0; + +char &llvm::MachineSchedulerID = MachineScheduler::ID; + +INITIALIZE_PASS_BEGIN(MachineScheduler, DEBUG_TYPE, +                      "Machine Instruction Scheduler", false, false) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) +INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) +INITIALIZE_PASS_DEPENDENCY(SlotIndexes) +INITIALIZE_PASS_DEPENDENCY(LiveIntervals) +INITIALIZE_PASS_END(MachineScheduler, DEBUG_TYPE, +                    "Machine Instruction Scheduler", false, false) + +MachineScheduler::MachineScheduler() : MachineSchedulerBase(ID) { +  initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); +} + +void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { +  AU.setPreservesCFG(); +  AU.addRequired<MachineDominatorTree>(); +  AU.addRequired<MachineLoopInfo>(); +  AU.addRequired<AAResultsWrapperPass>(); +  AU.addRequired<TargetPassConfig>(); +  AU.addRequired<SlotIndexes>(); +  AU.addPreserved<SlotIndexes>(); +  AU.addRequired<LiveIntervals>(); +  AU.addPreserved<LiveIntervals>(); +  MachineFunctionPass::getAnalysisUsage(AU); +} + +char PostMachineScheduler::ID = 0; + +char &llvm::PostMachineSchedulerID = PostMachineScheduler::ID; +  INITIALIZE_PASS_BEGIN(PostMachineScheduler, "postmisched",                        "PostRA Machine Instruction Scheduler", false, false)  INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) @@ -247,1360 +247,1360 @@ INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)  INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)  INITIALIZE_PASS_END(PostMachineScheduler, "postmisched",                      "PostRA Machine Instruction Scheduler", false, false) -  -PostMachineScheduler::PostMachineScheduler() : MachineSchedulerBase(ID) {  -  initializePostMachineSchedulerPass(*PassRegistry::getPassRegistry());  -}  -  -void PostMachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {  -  AU.setPreservesCFG();  -  AU.addRequired<MachineDominatorTree>();  -  AU.addRequired<MachineLoopInfo>();  -  AU.addRequired<AAResultsWrapperPass>();  -  AU.addRequired<TargetPassConfig>();  -  MachineFunctionPass::getAnalysisUsage(AU);  -}  -  -MachinePassRegistry<MachineSchedRegistry::ScheduleDAGCtor>  -    MachineSchedRegistry::Registry;  -  -/// A dummy default scheduler factory indicates whether the scheduler  -/// is overridden on the command line.  -static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) {  -  return nullptr;  -}  -  -/// MachineSchedOpt allows command line selection of the scheduler.  -static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false,  -               RegisterPassParser<MachineSchedRegistry>>  -MachineSchedOpt("misched",  -                cl::init(&useDefaultMachineSched), cl::Hidden,  -                cl::desc("Machine instruction scheduler to use"));  -  -static MachineSchedRegistry  -DefaultSchedRegistry("default", "Use the target's default scheduler choice.",  -                     useDefaultMachineSched);  -  -static cl::opt<bool> EnableMachineSched(  -    "enable-misched",  -    cl::desc("Enable the machine instruction scheduling pass."), cl::init(true),  -    cl::Hidden);  -  -static cl::opt<bool> EnablePostRAMachineSched(  -    "enable-post-misched",  -    cl::desc("Enable the post-ra machine instruction scheduling pass."),  -    cl::init(true), cl::Hidden);  -  -/// Decrement this iterator until reaching the top or a non-debug instr.  -static MachineBasicBlock::const_iterator  -priorNonDebug(MachineBasicBlock::const_iterator I,  -              MachineBasicBlock::const_iterator Beg) {  -  assert(I != Beg && "reached the top of the region, cannot decrement");  -  while (--I != Beg) {  -    if (!I->isDebugInstr())  -      break;  -  }  -  return I;  -}  -  -/// Non-const version.  -static MachineBasicBlock::iterator  -priorNonDebug(MachineBasicBlock::iterator I,  -              MachineBasicBlock::const_iterator Beg) {  -  return priorNonDebug(MachineBasicBlock::const_iterator(I), Beg)  -      .getNonConstIterator();  -}  -  -/// If this iterator is a debug value, increment until reaching the End or a  -/// non-debug instruction.  -static MachineBasicBlock::const_iterator  -nextIfDebug(MachineBasicBlock::const_iterator I,  -            MachineBasicBlock::const_iterator End) {  -  for(; I != End; ++I) {  -    if (!I->isDebugInstr())  -      break;  -  }  -  return I;  -}  -  -/// Non-const version.  -static MachineBasicBlock::iterator  -nextIfDebug(MachineBasicBlock::iterator I,  -            MachineBasicBlock::const_iterator End) {  -  return nextIfDebug(MachineBasicBlock::const_iterator(I), End)  -      .getNonConstIterator();  -}  -  -/// Instantiate a ScheduleDAGInstrs that will be owned by the caller.  -ScheduleDAGInstrs *MachineScheduler::createMachineScheduler() {  -  // Select the scheduler, or set the default.  -  MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt;  -  if (Ctor != useDefaultMachineSched)  -    return Ctor(this);  -  -  // Get the default scheduler set by the target for this function.  -  ScheduleDAGInstrs *Scheduler = PassConfig->createMachineScheduler(this);  -  if (Scheduler)  -    return Scheduler;  -  -  // Default to GenericScheduler.  -  return createGenericSchedLive(this);  -}  -  -/// Instantiate a ScheduleDAGInstrs for PostRA scheduling that will be owned by  -/// the caller. We don't have a command line option to override the postRA  -/// scheduler. The Target must configure it.  -ScheduleDAGInstrs *PostMachineScheduler::createPostMachineScheduler() {  -  // Get the postRA scheduler set by the target for this function.  -  ScheduleDAGInstrs *Scheduler = PassConfig->createPostMachineScheduler(this);  -  if (Scheduler)  -    return Scheduler;  -  -  // Default to GenericScheduler.  -  return createGenericSchedPostRA(this);  -}  -  -/// Top-level MachineScheduler pass driver.  -///  -/// Visit blocks in function order. Divide each block into scheduling regions  -/// and visit them bottom-up. Visiting regions bottom-up is not required, but is  -/// consistent with the DAG builder, which traverses the interior of the  -/// scheduling regions bottom-up.  -///  -/// This design avoids exposing scheduling boundaries to the DAG builder,  -/// simplifying the DAG builder's support for "special" target instructions.  -/// At the same time the design allows target schedulers to operate across  -/// scheduling boundaries, for example to bundle the boundary instructions  -/// without reordering them. This creates complexity, because the target  -/// scheduler must update the RegionBegin and RegionEnd positions cached by  -/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler  -/// design would be to split blocks at scheduling boundaries, but LLVM has a  -/// general bias against block splitting purely for implementation simplicity.  -bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) {  -  if (skipFunction(mf.getFunction()))  -    return false;  -  -  if (EnableMachineSched.getNumOccurrences()) {  -    if (!EnableMachineSched)  -      return false;  -  } else if (!mf.getSubtarget().enableMachineScheduler())  -    return false;  -  -  LLVM_DEBUG(dbgs() << "Before MISched:\n"; mf.print(dbgs()));  -  -  // Initialize the context of the pass.  -  MF = &mf;  -  MLI = &getAnalysis<MachineLoopInfo>();  -  MDT = &getAnalysis<MachineDominatorTree>();  -  PassConfig = &getAnalysis<TargetPassConfig>();  -  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();  -  -  LIS = &getAnalysis<LiveIntervals>();  -  -  if (VerifyScheduling) {  -    LLVM_DEBUG(LIS->dump());  -    MF->verify(this, "Before machine scheduling.");  -  }  -  RegClassInfo->runOnMachineFunction(*MF);  -  -  // Instantiate the selected scheduler for this target, function, and  -  // optimization level.  -  std::unique_ptr<ScheduleDAGInstrs> Scheduler(createMachineScheduler());  -  scheduleRegions(*Scheduler, false);  -  -  LLVM_DEBUG(LIS->dump());  -  if (VerifyScheduling)  -    MF->verify(this, "After machine scheduling.");  -  return true;  -}  -  -bool PostMachineScheduler::runOnMachineFunction(MachineFunction &mf) {  -  if (skipFunction(mf.getFunction()))  -    return false;  -  -  if (EnablePostRAMachineSched.getNumOccurrences()) {  -    if (!EnablePostRAMachineSched)  -      return false;  -  } else if (!mf.getSubtarget().enablePostRAMachineScheduler()) {  -    LLVM_DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");  -    return false;  -  }  -  LLVM_DEBUG(dbgs() << "Before post-MI-sched:\n"; mf.print(dbgs()));  -  -  // Initialize the context of the pass.  -  MF = &mf;  -  MLI = &getAnalysis<MachineLoopInfo>();  -  PassConfig = &getAnalysis<TargetPassConfig>();  -  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();  -  -  if (VerifyScheduling)  -    MF->verify(this, "Before post machine scheduling.");  -  -  // Instantiate the selected scheduler for this target, function, and  -  // optimization level.  -  std::unique_ptr<ScheduleDAGInstrs> Scheduler(createPostMachineScheduler());  -  scheduleRegions(*Scheduler, true);  -  -  if (VerifyScheduling)  -    MF->verify(this, "After post machine scheduling.");  -  return true;  -}  -  -/// Return true of the given instruction should not be included in a scheduling  -/// region.  -///  -/// MachineScheduler does not currently support scheduling across calls. To  -/// handle calls, the DAG builder needs to be modified to create register  -/// anti/output dependencies on the registers clobbered by the call's regmask  -/// operand. In PreRA scheduling, the stack pointer adjustment already prevents  -/// scheduling across calls. In PostRA scheduling, we need the isCall to enforce  -/// the boundary, but there would be no benefit to postRA scheduling across  -/// calls this late anyway.  -static bool isSchedBoundary(MachineBasicBlock::iterator MI,  -                            MachineBasicBlock *MBB,  -                            MachineFunction *MF,  -                            const TargetInstrInfo *TII) {  -  return MI->isCall() || TII->isSchedulingBoundary(*MI, MBB, *MF);  -}  -  -/// A region of an MBB for scheduling.  -namespace {  -struct SchedRegion {  -  /// RegionBegin is the first instruction in the scheduling region, and  -  /// RegionEnd is either MBB->end() or the scheduling boundary after the  -  /// last instruction in the scheduling region. These iterators cannot refer  -  /// to instructions outside of the identified scheduling region because  -  /// those may be reordered before scheduling this region.  -  MachineBasicBlock::iterator RegionBegin;  -  MachineBasicBlock::iterator RegionEnd;  -  unsigned NumRegionInstrs;  -  -  SchedRegion(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E,  -              unsigned N) :  -    RegionBegin(B), RegionEnd(E), NumRegionInstrs(N) {}  -};  -} // end anonymous namespace  -  -using MBBRegionsVector = SmallVector<SchedRegion, 16>;  -  -static void  -getSchedRegions(MachineBasicBlock *MBB,  -                MBBRegionsVector &Regions,  -                bool RegionsTopDown) {  -  MachineFunction *MF = MBB->getParent();  -  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();  -  -  MachineBasicBlock::iterator I = nullptr;  -  for(MachineBasicBlock::iterator RegionEnd = MBB->end();  -      RegionEnd != MBB->begin(); RegionEnd = I) {  -  -    // Avoid decrementing RegionEnd for blocks with no terminator.  -    if (RegionEnd != MBB->end() ||  -        isSchedBoundary(&*std::prev(RegionEnd), &*MBB, MF, TII)) {  -      --RegionEnd;  -    }  -  -    // The next region starts above the previous region. Look backward in the  -    // instruction stream until we find the nearest boundary.  -    unsigned NumRegionInstrs = 0;  -    I = RegionEnd;  -    for (;I != MBB->begin(); --I) {  -      MachineInstr &MI = *std::prev(I);  -      if (isSchedBoundary(&MI, &*MBB, MF, TII))  -        break;  -      if (!MI.isDebugInstr()) {  -        // MBB::size() uses instr_iterator to count. Here we need a bundle to  -        // count as a single instruction.  -        ++NumRegionInstrs;  -      }  -    }  -  -    // It's possible we found a scheduling region that only has debug  -    // instructions. Don't bother scheduling these.  -    if (NumRegionInstrs != 0)  -      Regions.push_back(SchedRegion(I, RegionEnd, NumRegionInstrs));  -  }  -  -  if (RegionsTopDown)  -    std::reverse(Regions.begin(), Regions.end());  -}  -  -/// Main driver for both MachineScheduler and PostMachineScheduler.  -void MachineSchedulerBase::scheduleRegions(ScheduleDAGInstrs &Scheduler,  -                                           bool FixKillFlags) {  -  // Visit all machine basic blocks.  -  //  -  // TODO: Visit blocks in global postorder or postorder within the bottom-up  -  // loop tree. Then we can optionally compute global RegPressure.  -  for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end();  -       MBB != MBBEnd; ++MBB) {  -  -    Scheduler.startBlock(&*MBB);  -  -#ifndef NDEBUG  -    if (SchedOnlyFunc.getNumOccurrences() && SchedOnlyFunc != MF->getName())  -      continue;  -    if (SchedOnlyBlock.getNumOccurrences()  -        && (int)SchedOnlyBlock != MBB->getNumber())  -      continue;  -#endif  -  -    // Break the block into scheduling regions [I, RegionEnd). RegionEnd  -    // points to the scheduling boundary at the bottom of the region. The DAG  -    // does not include RegionEnd, but the region does (i.e. the next  -    // RegionEnd is above the previous RegionBegin). If the current block has  -    // no terminator then RegionEnd == MBB->end() for the bottom region.  -    //  -    // All the regions of MBB are first found and stored in MBBRegions, which  -    // will be processed (MBB) top-down if initialized with true.  -    //  -    // The Scheduler may insert instructions during either schedule() or  -    // exitRegion(), even for empty regions. So the local iterators 'I' and  -    // 'RegionEnd' are invalid across these calls. Instructions must not be  -    // added to other regions than the current one without updating MBBRegions.  -  -    MBBRegionsVector MBBRegions;  -    getSchedRegions(&*MBB, MBBRegions, Scheduler.doMBBSchedRegionsTopDown());  -    for (MBBRegionsVector::iterator R = MBBRegions.begin();  -         R != MBBRegions.end(); ++R) {  -      MachineBasicBlock::iterator I = R->RegionBegin;  -      MachineBasicBlock::iterator RegionEnd = R->RegionEnd;  -      unsigned NumRegionInstrs = R->NumRegionInstrs;  -  -      // Notify the scheduler of the region, even if we may skip scheduling  -      // it. Perhaps it still needs to be bundled.  -      Scheduler.enterRegion(&*MBB, I, RegionEnd, NumRegionInstrs);  -  -      // Skip empty scheduling regions (0 or 1 schedulable instructions).  -      if (I == RegionEnd || I == std::prev(RegionEnd)) {  -        // Close the current region. Bundle the terminator if needed.  -        // This invalidates 'RegionEnd' and 'I'.  -        Scheduler.exitRegion();  -        continue;  -      }  -      LLVM_DEBUG(dbgs() << "********** MI Scheduling **********\n");  -      LLVM_DEBUG(dbgs() << MF->getName() << ":" << printMBBReference(*MBB)  -                        << " " << MBB->getName() << "\n  From: " << *I  -                        << "    To: ";  -                 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd;  -                 else dbgs() << "End";  -                 dbgs() << " RegionInstrs: " << NumRegionInstrs << '\n');  -      if (DumpCriticalPathLength) {  -        errs() << MF->getName();  -        errs() << ":%bb. " << MBB->getNumber();  -        errs() << " " << MBB->getName() << " \n";  -      }  -  -      // Schedule a region: possibly reorder instructions.  -      // This invalidates the original region iterators.  -      Scheduler.schedule();  -  -      // Close the current region.  -      Scheduler.exitRegion();  -    }  -    Scheduler.finishBlock();  -    // FIXME: Ideally, no further passes should rely on kill flags. However,  -    // thumb2 size reduction is currently an exception, so the PostMIScheduler  -    // needs to do this.  -    if (FixKillFlags)  -      Scheduler.fixupKills(*MBB);  -  }  -  Scheduler.finalizeSchedule();  -}  -  -void MachineSchedulerBase::print(raw_ostream &O, const Module* m) const {  -  // unimplemented  -}  -  -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)  -LLVM_DUMP_METHOD void ReadyQueue::dump() const {  -  dbgs() << "Queue " << Name << ": ";  -  for (const SUnit *SU : Queue)  -    dbgs() << SU->NodeNum << " ";  -  dbgs() << "\n";  -}  -#endif  -  -//===----------------------------------------------------------------------===//  -// ScheduleDAGMI - Basic machine instruction scheduling. This is  -// independent of PreRA/PostRA scheduling and involves no extra book-keeping for  -// virtual registers.  -// ===----------------------------------------------------------------------===/  -  -// Provide a vtable anchor.  -ScheduleDAGMI::~ScheduleDAGMI() = default;  -  -/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When  -/// NumPredsLeft reaches zero, release the successor node.  -///  -/// FIXME: Adjust SuccSU height based on MinLatency.  -void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) {  -  SUnit *SuccSU = SuccEdge->getSUnit();  -  -  if (SuccEdge->isWeak()) {  -    --SuccSU->WeakPredsLeft;  -    if (SuccEdge->isCluster())  -      NextClusterSucc = SuccSU;  -    return;  -  }  -#ifndef NDEBUG  -  if (SuccSU->NumPredsLeft == 0) {  -    dbgs() << "*** Scheduling failed! ***\n";  -    dumpNode(*SuccSU);  -    dbgs() << " has been released too many times!\n";  -    llvm_unreachable(nullptr);  -  }  -#endif  -  // SU->TopReadyCycle was set to CurrCycle when it was scheduled. However,  -  // CurrCycle may have advanced since then.  -  if (SuccSU->TopReadyCycle < SU->TopReadyCycle + SuccEdge->getLatency())  -    SuccSU->TopReadyCycle = SU->TopReadyCycle + SuccEdge->getLatency();  -  -  --SuccSU->NumPredsLeft;  -  if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)  -    SchedImpl->releaseTopNode(SuccSU);  -}  -  -/// releaseSuccessors - Call releaseSucc on each of SU's successors.  -void ScheduleDAGMI::releaseSuccessors(SUnit *SU) {  -  for (SDep &Succ : SU->Succs)  -    releaseSucc(SU, &Succ);  -}  -  -/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When  -/// NumSuccsLeft reaches zero, release the predecessor node.  -///  -/// FIXME: Adjust PredSU height based on MinLatency.  -void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) {  -  SUnit *PredSU = PredEdge->getSUnit();  -  -  if (PredEdge->isWeak()) {  -    --PredSU->WeakSuccsLeft;  -    if (PredEdge->isCluster())  -      NextClusterPred = PredSU;  -    return;  -  }  -#ifndef NDEBUG  -  if (PredSU->NumSuccsLeft == 0) {  -    dbgs() << "*** Scheduling failed! ***\n";  -    dumpNode(*PredSU);  -    dbgs() << " has been released too many times!\n";  -    llvm_unreachable(nullptr);  -  }  -#endif  -  // SU->BotReadyCycle was set to CurrCycle when it was scheduled. However,  -  // CurrCycle may have advanced since then.  -  if (PredSU->BotReadyCycle < SU->BotReadyCycle + PredEdge->getLatency())  -    PredSU->BotReadyCycle = SU->BotReadyCycle + PredEdge->getLatency();  -  -  --PredSU->NumSuccsLeft;  -  if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU)  -    SchedImpl->releaseBottomNode(PredSU);  -}  -  -/// releasePredecessors - Call releasePred on each of SU's predecessors.  -void ScheduleDAGMI::releasePredecessors(SUnit *SU) {  -  for (SDep &Pred : SU->Preds)  -    releasePred(SU, &Pred);  -}  -  -void ScheduleDAGMI::startBlock(MachineBasicBlock *bb) {  -  ScheduleDAGInstrs::startBlock(bb);  -  SchedImpl->enterMBB(bb);  -}  -  -void ScheduleDAGMI::finishBlock() {  -  SchedImpl->leaveMBB();  -  ScheduleDAGInstrs::finishBlock();  -}  -  -/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after  -/// crossing a scheduling boundary. [begin, end) includes all instructions in  -/// the region, including the boundary itself and single-instruction regions  -/// that don't get scheduled.  -void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb,  -                                     MachineBasicBlock::iterator begin,  -                                     MachineBasicBlock::iterator end,  -                                     unsigned regioninstrs)  -{  -  ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);  -  -  SchedImpl->initPolicy(begin, end, regioninstrs);  -}  -  -/// This is normally called from the main scheduler loop but may also be invoked  -/// by the scheduling strategy to perform additional code motion.  -void ScheduleDAGMI::moveInstruction(  -  MachineInstr *MI, MachineBasicBlock::iterator InsertPos) {  -  // Advance RegionBegin if the first instruction moves down.  -  if (&*RegionBegin == MI)  -    ++RegionBegin;  -  -  // Update the instruction stream.  -  BB->splice(InsertPos, BB, MI);  -  -  // Update LiveIntervals  -  if (LIS)  -    LIS->handleMove(*MI, /*UpdateFlags=*/true);  -  -  // Recede RegionBegin if an instruction moves above the first.  -  if (RegionBegin == InsertPos)  -    RegionBegin = MI;  -}  -  -bool ScheduleDAGMI::checkSchedLimit() {  -#ifndef NDEBUG  -  if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) {  -    CurrentTop = CurrentBottom;  -    return false;  -  }  -  ++NumInstrsScheduled;  -#endif  -  return true;  -}  -  -/// Per-region scheduling driver, called back from  -/// MachineScheduler::runOnMachineFunction. This is a simplified driver that  -/// does not consider liveness or register pressure. It is useful for PostRA  -/// scheduling and potentially other custom schedulers.  -void ScheduleDAGMI::schedule() {  -  LLVM_DEBUG(dbgs() << "ScheduleDAGMI::schedule starting\n");  -  LLVM_DEBUG(SchedImpl->dumpPolicy());  -  -  // Build the DAG.  -  buildSchedGraph(AA);  -  -  postprocessDAG();  -  -  SmallVector<SUnit*, 8> TopRoots, BotRoots;  -  findRootsAndBiasEdges(TopRoots, BotRoots);  -  -  LLVM_DEBUG(dump());  -  if (PrintDAGs) dump();  -  if (ViewMISchedDAGs) viewGraph();  -  -  // Initialize the strategy before modifying the DAG.  -  // This may initialize a DFSResult to be used for queue priority.  -  SchedImpl->initialize(this);  -  -  // Initialize ready queues now that the DAG and priority data are finalized.  -  initQueues(TopRoots, BotRoots);  -  -  bool IsTopNode = false;  -  while (true) {  -    LLVM_DEBUG(dbgs() << "** ScheduleDAGMI::schedule picking next node\n");  -    SUnit *SU = SchedImpl->pickNode(IsTopNode);  -    if (!SU) break;  -  -    assert(!SU->isScheduled && "Node already scheduled");  -    if (!checkSchedLimit())  -      break;  -  -    MachineInstr *MI = SU->getInstr();  -    if (IsTopNode) {  -      assert(SU->isTopReady() && "node still has unscheduled dependencies");  -      if (&*CurrentTop == MI)  -        CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);  -      else  -        moveInstruction(MI, CurrentTop);  -    } else {  -      assert(SU->isBottomReady() && "node still has unscheduled dependencies");  -      MachineBasicBlock::iterator priorII =  -        priorNonDebug(CurrentBottom, CurrentTop);  -      if (&*priorII == MI)  -        CurrentBottom = priorII;  -      else {  -        if (&*CurrentTop == MI)  -          CurrentTop = nextIfDebug(++CurrentTop, priorII);  -        moveInstruction(MI, CurrentBottom);  -        CurrentBottom = MI;  -      }  -    }  -    // Notify the scheduling strategy before updating the DAG.  -    // This sets the scheduled node's ReadyCycle to CurrCycle. When updateQueues  -    // runs, it can then use the accurate ReadyCycle time to determine whether  -    // newly released nodes can move to the readyQ.  -    SchedImpl->schedNode(SU, IsTopNode);  -  -    updateQueues(SU, IsTopNode);  -  }  -  assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");  -  -  placeDebugValues();  -  -  LLVM_DEBUG({  -    dbgs() << "*** Final schedule for "  -           << printMBBReference(*begin()->getParent()) << " ***\n";  -    dumpSchedule();  -    dbgs() << '\n';  -  });  -}  -  -/// Apply each ScheduleDAGMutation step in order.  -void ScheduleDAGMI::postprocessDAG() {  -  for (auto &m : Mutations)  -    m->apply(this);  -}  -  -void ScheduleDAGMI::  -findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,  -                      SmallVectorImpl<SUnit*> &BotRoots) {  -  for (SUnit &SU : SUnits) {  -    assert(!SU.isBoundaryNode() && "Boundary node should not be in SUnits");  -  -    // Order predecessors so DFSResult follows the critical path.  -    SU.biasCriticalPath();  -  -    // A SUnit is ready to top schedule if it has no predecessors.  -    if (!SU.NumPredsLeft)  -      TopRoots.push_back(&SU);  -    // A SUnit is ready to bottom schedule if it has no successors.  -    if (!SU.NumSuccsLeft)  -      BotRoots.push_back(&SU);  -  }  -  ExitSU.biasCriticalPath();  -}  -  -/// Identify DAG roots and setup scheduler queues.  -void ScheduleDAGMI::initQueues(ArrayRef<SUnit*> TopRoots,  -                               ArrayRef<SUnit*> BotRoots) {  -  NextClusterSucc = nullptr;  -  NextClusterPred = nullptr;  -  -  // Release all DAG roots for scheduling, not including EntrySU/ExitSU.  -  //  -  // Nodes with unreleased weak edges can still be roots.  -  // Release top roots in forward order.  -  for (SUnit *SU : TopRoots)  -    SchedImpl->releaseTopNode(SU);  -  -  // Release bottom roots in reverse order so the higher priority nodes appear  -  // first. This is more natural and slightly more efficient.  -  for (SmallVectorImpl<SUnit*>::const_reverse_iterator  -         I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) {  -    SchedImpl->releaseBottomNode(*I);  -  }  -  -  releaseSuccessors(&EntrySU);  -  releasePredecessors(&ExitSU);  -  -  SchedImpl->registerRoots();  -  -  // Advance past initial DebugValues.  -  CurrentTop = nextIfDebug(RegionBegin, RegionEnd);  -  CurrentBottom = RegionEnd;  -}  -  -/// Update scheduler queues after scheduling an instruction.  -void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) {  -  // Release dependent instructions for scheduling.  -  if (IsTopNode)  -    releaseSuccessors(SU);  -  else  -    releasePredecessors(SU);  -  -  SU->isScheduled = true;  -}  -  -/// Reinsert any remaining debug_values, just like the PostRA scheduler.  -void ScheduleDAGMI::placeDebugValues() {  -  // If first instruction was a DBG_VALUE then put it back.  -  if (FirstDbgValue) {  -    BB->splice(RegionBegin, BB, FirstDbgValue);  -    RegionBegin = FirstDbgValue;  -  }  -  -  for (std::vector<std::pair<MachineInstr *, MachineInstr *>>::iterator  -         DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {  -    std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);  -    MachineInstr *DbgValue = P.first;  -    MachineBasicBlock::iterator OrigPrevMI = P.second;  -    if (&*RegionBegin == DbgValue)  -      ++RegionBegin;  -    BB->splice(++OrigPrevMI, BB, DbgValue);  -    if (OrigPrevMI == std::prev(RegionEnd))  -      RegionEnd = DbgValue;  -  }  -  DbgValues.clear();  -  FirstDbgValue = nullptr;  -}  -  -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)  -LLVM_DUMP_METHOD void ScheduleDAGMI::dumpSchedule() const {  -  for (MachineBasicBlock::iterator MI = begin(), ME = end(); MI != ME; ++MI) {  -    if (SUnit *SU = getSUnit(&(*MI)))  -      dumpNode(*SU);  -    else  -      dbgs() << "Missing SUnit\n";  -  }  -}  -#endif  -  -//===----------------------------------------------------------------------===//  -// ScheduleDAGMILive - Base class for MachineInstr scheduling with LiveIntervals  -// preservation.  -//===----------------------------------------------------------------------===//  -  -ScheduleDAGMILive::~ScheduleDAGMILive() {  -  delete DFSResult;  -}  -  -void ScheduleDAGMILive::collectVRegUses(SUnit &SU) {  -  const MachineInstr &MI = *SU.getInstr();  -  for (const MachineOperand &MO : MI.operands()) {  -    if (!MO.isReg())  -      continue;  -    if (!MO.readsReg())  -      continue;  -    if (TrackLaneMasks && !MO.isUse())  -      continue;  -  -    Register Reg = MO.getReg();  -    if (!Register::isVirtualRegister(Reg))  -      continue;  -  -    // Ignore re-defs.  -    if (TrackLaneMasks) {  -      bool FoundDef = false;  -      for (const MachineOperand &MO2 : MI.operands()) {  -        if (MO2.isReg() && MO2.isDef() && MO2.getReg() == Reg && !MO2.isDead()) {  -          FoundDef = true;  -          break;  -        }  -      }  -      if (FoundDef)  -        continue;  -    }  -  -    // Record this local VReg use.  -    VReg2SUnitMultiMap::iterator UI = VRegUses.find(Reg);  -    for (; UI != VRegUses.end(); ++UI) {  -      if (UI->SU == &SU)  -        break;  -    }  -    if (UI == VRegUses.end())  -      VRegUses.insert(VReg2SUnit(Reg, LaneBitmask::getNone(), &SU));  -  }  -}  -  -/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after  -/// crossing a scheduling boundary. [begin, end) includes all instructions in  -/// the region, including the boundary itself and single-instruction regions  -/// that don't get scheduled.  -void ScheduleDAGMILive::enterRegion(MachineBasicBlock *bb,  -                                MachineBasicBlock::iterator begin,  -                                MachineBasicBlock::iterator end,  -                                unsigned regioninstrs)  -{  -  // ScheduleDAGMI initializes SchedImpl's per-region policy.  -  ScheduleDAGMI::enterRegion(bb, begin, end, regioninstrs);  -  -  // For convenience remember the end of the liveness region.  -  LiveRegionEnd = (RegionEnd == bb->end()) ? RegionEnd : std::next(RegionEnd);  -  -  SUPressureDiffs.clear();  -  -  ShouldTrackPressure = SchedImpl->shouldTrackPressure();  -  ShouldTrackLaneMasks = SchedImpl->shouldTrackLaneMasks();  -  -  assert((!ShouldTrackLaneMasks || ShouldTrackPressure) &&  -         "ShouldTrackLaneMasks requires ShouldTrackPressure");  -}  -  -// Setup the register pressure trackers for the top scheduled and bottom  -// scheduled regions.  -void ScheduleDAGMILive::initRegPressure() {  -  VRegUses.clear();  -  VRegUses.setUniverse(MRI.getNumVirtRegs());  -  for (SUnit &SU : SUnits)  -    collectVRegUses(SU);  -  -  TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin,  -                    ShouldTrackLaneMasks, false);  -  BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,  -                    ShouldTrackLaneMasks, false);  -  -  // Close the RPTracker to finalize live ins.  -  RPTracker.closeRegion();  -  -  LLVM_DEBUG(RPTracker.dump());  -  -  // Initialize the live ins and live outs.  -  TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs);  -  BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs);  -  -  // Close one end of the tracker so we can call  -  // getMaxUpward/DownwardPressureDelta before advancing across any  -  // instructions. This converts currently live regs into live ins/outs.  -  TopRPTracker.closeTop();  -  BotRPTracker.closeBottom();  -  -  BotRPTracker.initLiveThru(RPTracker);  -  if (!BotRPTracker.getLiveThru().empty()) {  -    TopRPTracker.initLiveThru(BotRPTracker.getLiveThru());  -    LLVM_DEBUG(dbgs() << "Live Thru: ";  -               dumpRegSetPressure(BotRPTracker.getLiveThru(), TRI));  -  };  -  -  // For each live out vreg reduce the pressure change associated with other  -  // uses of the same vreg below the live-out reaching def.  -  updatePressureDiffs(RPTracker.getPressure().LiveOutRegs);  -  -  // Account for liveness generated by the region boundary.  -  if (LiveRegionEnd != RegionEnd) {  -    SmallVector<RegisterMaskPair, 8> LiveUses;  -    BotRPTracker.recede(&LiveUses);  -    updatePressureDiffs(LiveUses);  -  }  -  -  LLVM_DEBUG(dbgs() << "Top Pressure:\n";  -             dumpRegSetPressure(TopRPTracker.getRegSetPressureAtPos(), TRI);  -             dbgs() << "Bottom Pressure:\n";  -             dumpRegSetPressure(BotRPTracker.getRegSetPressureAtPos(), TRI););  -  -  assert((BotRPTracker.getPos() == RegionEnd ||  -          (RegionEnd->isDebugInstr() &&  -           BotRPTracker.getPos() == priorNonDebug(RegionEnd, RegionBegin))) &&  -         "Can't find the region bottom");  -  -  // Cache the list of excess pressure sets in this region. This will also track  -  // the max pressure in the scheduled code for these sets.  -  RegionCriticalPSets.clear();  -  const std::vector<unsigned> &RegionPressure =  -    RPTracker.getPressure().MaxSetPressure;  -  for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {  -    unsigned Limit = RegClassInfo->getRegPressureSetLimit(i);  -    if (RegionPressure[i] > Limit) {  -      LLVM_DEBUG(dbgs() << TRI->getRegPressureSetName(i) << " Limit " << Limit  -                        << " Actual " << RegionPressure[i] << "\n");  -      RegionCriticalPSets.push_back(PressureChange(i));  -    }  -  }  -  LLVM_DEBUG(dbgs() << "Excess PSets: ";  -             for (const PressureChange &RCPS  -                  : RegionCriticalPSets) dbgs()  -             << TRI->getRegPressureSetName(RCPS.getPSet()) << " ";  -             dbgs() << "\n");  -}  -  -void ScheduleDAGMILive::  -updateScheduledPressure(const SUnit *SU,  -                        const std::vector<unsigned> &NewMaxPressure) {  -  const PressureDiff &PDiff = getPressureDiff(SU);  -  unsigned CritIdx = 0, CritEnd = RegionCriticalPSets.size();  -  for (const PressureChange &PC : PDiff) {  -    if (!PC.isValid())  -      break;  -    unsigned ID = PC.getPSet();  -    while (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() < ID)  -      ++CritIdx;  -    if (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() == ID) {  -      if ((int)NewMaxPressure[ID] > RegionCriticalPSets[CritIdx].getUnitInc()  -          && NewMaxPressure[ID] <= (unsigned)std::numeric_limits<int16_t>::max())  -        RegionCriticalPSets[CritIdx].setUnitInc(NewMaxPressure[ID]);  -    }  -    unsigned Limit = RegClassInfo->getRegPressureSetLimit(ID);  -    if (NewMaxPressure[ID] >= Limit - 2) {  -      LLVM_DEBUG(dbgs() << "  " << TRI->getRegPressureSetName(ID) << ": "  -                        << NewMaxPressure[ID]  -                        << ((NewMaxPressure[ID] > Limit) ? " > " : " <= ")  -                        << Limit << "(+ " << BotRPTracker.getLiveThru()[ID]  -                        << " livethru)\n");  -    }  -  }  -}  -  -/// Update the PressureDiff array for liveness after scheduling this  -/// instruction.  -void ScheduleDAGMILive::updatePressureDiffs(  -    ArrayRef<RegisterMaskPair> LiveUses) {  -  for (const RegisterMaskPair &P : LiveUses) {  + +PostMachineScheduler::PostMachineScheduler() : MachineSchedulerBase(ID) { +  initializePostMachineSchedulerPass(*PassRegistry::getPassRegistry()); +} + +void PostMachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { +  AU.setPreservesCFG(); +  AU.addRequired<MachineDominatorTree>(); +  AU.addRequired<MachineLoopInfo>(); +  AU.addRequired<AAResultsWrapperPass>(); +  AU.addRequired<TargetPassConfig>(); +  MachineFunctionPass::getAnalysisUsage(AU); +} + +MachinePassRegistry<MachineSchedRegistry::ScheduleDAGCtor> +    MachineSchedRegistry::Registry; + +/// A dummy default scheduler factory indicates whether the scheduler +/// is overridden on the command line. +static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) { +  return nullptr; +} + +/// MachineSchedOpt allows command line selection of the scheduler. +static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, +               RegisterPassParser<MachineSchedRegistry>> +MachineSchedOpt("misched", +                cl::init(&useDefaultMachineSched), cl::Hidden, +                cl::desc("Machine instruction scheduler to use")); + +static MachineSchedRegistry +DefaultSchedRegistry("default", "Use the target's default scheduler choice.", +                     useDefaultMachineSched); + +static cl::opt<bool> EnableMachineSched( +    "enable-misched", +    cl::desc("Enable the machine instruction scheduling pass."), cl::init(true), +    cl::Hidden); + +static cl::opt<bool> EnablePostRAMachineSched( +    "enable-post-misched", +    cl::desc("Enable the post-ra machine instruction scheduling pass."), +    cl::init(true), cl::Hidden); + +/// Decrement this iterator until reaching the top or a non-debug instr. +static MachineBasicBlock::const_iterator +priorNonDebug(MachineBasicBlock::const_iterator I, +              MachineBasicBlock::const_iterator Beg) { +  assert(I != Beg && "reached the top of the region, cannot decrement"); +  while (--I != Beg) { +    if (!I->isDebugInstr()) +      break; +  } +  return I; +} + +/// Non-const version. +static MachineBasicBlock::iterator +priorNonDebug(MachineBasicBlock::iterator I, +              MachineBasicBlock::const_iterator Beg) { +  return priorNonDebug(MachineBasicBlock::const_iterator(I), Beg) +      .getNonConstIterator(); +} + +/// If this iterator is a debug value, increment until reaching the End or a +/// non-debug instruction. +static MachineBasicBlock::const_iterator +nextIfDebug(MachineBasicBlock::const_iterator I, +            MachineBasicBlock::const_iterator End) { +  for(; I != End; ++I) { +    if (!I->isDebugInstr()) +      break; +  } +  return I; +} + +/// Non-const version. +static MachineBasicBlock::iterator +nextIfDebug(MachineBasicBlock::iterator I, +            MachineBasicBlock::const_iterator End) { +  return nextIfDebug(MachineBasicBlock::const_iterator(I), End) +      .getNonConstIterator(); +} + +/// Instantiate a ScheduleDAGInstrs that will be owned by the caller. +ScheduleDAGInstrs *MachineScheduler::createMachineScheduler() { +  // Select the scheduler, or set the default. +  MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt; +  if (Ctor != useDefaultMachineSched) +    return Ctor(this); + +  // Get the default scheduler set by the target for this function. +  ScheduleDAGInstrs *Scheduler = PassConfig->createMachineScheduler(this); +  if (Scheduler) +    return Scheduler; + +  // Default to GenericScheduler. +  return createGenericSchedLive(this); +} + +/// Instantiate a ScheduleDAGInstrs for PostRA scheduling that will be owned by +/// the caller. We don't have a command line option to override the postRA +/// scheduler. The Target must configure it. +ScheduleDAGInstrs *PostMachineScheduler::createPostMachineScheduler() { +  // Get the postRA scheduler set by the target for this function. +  ScheduleDAGInstrs *Scheduler = PassConfig->createPostMachineScheduler(this); +  if (Scheduler) +    return Scheduler; + +  // Default to GenericScheduler. +  return createGenericSchedPostRA(this); +} + +/// Top-level MachineScheduler pass driver. +/// +/// Visit blocks in function order. Divide each block into scheduling regions +/// and visit them bottom-up. Visiting regions bottom-up is not required, but is +/// consistent with the DAG builder, which traverses the interior of the +/// scheduling regions bottom-up. +/// +/// This design avoids exposing scheduling boundaries to the DAG builder, +/// simplifying the DAG builder's support for "special" target instructions. +/// At the same time the design allows target schedulers to operate across +/// scheduling boundaries, for example to bundle the boundary instructions +/// without reordering them. This creates complexity, because the target +/// scheduler must update the RegionBegin and RegionEnd positions cached by +/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler +/// design would be to split blocks at scheduling boundaries, but LLVM has a +/// general bias against block splitting purely for implementation simplicity. +bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { +  if (skipFunction(mf.getFunction())) +    return false; + +  if (EnableMachineSched.getNumOccurrences()) { +    if (!EnableMachineSched) +      return false; +  } else if (!mf.getSubtarget().enableMachineScheduler()) +    return false; + +  LLVM_DEBUG(dbgs() << "Before MISched:\n"; mf.print(dbgs())); + +  // Initialize the context of the pass. +  MF = &mf; +  MLI = &getAnalysis<MachineLoopInfo>(); +  MDT = &getAnalysis<MachineDominatorTree>(); +  PassConfig = &getAnalysis<TargetPassConfig>(); +  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); + +  LIS = &getAnalysis<LiveIntervals>(); + +  if (VerifyScheduling) { +    LLVM_DEBUG(LIS->dump()); +    MF->verify(this, "Before machine scheduling."); +  } +  RegClassInfo->runOnMachineFunction(*MF); + +  // Instantiate the selected scheduler for this target, function, and +  // optimization level. +  std::unique_ptr<ScheduleDAGInstrs> Scheduler(createMachineScheduler()); +  scheduleRegions(*Scheduler, false); + +  LLVM_DEBUG(LIS->dump()); +  if (VerifyScheduling) +    MF->verify(this, "After machine scheduling."); +  return true; +} + +bool PostMachineScheduler::runOnMachineFunction(MachineFunction &mf) { +  if (skipFunction(mf.getFunction())) +    return false; + +  if (EnablePostRAMachineSched.getNumOccurrences()) { +    if (!EnablePostRAMachineSched) +      return false; +  } else if (!mf.getSubtarget().enablePostRAMachineScheduler()) { +    LLVM_DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n"); +    return false; +  } +  LLVM_DEBUG(dbgs() << "Before post-MI-sched:\n"; mf.print(dbgs())); + +  // Initialize the context of the pass. +  MF = &mf; +  MLI = &getAnalysis<MachineLoopInfo>(); +  PassConfig = &getAnalysis<TargetPassConfig>(); +  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); + +  if (VerifyScheduling) +    MF->verify(this, "Before post machine scheduling."); + +  // Instantiate the selected scheduler for this target, function, and +  // optimization level. +  std::unique_ptr<ScheduleDAGInstrs> Scheduler(createPostMachineScheduler()); +  scheduleRegions(*Scheduler, true); + +  if (VerifyScheduling) +    MF->verify(this, "After post machine scheduling."); +  return true; +} + +/// Return true of the given instruction should not be included in a scheduling +/// region. +/// +/// MachineScheduler does not currently support scheduling across calls. To +/// handle calls, the DAG builder needs to be modified to create register +/// anti/output dependencies on the registers clobbered by the call's regmask +/// operand. In PreRA scheduling, the stack pointer adjustment already prevents +/// scheduling across calls. In PostRA scheduling, we need the isCall to enforce +/// the boundary, but there would be no benefit to postRA scheduling across +/// calls this late anyway. +static bool isSchedBoundary(MachineBasicBlock::iterator MI, +                            MachineBasicBlock *MBB, +                            MachineFunction *MF, +                            const TargetInstrInfo *TII) { +  return MI->isCall() || TII->isSchedulingBoundary(*MI, MBB, *MF); +} + +/// A region of an MBB for scheduling. +namespace { +struct SchedRegion { +  /// RegionBegin is the first instruction in the scheduling region, and +  /// RegionEnd is either MBB->end() or the scheduling boundary after the +  /// last instruction in the scheduling region. These iterators cannot refer +  /// to instructions outside of the identified scheduling region because +  /// those may be reordered before scheduling this region. +  MachineBasicBlock::iterator RegionBegin; +  MachineBasicBlock::iterator RegionEnd; +  unsigned NumRegionInstrs; + +  SchedRegion(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E, +              unsigned N) : +    RegionBegin(B), RegionEnd(E), NumRegionInstrs(N) {} +}; +} // end anonymous namespace + +using MBBRegionsVector = SmallVector<SchedRegion, 16>; + +static void +getSchedRegions(MachineBasicBlock *MBB, +                MBBRegionsVector &Regions, +                bool RegionsTopDown) { +  MachineFunction *MF = MBB->getParent(); +  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); + +  MachineBasicBlock::iterator I = nullptr; +  for(MachineBasicBlock::iterator RegionEnd = MBB->end(); +      RegionEnd != MBB->begin(); RegionEnd = I) { + +    // Avoid decrementing RegionEnd for blocks with no terminator. +    if (RegionEnd != MBB->end() || +        isSchedBoundary(&*std::prev(RegionEnd), &*MBB, MF, TII)) { +      --RegionEnd; +    } + +    // The next region starts above the previous region. Look backward in the +    // instruction stream until we find the nearest boundary. +    unsigned NumRegionInstrs = 0; +    I = RegionEnd; +    for (;I != MBB->begin(); --I) { +      MachineInstr &MI = *std::prev(I); +      if (isSchedBoundary(&MI, &*MBB, MF, TII)) +        break; +      if (!MI.isDebugInstr()) { +        // MBB::size() uses instr_iterator to count. Here we need a bundle to +        // count as a single instruction. +        ++NumRegionInstrs; +      } +    } + +    // It's possible we found a scheduling region that only has debug +    // instructions. Don't bother scheduling these. +    if (NumRegionInstrs != 0) +      Regions.push_back(SchedRegion(I, RegionEnd, NumRegionInstrs)); +  } + +  if (RegionsTopDown) +    std::reverse(Regions.begin(), Regions.end()); +} + +/// Main driver for both MachineScheduler and PostMachineScheduler. +void MachineSchedulerBase::scheduleRegions(ScheduleDAGInstrs &Scheduler, +                                           bool FixKillFlags) { +  // Visit all machine basic blocks. +  // +  // TODO: Visit blocks in global postorder or postorder within the bottom-up +  // loop tree. Then we can optionally compute global RegPressure. +  for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); +       MBB != MBBEnd; ++MBB) { + +    Scheduler.startBlock(&*MBB); + +#ifndef NDEBUG +    if (SchedOnlyFunc.getNumOccurrences() && SchedOnlyFunc != MF->getName()) +      continue; +    if (SchedOnlyBlock.getNumOccurrences() +        && (int)SchedOnlyBlock != MBB->getNumber()) +      continue; +#endif + +    // Break the block into scheduling regions [I, RegionEnd). RegionEnd +    // points to the scheduling boundary at the bottom of the region. The DAG +    // does not include RegionEnd, but the region does (i.e. the next +    // RegionEnd is above the previous RegionBegin). If the current block has +    // no terminator then RegionEnd == MBB->end() for the bottom region. +    // +    // All the regions of MBB are first found and stored in MBBRegions, which +    // will be processed (MBB) top-down if initialized with true. +    // +    // The Scheduler may insert instructions during either schedule() or +    // exitRegion(), even for empty regions. So the local iterators 'I' and +    // 'RegionEnd' are invalid across these calls. Instructions must not be +    // added to other regions than the current one without updating MBBRegions. + +    MBBRegionsVector MBBRegions; +    getSchedRegions(&*MBB, MBBRegions, Scheduler.doMBBSchedRegionsTopDown()); +    for (MBBRegionsVector::iterator R = MBBRegions.begin(); +         R != MBBRegions.end(); ++R) { +      MachineBasicBlock::iterator I = R->RegionBegin; +      MachineBasicBlock::iterator RegionEnd = R->RegionEnd; +      unsigned NumRegionInstrs = R->NumRegionInstrs; + +      // Notify the scheduler of the region, even if we may skip scheduling +      // it. Perhaps it still needs to be bundled. +      Scheduler.enterRegion(&*MBB, I, RegionEnd, NumRegionInstrs); + +      // Skip empty scheduling regions (0 or 1 schedulable instructions). +      if (I == RegionEnd || I == std::prev(RegionEnd)) { +        // Close the current region. Bundle the terminator if needed. +        // This invalidates 'RegionEnd' and 'I'. +        Scheduler.exitRegion(); +        continue; +      } +      LLVM_DEBUG(dbgs() << "********** MI Scheduling **********\n"); +      LLVM_DEBUG(dbgs() << MF->getName() << ":" << printMBBReference(*MBB) +                        << " " << MBB->getName() << "\n  From: " << *I +                        << "    To: "; +                 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd; +                 else dbgs() << "End"; +                 dbgs() << " RegionInstrs: " << NumRegionInstrs << '\n'); +      if (DumpCriticalPathLength) { +        errs() << MF->getName(); +        errs() << ":%bb. " << MBB->getNumber(); +        errs() << " " << MBB->getName() << " \n"; +      } + +      // Schedule a region: possibly reorder instructions. +      // This invalidates the original region iterators. +      Scheduler.schedule(); + +      // Close the current region. +      Scheduler.exitRegion(); +    } +    Scheduler.finishBlock(); +    // FIXME: Ideally, no further passes should rely on kill flags. However, +    // thumb2 size reduction is currently an exception, so the PostMIScheduler +    // needs to do this. +    if (FixKillFlags) +      Scheduler.fixupKills(*MBB); +  } +  Scheduler.finalizeSchedule(); +} + +void MachineSchedulerBase::print(raw_ostream &O, const Module* m) const { +  // unimplemented +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD void ReadyQueue::dump() const { +  dbgs() << "Queue " << Name << ": "; +  for (const SUnit *SU : Queue) +    dbgs() << SU->NodeNum << " "; +  dbgs() << "\n"; +} +#endif + +//===----------------------------------------------------------------------===// +// ScheduleDAGMI - Basic machine instruction scheduling. This is +// independent of PreRA/PostRA scheduling and involves no extra book-keeping for +// virtual registers. +// ===----------------------------------------------------------------------===/ + +// Provide a vtable anchor. +ScheduleDAGMI::~ScheduleDAGMI() = default; + +/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When +/// NumPredsLeft reaches zero, release the successor node. +/// +/// FIXME: Adjust SuccSU height based on MinLatency. +void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) { +  SUnit *SuccSU = SuccEdge->getSUnit(); + +  if (SuccEdge->isWeak()) { +    --SuccSU->WeakPredsLeft; +    if (SuccEdge->isCluster()) +      NextClusterSucc = SuccSU; +    return; +  } +#ifndef NDEBUG +  if (SuccSU->NumPredsLeft == 0) { +    dbgs() << "*** Scheduling failed! ***\n"; +    dumpNode(*SuccSU); +    dbgs() << " has been released too many times!\n"; +    llvm_unreachable(nullptr); +  } +#endif +  // SU->TopReadyCycle was set to CurrCycle when it was scheduled. However, +  // CurrCycle may have advanced since then. +  if (SuccSU->TopReadyCycle < SU->TopReadyCycle + SuccEdge->getLatency()) +    SuccSU->TopReadyCycle = SU->TopReadyCycle + SuccEdge->getLatency(); + +  --SuccSU->NumPredsLeft; +  if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) +    SchedImpl->releaseTopNode(SuccSU); +} + +/// releaseSuccessors - Call releaseSucc on each of SU's successors. +void ScheduleDAGMI::releaseSuccessors(SUnit *SU) { +  for (SDep &Succ : SU->Succs) +    releaseSucc(SU, &Succ); +} + +/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When +/// NumSuccsLeft reaches zero, release the predecessor node. +/// +/// FIXME: Adjust PredSU height based on MinLatency. +void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) { +  SUnit *PredSU = PredEdge->getSUnit(); + +  if (PredEdge->isWeak()) { +    --PredSU->WeakSuccsLeft; +    if (PredEdge->isCluster()) +      NextClusterPred = PredSU; +    return; +  } +#ifndef NDEBUG +  if (PredSU->NumSuccsLeft == 0) { +    dbgs() << "*** Scheduling failed! ***\n"; +    dumpNode(*PredSU); +    dbgs() << " has been released too many times!\n"; +    llvm_unreachable(nullptr); +  } +#endif +  // SU->BotReadyCycle was set to CurrCycle when it was scheduled. However, +  // CurrCycle may have advanced since then. +  if (PredSU->BotReadyCycle < SU->BotReadyCycle + PredEdge->getLatency()) +    PredSU->BotReadyCycle = SU->BotReadyCycle + PredEdge->getLatency(); + +  --PredSU->NumSuccsLeft; +  if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) +    SchedImpl->releaseBottomNode(PredSU); +} + +/// releasePredecessors - Call releasePred on each of SU's predecessors. +void ScheduleDAGMI::releasePredecessors(SUnit *SU) { +  for (SDep &Pred : SU->Preds) +    releasePred(SU, &Pred); +} + +void ScheduleDAGMI::startBlock(MachineBasicBlock *bb) { +  ScheduleDAGInstrs::startBlock(bb); +  SchedImpl->enterMBB(bb); +} + +void ScheduleDAGMI::finishBlock() { +  SchedImpl->leaveMBB(); +  ScheduleDAGInstrs::finishBlock(); +} + +/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after +/// crossing a scheduling boundary. [begin, end) includes all instructions in +/// the region, including the boundary itself and single-instruction regions +/// that don't get scheduled. +void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb, +                                     MachineBasicBlock::iterator begin, +                                     MachineBasicBlock::iterator end, +                                     unsigned regioninstrs) +{ +  ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs); + +  SchedImpl->initPolicy(begin, end, regioninstrs); +} + +/// This is normally called from the main scheduler loop but may also be invoked +/// by the scheduling strategy to perform additional code motion. +void ScheduleDAGMI::moveInstruction( +  MachineInstr *MI, MachineBasicBlock::iterator InsertPos) { +  // Advance RegionBegin if the first instruction moves down. +  if (&*RegionBegin == MI) +    ++RegionBegin; + +  // Update the instruction stream. +  BB->splice(InsertPos, BB, MI); + +  // Update LiveIntervals +  if (LIS) +    LIS->handleMove(*MI, /*UpdateFlags=*/true); + +  // Recede RegionBegin if an instruction moves above the first. +  if (RegionBegin == InsertPos) +    RegionBegin = MI; +} + +bool ScheduleDAGMI::checkSchedLimit() { +#ifndef NDEBUG +  if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) { +    CurrentTop = CurrentBottom; +    return false; +  } +  ++NumInstrsScheduled; +#endif +  return true; +} + +/// Per-region scheduling driver, called back from +/// MachineScheduler::runOnMachineFunction. This is a simplified driver that +/// does not consider liveness or register pressure. It is useful for PostRA +/// scheduling and potentially other custom schedulers. +void ScheduleDAGMI::schedule() { +  LLVM_DEBUG(dbgs() << "ScheduleDAGMI::schedule starting\n"); +  LLVM_DEBUG(SchedImpl->dumpPolicy()); + +  // Build the DAG. +  buildSchedGraph(AA); + +  postprocessDAG(); + +  SmallVector<SUnit*, 8> TopRoots, BotRoots; +  findRootsAndBiasEdges(TopRoots, BotRoots); + +  LLVM_DEBUG(dump()); +  if (PrintDAGs) dump(); +  if (ViewMISchedDAGs) viewGraph(); + +  // Initialize the strategy before modifying the DAG. +  // This may initialize a DFSResult to be used for queue priority. +  SchedImpl->initialize(this); + +  // Initialize ready queues now that the DAG and priority data are finalized. +  initQueues(TopRoots, BotRoots); + +  bool IsTopNode = false; +  while (true) { +    LLVM_DEBUG(dbgs() << "** ScheduleDAGMI::schedule picking next node\n"); +    SUnit *SU = SchedImpl->pickNode(IsTopNode); +    if (!SU) break; + +    assert(!SU->isScheduled && "Node already scheduled"); +    if (!checkSchedLimit()) +      break; + +    MachineInstr *MI = SU->getInstr(); +    if (IsTopNode) { +      assert(SU->isTopReady() && "node still has unscheduled dependencies"); +      if (&*CurrentTop == MI) +        CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom); +      else +        moveInstruction(MI, CurrentTop); +    } else { +      assert(SU->isBottomReady() && "node still has unscheduled dependencies"); +      MachineBasicBlock::iterator priorII = +        priorNonDebug(CurrentBottom, CurrentTop); +      if (&*priorII == MI) +        CurrentBottom = priorII; +      else { +        if (&*CurrentTop == MI) +          CurrentTop = nextIfDebug(++CurrentTop, priorII); +        moveInstruction(MI, CurrentBottom); +        CurrentBottom = MI; +      } +    } +    // Notify the scheduling strategy before updating the DAG. +    // This sets the scheduled node's ReadyCycle to CurrCycle. When updateQueues +    // runs, it can then use the accurate ReadyCycle time to determine whether +    // newly released nodes can move to the readyQ. +    SchedImpl->schedNode(SU, IsTopNode); + +    updateQueues(SU, IsTopNode); +  } +  assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); + +  placeDebugValues(); + +  LLVM_DEBUG({ +    dbgs() << "*** Final schedule for " +           << printMBBReference(*begin()->getParent()) << " ***\n"; +    dumpSchedule(); +    dbgs() << '\n'; +  }); +} + +/// Apply each ScheduleDAGMutation step in order. +void ScheduleDAGMI::postprocessDAG() { +  for (auto &m : Mutations) +    m->apply(this); +} + +void ScheduleDAGMI:: +findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots, +                      SmallVectorImpl<SUnit*> &BotRoots) { +  for (SUnit &SU : SUnits) { +    assert(!SU.isBoundaryNode() && "Boundary node should not be in SUnits"); + +    // Order predecessors so DFSResult follows the critical path. +    SU.biasCriticalPath(); + +    // A SUnit is ready to top schedule if it has no predecessors. +    if (!SU.NumPredsLeft) +      TopRoots.push_back(&SU); +    // A SUnit is ready to bottom schedule if it has no successors. +    if (!SU.NumSuccsLeft) +      BotRoots.push_back(&SU); +  } +  ExitSU.biasCriticalPath(); +} + +/// Identify DAG roots and setup scheduler queues. +void ScheduleDAGMI::initQueues(ArrayRef<SUnit*> TopRoots, +                               ArrayRef<SUnit*> BotRoots) { +  NextClusterSucc = nullptr; +  NextClusterPred = nullptr; + +  // Release all DAG roots for scheduling, not including EntrySU/ExitSU. +  // +  // Nodes with unreleased weak edges can still be roots. +  // Release top roots in forward order. +  for (SUnit *SU : TopRoots) +    SchedImpl->releaseTopNode(SU); + +  // Release bottom roots in reverse order so the higher priority nodes appear +  // first. This is more natural and slightly more efficient. +  for (SmallVectorImpl<SUnit*>::const_reverse_iterator +         I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) { +    SchedImpl->releaseBottomNode(*I); +  } + +  releaseSuccessors(&EntrySU); +  releasePredecessors(&ExitSU); + +  SchedImpl->registerRoots(); + +  // Advance past initial DebugValues. +  CurrentTop = nextIfDebug(RegionBegin, RegionEnd); +  CurrentBottom = RegionEnd; +} + +/// Update scheduler queues after scheduling an instruction. +void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) { +  // Release dependent instructions for scheduling. +  if (IsTopNode) +    releaseSuccessors(SU); +  else +    releasePredecessors(SU); + +  SU->isScheduled = true; +} + +/// Reinsert any remaining debug_values, just like the PostRA scheduler. +void ScheduleDAGMI::placeDebugValues() { +  // If first instruction was a DBG_VALUE then put it back. +  if (FirstDbgValue) { +    BB->splice(RegionBegin, BB, FirstDbgValue); +    RegionBegin = FirstDbgValue; +  } + +  for (std::vector<std::pair<MachineInstr *, MachineInstr *>>::iterator +         DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { +    std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI); +    MachineInstr *DbgValue = P.first; +    MachineBasicBlock::iterator OrigPrevMI = P.second; +    if (&*RegionBegin == DbgValue) +      ++RegionBegin; +    BB->splice(++OrigPrevMI, BB, DbgValue); +    if (OrigPrevMI == std::prev(RegionEnd)) +      RegionEnd = DbgValue; +  } +  DbgValues.clear(); +  FirstDbgValue = nullptr; +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD void ScheduleDAGMI::dumpSchedule() const { +  for (MachineBasicBlock::iterator MI = begin(), ME = end(); MI != ME; ++MI) { +    if (SUnit *SU = getSUnit(&(*MI))) +      dumpNode(*SU); +    else +      dbgs() << "Missing SUnit\n"; +  } +} +#endif + +//===----------------------------------------------------------------------===// +// ScheduleDAGMILive - Base class for MachineInstr scheduling with LiveIntervals +// preservation. +//===----------------------------------------------------------------------===// + +ScheduleDAGMILive::~ScheduleDAGMILive() { +  delete DFSResult; +} + +void ScheduleDAGMILive::collectVRegUses(SUnit &SU) { +  const MachineInstr &MI = *SU.getInstr(); +  for (const MachineOperand &MO : MI.operands()) { +    if (!MO.isReg()) +      continue; +    if (!MO.readsReg()) +      continue; +    if (TrackLaneMasks && !MO.isUse()) +      continue; + +    Register Reg = MO.getReg(); +    if (!Register::isVirtualRegister(Reg)) +      continue; + +    // Ignore re-defs. +    if (TrackLaneMasks) { +      bool FoundDef = false; +      for (const MachineOperand &MO2 : MI.operands()) { +        if (MO2.isReg() && MO2.isDef() && MO2.getReg() == Reg && !MO2.isDead()) { +          FoundDef = true; +          break; +        } +      } +      if (FoundDef) +        continue; +    } + +    // Record this local VReg use. +    VReg2SUnitMultiMap::iterator UI = VRegUses.find(Reg); +    for (; UI != VRegUses.end(); ++UI) { +      if (UI->SU == &SU) +        break; +    } +    if (UI == VRegUses.end()) +      VRegUses.insert(VReg2SUnit(Reg, LaneBitmask::getNone(), &SU)); +  } +} + +/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after +/// crossing a scheduling boundary. [begin, end) includes all instructions in +/// the region, including the boundary itself and single-instruction regions +/// that don't get scheduled. +void ScheduleDAGMILive::enterRegion(MachineBasicBlock *bb, +                                MachineBasicBlock::iterator begin, +                                MachineBasicBlock::iterator end, +                                unsigned regioninstrs) +{ +  // ScheduleDAGMI initializes SchedImpl's per-region policy. +  ScheduleDAGMI::enterRegion(bb, begin, end, regioninstrs); + +  // For convenience remember the end of the liveness region. +  LiveRegionEnd = (RegionEnd == bb->end()) ? RegionEnd : std::next(RegionEnd); + +  SUPressureDiffs.clear(); + +  ShouldTrackPressure = SchedImpl->shouldTrackPressure(); +  ShouldTrackLaneMasks = SchedImpl->shouldTrackLaneMasks(); + +  assert((!ShouldTrackLaneMasks || ShouldTrackPressure) && +         "ShouldTrackLaneMasks requires ShouldTrackPressure"); +} + +// Setup the register pressure trackers for the top scheduled and bottom +// scheduled regions. +void ScheduleDAGMILive::initRegPressure() { +  VRegUses.clear(); +  VRegUses.setUniverse(MRI.getNumVirtRegs()); +  for (SUnit &SU : SUnits) +    collectVRegUses(SU); + +  TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin, +                    ShouldTrackLaneMasks, false); +  BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd, +                    ShouldTrackLaneMasks, false); + +  // Close the RPTracker to finalize live ins. +  RPTracker.closeRegion(); + +  LLVM_DEBUG(RPTracker.dump()); + +  // Initialize the live ins and live outs. +  TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs); +  BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs); + +  // Close one end of the tracker so we can call +  // getMaxUpward/DownwardPressureDelta before advancing across any +  // instructions. This converts currently live regs into live ins/outs. +  TopRPTracker.closeTop(); +  BotRPTracker.closeBottom(); + +  BotRPTracker.initLiveThru(RPTracker); +  if (!BotRPTracker.getLiveThru().empty()) { +    TopRPTracker.initLiveThru(BotRPTracker.getLiveThru()); +    LLVM_DEBUG(dbgs() << "Live Thru: "; +               dumpRegSetPressure(BotRPTracker.getLiveThru(), TRI)); +  }; + +  // For each live out vreg reduce the pressure change associated with other +  // uses of the same vreg below the live-out reaching def. +  updatePressureDiffs(RPTracker.getPressure().LiveOutRegs); + +  // Account for liveness generated by the region boundary. +  if (LiveRegionEnd != RegionEnd) { +    SmallVector<RegisterMaskPair, 8> LiveUses; +    BotRPTracker.recede(&LiveUses); +    updatePressureDiffs(LiveUses); +  } + +  LLVM_DEBUG(dbgs() << "Top Pressure:\n"; +             dumpRegSetPressure(TopRPTracker.getRegSetPressureAtPos(), TRI); +             dbgs() << "Bottom Pressure:\n"; +             dumpRegSetPressure(BotRPTracker.getRegSetPressureAtPos(), TRI);); + +  assert((BotRPTracker.getPos() == RegionEnd || +          (RegionEnd->isDebugInstr() && +           BotRPTracker.getPos() == priorNonDebug(RegionEnd, RegionBegin))) && +         "Can't find the region bottom"); + +  // Cache the list of excess pressure sets in this region. This will also track +  // the max pressure in the scheduled code for these sets. +  RegionCriticalPSets.clear(); +  const std::vector<unsigned> &RegionPressure = +    RPTracker.getPressure().MaxSetPressure; +  for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) { +    unsigned Limit = RegClassInfo->getRegPressureSetLimit(i); +    if (RegionPressure[i] > Limit) { +      LLVM_DEBUG(dbgs() << TRI->getRegPressureSetName(i) << " Limit " << Limit +                        << " Actual " << RegionPressure[i] << "\n"); +      RegionCriticalPSets.push_back(PressureChange(i)); +    } +  } +  LLVM_DEBUG(dbgs() << "Excess PSets: "; +             for (const PressureChange &RCPS +                  : RegionCriticalPSets) dbgs() +             << TRI->getRegPressureSetName(RCPS.getPSet()) << " "; +             dbgs() << "\n"); +} + +void ScheduleDAGMILive:: +updateScheduledPressure(const SUnit *SU, +                        const std::vector<unsigned> &NewMaxPressure) { +  const PressureDiff &PDiff = getPressureDiff(SU); +  unsigned CritIdx = 0, CritEnd = RegionCriticalPSets.size(); +  for (const PressureChange &PC : PDiff) { +    if (!PC.isValid()) +      break; +    unsigned ID = PC.getPSet(); +    while (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() < ID) +      ++CritIdx; +    if (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() == ID) { +      if ((int)NewMaxPressure[ID] > RegionCriticalPSets[CritIdx].getUnitInc() +          && NewMaxPressure[ID] <= (unsigned)std::numeric_limits<int16_t>::max()) +        RegionCriticalPSets[CritIdx].setUnitInc(NewMaxPressure[ID]); +    } +    unsigned Limit = RegClassInfo->getRegPressureSetLimit(ID); +    if (NewMaxPressure[ID] >= Limit - 2) { +      LLVM_DEBUG(dbgs() << "  " << TRI->getRegPressureSetName(ID) << ": " +                        << NewMaxPressure[ID] +                        << ((NewMaxPressure[ID] > Limit) ? " > " : " <= ") +                        << Limit << "(+ " << BotRPTracker.getLiveThru()[ID] +                        << " livethru)\n"); +    } +  } +} + +/// Update the PressureDiff array for liveness after scheduling this +/// instruction. +void ScheduleDAGMILive::updatePressureDiffs( +    ArrayRef<RegisterMaskPair> LiveUses) { +  for (const RegisterMaskPair &P : LiveUses) {      Register Reg = P.RegUnit; -    /// FIXME: Currently assuming single-use physregs.  -    if (!Register::isVirtualRegister(Reg))  -      continue;  -  -    if (ShouldTrackLaneMasks) {  -      // If the register has just become live then other uses won't change  -      // this fact anymore => decrement pressure.  -      // If the register has just become dead then other uses make it come  -      // back to life => increment pressure.  -      bool Decrement = P.LaneMask.any();  -  -      for (const VReg2SUnit &V2SU  -           : make_range(VRegUses.find(Reg), VRegUses.end())) {  -        SUnit &SU = *V2SU.SU;  -        if (SU.isScheduled || &SU == &ExitSU)  -          continue;  -  -        PressureDiff &PDiff = getPressureDiff(&SU);  -        PDiff.addPressureChange(Reg, Decrement, &MRI);  -        LLVM_DEBUG(dbgs() << "  UpdateRegP: SU(" << SU.NodeNum << ") "  -                          << printReg(Reg, TRI) << ':'  -                          << PrintLaneMask(P.LaneMask) << ' ' << *SU.getInstr();  -                   dbgs() << "              to "; PDiff.dump(*TRI););  -      }  -    } else {  -      assert(P.LaneMask.any());  -      LLVM_DEBUG(dbgs() << "  LiveReg: " << printVRegOrUnit(Reg, TRI) << "\n");  -      // This may be called before CurrentBottom has been initialized. However,  -      // BotRPTracker must have a valid position. We want the value live into the  -      // instruction or live out of the block, so ask for the previous  -      // instruction's live-out.  -      const LiveInterval &LI = LIS->getInterval(Reg);  -      VNInfo *VNI;  -      MachineBasicBlock::const_iterator I =  -        nextIfDebug(BotRPTracker.getPos(), BB->end());  -      if (I == BB->end())  -        VNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB));  -      else {  -        LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(*I));  -        VNI = LRQ.valueIn();  -      }  -      // RegisterPressureTracker guarantees that readsReg is true for LiveUses.  -      assert(VNI && "No live value at use.");  -      for (const VReg2SUnit &V2SU  -           : make_range(VRegUses.find(Reg), VRegUses.end())) {  -        SUnit *SU = V2SU.SU;  -        // If this use comes before the reaching def, it cannot be a last use,  -        // so decrease its pressure change.  -        if (!SU->isScheduled && SU != &ExitSU) {  -          LiveQueryResult LRQ =  -              LI.Query(LIS->getInstructionIndex(*SU->getInstr()));  -          if (LRQ.valueIn() == VNI) {  -            PressureDiff &PDiff = getPressureDiff(SU);  -            PDiff.addPressureChange(Reg, true, &MRI);  -            LLVM_DEBUG(dbgs() << "  UpdateRegP: SU(" << SU->NodeNum << ") "  -                              << *SU->getInstr();  -                       dbgs() << "              to "; PDiff.dump(*TRI););  -          }  -        }  -      }  -    }  -  }  -}  -  -void ScheduleDAGMILive::dump() const {  -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)  -  if (EntrySU.getInstr() != nullptr)  -    dumpNodeAll(EntrySU);  -  for (const SUnit &SU : SUnits) {  -    dumpNodeAll(SU);  -    if (ShouldTrackPressure) {  -      dbgs() << "  Pressure Diff      : ";  -      getPressureDiff(&SU).dump(*TRI);  -    }  -    dbgs() << "  Single Issue       : ";  -    if (SchedModel.mustBeginGroup(SU.getInstr()) &&  -        SchedModel.mustEndGroup(SU.getInstr()))  -      dbgs() << "true;";  -    else  -      dbgs() << "false;";  -    dbgs() << '\n';  -  }  -  if (ExitSU.getInstr() != nullptr)  -    dumpNodeAll(ExitSU);  -#endif  -}  -  -/// schedule - Called back from MachineScheduler::runOnMachineFunction  -/// after setting up the current scheduling region. [RegionBegin, RegionEnd)  -/// only includes instructions that have DAG nodes, not scheduling boundaries.  -///  -/// This is a skeletal driver, with all the functionality pushed into helpers,  -/// so that it can be easily extended by experimental schedulers. Generally,  -/// implementing MachineSchedStrategy should be sufficient to implement a new  -/// scheduling algorithm. However, if a scheduler further subclasses  -/// ScheduleDAGMILive then it will want to override this virtual method in order  -/// to update any specialized state.  -void ScheduleDAGMILive::schedule() {  -  LLVM_DEBUG(dbgs() << "ScheduleDAGMILive::schedule starting\n");  -  LLVM_DEBUG(SchedImpl->dumpPolicy());  -  buildDAGWithRegPressure();  -  -  postprocessDAG();  -  -  SmallVector<SUnit*, 8> TopRoots, BotRoots;  -  findRootsAndBiasEdges(TopRoots, BotRoots);  -  -  // Initialize the strategy before modifying the DAG.  -  // This may initialize a DFSResult to be used for queue priority.  -  SchedImpl->initialize(this);  -  -  LLVM_DEBUG(dump());  -  if (PrintDAGs) dump();  -  if (ViewMISchedDAGs) viewGraph();  -  -  // Initialize ready queues now that the DAG and priority data are finalized.  -  initQueues(TopRoots, BotRoots);  -  -  bool IsTopNode = false;  -  while (true) {  -    LLVM_DEBUG(dbgs() << "** ScheduleDAGMILive::schedule picking next node\n");  -    SUnit *SU = SchedImpl->pickNode(IsTopNode);  -    if (!SU) break;  -  -    assert(!SU->isScheduled && "Node already scheduled");  -    if (!checkSchedLimit())  -      break;  -  -    scheduleMI(SU, IsTopNode);  -  -    if (DFSResult) {  -      unsigned SubtreeID = DFSResult->getSubtreeID(SU);  -      if (!ScheduledTrees.test(SubtreeID)) {  -        ScheduledTrees.set(SubtreeID);  -        DFSResult->scheduleTree(SubtreeID);  -        SchedImpl->scheduleTree(SubtreeID);  -      }  -    }  -  -    // Notify the scheduling strategy after updating the DAG.  -    SchedImpl->schedNode(SU, IsTopNode);  -  -    updateQueues(SU, IsTopNode);  -  }  -  assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");  -  -  placeDebugValues();  -  -  LLVM_DEBUG({  -    dbgs() << "*** Final schedule for "  -           << printMBBReference(*begin()->getParent()) << " ***\n";  -    dumpSchedule();  -    dbgs() << '\n';  -  });  -}  -  -/// Build the DAG and setup three register pressure trackers.  -void ScheduleDAGMILive::buildDAGWithRegPressure() {  -  if (!ShouldTrackPressure) {  -    RPTracker.reset();  -    RegionCriticalPSets.clear();  -    buildSchedGraph(AA);  -    return;  -  }  -  -  // Initialize the register pressure tracker used by buildSchedGraph.  -  RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,  -                 ShouldTrackLaneMasks, /*TrackUntiedDefs=*/true);  -  -  // Account for liveness generate by the region boundary.  -  if (LiveRegionEnd != RegionEnd)  -    RPTracker.recede();  -  -  // Build the DAG, and compute current register pressure.  -  buildSchedGraph(AA, &RPTracker, &SUPressureDiffs, LIS, ShouldTrackLaneMasks);  -  -  // Initialize top/bottom trackers after computing region pressure.  -  initRegPressure();  -}  -  -void ScheduleDAGMILive::computeDFSResult() {  -  if (!DFSResult)  -    DFSResult = new SchedDFSResult(/*BottomU*/true, MinSubtreeSize);  -  DFSResult->clear();  -  ScheduledTrees.clear();  -  DFSResult->resize(SUnits.size());  -  DFSResult->compute(SUnits);  -  ScheduledTrees.resize(DFSResult->getNumSubtrees());  -}  -  -/// Compute the max cyclic critical path through the DAG. The scheduling DAG  -/// only provides the critical path for single block loops. To handle loops that  -/// span blocks, we could use the vreg path latencies provided by  -/// MachineTraceMetrics instead. However, MachineTraceMetrics is not currently  -/// available for use in the scheduler.  -///  -/// The cyclic path estimation identifies a def-use pair that crosses the back  -/// edge and considers the depth and height of the nodes. For example, consider  -/// the following instruction sequence where each instruction has unit latency  +    /// FIXME: Currently assuming single-use physregs. +    if (!Register::isVirtualRegister(Reg)) +      continue; + +    if (ShouldTrackLaneMasks) { +      // If the register has just become live then other uses won't change +      // this fact anymore => decrement pressure. +      // If the register has just become dead then other uses make it come +      // back to life => increment pressure. +      bool Decrement = P.LaneMask.any(); + +      for (const VReg2SUnit &V2SU +           : make_range(VRegUses.find(Reg), VRegUses.end())) { +        SUnit &SU = *V2SU.SU; +        if (SU.isScheduled || &SU == &ExitSU) +          continue; + +        PressureDiff &PDiff = getPressureDiff(&SU); +        PDiff.addPressureChange(Reg, Decrement, &MRI); +        LLVM_DEBUG(dbgs() << "  UpdateRegP: SU(" << SU.NodeNum << ") " +                          << printReg(Reg, TRI) << ':' +                          << PrintLaneMask(P.LaneMask) << ' ' << *SU.getInstr(); +                   dbgs() << "              to "; PDiff.dump(*TRI);); +      } +    } else { +      assert(P.LaneMask.any()); +      LLVM_DEBUG(dbgs() << "  LiveReg: " << printVRegOrUnit(Reg, TRI) << "\n"); +      // This may be called before CurrentBottom has been initialized. However, +      // BotRPTracker must have a valid position. We want the value live into the +      // instruction or live out of the block, so ask for the previous +      // instruction's live-out. +      const LiveInterval &LI = LIS->getInterval(Reg); +      VNInfo *VNI; +      MachineBasicBlock::const_iterator I = +        nextIfDebug(BotRPTracker.getPos(), BB->end()); +      if (I == BB->end()) +        VNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB)); +      else { +        LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(*I)); +        VNI = LRQ.valueIn(); +      } +      // RegisterPressureTracker guarantees that readsReg is true for LiveUses. +      assert(VNI && "No live value at use."); +      for (const VReg2SUnit &V2SU +           : make_range(VRegUses.find(Reg), VRegUses.end())) { +        SUnit *SU = V2SU.SU; +        // If this use comes before the reaching def, it cannot be a last use, +        // so decrease its pressure change. +        if (!SU->isScheduled && SU != &ExitSU) { +          LiveQueryResult LRQ = +              LI.Query(LIS->getInstructionIndex(*SU->getInstr())); +          if (LRQ.valueIn() == VNI) { +            PressureDiff &PDiff = getPressureDiff(SU); +            PDiff.addPressureChange(Reg, true, &MRI); +            LLVM_DEBUG(dbgs() << "  UpdateRegP: SU(" << SU->NodeNum << ") " +                              << *SU->getInstr(); +                       dbgs() << "              to "; PDiff.dump(*TRI);); +          } +        } +      } +    } +  } +} + +void ScheduleDAGMILive::dump() const { +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +  if (EntrySU.getInstr() != nullptr) +    dumpNodeAll(EntrySU); +  for (const SUnit &SU : SUnits) { +    dumpNodeAll(SU); +    if (ShouldTrackPressure) { +      dbgs() << "  Pressure Diff      : "; +      getPressureDiff(&SU).dump(*TRI); +    } +    dbgs() << "  Single Issue       : "; +    if (SchedModel.mustBeginGroup(SU.getInstr()) && +        SchedModel.mustEndGroup(SU.getInstr())) +      dbgs() << "true;"; +    else +      dbgs() << "false;"; +    dbgs() << '\n'; +  } +  if (ExitSU.getInstr() != nullptr) +    dumpNodeAll(ExitSU); +#endif +} + +/// schedule - Called back from MachineScheduler::runOnMachineFunction +/// after setting up the current scheduling region. [RegionBegin, RegionEnd) +/// only includes instructions that have DAG nodes, not scheduling boundaries. +/// +/// This is a skeletal driver, with all the functionality pushed into helpers, +/// so that it can be easily extended by experimental schedulers. Generally, +/// implementing MachineSchedStrategy should be sufficient to implement a new +/// scheduling algorithm. However, if a scheduler further subclasses +/// ScheduleDAGMILive then it will want to override this virtual method in order +/// to update any specialized state. +void ScheduleDAGMILive::schedule() { +  LLVM_DEBUG(dbgs() << "ScheduleDAGMILive::schedule starting\n"); +  LLVM_DEBUG(SchedImpl->dumpPolicy()); +  buildDAGWithRegPressure(); + +  postprocessDAG(); + +  SmallVector<SUnit*, 8> TopRoots, BotRoots; +  findRootsAndBiasEdges(TopRoots, BotRoots); + +  // Initialize the strategy before modifying the DAG. +  // This may initialize a DFSResult to be used for queue priority. +  SchedImpl->initialize(this); + +  LLVM_DEBUG(dump()); +  if (PrintDAGs) dump(); +  if (ViewMISchedDAGs) viewGraph(); + +  // Initialize ready queues now that the DAG and priority data are finalized. +  initQueues(TopRoots, BotRoots); + +  bool IsTopNode = false; +  while (true) { +    LLVM_DEBUG(dbgs() << "** ScheduleDAGMILive::schedule picking next node\n"); +    SUnit *SU = SchedImpl->pickNode(IsTopNode); +    if (!SU) break; + +    assert(!SU->isScheduled && "Node already scheduled"); +    if (!checkSchedLimit()) +      break; + +    scheduleMI(SU, IsTopNode); + +    if (DFSResult) { +      unsigned SubtreeID = DFSResult->getSubtreeID(SU); +      if (!ScheduledTrees.test(SubtreeID)) { +        ScheduledTrees.set(SubtreeID); +        DFSResult->scheduleTree(SubtreeID); +        SchedImpl->scheduleTree(SubtreeID); +      } +    } + +    // Notify the scheduling strategy after updating the DAG. +    SchedImpl->schedNode(SU, IsTopNode); + +    updateQueues(SU, IsTopNode); +  } +  assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); + +  placeDebugValues(); + +  LLVM_DEBUG({ +    dbgs() << "*** Final schedule for " +           << printMBBReference(*begin()->getParent()) << " ***\n"; +    dumpSchedule(); +    dbgs() << '\n'; +  }); +} + +/// Build the DAG and setup three register pressure trackers. +void ScheduleDAGMILive::buildDAGWithRegPressure() { +  if (!ShouldTrackPressure) { +    RPTracker.reset(); +    RegionCriticalPSets.clear(); +    buildSchedGraph(AA); +    return; +  } + +  // Initialize the register pressure tracker used by buildSchedGraph. +  RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd, +                 ShouldTrackLaneMasks, /*TrackUntiedDefs=*/true); + +  // Account for liveness generate by the region boundary. +  if (LiveRegionEnd != RegionEnd) +    RPTracker.recede(); + +  // Build the DAG, and compute current register pressure. +  buildSchedGraph(AA, &RPTracker, &SUPressureDiffs, LIS, ShouldTrackLaneMasks); + +  // Initialize top/bottom trackers after computing region pressure. +  initRegPressure(); +} + +void ScheduleDAGMILive::computeDFSResult() { +  if (!DFSResult) +    DFSResult = new SchedDFSResult(/*BottomU*/true, MinSubtreeSize); +  DFSResult->clear(); +  ScheduledTrees.clear(); +  DFSResult->resize(SUnits.size()); +  DFSResult->compute(SUnits); +  ScheduledTrees.resize(DFSResult->getNumSubtrees()); +} + +/// Compute the max cyclic critical path through the DAG. The scheduling DAG +/// only provides the critical path for single block loops. To handle loops that +/// span blocks, we could use the vreg path latencies provided by +/// MachineTraceMetrics instead. However, MachineTraceMetrics is not currently +/// available for use in the scheduler. +/// +/// The cyclic path estimation identifies a def-use pair that crosses the back +/// edge and considers the depth and height of the nodes. For example, consider +/// the following instruction sequence where each instruction has unit latency  /// and defines an eponymous virtual register: -///  -/// a->b(a,c)->c(b)->d(c)->exit  -///  -/// The cyclic critical path is a two cycles: b->c->b  -/// The acyclic critical path is four cycles: a->b->c->d->exit  -/// LiveOutHeight = height(c) = len(c->d->exit) = 2  -/// LiveOutDepth = depth(c) + 1 = len(a->b->c) + 1 = 3  -/// LiveInHeight = height(b) + 1 = len(b->c->d->exit) + 1 = 4  -/// LiveInDepth = depth(b) = len(a->b) = 1  -///  -/// LiveOutDepth - LiveInDepth = 3 - 1 = 2  -/// LiveInHeight - LiveOutHeight = 4 - 2 = 2  -/// CyclicCriticalPath = min(2, 2) = 2  -///  -/// This could be relevant to PostRA scheduling, but is currently implemented  -/// assuming LiveIntervals.  -unsigned ScheduleDAGMILive::computeCyclicCriticalPath() {  -  // This only applies to single block loop.  -  if (!BB->isSuccessor(BB))  -    return 0;  -  -  unsigned MaxCyclicLatency = 0;  -  // Visit each live out vreg def to find def/use pairs that cross iterations.  -  for (const RegisterMaskPair &P : RPTracker.getPressure().LiveOutRegs) {  +/// +/// a->b(a,c)->c(b)->d(c)->exit +/// +/// The cyclic critical path is a two cycles: b->c->b +/// The acyclic critical path is four cycles: a->b->c->d->exit +/// LiveOutHeight = height(c) = len(c->d->exit) = 2 +/// LiveOutDepth = depth(c) + 1 = len(a->b->c) + 1 = 3 +/// LiveInHeight = height(b) + 1 = len(b->c->d->exit) + 1 = 4 +/// LiveInDepth = depth(b) = len(a->b) = 1 +/// +/// LiveOutDepth - LiveInDepth = 3 - 1 = 2 +/// LiveInHeight - LiveOutHeight = 4 - 2 = 2 +/// CyclicCriticalPath = min(2, 2) = 2 +/// +/// This could be relevant to PostRA scheduling, but is currently implemented +/// assuming LiveIntervals. +unsigned ScheduleDAGMILive::computeCyclicCriticalPath() { +  // This only applies to single block loop. +  if (!BB->isSuccessor(BB)) +    return 0; + +  unsigned MaxCyclicLatency = 0; +  // Visit each live out vreg def to find def/use pairs that cross iterations. +  for (const RegisterMaskPair &P : RPTracker.getPressure().LiveOutRegs) {      Register Reg = P.RegUnit; -    if (!Register::isVirtualRegister(Reg))  -      continue;  -    const LiveInterval &LI = LIS->getInterval(Reg);  -    const VNInfo *DefVNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB));  -    if (!DefVNI)  -      continue;  -  -    MachineInstr *DefMI = LIS->getInstructionFromIndex(DefVNI->def);  -    const SUnit *DefSU = getSUnit(DefMI);  -    if (!DefSU)  -      continue;  -  -    unsigned LiveOutHeight = DefSU->getHeight();  -    unsigned LiveOutDepth = DefSU->getDepth() + DefSU->Latency;  -    // Visit all local users of the vreg def.  -    for (const VReg2SUnit &V2SU  -         : make_range(VRegUses.find(Reg), VRegUses.end())) {  -      SUnit *SU = V2SU.SU;  -      if (SU == &ExitSU)  -        continue;  -  -      // Only consider uses of the phi.  -      LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(*SU->getInstr()));  -      if (!LRQ.valueIn()->isPHIDef())  -        continue;  -  -      // Assume that a path spanning two iterations is a cycle, which could  -      // overestimate in strange cases. This allows cyclic latency to be  -      // estimated as the minimum slack of the vreg's depth or height.  -      unsigned CyclicLatency = 0;  -      if (LiveOutDepth > SU->getDepth())  -        CyclicLatency = LiveOutDepth - SU->getDepth();  -  -      unsigned LiveInHeight = SU->getHeight() + DefSU->Latency;  -      if (LiveInHeight > LiveOutHeight) {  -        if (LiveInHeight - LiveOutHeight < CyclicLatency)  -          CyclicLatency = LiveInHeight - LiveOutHeight;  -      } else  -        CyclicLatency = 0;  -  -      LLVM_DEBUG(dbgs() << "Cyclic Path: SU(" << DefSU->NodeNum << ") -> SU("  -                        << SU->NodeNum << ") = " << CyclicLatency << "c\n");  -      if (CyclicLatency > MaxCyclicLatency)  -        MaxCyclicLatency = CyclicLatency;  -    }  -  }  -  LLVM_DEBUG(dbgs() << "Cyclic Critical Path: " << MaxCyclicLatency << "c\n");  -  return MaxCyclicLatency;  -}  -  -/// Release ExitSU predecessors and setup scheduler queues. Re-position  -/// the Top RP tracker in case the region beginning has changed.  -void ScheduleDAGMILive::initQueues(ArrayRef<SUnit*> TopRoots,  -                                   ArrayRef<SUnit*> BotRoots) {  -  ScheduleDAGMI::initQueues(TopRoots, BotRoots);  -  if (ShouldTrackPressure) {  -    assert(TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker");  -    TopRPTracker.setPos(CurrentTop);  -  }  -}  -  -/// Move an instruction and update register pressure.  -void ScheduleDAGMILive::scheduleMI(SUnit *SU, bool IsTopNode) {  -  // Move the instruction to its new location in the instruction stream.  -  MachineInstr *MI = SU->getInstr();  -  -  if (IsTopNode) {  -    assert(SU->isTopReady() && "node still has unscheduled dependencies");  -    if (&*CurrentTop == MI)  -      CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);  -    else {  -      moveInstruction(MI, CurrentTop);  -      TopRPTracker.setPos(MI);  -    }  -  -    if (ShouldTrackPressure) {  -      // Update top scheduled pressure.  -      RegisterOperands RegOpers;  -      RegOpers.collect(*MI, *TRI, MRI, ShouldTrackLaneMasks, false);  -      if (ShouldTrackLaneMasks) {  -        // Adjust liveness and add missing dead+read-undef flags.  -        SlotIndex SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();  -        RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);  -      } else {  -        // Adjust for missing dead-def flags.  -        RegOpers.detectDeadDefs(*MI, *LIS);  -      }  -  -      TopRPTracker.advance(RegOpers);  -      assert(TopRPTracker.getPos() == CurrentTop && "out of sync");  -      LLVM_DEBUG(dbgs() << "Top Pressure:\n"; dumpRegSetPressure(  -                     TopRPTracker.getRegSetPressureAtPos(), TRI););  -  -      updateScheduledPressure(SU, TopRPTracker.getPressure().MaxSetPressure);  -    }  -  } else {  -    assert(SU->isBottomReady() && "node still has unscheduled dependencies");  -    MachineBasicBlock::iterator priorII =  -      priorNonDebug(CurrentBottom, CurrentTop);  -    if (&*priorII == MI)  -      CurrentBottom = priorII;  -    else {  -      if (&*CurrentTop == MI) {  -        CurrentTop = nextIfDebug(++CurrentTop, priorII);  -        TopRPTracker.setPos(CurrentTop);  -      }  -      moveInstruction(MI, CurrentBottom);  -      CurrentBottom = MI;  -      BotRPTracker.setPos(CurrentBottom);  -    }  -    if (ShouldTrackPressure) {  -      RegisterOperands RegOpers;  -      RegOpers.collect(*MI, *TRI, MRI, ShouldTrackLaneMasks, false);  -      if (ShouldTrackLaneMasks) {  -        // Adjust liveness and add missing dead+read-undef flags.  -        SlotIndex SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();  -        RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);  -      } else {  -        // Adjust for missing dead-def flags.  -        RegOpers.detectDeadDefs(*MI, *LIS);  -      }  -  -      if (BotRPTracker.getPos() != CurrentBottom)  -        BotRPTracker.recedeSkipDebugValues();  -      SmallVector<RegisterMaskPair, 8> LiveUses;  -      BotRPTracker.recede(RegOpers, &LiveUses);  -      assert(BotRPTracker.getPos() == CurrentBottom && "out of sync");  -      LLVM_DEBUG(dbgs() << "Bottom Pressure:\n"; dumpRegSetPressure(  -                     BotRPTracker.getRegSetPressureAtPos(), TRI););  -  -      updateScheduledPressure(SU, BotRPTracker.getPressure().MaxSetPressure);  -      updatePressureDiffs(LiveUses);  -    }  -  }  -}  -  -//===----------------------------------------------------------------------===//  -// BaseMemOpClusterMutation - DAG post-processing to cluster loads or stores.  -//===----------------------------------------------------------------------===//  -  -namespace {  -  -/// Post-process the DAG to create cluster edges between neighboring  -/// loads or between neighboring stores.  -class BaseMemOpClusterMutation : public ScheduleDAGMutation {  -  struct MemOpInfo {  -    SUnit *SU;  -    SmallVector<const MachineOperand *, 4> BaseOps;  -    int64_t Offset;  -    unsigned Width;  -  -    MemOpInfo(SUnit *SU, ArrayRef<const MachineOperand *> BaseOps,  -              int64_t Offset, unsigned Width)  -        : SU(SU), BaseOps(BaseOps.begin(), BaseOps.end()), Offset(Offset),  -          Width(Width) {}  -  -    static bool Compare(const MachineOperand *const &A,  -                        const MachineOperand *const &B) {  -      if (A->getType() != B->getType())  -        return A->getType() < B->getType();  -      if (A->isReg())  -        return A->getReg() < B->getReg();  -      if (A->isFI()) {  -        const MachineFunction &MF = *A->getParent()->getParent()->getParent();  -        const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();  -        bool StackGrowsDown = TFI.getStackGrowthDirection() ==  -                              TargetFrameLowering::StackGrowsDown;  -        return StackGrowsDown ? A->getIndex() > B->getIndex()  -                              : A->getIndex() < B->getIndex();  -      }  -  -      llvm_unreachable("MemOpClusterMutation only supports register or frame "  -                       "index bases.");  -    }  -  -    bool operator<(const MemOpInfo &RHS) const {  -      // FIXME: Don't compare everything twice. Maybe use C++20 three way  -      // comparison instead when it's available.  -      if (std::lexicographical_compare(BaseOps.begin(), BaseOps.end(),  -                                       RHS.BaseOps.begin(), RHS.BaseOps.end(),  -                                       Compare))  -        return true;  -      if (std::lexicographical_compare(RHS.BaseOps.begin(), RHS.BaseOps.end(),  -                                       BaseOps.begin(), BaseOps.end(), Compare))  -        return false;  -      if (Offset != RHS.Offset)  -        return Offset < RHS.Offset;  -      return SU->NodeNum < RHS.SU->NodeNum;  -    }  -  };  -  -  const TargetInstrInfo *TII;  -  const TargetRegisterInfo *TRI;  -  bool IsLoad;  -  -public:  -  BaseMemOpClusterMutation(const TargetInstrInfo *tii,  -                           const TargetRegisterInfo *tri, bool IsLoad)  -      : TII(tii), TRI(tri), IsLoad(IsLoad) {}  -  -  void apply(ScheduleDAGInstrs *DAGInstrs) override;  -  -protected:  +    if (!Register::isVirtualRegister(Reg)) +      continue; +    const LiveInterval &LI = LIS->getInterval(Reg); +    const VNInfo *DefVNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB)); +    if (!DefVNI) +      continue; + +    MachineInstr *DefMI = LIS->getInstructionFromIndex(DefVNI->def); +    const SUnit *DefSU = getSUnit(DefMI); +    if (!DefSU) +      continue; + +    unsigned LiveOutHeight = DefSU->getHeight(); +    unsigned LiveOutDepth = DefSU->getDepth() + DefSU->Latency; +    // Visit all local users of the vreg def. +    for (const VReg2SUnit &V2SU +         : make_range(VRegUses.find(Reg), VRegUses.end())) { +      SUnit *SU = V2SU.SU; +      if (SU == &ExitSU) +        continue; + +      // Only consider uses of the phi. +      LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(*SU->getInstr())); +      if (!LRQ.valueIn()->isPHIDef()) +        continue; + +      // Assume that a path spanning two iterations is a cycle, which could +      // overestimate in strange cases. This allows cyclic latency to be +      // estimated as the minimum slack of the vreg's depth or height. +      unsigned CyclicLatency = 0; +      if (LiveOutDepth > SU->getDepth()) +        CyclicLatency = LiveOutDepth - SU->getDepth(); + +      unsigned LiveInHeight = SU->getHeight() + DefSU->Latency; +      if (LiveInHeight > LiveOutHeight) { +        if (LiveInHeight - LiveOutHeight < CyclicLatency) +          CyclicLatency = LiveInHeight - LiveOutHeight; +      } else +        CyclicLatency = 0; + +      LLVM_DEBUG(dbgs() << "Cyclic Path: SU(" << DefSU->NodeNum << ") -> SU(" +                        << SU->NodeNum << ") = " << CyclicLatency << "c\n"); +      if (CyclicLatency > MaxCyclicLatency) +        MaxCyclicLatency = CyclicLatency; +    } +  } +  LLVM_DEBUG(dbgs() << "Cyclic Critical Path: " << MaxCyclicLatency << "c\n"); +  return MaxCyclicLatency; +} + +/// Release ExitSU predecessors and setup scheduler queues. Re-position +/// the Top RP tracker in case the region beginning has changed. +void ScheduleDAGMILive::initQueues(ArrayRef<SUnit*> TopRoots, +                                   ArrayRef<SUnit*> BotRoots) { +  ScheduleDAGMI::initQueues(TopRoots, BotRoots); +  if (ShouldTrackPressure) { +    assert(TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker"); +    TopRPTracker.setPos(CurrentTop); +  } +} + +/// Move an instruction and update register pressure. +void ScheduleDAGMILive::scheduleMI(SUnit *SU, bool IsTopNode) { +  // Move the instruction to its new location in the instruction stream. +  MachineInstr *MI = SU->getInstr(); + +  if (IsTopNode) { +    assert(SU->isTopReady() && "node still has unscheduled dependencies"); +    if (&*CurrentTop == MI) +      CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom); +    else { +      moveInstruction(MI, CurrentTop); +      TopRPTracker.setPos(MI); +    } + +    if (ShouldTrackPressure) { +      // Update top scheduled pressure. +      RegisterOperands RegOpers; +      RegOpers.collect(*MI, *TRI, MRI, ShouldTrackLaneMasks, false); +      if (ShouldTrackLaneMasks) { +        // Adjust liveness and add missing dead+read-undef flags. +        SlotIndex SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot(); +        RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI); +      } else { +        // Adjust for missing dead-def flags. +        RegOpers.detectDeadDefs(*MI, *LIS); +      } + +      TopRPTracker.advance(RegOpers); +      assert(TopRPTracker.getPos() == CurrentTop && "out of sync"); +      LLVM_DEBUG(dbgs() << "Top Pressure:\n"; dumpRegSetPressure( +                     TopRPTracker.getRegSetPressureAtPos(), TRI);); + +      updateScheduledPressure(SU, TopRPTracker.getPressure().MaxSetPressure); +    } +  } else { +    assert(SU->isBottomReady() && "node still has unscheduled dependencies"); +    MachineBasicBlock::iterator priorII = +      priorNonDebug(CurrentBottom, CurrentTop); +    if (&*priorII == MI) +      CurrentBottom = priorII; +    else { +      if (&*CurrentTop == MI) { +        CurrentTop = nextIfDebug(++CurrentTop, priorII); +        TopRPTracker.setPos(CurrentTop); +      } +      moveInstruction(MI, CurrentBottom); +      CurrentBottom = MI; +      BotRPTracker.setPos(CurrentBottom); +    } +    if (ShouldTrackPressure) { +      RegisterOperands RegOpers; +      RegOpers.collect(*MI, *TRI, MRI, ShouldTrackLaneMasks, false); +      if (ShouldTrackLaneMasks) { +        // Adjust liveness and add missing dead+read-undef flags. +        SlotIndex SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot(); +        RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI); +      } else { +        // Adjust for missing dead-def flags. +        RegOpers.detectDeadDefs(*MI, *LIS); +      } + +      if (BotRPTracker.getPos() != CurrentBottom) +        BotRPTracker.recedeSkipDebugValues(); +      SmallVector<RegisterMaskPair, 8> LiveUses; +      BotRPTracker.recede(RegOpers, &LiveUses); +      assert(BotRPTracker.getPos() == CurrentBottom && "out of sync"); +      LLVM_DEBUG(dbgs() << "Bottom Pressure:\n"; dumpRegSetPressure( +                     BotRPTracker.getRegSetPressureAtPos(), TRI);); + +      updateScheduledPressure(SU, BotRPTracker.getPressure().MaxSetPressure); +      updatePressureDiffs(LiveUses); +    } +  } +} + +//===----------------------------------------------------------------------===// +// BaseMemOpClusterMutation - DAG post-processing to cluster loads or stores. +//===----------------------------------------------------------------------===// + +namespace { + +/// Post-process the DAG to create cluster edges between neighboring +/// loads or between neighboring stores. +class BaseMemOpClusterMutation : public ScheduleDAGMutation { +  struct MemOpInfo { +    SUnit *SU; +    SmallVector<const MachineOperand *, 4> BaseOps; +    int64_t Offset; +    unsigned Width; + +    MemOpInfo(SUnit *SU, ArrayRef<const MachineOperand *> BaseOps, +              int64_t Offset, unsigned Width) +        : SU(SU), BaseOps(BaseOps.begin(), BaseOps.end()), Offset(Offset), +          Width(Width) {} + +    static bool Compare(const MachineOperand *const &A, +                        const MachineOperand *const &B) { +      if (A->getType() != B->getType()) +        return A->getType() < B->getType(); +      if (A->isReg()) +        return A->getReg() < B->getReg(); +      if (A->isFI()) { +        const MachineFunction &MF = *A->getParent()->getParent()->getParent(); +        const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering(); +        bool StackGrowsDown = TFI.getStackGrowthDirection() == +                              TargetFrameLowering::StackGrowsDown; +        return StackGrowsDown ? A->getIndex() > B->getIndex() +                              : A->getIndex() < B->getIndex(); +      } + +      llvm_unreachable("MemOpClusterMutation only supports register or frame " +                       "index bases."); +    } + +    bool operator<(const MemOpInfo &RHS) const { +      // FIXME: Don't compare everything twice. Maybe use C++20 three way +      // comparison instead when it's available. +      if (std::lexicographical_compare(BaseOps.begin(), BaseOps.end(), +                                       RHS.BaseOps.begin(), RHS.BaseOps.end(), +                                       Compare)) +        return true; +      if (std::lexicographical_compare(RHS.BaseOps.begin(), RHS.BaseOps.end(), +                                       BaseOps.begin(), BaseOps.end(), Compare)) +        return false; +      if (Offset != RHS.Offset) +        return Offset < RHS.Offset; +      return SU->NodeNum < RHS.SU->NodeNum; +    } +  }; + +  const TargetInstrInfo *TII; +  const TargetRegisterInfo *TRI; +  bool IsLoad; + +public: +  BaseMemOpClusterMutation(const TargetInstrInfo *tii, +                           const TargetRegisterInfo *tri, bool IsLoad) +      : TII(tii), TRI(tri), IsLoad(IsLoad) {} + +  void apply(ScheduleDAGInstrs *DAGInstrs) override; + +protected:    void clusterNeighboringMemOps(ArrayRef<MemOpInfo> MemOps, bool FastCluster,                                  ScheduleDAGInstrs *DAG);    void collectMemOpRecords(std::vector<SUnit> &SUnits,                             SmallVectorImpl<MemOpInfo> &MemOpRecords);    bool groupMemOps(ArrayRef<MemOpInfo> MemOps, ScheduleDAGInstrs *DAG,                     DenseMap<unsigned, SmallVector<MemOpInfo, 32>> &Groups); -};  -  -class StoreClusterMutation : public BaseMemOpClusterMutation {  -public:  -  StoreClusterMutation(const TargetInstrInfo *tii,  -                       const TargetRegisterInfo *tri)  -      : BaseMemOpClusterMutation(tii, tri, false) {}  -};  -  -class LoadClusterMutation : public BaseMemOpClusterMutation {  -public:  -  LoadClusterMutation(const TargetInstrInfo *tii, const TargetRegisterInfo *tri)  -      : BaseMemOpClusterMutation(tii, tri, true) {}  -};  -  -} // end anonymous namespace  -  -namespace llvm {  -  -std::unique_ptr<ScheduleDAGMutation>  -createLoadClusterDAGMutation(const TargetInstrInfo *TII,  -                             const TargetRegisterInfo *TRI) {  -  return EnableMemOpCluster ? std::make_unique<LoadClusterMutation>(TII, TRI)  -                            : nullptr;  -}  -  -std::unique_ptr<ScheduleDAGMutation>  -createStoreClusterDAGMutation(const TargetInstrInfo *TII,  -                              const TargetRegisterInfo *TRI) {  -  return EnableMemOpCluster ? std::make_unique<StoreClusterMutation>(TII, TRI)  -                            : nullptr;  -}  -  -} // end namespace llvm  -  +}; + +class StoreClusterMutation : public BaseMemOpClusterMutation { +public: +  StoreClusterMutation(const TargetInstrInfo *tii, +                       const TargetRegisterInfo *tri) +      : BaseMemOpClusterMutation(tii, tri, false) {} +}; + +class LoadClusterMutation : public BaseMemOpClusterMutation { +public: +  LoadClusterMutation(const TargetInstrInfo *tii, const TargetRegisterInfo *tri) +      : BaseMemOpClusterMutation(tii, tri, true) {} +}; + +} // end anonymous namespace + +namespace llvm { + +std::unique_ptr<ScheduleDAGMutation> +createLoadClusterDAGMutation(const TargetInstrInfo *TII, +                             const TargetRegisterInfo *TRI) { +  return EnableMemOpCluster ? std::make_unique<LoadClusterMutation>(TII, TRI) +                            : nullptr; +} + +std::unique_ptr<ScheduleDAGMutation> +createStoreClusterDAGMutation(const TargetInstrInfo *TII, +                              const TargetRegisterInfo *TRI) { +  return EnableMemOpCluster ? std::make_unique<StoreClusterMutation>(TII, TRI) +                            : nullptr; +} + +} // end namespace llvm +  // Sorting all the loads/stores first, then for each load/store, checking the  // following load/store one by one, until reach the first non-dependent one and  // call target hook to see if they can cluster.  // If FastCluster is enabled, we assume that, all the loads/stores have been  // preprocessed and now, they didn't have dependencies on each other. -void BaseMemOpClusterMutation::clusterNeighboringMemOps(  +void BaseMemOpClusterMutation::clusterNeighboringMemOps(      ArrayRef<MemOpInfo> MemOpRecords, bool FastCluster,      ScheduleDAGInstrs *DAG) {    // Keep track of the current cluster length and bytes for each SUnit.    DenseMap<unsigned, std::pair<unsigned, unsigned>> SUnit2ClusterInfo; -  -  // At this point, `MemOpRecords` array must hold atleast two mem ops. Try to  -  // cluster mem ops collected within `MemOpRecords` array.  -  for (unsigned Idx = 0, End = MemOpRecords.size(); Idx < (End - 1); ++Idx) {  -    // Decision to cluster mem ops is taken based on target dependent logic  -    auto MemOpa = MemOpRecords[Idx];  + +  // At this point, `MemOpRecords` array must hold atleast two mem ops. Try to +  // cluster mem ops collected within `MemOpRecords` array. +  for (unsigned Idx = 0, End = MemOpRecords.size(); Idx < (End - 1); ++Idx) { +    // Decision to cluster mem ops is taken based on target dependent logic +    auto MemOpa = MemOpRecords[Idx];      // Seek for the next load/store to do the cluster.      unsigned NextIdx = Idx + 1; @@ -1613,7 +1613,7 @@ void BaseMemOpClusterMutation::clusterNeighboringMemOps(              !DAG->IsReachable(MemOpa.SU, MemOpRecords[NextIdx].SU))))          break;      if (NextIdx == End) -      continue;  +      continue;      auto MemOpb = MemOpRecords[NextIdx];      unsigned ClusterLength = 2; @@ -1622,25 +1622,25 @@ void BaseMemOpClusterMutation::clusterNeighboringMemOps(        ClusterLength = SUnit2ClusterInfo[MemOpa.SU->NodeNum].first + 1;        CurrentClusterBytes =            SUnit2ClusterInfo[MemOpa.SU->NodeNum].second + MemOpb.Width; -    }  -  +    } +      if (!TII->shouldClusterMemOps(MemOpa.BaseOps, MemOpb.BaseOps, ClusterLength,                                    CurrentClusterBytes))        continue; -    SUnit *SUa = MemOpa.SU;  -    SUnit *SUb = MemOpb.SU;  -    if (SUa->NodeNum > SUb->NodeNum)  -      std::swap(SUa, SUb);  -  -    // FIXME: Is this check really required?  +    SUnit *SUa = MemOpa.SU; +    SUnit *SUb = MemOpb.SU; +    if (SUa->NodeNum > SUb->NodeNum) +      std::swap(SUa, SUb); + +    // FIXME: Is this check really required?      if (!DAG->addEdge(SUb, SDep(SUa, SDep::Cluster))) -      continue;  -  -    LLVM_DEBUG(dbgs() << "Cluster ld/st SU(" << SUa->NodeNum << ") - SU("  -                      << SUb->NodeNum << ")\n");  +      continue; + +    LLVM_DEBUG(dbgs() << "Cluster ld/st SU(" << SUa->NodeNum << ") - SU(" +                      << SUb->NodeNum << ")\n");      ++NumClustered; -  +      if (IsLoad) {        // Copy successor edges from SUa to SUb. Interleaving computation        // dependent on SUa can prevent load combining due to register reuse. @@ -1667,24 +1667,24 @@ void BaseMemOpClusterMutation::clusterNeighboringMemOps(                            << ")\n");          DAG->addEdge(SUa, SDep(Pred.getSUnit(), SDep::Artificial));        } -    }  -  +    } +      SUnit2ClusterInfo[MemOpb.SU->NodeNum] = {ClusterLength,                                               CurrentClusterBytes}; -    LLVM_DEBUG(dbgs() << "  Curr cluster length: " << ClusterLength  -                      << ", Curr cluster bytes: " << CurrentClusterBytes  -                      << "\n");  -  }  -}  -  +    LLVM_DEBUG(dbgs() << "  Curr cluster length: " << ClusterLength +                      << ", Curr cluster bytes: " << CurrentClusterBytes +                      << "\n"); +  } +} +  void BaseMemOpClusterMutation::collectMemOpRecords(      std::vector<SUnit> &SUnits, SmallVectorImpl<MemOpInfo> &MemOpRecords) {    for (auto &SU : SUnits) { -    if ((IsLoad && !SU.getInstr()->mayLoad()) ||  -        (!IsLoad && !SU.getInstr()->mayStore()))  -      continue;  -  +    if ((IsLoad && !SU.getInstr()->mayLoad()) || +        (!IsLoad && !SU.getInstr()->mayStore())) +      continue; +      const MachineInstr &MI = *SU.getInstr();      SmallVector<const MachineOperand *, 4> BaseOps;      int64_t Offset; @@ -1713,7 +1713,7 @@ bool BaseMemOpClusterMutation::groupMemOps(        MemOps.size() * DAG->SUnits.size() / 1000 > FastClusterThreshold;    for (const auto &MemOp : MemOps) { -    unsigned ChainPredID = DAG->SUnits.size();  +    unsigned ChainPredID = DAG->SUnits.size();      if (FastCluster) {        for (const SDep &Pred : MemOp.SU->Preds) {          // We only want to cluster the mem ops that have the same ctrl(non-data) @@ -1726,15 +1726,15 @@ bool BaseMemOpClusterMutation::groupMemOps(            ChainPredID = Pred.getSUnit()->NodeNum;            break;          } -      }  +      }      } else        ChainPredID = 0;      Groups[ChainPredID].push_back(MemOp); -  }  +  }    return FastCluster;  } -  +  /// Callback from DAG postProcessing to create cluster edges for loads/stores.  void BaseMemOpClusterMutation::apply(ScheduleDAGInstrs *DAG) {    // Collect all the clusterable loads/stores @@ -1758,2148 +1758,2148 @@ void BaseMemOpClusterMutation::apply(ScheduleDAGInstrs *DAG) {      // Trying to cluster all the neighboring loads/stores.      clusterNeighboringMemOps(Group.second, FastCluster, DAG);    } -}  -  -//===----------------------------------------------------------------------===//  -// CopyConstrain - DAG post-processing to encourage copy elimination.  -//===----------------------------------------------------------------------===//  -  -namespace {  -  -/// Post-process the DAG to create weak edges from all uses of a copy to  -/// the one use that defines the copy's source vreg, most likely an induction  -/// variable increment.  -class CopyConstrain : public ScheduleDAGMutation {  -  // Transient state.  -  SlotIndex RegionBeginIdx;  -  -  // RegionEndIdx is the slot index of the last non-debug instruction in the  -  // scheduling region. So we may have RegionBeginIdx == RegionEndIdx.  -  SlotIndex RegionEndIdx;  -  -public:  -  CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {}  -  -  void apply(ScheduleDAGInstrs *DAGInstrs) override;  -  -protected:  -  void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG);  -};  -  -} // end anonymous namespace  -  -namespace llvm {  -  -std::unique_ptr<ScheduleDAGMutation>  -createCopyConstrainDAGMutation(const TargetInstrInfo *TII,  -                               const TargetRegisterInfo *TRI) {  -  return std::make_unique<CopyConstrain>(TII, TRI);  -}  -  -} // end namespace llvm  -  -/// constrainLocalCopy handles two possibilities:  -/// 1) Local src:  -/// I0:     = dst  -/// I1: src = ...  -/// I2:     = dst  -/// I3: dst = src (copy)  -/// (create pred->succ edges I0->I1, I2->I1)  -///  -/// 2) Local copy:  -/// I0: dst = src (copy)  -/// I1:     = dst  -/// I2: src = ...  -/// I3:     = dst  -/// (create pred->succ edges I1->I2, I3->I2)  -///  -/// Although the MachineScheduler is currently constrained to single blocks,  -/// this algorithm should handle extended blocks. An EBB is a set of  -/// contiguously numbered blocks such that the previous block in the EBB is  -/// always the single predecessor.  -void CopyConstrain::constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG) {  -  LiveIntervals *LIS = DAG->getLIS();  -  MachineInstr *Copy = CopySU->getInstr();  -  -  // Check for pure vreg copies.  -  const MachineOperand &SrcOp = Copy->getOperand(1);  -  Register SrcReg = SrcOp.getReg();  -  if (!Register::isVirtualRegister(SrcReg) || !SrcOp.readsReg())  -    return;  -  -  const MachineOperand &DstOp = Copy->getOperand(0);  -  Register DstReg = DstOp.getReg();  -  if (!Register::isVirtualRegister(DstReg) || DstOp.isDead())  -    return;  -  -  // Check if either the dest or source is local. If it's live across a back  -  // edge, it's not local. Note that if both vregs are live across the back  -  // edge, we cannot successfully contrain the copy without cyclic scheduling.  -  // If both the copy's source and dest are local live intervals, then we  -  // should treat the dest as the global for the purpose of adding  -  // constraints. This adds edges from source's other uses to the copy.  -  unsigned LocalReg = SrcReg;  -  unsigned GlobalReg = DstReg;  -  LiveInterval *LocalLI = &LIS->getInterval(LocalReg);  -  if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) {  -    LocalReg = DstReg;  -    GlobalReg = SrcReg;  -    LocalLI = &LIS->getInterval(LocalReg);  -    if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx))  -      return;  -  }  -  LiveInterval *GlobalLI = &LIS->getInterval(GlobalReg);  -  -  // Find the global segment after the start of the local LI.  -  LiveInterval::iterator GlobalSegment = GlobalLI->find(LocalLI->beginIndex());  -  // If GlobalLI does not overlap LocalLI->start, then a copy directly feeds a  -  // local live range. We could create edges from other global uses to the local  -  // start, but the coalescer should have already eliminated these cases, so  -  // don't bother dealing with it.  -  if (GlobalSegment == GlobalLI->end())  -    return;  -  -  // If GlobalSegment is killed at the LocalLI->start, the call to find()  -  // returned the next global segment. But if GlobalSegment overlaps with  -  // LocalLI->start, then advance to the next segment. If a hole in GlobalLI  -  // exists in LocalLI's vicinity, GlobalSegment will be the end of the hole.  -  if (GlobalSegment->contains(LocalLI->beginIndex()))  -    ++GlobalSegment;  -  -  if (GlobalSegment == GlobalLI->end())  -    return;  -  -  // Check if GlobalLI contains a hole in the vicinity of LocalLI.  -  if (GlobalSegment != GlobalLI->begin()) {  -    // Two address defs have no hole.  -    if (SlotIndex::isSameInstr(std::prev(GlobalSegment)->end,  -                               GlobalSegment->start)) {  -      return;  -    }  -    // If the prior global segment may be defined by the same two-address  -    // instruction that also defines LocalLI, then can't make a hole here.  -    if (SlotIndex::isSameInstr(std::prev(GlobalSegment)->start,  -                               LocalLI->beginIndex())) {  -      return;  -    }  -    // If GlobalLI has a prior segment, it must be live into the EBB. Otherwise  -    // it would be a disconnected component in the live range.  -    assert(std::prev(GlobalSegment)->start < LocalLI->beginIndex() &&  -           "Disconnected LRG within the scheduling region.");  -  }  -  MachineInstr *GlobalDef = LIS->getInstructionFromIndex(GlobalSegment->start);  -  if (!GlobalDef)  -    return;  -  -  SUnit *GlobalSU = DAG->getSUnit(GlobalDef);  -  if (!GlobalSU)  -    return;  -  -  // GlobalDef is the bottom of the GlobalLI hole. Open the hole by  -  // constraining the uses of the last local def to precede GlobalDef.  -  SmallVector<SUnit*,8> LocalUses;  -  const VNInfo *LastLocalVN = LocalLI->getVNInfoBefore(LocalLI->endIndex());  -  MachineInstr *LastLocalDef = LIS->getInstructionFromIndex(LastLocalVN->def);  -  SUnit *LastLocalSU = DAG->getSUnit(LastLocalDef);  -  for (const SDep &Succ : LastLocalSU->Succs) {  -    if (Succ.getKind() != SDep::Data || Succ.getReg() != LocalReg)  -      continue;  -    if (Succ.getSUnit() == GlobalSU)  -      continue;  -    if (!DAG->canAddEdge(GlobalSU, Succ.getSUnit()))  -      return;  -    LocalUses.push_back(Succ.getSUnit());  -  }  -  // Open the top of the GlobalLI hole by constraining any earlier global uses  -  // to precede the start of LocalLI.  -  SmallVector<SUnit*,8> GlobalUses;  -  MachineInstr *FirstLocalDef =  -    LIS->getInstructionFromIndex(LocalLI->beginIndex());  -  SUnit *FirstLocalSU = DAG->getSUnit(FirstLocalDef);  -  for (const SDep &Pred : GlobalSU->Preds) {  -    if (Pred.getKind() != SDep::Anti || Pred.getReg() != GlobalReg)  -      continue;  -    if (Pred.getSUnit() == FirstLocalSU)  -      continue;  -    if (!DAG->canAddEdge(FirstLocalSU, Pred.getSUnit()))  -      return;  -    GlobalUses.push_back(Pred.getSUnit());  -  }  -  LLVM_DEBUG(dbgs() << "Constraining copy SU(" << CopySU->NodeNum << ")\n");  -  // Add the weak edges.  -  for (SmallVectorImpl<SUnit*>::const_iterator  -         I = LocalUses.begin(), E = LocalUses.end(); I != E; ++I) {  -    LLVM_DEBUG(dbgs() << "  Local use SU(" << (*I)->NodeNum << ") -> SU("  -                      << GlobalSU->NodeNum << ")\n");  -    DAG->addEdge(GlobalSU, SDep(*I, SDep::Weak));  -  }  -  for (SmallVectorImpl<SUnit*>::const_iterator  -         I = GlobalUses.begin(), E = GlobalUses.end(); I != E; ++I) {  -    LLVM_DEBUG(dbgs() << "  Global use SU(" << (*I)->NodeNum << ") -> SU("  -                      << FirstLocalSU->NodeNum << ")\n");  -    DAG->addEdge(FirstLocalSU, SDep(*I, SDep::Weak));  -  }  -}  -  -/// Callback from DAG postProcessing to create weak edges to encourage  -/// copy elimination.  -void CopyConstrain::apply(ScheduleDAGInstrs *DAGInstrs) {  -  ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);  -  assert(DAG->hasVRegLiveness() && "Expect VRegs with LiveIntervals");  -  -  MachineBasicBlock::iterator FirstPos = nextIfDebug(DAG->begin(), DAG->end());  -  if (FirstPos == DAG->end())  -    return;  -  RegionBeginIdx = DAG->getLIS()->getInstructionIndex(*FirstPos);  -  RegionEndIdx = DAG->getLIS()->getInstructionIndex(  -      *priorNonDebug(DAG->end(), DAG->begin()));  -  -  for (SUnit &SU : DAG->SUnits) {  -    if (!SU.getInstr()->isCopy())  -      continue;  -  -    constrainLocalCopy(&SU, static_cast<ScheduleDAGMILive*>(DAG));  -  }  -}  -  -//===----------------------------------------------------------------------===//  -// MachineSchedStrategy helpers used by GenericScheduler, GenericPostScheduler  -// and possibly other custom schedulers.  -//===----------------------------------------------------------------------===//  -  -static const unsigned InvalidCycle = ~0U;  -  -SchedBoundary::~SchedBoundary() { delete HazardRec; }  -  -/// Given a Count of resource usage and a Latency value, return true if a  -/// SchedBoundary becomes resource limited.  -/// If we are checking after scheduling a node, we should return true when  -/// we just reach the resource limit.  -static bool checkResourceLimit(unsigned LFactor, unsigned Count,  -                               unsigned Latency, bool AfterSchedNode) {  -  int ResCntFactor = (int)(Count - (Latency * LFactor));  -  if (AfterSchedNode)  -    return ResCntFactor >= (int)LFactor;  -  else  -    return ResCntFactor > (int)LFactor;  -}  -  -void SchedBoundary::reset() {  -  // A new HazardRec is created for each DAG and owned by SchedBoundary.  -  // Destroying and reconstructing it is very expensive though. So keep  -  // invalid, placeholder HazardRecs.  -  if (HazardRec && HazardRec->isEnabled()) {  -    delete HazardRec;  -    HazardRec = nullptr;  -  }  -  Available.clear();  -  Pending.clear();  -  CheckPending = false;  -  CurrCycle = 0;  -  CurrMOps = 0;  -  MinReadyCycle = std::numeric_limits<unsigned>::max();  -  ExpectedLatency = 0;  -  DependentLatency = 0;  -  RetiredMOps = 0;  -  MaxExecutedResCount = 0;  -  ZoneCritResIdx = 0;  -  IsResourceLimited = false;  -  ReservedCycles.clear();  -  ReservedCyclesIndex.clear();  -#ifndef NDEBUG  -  // Track the maximum number of stall cycles that could arise either from the  -  // latency of a DAG edge or the number of cycles that a processor resource is  -  // reserved (SchedBoundary::ReservedCycles).  -  MaxObservedStall = 0;  -#endif  -  // Reserve a zero-count for invalid CritResIdx.  -  ExecutedResCounts.resize(1);  -  assert(!ExecutedResCounts[0] && "nonzero count for bad resource");  -}  -  -void SchedRemainder::  -init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) {  -  reset();  -  if (!SchedModel->hasInstrSchedModel())  -    return;  -  RemainingCounts.resize(SchedModel->getNumProcResourceKinds());  -  for (SUnit &SU : DAG->SUnits) {  -    const MCSchedClassDesc *SC = DAG->getSchedClass(&SU);  -    RemIssueCount += SchedModel->getNumMicroOps(SU.getInstr(), SC)  -      * SchedModel->getMicroOpFactor();  -    for (TargetSchedModel::ProcResIter  -           PI = SchedModel->getWriteProcResBegin(SC),  -           PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {  -      unsigned PIdx = PI->ProcResourceIdx;  -      unsigned Factor = SchedModel->getResourceFactor(PIdx);  -      RemainingCounts[PIdx] += (Factor * PI->Cycles);  -    }  -  }  -}  -  -void SchedBoundary::  -init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) {  -  reset();  -  DAG = dag;  -  SchedModel = smodel;  -  Rem = rem;  -  if (SchedModel->hasInstrSchedModel()) {  -    unsigned ResourceCount = SchedModel->getNumProcResourceKinds();  -    ReservedCyclesIndex.resize(ResourceCount);  -    ExecutedResCounts.resize(ResourceCount);  -    unsigned NumUnits = 0;  -  -    for (unsigned i = 0; i < ResourceCount; ++i) {  -      ReservedCyclesIndex[i] = NumUnits;  -      NumUnits += SchedModel->getProcResource(i)->NumUnits;  -    }  -  -    ReservedCycles.resize(NumUnits, InvalidCycle);  -  }  -}  -  -/// Compute the stall cycles based on this SUnit's ready time. Heuristics treat  -/// these "soft stalls" differently than the hard stall cycles based on CPU  -/// resources and computed by checkHazard(). A fully in-order model  -/// (MicroOpBufferSize==0) will not make use of this since instructions are not  -/// available for scheduling until they are ready. However, a weaker in-order  -/// model may use this for heuristics. For example, if a processor has in-order  -/// behavior when reading certain resources, this may come into play.  -unsigned SchedBoundary::getLatencyStallCycles(SUnit *SU) {  -  if (!SU->isUnbuffered)  -    return 0;  -  -  unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);  -  if (ReadyCycle > CurrCycle)  -    return ReadyCycle - CurrCycle;  -  return 0;  -}  -  -/// Compute the next cycle at which the given processor resource unit  -/// can be scheduled.  -unsigned SchedBoundary::getNextResourceCycleByInstance(unsigned InstanceIdx,  -                                                       unsigned Cycles) {  -  unsigned NextUnreserved = ReservedCycles[InstanceIdx];  -  // If this resource has never been used, always return cycle zero.  -  if (NextUnreserved == InvalidCycle)  -    return 0;  -  // For bottom-up scheduling add the cycles needed for the current operation.  -  if (!isTop())  -    NextUnreserved += Cycles;  -  return NextUnreserved;  -}  -  -/// Compute the next cycle at which the given processor resource can be  -/// scheduled.  Returns the next cycle and the index of the processor resource  -/// instance in the reserved cycles vector.  -std::pair<unsigned, unsigned>  -SchedBoundary::getNextResourceCycle(unsigned PIdx, unsigned Cycles) {  -  unsigned MinNextUnreserved = InvalidCycle;  -  unsigned InstanceIdx = 0;  -  unsigned StartIndex = ReservedCyclesIndex[PIdx];  -  unsigned NumberOfInstances = SchedModel->getProcResource(PIdx)->NumUnits;  -  assert(NumberOfInstances > 0 &&  -         "Cannot have zero instances of a ProcResource");  -  -  for (unsigned I = StartIndex, End = StartIndex + NumberOfInstances; I < End;  -       ++I) {  -    unsigned NextUnreserved = getNextResourceCycleByInstance(I, Cycles);  -    if (MinNextUnreserved > NextUnreserved) {  -      InstanceIdx = I;  -      MinNextUnreserved = NextUnreserved;  -    }  -  }  -  return std::make_pair(MinNextUnreserved, InstanceIdx);  -}  -  -/// Does this SU have a hazard within the current instruction group.  -///  -/// The scheduler supports two modes of hazard recognition. The first is the  -/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that  -/// supports highly complicated in-order reservation tables  -/// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.  -///  -/// The second is a streamlined mechanism that checks for hazards based on  -/// simple counters that the scheduler itself maintains. It explicitly checks  -/// for instruction dispatch limitations, including the number of micro-ops that  -/// can dispatch per cycle.  -///  -/// TODO: Also check whether the SU must start a new group.  -bool SchedBoundary::checkHazard(SUnit *SU) {  -  if (HazardRec->isEnabled()  -      && HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard) {  -    return true;  -  }  -  -  unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());  -  if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) {  -    LLVM_DEBUG(dbgs() << "  SU(" << SU->NodeNum << ") uops="  -                      << SchedModel->getNumMicroOps(SU->getInstr()) << '\n');  -    return true;  -  }  -  -  if (CurrMOps > 0 &&  -      ((isTop() && SchedModel->mustBeginGroup(SU->getInstr())) ||  -       (!isTop() && SchedModel->mustEndGroup(SU->getInstr())))) {  -    LLVM_DEBUG(dbgs() << "  hazard: SU(" << SU->NodeNum << ") must "  -                      << (isTop() ? "begin" : "end") << " group\n");  -    return true;  -  }  -  -  if (SchedModel->hasInstrSchedModel() && SU->hasReservedResource) {  -    const MCSchedClassDesc *SC = DAG->getSchedClass(SU);  -    for (const MCWriteProcResEntry &PE :  -          make_range(SchedModel->getWriteProcResBegin(SC),  -                     SchedModel->getWriteProcResEnd(SC))) {  -      unsigned ResIdx = PE.ProcResourceIdx;  -      unsigned Cycles = PE.Cycles;  -      unsigned NRCycle, InstanceIdx;  -      std::tie(NRCycle, InstanceIdx) = getNextResourceCycle(ResIdx, Cycles);  -      if (NRCycle > CurrCycle) {  -#ifndef NDEBUG  -        MaxObservedStall = std::max(Cycles, MaxObservedStall);  -#endif  -        LLVM_DEBUG(dbgs() << "  SU(" << SU->NodeNum << ") "  -                          << SchedModel->getResourceName(ResIdx)  -                          << '[' << InstanceIdx - ReservedCyclesIndex[ResIdx]  << ']'  -                          << "=" << NRCycle << "c\n");  -        return true;  -      }  -    }  -  }  -  return false;  -}  -  -// Find the unscheduled node in ReadySUs with the highest latency.  -unsigned SchedBoundary::  -findMaxLatency(ArrayRef<SUnit*> ReadySUs) {  -  SUnit *LateSU = nullptr;  -  unsigned RemLatency = 0;  -  for (SUnit *SU : ReadySUs) {  -    unsigned L = getUnscheduledLatency(SU);  -    if (L > RemLatency) {  -      RemLatency = L;  -      LateSU = SU;  -    }  -  }  -  if (LateSU) {  -    LLVM_DEBUG(dbgs() << Available.getName() << " RemLatency SU("  -                      << LateSU->NodeNum << ") " << RemLatency << "c\n");  -  }  -  return RemLatency;  -}  -  -// Count resources in this zone and the remaining unscheduled  -// instruction. Return the max count, scaled. Set OtherCritIdx to the critical  -// resource index, or zero if the zone is issue limited.  -unsigned SchedBoundary::  -getOtherResourceCount(unsigned &OtherCritIdx) {  -  OtherCritIdx = 0;  -  if (!SchedModel->hasInstrSchedModel())  -    return 0;  -  -  unsigned OtherCritCount = Rem->RemIssueCount  -    + (RetiredMOps * SchedModel->getMicroOpFactor());  -  LLVM_DEBUG(dbgs() << "  " << Available.getName() << " + Remain MOps: "  -                    << OtherCritCount / SchedModel->getMicroOpFactor() << '\n');  -  for (unsigned PIdx = 1, PEnd = SchedModel->getNumProcResourceKinds();  -       PIdx != PEnd; ++PIdx) {  -    unsigned OtherCount = getResourceCount(PIdx) + Rem->RemainingCounts[PIdx];  -    if (OtherCount > OtherCritCount) {  -      OtherCritCount = OtherCount;  -      OtherCritIdx = PIdx;  -    }  -  }  -  if (OtherCritIdx) {  -    LLVM_DEBUG(  -        dbgs() << "  " << Available.getName() << " + Remain CritRes: "  -               << OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx)  -               << " " << SchedModel->getResourceName(OtherCritIdx) << "\n");  -  }  -  return OtherCritCount;  -}  -  -void SchedBoundary::releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue,  -                                unsigned Idx) {  -  assert(SU->getInstr() && "Scheduled SUnit must have instr");  -  -#ifndef NDEBUG  -  // ReadyCycle was been bumped up to the CurrCycle when this node was  -  // scheduled, but CurrCycle may have been eagerly advanced immediately after  -  // scheduling, so may now be greater than ReadyCycle.  -  if (ReadyCycle > CurrCycle)  -    MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall);  -#endif  -  -  if (ReadyCycle < MinReadyCycle)  -    MinReadyCycle = ReadyCycle;  -  -  // Check for interlocks first. For the purpose of other heuristics, an  -  // instruction that cannot issue appears as if it's not in the ReadyQueue.  -  bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;  -  bool HazardDetected = (!IsBuffered && ReadyCycle > CurrCycle) ||  -                        checkHazard(SU) || (Available.size() >= ReadyListLimit);  -  -  if (!HazardDetected) {  -    Available.push(SU);  -  -    if (InPQueue)  -      Pending.remove(Pending.begin() + Idx);  -    return;  -  }  -  -  if (!InPQueue)  -    Pending.push(SU);  -}  -  -/// Move the boundary of scheduled code by one cycle.  -void SchedBoundary::bumpCycle(unsigned NextCycle) {  -  if (SchedModel->getMicroOpBufferSize() == 0) {  -    assert(MinReadyCycle < std::numeric_limits<unsigned>::max() &&  -           "MinReadyCycle uninitialized");  -    if (MinReadyCycle > NextCycle)  -      NextCycle = MinReadyCycle;  -  }  -  // Update the current micro-ops, which will issue in the next cycle.  -  unsigned DecMOps = SchedModel->getIssueWidth() * (NextCycle - CurrCycle);  -  CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps;  -  -  // Decrement DependentLatency based on the next cycle.  -  if ((NextCycle - CurrCycle) > DependentLatency)  -    DependentLatency = 0;  -  else  -    DependentLatency -= (NextCycle - CurrCycle);  -  -  if (!HazardRec->isEnabled()) {  -    // Bypass HazardRec virtual calls.  -    CurrCycle = NextCycle;  -  } else {  -    // Bypass getHazardType calls in case of long latency.  -    for (; CurrCycle != NextCycle; ++CurrCycle) {  -      if (isTop())  -        HazardRec->AdvanceCycle();  -      else  -        HazardRec->RecedeCycle();  -    }  -  }  -  CheckPending = true;  -  IsResourceLimited =  -      checkResourceLimit(SchedModel->getLatencyFactor(), getCriticalCount(),  -                         getScheduledLatency(), true);  -  -  LLVM_DEBUG(dbgs() << "Cycle: " << CurrCycle << ' ' << Available.getName()  -                    << '\n');  -}  -  -void SchedBoundary::incExecutedResources(unsigned PIdx, unsigned Count) {  -  ExecutedResCounts[PIdx] += Count;  -  if (ExecutedResCounts[PIdx] > MaxExecutedResCount)  -    MaxExecutedResCount = ExecutedResCounts[PIdx];  -}  -  -/// Add the given processor resource to this scheduled zone.  -///  -/// \param Cycles indicates the number of consecutive (non-pipelined) cycles  -/// during which this resource is consumed.  -///  -/// \return the next cycle at which the instruction may execute without  -/// oversubscribing resources.  -unsigned SchedBoundary::  -countResource(unsigned PIdx, unsigned Cycles, unsigned NextCycle) {  -  unsigned Factor = SchedModel->getResourceFactor(PIdx);  -  unsigned Count = Factor * Cycles;  -  LLVM_DEBUG(dbgs() << "  " << SchedModel->getResourceName(PIdx) << " +"  -                    << Cycles << "x" << Factor << "u\n");  -  -  // Update Executed resources counts.  -  incExecutedResources(PIdx, Count);  -  assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted");  -  Rem->RemainingCounts[PIdx] -= Count;  -  -  // Check if this resource exceeds the current critical resource. If so, it  -  // becomes the critical resource.  -  if (ZoneCritResIdx != PIdx && (getResourceCount(PIdx) > getCriticalCount())) {  -    ZoneCritResIdx = PIdx;  -    LLVM_DEBUG(dbgs() << "  *** Critical resource "  -                      << SchedModel->getResourceName(PIdx) << ": "  -                      << getResourceCount(PIdx) / SchedModel->getLatencyFactor()  -                      << "c\n");  -  }  -  // For reserved resources, record the highest cycle using the resource.  -  unsigned NextAvailable, InstanceIdx;  -  std::tie(NextAvailable, InstanceIdx) = getNextResourceCycle(PIdx, Cycles);  -  if (NextAvailable > CurrCycle) {  -    LLVM_DEBUG(dbgs() << "  Resource conflict: "  -                      << SchedModel->getResourceName(PIdx)  -                      << '[' << InstanceIdx - ReservedCyclesIndex[PIdx]  << ']'  -                      << " reserved until @" << NextAvailable << "\n");  -  }  -  return NextAvailable;  -}  -  -/// Move the boundary of scheduled code by one SUnit.  -void SchedBoundary::bumpNode(SUnit *SU) {  -  // Update the reservation table.  -  if (HazardRec->isEnabled()) {  -    if (!isTop() && SU->isCall) {  -      // Calls are scheduled with their preceding instructions. For bottom-up  -      // scheduling, clear the pipeline state before emitting.  -      HazardRec->Reset();  -    }  -    HazardRec->EmitInstruction(SU);  -    // Scheduling an instruction may have made pending instructions available.  -    CheckPending = true;  -  }  -  // checkHazard should prevent scheduling multiple instructions per cycle that  -  // exceed the issue width.  -  const MCSchedClassDesc *SC = DAG->getSchedClass(SU);  -  unsigned IncMOps = SchedModel->getNumMicroOps(SU->getInstr());  -  assert(  -      (CurrMOps == 0 || (CurrMOps + IncMOps) <= SchedModel->getIssueWidth()) &&  -      "Cannot schedule this instruction's MicroOps in the current cycle.");  -  -  unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);  -  LLVM_DEBUG(dbgs() << "  Ready @" << ReadyCycle << "c\n");  -  -  unsigned NextCycle = CurrCycle;  -  switch (SchedModel->getMicroOpBufferSize()) {  -  case 0:  -    assert(ReadyCycle <= CurrCycle && "Broken PendingQueue");  -    break;  -  case 1:  -    if (ReadyCycle > NextCycle) {  -      NextCycle = ReadyCycle;  -      LLVM_DEBUG(dbgs() << "  *** Stall until: " << ReadyCycle << "\n");  -    }  -    break;  -  default:  -    // We don't currently model the OOO reorder buffer, so consider all  -    // scheduled MOps to be "retired". We do loosely model in-order resource  -    // latency. If this instruction uses an in-order resource, account for any  -    // likely stall cycles.  -    if (SU->isUnbuffered && ReadyCycle > NextCycle)  -      NextCycle = ReadyCycle;  -    break;  -  }  -  RetiredMOps += IncMOps;  -  -  // Update resource counts and critical resource.  -  if (SchedModel->hasInstrSchedModel()) {  -    unsigned DecRemIssue = IncMOps * SchedModel->getMicroOpFactor();  -    assert(Rem->RemIssueCount >= DecRemIssue && "MOps double counted");  -    Rem->RemIssueCount -= DecRemIssue;  -    if (ZoneCritResIdx) {  -      // Scale scheduled micro-ops for comparing with the critical resource.  -      unsigned ScaledMOps =  -        RetiredMOps * SchedModel->getMicroOpFactor();  -  -      // If scaled micro-ops are now more than the previous critical resource by  -      // a full cycle, then micro-ops issue becomes critical.  -      if ((int)(ScaledMOps - getResourceCount(ZoneCritResIdx))  -          >= (int)SchedModel->getLatencyFactor()) {  -        ZoneCritResIdx = 0;  -        LLVM_DEBUG(dbgs() << "  *** Critical resource NumMicroOps: "  -                          << ScaledMOps / SchedModel->getLatencyFactor()  -                          << "c\n");  -      }  -    }  -    for (TargetSchedModel::ProcResIter  -           PI = SchedModel->getWriteProcResBegin(SC),  -           PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {  -      unsigned RCycle =  -        countResource(PI->ProcResourceIdx, PI->Cycles, NextCycle);  -      if (RCycle > NextCycle)  -        NextCycle = RCycle;  -    }  -    if (SU->hasReservedResource) {  -      // For reserved resources, record the highest cycle using the resource.  -      // For top-down scheduling, this is the cycle in which we schedule this  -      // instruction plus the number of cycles the operations reserves the  -      // resource. For bottom-up is it simply the instruction's cycle.  -      for (TargetSchedModel::ProcResIter  -             PI = SchedModel->getWriteProcResBegin(SC),  -             PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {  -        unsigned PIdx = PI->ProcResourceIdx;  -        if (SchedModel->getProcResource(PIdx)->BufferSize == 0) {  -          unsigned ReservedUntil, InstanceIdx;  -          std::tie(ReservedUntil, InstanceIdx) = getNextResourceCycle(PIdx, 0);  -          if (isTop()) {  -            ReservedCycles[InstanceIdx] =  -                std::max(ReservedUntil, NextCycle + PI->Cycles);  -          } else  -            ReservedCycles[InstanceIdx] = NextCycle;  -        }  -      }  -    }  -  }  -  // Update ExpectedLatency and DependentLatency.  -  unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;  -  unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;  -  if (SU->getDepth() > TopLatency) {  -    TopLatency = SU->getDepth();  -    LLVM_DEBUG(dbgs() << "  " << Available.getName() << " TopLatency SU("  -                      << SU->NodeNum << ") " << TopLatency << "c\n");  -  }  -  if (SU->getHeight() > BotLatency) {  -    BotLatency = SU->getHeight();  -    LLVM_DEBUG(dbgs() << "  " << Available.getName() << " BotLatency SU("  -                      << SU->NodeNum << ") " << BotLatency << "c\n");  -  }  -  // If we stall for any reason, bump the cycle.  -  if (NextCycle > CurrCycle)  -    bumpCycle(NextCycle);  -  else  -    // After updating ZoneCritResIdx and ExpectedLatency, check if we're  -    // resource limited. If a stall occurred, bumpCycle does this.  -    IsResourceLimited =  -        checkResourceLimit(SchedModel->getLatencyFactor(), getCriticalCount(),  -                           getScheduledLatency(), true);  -  -  // Update CurrMOps after calling bumpCycle to handle stalls, since bumpCycle  -  // resets CurrMOps. Loop to handle instructions with more MOps than issue in  -  // one cycle.  Since we commonly reach the max MOps here, opportunistically  -  // bump the cycle to avoid uselessly checking everything in the readyQ.  -  CurrMOps += IncMOps;  -  -  // Bump the cycle count for issue group constraints.  -  // This must be done after NextCycle has been adjust for all other stalls.  -  // Calling bumpCycle(X) will reduce CurrMOps by one issue group and set  -  // currCycle to X.  -  if ((isTop() &&  SchedModel->mustEndGroup(SU->getInstr())) ||  -      (!isTop() && SchedModel->mustBeginGroup(SU->getInstr()))) {  -    LLVM_DEBUG(dbgs() << "  Bump cycle to " << (isTop() ? "end" : "begin")  -                      << " group\n");  -    bumpCycle(++NextCycle);  -  }  -  -  while (CurrMOps >= SchedModel->getIssueWidth()) {  -    LLVM_DEBUG(dbgs() << "  *** Max MOps " << CurrMOps << " at cycle "  -                      << CurrCycle << '\n');  -    bumpCycle(++NextCycle);  -  }  -  LLVM_DEBUG(dumpScheduledState());  -}  -  -/// Release pending ready nodes in to the available queue. This makes them  -/// visible to heuristics.  -void SchedBoundary::releasePending() {  -  // If the available queue is empty, it is safe to reset MinReadyCycle.  -  if (Available.empty())  -    MinReadyCycle = std::numeric_limits<unsigned>::max();  -  -  // Check to see if any of the pending instructions are ready to issue.  If  -  // so, add them to the available queue.  -  for (unsigned I = 0, E = Pending.size(); I < E; ++I) {  -    SUnit *SU = *(Pending.begin() + I);  -    unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;  -  -    if (ReadyCycle < MinReadyCycle)  -      MinReadyCycle = ReadyCycle;  -  -    if (Available.size() >= ReadyListLimit)  -      break;  -  -    releaseNode(SU, ReadyCycle, true, I);  -    if (E != Pending.size()) {  -      --I;  -      --E;  -    }  -  }  -  CheckPending = false;  -}  -  -/// Remove SU from the ready set for this boundary.  -void SchedBoundary::removeReady(SUnit *SU) {  -  if (Available.isInQueue(SU))  -    Available.remove(Available.find(SU));  -  else {  -    assert(Pending.isInQueue(SU) && "bad ready count");  -    Pending.remove(Pending.find(SU));  -  }  -}  -  -/// If this queue only has one ready candidate, return it. As a side effect,  -/// defer any nodes that now hit a hazard, and advance the cycle until at least  -/// one node is ready. If multiple instructions are ready, return NULL.  -SUnit *SchedBoundary::pickOnlyChoice() {  -  if (CheckPending)  -    releasePending();  -  -  // Defer any ready instrs that now have a hazard.  -  for (ReadyQueue::iterator I = Available.begin(); I != Available.end();) {  -    if (checkHazard(*I)) {  -      Pending.push(*I);  -      I = Available.remove(I);  -      continue;  -    }  -    ++I;  -  }  -  for (unsigned i = 0; Available.empty(); ++i) {  -//  FIXME: Re-enable assert once PR20057 is resolved.  -//    assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedStall) &&  -//           "permanent hazard");  -    (void)i;  -    bumpCycle(CurrCycle + 1);  -    releasePending();  -  }  -  -  LLVM_DEBUG(Pending.dump());  -  LLVM_DEBUG(Available.dump());  -  -  if (Available.size() == 1)  -    return *Available.begin();  -  return nullptr;  -}  -  -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)  -// This is useful information to dump after bumpNode.  -// Note that the Queue contents are more useful before pickNodeFromQueue.  -LLVM_DUMP_METHOD void SchedBoundary::dumpScheduledState() const {  -  unsigned ResFactor;  -  unsigned ResCount;  -  if (ZoneCritResIdx) {  -    ResFactor = SchedModel->getResourceFactor(ZoneCritResIdx);  -    ResCount = getResourceCount(ZoneCritResIdx);  -  } else {  -    ResFactor = SchedModel->getMicroOpFactor();  -    ResCount = RetiredMOps * ResFactor;  -  }  -  unsigned LFactor = SchedModel->getLatencyFactor();  -  dbgs() << Available.getName() << " @" << CurrCycle << "c\n"  -         << "  Retired: " << RetiredMOps;  -  dbgs() << "\n  Executed: " << getExecutedCount() / LFactor << "c";  -  dbgs() << "\n  Critical: " << ResCount / LFactor << "c, "  -         << ResCount / ResFactor << " "  -         << SchedModel->getResourceName(ZoneCritResIdx)  -         << "\n  ExpectedLatency: " << ExpectedLatency << "c\n"  -         << (IsResourceLimited ? "  - Resource" : "  - Latency")  -         << " limited.\n";  -}  -#endif  -  -//===----------------------------------------------------------------------===//  -// GenericScheduler - Generic implementation of MachineSchedStrategy.  -//===----------------------------------------------------------------------===//  -  -void GenericSchedulerBase::SchedCandidate::  -initResourceDelta(const ScheduleDAGMI *DAG,  -                  const TargetSchedModel *SchedModel) {  -  if (!Policy.ReduceResIdx && !Policy.DemandResIdx)  -    return;  -  -  const MCSchedClassDesc *SC = DAG->getSchedClass(SU);  -  for (TargetSchedModel::ProcResIter  -         PI = SchedModel->getWriteProcResBegin(SC),  -         PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {  -    if (PI->ProcResourceIdx == Policy.ReduceResIdx)  -      ResDelta.CritResources += PI->Cycles;  -    if (PI->ProcResourceIdx == Policy.DemandResIdx)  -      ResDelta.DemandedResources += PI->Cycles;  -  }  -}  -  -/// Compute remaining latency. We need this both to determine whether the  -/// overall schedule has become latency-limited and whether the instructions  -/// outside this zone are resource or latency limited.  -///  -/// The "dependent" latency is updated incrementally during scheduling as the  -/// max height/depth of scheduled nodes minus the cycles since it was  -/// scheduled:  -///   DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone  -///  -/// The "independent" latency is the max ready queue depth:  -///   ILat = max N.depth for N in Available|Pending  -///  -/// RemainingLatency is the greater of independent and dependent latency.  -///  -/// These computations are expensive, especially in DAGs with many edges, so  -/// only do them if necessary.  -static unsigned computeRemLatency(SchedBoundary &CurrZone) {  -  unsigned RemLatency = CurrZone.getDependentLatency();  -  RemLatency = std::max(RemLatency,  -                        CurrZone.findMaxLatency(CurrZone.Available.elements()));  -  RemLatency = std::max(RemLatency,  -                        CurrZone.findMaxLatency(CurrZone.Pending.elements()));  -  return RemLatency;  -}  -  -/// Returns true if the current cycle plus remaning latency is greater than  -/// the critical path in the scheduling region.  -bool GenericSchedulerBase::shouldReduceLatency(const CandPolicy &Policy,  -                                               SchedBoundary &CurrZone,  -                                               bool ComputeRemLatency,  -                                               unsigned &RemLatency) const {  -  // The current cycle is already greater than the critical path, so we are  -  // already latency limited and don't need to compute the remaining latency.  -  if (CurrZone.getCurrCycle() > Rem.CriticalPath)  -    return true;  -  -  // If we haven't scheduled anything yet, then we aren't latency limited.  -  if (CurrZone.getCurrCycle() == 0)  -    return false;  -  -  if (ComputeRemLatency)  -    RemLatency = computeRemLatency(CurrZone);  -  -  return RemLatency + CurrZone.getCurrCycle() > Rem.CriticalPath;  -}  -  -/// Set the CandPolicy given a scheduling zone given the current resources and  -/// latencies inside and outside the zone.  -void GenericSchedulerBase::setPolicy(CandPolicy &Policy, bool IsPostRA,  -                                     SchedBoundary &CurrZone,  -                                     SchedBoundary *OtherZone) {  -  // Apply preemptive heuristics based on the total latency and resources  -  // inside and outside this zone. Potential stalls should be considered before  -  // following this policy.  -  -  // Compute the critical resource outside the zone.  -  unsigned OtherCritIdx = 0;  -  unsigned OtherCount =  -    OtherZone ? OtherZone->getOtherResourceCount(OtherCritIdx) : 0;  -  -  bool OtherResLimited = false;  -  unsigned RemLatency = 0;  -  bool RemLatencyComputed = false;  -  if (SchedModel->hasInstrSchedModel() && OtherCount != 0) {  -    RemLatency = computeRemLatency(CurrZone);  -    RemLatencyComputed = true;  -    OtherResLimited = checkResourceLimit(SchedModel->getLatencyFactor(),  -                                         OtherCount, RemLatency, false);  -  }  -  -  // Schedule aggressively for latency in PostRA mode. We don't check for  -  // acyclic latency during PostRA, and highly out-of-order processors will  -  // skip PostRA scheduling.  -  if (!OtherResLimited &&  -      (IsPostRA || shouldReduceLatency(Policy, CurrZone, !RemLatencyComputed,  -                                       RemLatency))) {  -    Policy.ReduceLatency |= true;  -    LLVM_DEBUG(dbgs() << "  " << CurrZone.Available.getName()  -                      << " RemainingLatency " << RemLatency << " + "  -                      << CurrZone.getCurrCycle() << "c > CritPath "  -                      << Rem.CriticalPath << "\n");  -  }  -  // If the same resource is limiting inside and outside the zone, do nothing.  -  if (CurrZone.getZoneCritResIdx() == OtherCritIdx)  -    return;  -  -  LLVM_DEBUG(if (CurrZone.isResourceLimited()) {  -    dbgs() << "  " << CurrZone.Available.getName() << " ResourceLimited: "  -           << SchedModel->getResourceName(CurrZone.getZoneCritResIdx()) << "\n";  -  } if (OtherResLimited) dbgs()  -                 << "  RemainingLimit: "  -                 << SchedModel->getResourceName(OtherCritIdx) << "\n";  -             if (!CurrZone.isResourceLimited() && !OtherResLimited) dbgs()  -             << "  Latency limited both directions.\n");  -  -  if (CurrZone.isResourceLimited() && !Policy.ReduceResIdx)  -    Policy.ReduceResIdx = CurrZone.getZoneCritResIdx();  -  -  if (OtherResLimited)  -    Policy.DemandResIdx = OtherCritIdx;  -}  -  -#ifndef NDEBUG  -const char *GenericSchedulerBase::getReasonStr(  -  GenericSchedulerBase::CandReason Reason) {  -  switch (Reason) {  -  case NoCand:         return "NOCAND    ";  -  case Only1:          return "ONLY1     ";  -  case PhysReg:        return "PHYS-REG  ";  -  case RegExcess:      return "REG-EXCESS";  -  case RegCritical:    return "REG-CRIT  ";  -  case Stall:          return "STALL     ";  -  case Cluster:        return "CLUSTER   ";  -  case Weak:           return "WEAK      ";  -  case RegMax:         return "REG-MAX   ";  -  case ResourceReduce: return "RES-REDUCE";  -  case ResourceDemand: return "RES-DEMAND";  -  case TopDepthReduce: return "TOP-DEPTH ";  -  case TopPathReduce:  return "TOP-PATH  ";  -  case BotHeightReduce:return "BOT-HEIGHT";  -  case BotPathReduce:  return "BOT-PATH  ";  -  case NextDefUse:     return "DEF-USE   ";  -  case NodeOrder:      return "ORDER     ";  -  };  -  llvm_unreachable("Unknown reason!");  -}  -  -void GenericSchedulerBase::traceCandidate(const SchedCandidate &Cand) {  -  PressureChange P;  -  unsigned ResIdx = 0;  -  unsigned Latency = 0;  -  switch (Cand.Reason) {  -  default:  -    break;  -  case RegExcess:  -    P = Cand.RPDelta.Excess;  -    break;  -  case RegCritical:  -    P = Cand.RPDelta.CriticalMax;  -    break;  -  case RegMax:  -    P = Cand.RPDelta.CurrentMax;  -    break;  -  case ResourceReduce:  -    ResIdx = Cand.Policy.ReduceResIdx;  -    break;  -  case ResourceDemand:  -    ResIdx = Cand.Policy.DemandResIdx;  -    break;  -  case TopDepthReduce:  -    Latency = Cand.SU->getDepth();  -    break;  -  case TopPathReduce:  -    Latency = Cand.SU->getHeight();  -    break;  -  case BotHeightReduce:  -    Latency = Cand.SU->getHeight();  -    break;  -  case BotPathReduce:  -    Latency = Cand.SU->getDepth();  -    break;  -  }  -  dbgs() << "  Cand SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason);  -  if (P.isValid())  -    dbgs() << " " << TRI->getRegPressureSetName(P.getPSet())  -           << ":" << P.getUnitInc() << " ";  -  else  -    dbgs() << "      ";  -  if (ResIdx)  -    dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " ";  -  else  -    dbgs() << "         ";  -  if (Latency)  -    dbgs() << " " << Latency << " cycles ";  -  else  -    dbgs() << "          ";  -  dbgs() << '\n';  -}  -#endif  -  -namespace llvm {  -/// Return true if this heuristic determines order.  -bool tryLess(int TryVal, int CandVal,  -             GenericSchedulerBase::SchedCandidate &TryCand,  -             GenericSchedulerBase::SchedCandidate &Cand,  -             GenericSchedulerBase::CandReason Reason) {  -  if (TryVal < CandVal) {  -    TryCand.Reason = Reason;  -    return true;  -  }  -  if (TryVal > CandVal) {  -    if (Cand.Reason > Reason)  -      Cand.Reason = Reason;  -    return true;  -  }  -  return false;  -}  -  -bool tryGreater(int TryVal, int CandVal,  -                GenericSchedulerBase::SchedCandidate &TryCand,  -                GenericSchedulerBase::SchedCandidate &Cand,  -                GenericSchedulerBase::CandReason Reason) {  -  if (TryVal > CandVal) {  -    TryCand.Reason = Reason;  -    return true;  -  }  -  if (TryVal < CandVal) {  -    if (Cand.Reason > Reason)  -      Cand.Reason = Reason;  -    return true;  -  }  -  return false;  -}  -  -bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,  -                GenericSchedulerBase::SchedCandidate &Cand,  -                SchedBoundary &Zone) {  -  if (Zone.isTop()) {  +} + +//===----------------------------------------------------------------------===// +// CopyConstrain - DAG post-processing to encourage copy elimination. +//===----------------------------------------------------------------------===// + +namespace { + +/// Post-process the DAG to create weak edges from all uses of a copy to +/// the one use that defines the copy's source vreg, most likely an induction +/// variable increment. +class CopyConstrain : public ScheduleDAGMutation { +  // Transient state. +  SlotIndex RegionBeginIdx; + +  // RegionEndIdx is the slot index of the last non-debug instruction in the +  // scheduling region. So we may have RegionBeginIdx == RegionEndIdx. +  SlotIndex RegionEndIdx; + +public: +  CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {} + +  void apply(ScheduleDAGInstrs *DAGInstrs) override; + +protected: +  void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG); +}; + +} // end anonymous namespace + +namespace llvm { + +std::unique_ptr<ScheduleDAGMutation> +createCopyConstrainDAGMutation(const TargetInstrInfo *TII, +                               const TargetRegisterInfo *TRI) { +  return std::make_unique<CopyConstrain>(TII, TRI); +} + +} // end namespace llvm + +/// constrainLocalCopy handles two possibilities: +/// 1) Local src: +/// I0:     = dst +/// I1: src = ... +/// I2:     = dst +/// I3: dst = src (copy) +/// (create pred->succ edges I0->I1, I2->I1) +/// +/// 2) Local copy: +/// I0: dst = src (copy) +/// I1:     = dst +/// I2: src = ... +/// I3:     = dst +/// (create pred->succ edges I1->I2, I3->I2) +/// +/// Although the MachineScheduler is currently constrained to single blocks, +/// this algorithm should handle extended blocks. An EBB is a set of +/// contiguously numbered blocks such that the previous block in the EBB is +/// always the single predecessor. +void CopyConstrain::constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG) { +  LiveIntervals *LIS = DAG->getLIS(); +  MachineInstr *Copy = CopySU->getInstr(); + +  // Check for pure vreg copies. +  const MachineOperand &SrcOp = Copy->getOperand(1); +  Register SrcReg = SrcOp.getReg(); +  if (!Register::isVirtualRegister(SrcReg) || !SrcOp.readsReg()) +    return; + +  const MachineOperand &DstOp = Copy->getOperand(0); +  Register DstReg = DstOp.getReg(); +  if (!Register::isVirtualRegister(DstReg) || DstOp.isDead()) +    return; + +  // Check if either the dest or source is local. If it's live across a back +  // edge, it's not local. Note that if both vregs are live across the back +  // edge, we cannot successfully contrain the copy without cyclic scheduling. +  // If both the copy's source and dest are local live intervals, then we +  // should treat the dest as the global for the purpose of adding +  // constraints. This adds edges from source's other uses to the copy. +  unsigned LocalReg = SrcReg; +  unsigned GlobalReg = DstReg; +  LiveInterval *LocalLI = &LIS->getInterval(LocalReg); +  if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) { +    LocalReg = DstReg; +    GlobalReg = SrcReg; +    LocalLI = &LIS->getInterval(LocalReg); +    if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) +      return; +  } +  LiveInterval *GlobalLI = &LIS->getInterval(GlobalReg); + +  // Find the global segment after the start of the local LI. +  LiveInterval::iterator GlobalSegment = GlobalLI->find(LocalLI->beginIndex()); +  // If GlobalLI does not overlap LocalLI->start, then a copy directly feeds a +  // local live range. We could create edges from other global uses to the local +  // start, but the coalescer should have already eliminated these cases, so +  // don't bother dealing with it. +  if (GlobalSegment == GlobalLI->end()) +    return; + +  // If GlobalSegment is killed at the LocalLI->start, the call to find() +  // returned the next global segment. But if GlobalSegment overlaps with +  // LocalLI->start, then advance to the next segment. If a hole in GlobalLI +  // exists in LocalLI's vicinity, GlobalSegment will be the end of the hole. +  if (GlobalSegment->contains(LocalLI->beginIndex())) +    ++GlobalSegment; + +  if (GlobalSegment == GlobalLI->end()) +    return; + +  // Check if GlobalLI contains a hole in the vicinity of LocalLI. +  if (GlobalSegment != GlobalLI->begin()) { +    // Two address defs have no hole. +    if (SlotIndex::isSameInstr(std::prev(GlobalSegment)->end, +                               GlobalSegment->start)) { +      return; +    } +    // If the prior global segment may be defined by the same two-address +    // instruction that also defines LocalLI, then can't make a hole here. +    if (SlotIndex::isSameInstr(std::prev(GlobalSegment)->start, +                               LocalLI->beginIndex())) { +      return; +    } +    // If GlobalLI has a prior segment, it must be live into the EBB. Otherwise +    // it would be a disconnected component in the live range. +    assert(std::prev(GlobalSegment)->start < LocalLI->beginIndex() && +           "Disconnected LRG within the scheduling region."); +  } +  MachineInstr *GlobalDef = LIS->getInstructionFromIndex(GlobalSegment->start); +  if (!GlobalDef) +    return; + +  SUnit *GlobalSU = DAG->getSUnit(GlobalDef); +  if (!GlobalSU) +    return; + +  // GlobalDef is the bottom of the GlobalLI hole. Open the hole by +  // constraining the uses of the last local def to precede GlobalDef. +  SmallVector<SUnit*,8> LocalUses; +  const VNInfo *LastLocalVN = LocalLI->getVNInfoBefore(LocalLI->endIndex()); +  MachineInstr *LastLocalDef = LIS->getInstructionFromIndex(LastLocalVN->def); +  SUnit *LastLocalSU = DAG->getSUnit(LastLocalDef); +  for (const SDep &Succ : LastLocalSU->Succs) { +    if (Succ.getKind() != SDep::Data || Succ.getReg() != LocalReg) +      continue; +    if (Succ.getSUnit() == GlobalSU) +      continue; +    if (!DAG->canAddEdge(GlobalSU, Succ.getSUnit())) +      return; +    LocalUses.push_back(Succ.getSUnit()); +  } +  // Open the top of the GlobalLI hole by constraining any earlier global uses +  // to precede the start of LocalLI. +  SmallVector<SUnit*,8> GlobalUses; +  MachineInstr *FirstLocalDef = +    LIS->getInstructionFromIndex(LocalLI->beginIndex()); +  SUnit *FirstLocalSU = DAG->getSUnit(FirstLocalDef); +  for (const SDep &Pred : GlobalSU->Preds) { +    if (Pred.getKind() != SDep::Anti || Pred.getReg() != GlobalReg) +      continue; +    if (Pred.getSUnit() == FirstLocalSU) +      continue; +    if (!DAG->canAddEdge(FirstLocalSU, Pred.getSUnit())) +      return; +    GlobalUses.push_back(Pred.getSUnit()); +  } +  LLVM_DEBUG(dbgs() << "Constraining copy SU(" << CopySU->NodeNum << ")\n"); +  // Add the weak edges. +  for (SmallVectorImpl<SUnit*>::const_iterator +         I = LocalUses.begin(), E = LocalUses.end(); I != E; ++I) { +    LLVM_DEBUG(dbgs() << "  Local use SU(" << (*I)->NodeNum << ") -> SU(" +                      << GlobalSU->NodeNum << ")\n"); +    DAG->addEdge(GlobalSU, SDep(*I, SDep::Weak)); +  } +  for (SmallVectorImpl<SUnit*>::const_iterator +         I = GlobalUses.begin(), E = GlobalUses.end(); I != E; ++I) { +    LLVM_DEBUG(dbgs() << "  Global use SU(" << (*I)->NodeNum << ") -> SU(" +                      << FirstLocalSU->NodeNum << ")\n"); +    DAG->addEdge(FirstLocalSU, SDep(*I, SDep::Weak)); +  } +} + +/// Callback from DAG postProcessing to create weak edges to encourage +/// copy elimination. +void CopyConstrain::apply(ScheduleDAGInstrs *DAGInstrs) { +  ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs); +  assert(DAG->hasVRegLiveness() && "Expect VRegs with LiveIntervals"); + +  MachineBasicBlock::iterator FirstPos = nextIfDebug(DAG->begin(), DAG->end()); +  if (FirstPos == DAG->end()) +    return; +  RegionBeginIdx = DAG->getLIS()->getInstructionIndex(*FirstPos); +  RegionEndIdx = DAG->getLIS()->getInstructionIndex( +      *priorNonDebug(DAG->end(), DAG->begin())); + +  for (SUnit &SU : DAG->SUnits) { +    if (!SU.getInstr()->isCopy()) +      continue; + +    constrainLocalCopy(&SU, static_cast<ScheduleDAGMILive*>(DAG)); +  } +} + +//===----------------------------------------------------------------------===// +// MachineSchedStrategy helpers used by GenericScheduler, GenericPostScheduler +// and possibly other custom schedulers. +//===----------------------------------------------------------------------===// + +static const unsigned InvalidCycle = ~0U; + +SchedBoundary::~SchedBoundary() { delete HazardRec; } + +/// Given a Count of resource usage and a Latency value, return true if a +/// SchedBoundary becomes resource limited. +/// If we are checking after scheduling a node, we should return true when +/// we just reach the resource limit. +static bool checkResourceLimit(unsigned LFactor, unsigned Count, +                               unsigned Latency, bool AfterSchedNode) { +  int ResCntFactor = (int)(Count - (Latency * LFactor)); +  if (AfterSchedNode) +    return ResCntFactor >= (int)LFactor; +  else +    return ResCntFactor > (int)LFactor; +} + +void SchedBoundary::reset() { +  // A new HazardRec is created for each DAG and owned by SchedBoundary. +  // Destroying and reconstructing it is very expensive though. So keep +  // invalid, placeholder HazardRecs. +  if (HazardRec && HazardRec->isEnabled()) { +    delete HazardRec; +    HazardRec = nullptr; +  } +  Available.clear(); +  Pending.clear(); +  CheckPending = false; +  CurrCycle = 0; +  CurrMOps = 0; +  MinReadyCycle = std::numeric_limits<unsigned>::max(); +  ExpectedLatency = 0; +  DependentLatency = 0; +  RetiredMOps = 0; +  MaxExecutedResCount = 0; +  ZoneCritResIdx = 0; +  IsResourceLimited = false; +  ReservedCycles.clear(); +  ReservedCyclesIndex.clear(); +#ifndef NDEBUG +  // Track the maximum number of stall cycles that could arise either from the +  // latency of a DAG edge or the number of cycles that a processor resource is +  // reserved (SchedBoundary::ReservedCycles). +  MaxObservedStall = 0; +#endif +  // Reserve a zero-count for invalid CritResIdx. +  ExecutedResCounts.resize(1); +  assert(!ExecutedResCounts[0] && "nonzero count for bad resource"); +} + +void SchedRemainder:: +init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) { +  reset(); +  if (!SchedModel->hasInstrSchedModel()) +    return; +  RemainingCounts.resize(SchedModel->getNumProcResourceKinds()); +  for (SUnit &SU : DAG->SUnits) { +    const MCSchedClassDesc *SC = DAG->getSchedClass(&SU); +    RemIssueCount += SchedModel->getNumMicroOps(SU.getInstr(), SC) +      * SchedModel->getMicroOpFactor(); +    for (TargetSchedModel::ProcResIter +           PI = SchedModel->getWriteProcResBegin(SC), +           PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { +      unsigned PIdx = PI->ProcResourceIdx; +      unsigned Factor = SchedModel->getResourceFactor(PIdx); +      RemainingCounts[PIdx] += (Factor * PI->Cycles); +    } +  } +} + +void SchedBoundary:: +init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) { +  reset(); +  DAG = dag; +  SchedModel = smodel; +  Rem = rem; +  if (SchedModel->hasInstrSchedModel()) { +    unsigned ResourceCount = SchedModel->getNumProcResourceKinds(); +    ReservedCyclesIndex.resize(ResourceCount); +    ExecutedResCounts.resize(ResourceCount); +    unsigned NumUnits = 0; + +    for (unsigned i = 0; i < ResourceCount; ++i) { +      ReservedCyclesIndex[i] = NumUnits; +      NumUnits += SchedModel->getProcResource(i)->NumUnits; +    } + +    ReservedCycles.resize(NumUnits, InvalidCycle); +  } +} + +/// Compute the stall cycles based on this SUnit's ready time. Heuristics treat +/// these "soft stalls" differently than the hard stall cycles based on CPU +/// resources and computed by checkHazard(). A fully in-order model +/// (MicroOpBufferSize==0) will not make use of this since instructions are not +/// available for scheduling until they are ready. However, a weaker in-order +/// model may use this for heuristics. For example, if a processor has in-order +/// behavior when reading certain resources, this may come into play. +unsigned SchedBoundary::getLatencyStallCycles(SUnit *SU) { +  if (!SU->isUnbuffered) +    return 0; + +  unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle); +  if (ReadyCycle > CurrCycle) +    return ReadyCycle - CurrCycle; +  return 0; +} + +/// Compute the next cycle at which the given processor resource unit +/// can be scheduled. +unsigned SchedBoundary::getNextResourceCycleByInstance(unsigned InstanceIdx, +                                                       unsigned Cycles) { +  unsigned NextUnreserved = ReservedCycles[InstanceIdx]; +  // If this resource has never been used, always return cycle zero. +  if (NextUnreserved == InvalidCycle) +    return 0; +  // For bottom-up scheduling add the cycles needed for the current operation. +  if (!isTop()) +    NextUnreserved += Cycles; +  return NextUnreserved; +} + +/// Compute the next cycle at which the given processor resource can be +/// scheduled.  Returns the next cycle and the index of the processor resource +/// instance in the reserved cycles vector. +std::pair<unsigned, unsigned> +SchedBoundary::getNextResourceCycle(unsigned PIdx, unsigned Cycles) { +  unsigned MinNextUnreserved = InvalidCycle; +  unsigned InstanceIdx = 0; +  unsigned StartIndex = ReservedCyclesIndex[PIdx]; +  unsigned NumberOfInstances = SchedModel->getProcResource(PIdx)->NumUnits; +  assert(NumberOfInstances > 0 && +         "Cannot have zero instances of a ProcResource"); + +  for (unsigned I = StartIndex, End = StartIndex + NumberOfInstances; I < End; +       ++I) { +    unsigned NextUnreserved = getNextResourceCycleByInstance(I, Cycles); +    if (MinNextUnreserved > NextUnreserved) { +      InstanceIdx = I; +      MinNextUnreserved = NextUnreserved; +    } +  } +  return std::make_pair(MinNextUnreserved, InstanceIdx); +} + +/// Does this SU have a hazard within the current instruction group. +/// +/// The scheduler supports two modes of hazard recognition. The first is the +/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that +/// supports highly complicated in-order reservation tables +/// (ScoreboardHazardRecognizer) and arbitrary target-specific logic. +/// +/// The second is a streamlined mechanism that checks for hazards based on +/// simple counters that the scheduler itself maintains. It explicitly checks +/// for instruction dispatch limitations, including the number of micro-ops that +/// can dispatch per cycle. +/// +/// TODO: Also check whether the SU must start a new group. +bool SchedBoundary::checkHazard(SUnit *SU) { +  if (HazardRec->isEnabled() +      && HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard) { +    return true; +  } + +  unsigned uops = SchedModel->getNumMicroOps(SU->getInstr()); +  if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) { +    LLVM_DEBUG(dbgs() << "  SU(" << SU->NodeNum << ") uops=" +                      << SchedModel->getNumMicroOps(SU->getInstr()) << '\n'); +    return true; +  } + +  if (CurrMOps > 0 && +      ((isTop() && SchedModel->mustBeginGroup(SU->getInstr())) || +       (!isTop() && SchedModel->mustEndGroup(SU->getInstr())))) { +    LLVM_DEBUG(dbgs() << "  hazard: SU(" << SU->NodeNum << ") must " +                      << (isTop() ? "begin" : "end") << " group\n"); +    return true; +  } + +  if (SchedModel->hasInstrSchedModel() && SU->hasReservedResource) { +    const MCSchedClassDesc *SC = DAG->getSchedClass(SU); +    for (const MCWriteProcResEntry &PE : +          make_range(SchedModel->getWriteProcResBegin(SC), +                     SchedModel->getWriteProcResEnd(SC))) { +      unsigned ResIdx = PE.ProcResourceIdx; +      unsigned Cycles = PE.Cycles; +      unsigned NRCycle, InstanceIdx; +      std::tie(NRCycle, InstanceIdx) = getNextResourceCycle(ResIdx, Cycles); +      if (NRCycle > CurrCycle) { +#ifndef NDEBUG +        MaxObservedStall = std::max(Cycles, MaxObservedStall); +#endif +        LLVM_DEBUG(dbgs() << "  SU(" << SU->NodeNum << ") " +                          << SchedModel->getResourceName(ResIdx) +                          << '[' << InstanceIdx - ReservedCyclesIndex[ResIdx]  << ']' +                          << "=" << NRCycle << "c\n"); +        return true; +      } +    } +  } +  return false; +} + +// Find the unscheduled node in ReadySUs with the highest latency. +unsigned SchedBoundary:: +findMaxLatency(ArrayRef<SUnit*> ReadySUs) { +  SUnit *LateSU = nullptr; +  unsigned RemLatency = 0; +  for (SUnit *SU : ReadySUs) { +    unsigned L = getUnscheduledLatency(SU); +    if (L > RemLatency) { +      RemLatency = L; +      LateSU = SU; +    } +  } +  if (LateSU) { +    LLVM_DEBUG(dbgs() << Available.getName() << " RemLatency SU(" +                      << LateSU->NodeNum << ") " << RemLatency << "c\n"); +  } +  return RemLatency; +} + +// Count resources in this zone and the remaining unscheduled +// instruction. Return the max count, scaled. Set OtherCritIdx to the critical +// resource index, or zero if the zone is issue limited. +unsigned SchedBoundary:: +getOtherResourceCount(unsigned &OtherCritIdx) { +  OtherCritIdx = 0; +  if (!SchedModel->hasInstrSchedModel()) +    return 0; + +  unsigned OtherCritCount = Rem->RemIssueCount +    + (RetiredMOps * SchedModel->getMicroOpFactor()); +  LLVM_DEBUG(dbgs() << "  " << Available.getName() << " + Remain MOps: " +                    << OtherCritCount / SchedModel->getMicroOpFactor() << '\n'); +  for (unsigned PIdx = 1, PEnd = SchedModel->getNumProcResourceKinds(); +       PIdx != PEnd; ++PIdx) { +    unsigned OtherCount = getResourceCount(PIdx) + Rem->RemainingCounts[PIdx]; +    if (OtherCount > OtherCritCount) { +      OtherCritCount = OtherCount; +      OtherCritIdx = PIdx; +    } +  } +  if (OtherCritIdx) { +    LLVM_DEBUG( +        dbgs() << "  " << Available.getName() << " + Remain CritRes: " +               << OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx) +               << " " << SchedModel->getResourceName(OtherCritIdx) << "\n"); +  } +  return OtherCritCount; +} + +void SchedBoundary::releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue, +                                unsigned Idx) { +  assert(SU->getInstr() && "Scheduled SUnit must have instr"); + +#ifndef NDEBUG +  // ReadyCycle was been bumped up to the CurrCycle when this node was +  // scheduled, but CurrCycle may have been eagerly advanced immediately after +  // scheduling, so may now be greater than ReadyCycle. +  if (ReadyCycle > CurrCycle) +    MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall); +#endif + +  if (ReadyCycle < MinReadyCycle) +    MinReadyCycle = ReadyCycle; + +  // Check for interlocks first. For the purpose of other heuristics, an +  // instruction that cannot issue appears as if it's not in the ReadyQueue. +  bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0; +  bool HazardDetected = (!IsBuffered && ReadyCycle > CurrCycle) || +                        checkHazard(SU) || (Available.size() >= ReadyListLimit); + +  if (!HazardDetected) { +    Available.push(SU); + +    if (InPQueue) +      Pending.remove(Pending.begin() + Idx); +    return; +  } + +  if (!InPQueue) +    Pending.push(SU); +} + +/// Move the boundary of scheduled code by one cycle. +void SchedBoundary::bumpCycle(unsigned NextCycle) { +  if (SchedModel->getMicroOpBufferSize() == 0) { +    assert(MinReadyCycle < std::numeric_limits<unsigned>::max() && +           "MinReadyCycle uninitialized"); +    if (MinReadyCycle > NextCycle) +      NextCycle = MinReadyCycle; +  } +  // Update the current micro-ops, which will issue in the next cycle. +  unsigned DecMOps = SchedModel->getIssueWidth() * (NextCycle - CurrCycle); +  CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps; + +  // Decrement DependentLatency based on the next cycle. +  if ((NextCycle - CurrCycle) > DependentLatency) +    DependentLatency = 0; +  else +    DependentLatency -= (NextCycle - CurrCycle); + +  if (!HazardRec->isEnabled()) { +    // Bypass HazardRec virtual calls. +    CurrCycle = NextCycle; +  } else { +    // Bypass getHazardType calls in case of long latency. +    for (; CurrCycle != NextCycle; ++CurrCycle) { +      if (isTop()) +        HazardRec->AdvanceCycle(); +      else +        HazardRec->RecedeCycle(); +    } +  } +  CheckPending = true; +  IsResourceLimited = +      checkResourceLimit(SchedModel->getLatencyFactor(), getCriticalCount(), +                         getScheduledLatency(), true); + +  LLVM_DEBUG(dbgs() << "Cycle: " << CurrCycle << ' ' << Available.getName() +                    << '\n'); +} + +void SchedBoundary::incExecutedResources(unsigned PIdx, unsigned Count) { +  ExecutedResCounts[PIdx] += Count; +  if (ExecutedResCounts[PIdx] > MaxExecutedResCount) +    MaxExecutedResCount = ExecutedResCounts[PIdx]; +} + +/// Add the given processor resource to this scheduled zone. +/// +/// \param Cycles indicates the number of consecutive (non-pipelined) cycles +/// during which this resource is consumed. +/// +/// \return the next cycle at which the instruction may execute without +/// oversubscribing resources. +unsigned SchedBoundary:: +countResource(unsigned PIdx, unsigned Cycles, unsigned NextCycle) { +  unsigned Factor = SchedModel->getResourceFactor(PIdx); +  unsigned Count = Factor * Cycles; +  LLVM_DEBUG(dbgs() << "  " << SchedModel->getResourceName(PIdx) << " +" +                    << Cycles << "x" << Factor << "u\n"); + +  // Update Executed resources counts. +  incExecutedResources(PIdx, Count); +  assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted"); +  Rem->RemainingCounts[PIdx] -= Count; + +  // Check if this resource exceeds the current critical resource. If so, it +  // becomes the critical resource. +  if (ZoneCritResIdx != PIdx && (getResourceCount(PIdx) > getCriticalCount())) { +    ZoneCritResIdx = PIdx; +    LLVM_DEBUG(dbgs() << "  *** Critical resource " +                      << SchedModel->getResourceName(PIdx) << ": " +                      << getResourceCount(PIdx) / SchedModel->getLatencyFactor() +                      << "c\n"); +  } +  // For reserved resources, record the highest cycle using the resource. +  unsigned NextAvailable, InstanceIdx; +  std::tie(NextAvailable, InstanceIdx) = getNextResourceCycle(PIdx, Cycles); +  if (NextAvailable > CurrCycle) { +    LLVM_DEBUG(dbgs() << "  Resource conflict: " +                      << SchedModel->getResourceName(PIdx) +                      << '[' << InstanceIdx - ReservedCyclesIndex[PIdx]  << ']' +                      << " reserved until @" << NextAvailable << "\n"); +  } +  return NextAvailable; +} + +/// Move the boundary of scheduled code by one SUnit. +void SchedBoundary::bumpNode(SUnit *SU) { +  // Update the reservation table. +  if (HazardRec->isEnabled()) { +    if (!isTop() && SU->isCall) { +      // Calls are scheduled with their preceding instructions. For bottom-up +      // scheduling, clear the pipeline state before emitting. +      HazardRec->Reset(); +    } +    HazardRec->EmitInstruction(SU); +    // Scheduling an instruction may have made pending instructions available. +    CheckPending = true; +  } +  // checkHazard should prevent scheduling multiple instructions per cycle that +  // exceed the issue width. +  const MCSchedClassDesc *SC = DAG->getSchedClass(SU); +  unsigned IncMOps = SchedModel->getNumMicroOps(SU->getInstr()); +  assert( +      (CurrMOps == 0 || (CurrMOps + IncMOps) <= SchedModel->getIssueWidth()) && +      "Cannot schedule this instruction's MicroOps in the current cycle."); + +  unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle); +  LLVM_DEBUG(dbgs() << "  Ready @" << ReadyCycle << "c\n"); + +  unsigned NextCycle = CurrCycle; +  switch (SchedModel->getMicroOpBufferSize()) { +  case 0: +    assert(ReadyCycle <= CurrCycle && "Broken PendingQueue"); +    break; +  case 1: +    if (ReadyCycle > NextCycle) { +      NextCycle = ReadyCycle; +      LLVM_DEBUG(dbgs() << "  *** Stall until: " << ReadyCycle << "\n"); +    } +    break; +  default: +    // We don't currently model the OOO reorder buffer, so consider all +    // scheduled MOps to be "retired". We do loosely model in-order resource +    // latency. If this instruction uses an in-order resource, account for any +    // likely stall cycles. +    if (SU->isUnbuffered && ReadyCycle > NextCycle) +      NextCycle = ReadyCycle; +    break; +  } +  RetiredMOps += IncMOps; + +  // Update resource counts and critical resource. +  if (SchedModel->hasInstrSchedModel()) { +    unsigned DecRemIssue = IncMOps * SchedModel->getMicroOpFactor(); +    assert(Rem->RemIssueCount >= DecRemIssue && "MOps double counted"); +    Rem->RemIssueCount -= DecRemIssue; +    if (ZoneCritResIdx) { +      // Scale scheduled micro-ops for comparing with the critical resource. +      unsigned ScaledMOps = +        RetiredMOps * SchedModel->getMicroOpFactor(); + +      // If scaled micro-ops are now more than the previous critical resource by +      // a full cycle, then micro-ops issue becomes critical. +      if ((int)(ScaledMOps - getResourceCount(ZoneCritResIdx)) +          >= (int)SchedModel->getLatencyFactor()) { +        ZoneCritResIdx = 0; +        LLVM_DEBUG(dbgs() << "  *** Critical resource NumMicroOps: " +                          << ScaledMOps / SchedModel->getLatencyFactor() +                          << "c\n"); +      } +    } +    for (TargetSchedModel::ProcResIter +           PI = SchedModel->getWriteProcResBegin(SC), +           PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { +      unsigned RCycle = +        countResource(PI->ProcResourceIdx, PI->Cycles, NextCycle); +      if (RCycle > NextCycle) +        NextCycle = RCycle; +    } +    if (SU->hasReservedResource) { +      // For reserved resources, record the highest cycle using the resource. +      // For top-down scheduling, this is the cycle in which we schedule this +      // instruction plus the number of cycles the operations reserves the +      // resource. For bottom-up is it simply the instruction's cycle. +      for (TargetSchedModel::ProcResIter +             PI = SchedModel->getWriteProcResBegin(SC), +             PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { +        unsigned PIdx = PI->ProcResourceIdx; +        if (SchedModel->getProcResource(PIdx)->BufferSize == 0) { +          unsigned ReservedUntil, InstanceIdx; +          std::tie(ReservedUntil, InstanceIdx) = getNextResourceCycle(PIdx, 0); +          if (isTop()) { +            ReservedCycles[InstanceIdx] = +                std::max(ReservedUntil, NextCycle + PI->Cycles); +          } else +            ReservedCycles[InstanceIdx] = NextCycle; +        } +      } +    } +  } +  // Update ExpectedLatency and DependentLatency. +  unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency; +  unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency; +  if (SU->getDepth() > TopLatency) { +    TopLatency = SU->getDepth(); +    LLVM_DEBUG(dbgs() << "  " << Available.getName() << " TopLatency SU(" +                      << SU->NodeNum << ") " << TopLatency << "c\n"); +  } +  if (SU->getHeight() > BotLatency) { +    BotLatency = SU->getHeight(); +    LLVM_DEBUG(dbgs() << "  " << Available.getName() << " BotLatency SU(" +                      << SU->NodeNum << ") " << BotLatency << "c\n"); +  } +  // If we stall for any reason, bump the cycle. +  if (NextCycle > CurrCycle) +    bumpCycle(NextCycle); +  else +    // After updating ZoneCritResIdx and ExpectedLatency, check if we're +    // resource limited. If a stall occurred, bumpCycle does this. +    IsResourceLimited = +        checkResourceLimit(SchedModel->getLatencyFactor(), getCriticalCount(), +                           getScheduledLatency(), true); + +  // Update CurrMOps after calling bumpCycle to handle stalls, since bumpCycle +  // resets CurrMOps. Loop to handle instructions with more MOps than issue in +  // one cycle.  Since we commonly reach the max MOps here, opportunistically +  // bump the cycle to avoid uselessly checking everything in the readyQ. +  CurrMOps += IncMOps; + +  // Bump the cycle count for issue group constraints. +  // This must be done after NextCycle has been adjust for all other stalls. +  // Calling bumpCycle(X) will reduce CurrMOps by one issue group and set +  // currCycle to X. +  if ((isTop() &&  SchedModel->mustEndGroup(SU->getInstr())) || +      (!isTop() && SchedModel->mustBeginGroup(SU->getInstr()))) { +    LLVM_DEBUG(dbgs() << "  Bump cycle to " << (isTop() ? "end" : "begin") +                      << " group\n"); +    bumpCycle(++NextCycle); +  } + +  while (CurrMOps >= SchedModel->getIssueWidth()) { +    LLVM_DEBUG(dbgs() << "  *** Max MOps " << CurrMOps << " at cycle " +                      << CurrCycle << '\n'); +    bumpCycle(++NextCycle); +  } +  LLVM_DEBUG(dumpScheduledState()); +} + +/// Release pending ready nodes in to the available queue. This makes them +/// visible to heuristics. +void SchedBoundary::releasePending() { +  // If the available queue is empty, it is safe to reset MinReadyCycle. +  if (Available.empty()) +    MinReadyCycle = std::numeric_limits<unsigned>::max(); + +  // Check to see if any of the pending instructions are ready to issue.  If +  // so, add them to the available queue. +  for (unsigned I = 0, E = Pending.size(); I < E; ++I) { +    SUnit *SU = *(Pending.begin() + I); +    unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle; + +    if (ReadyCycle < MinReadyCycle) +      MinReadyCycle = ReadyCycle; + +    if (Available.size() >= ReadyListLimit) +      break; + +    releaseNode(SU, ReadyCycle, true, I); +    if (E != Pending.size()) { +      --I; +      --E; +    } +  } +  CheckPending = false; +} + +/// Remove SU from the ready set for this boundary. +void SchedBoundary::removeReady(SUnit *SU) { +  if (Available.isInQueue(SU)) +    Available.remove(Available.find(SU)); +  else { +    assert(Pending.isInQueue(SU) && "bad ready count"); +    Pending.remove(Pending.find(SU)); +  } +} + +/// If this queue only has one ready candidate, return it. As a side effect, +/// defer any nodes that now hit a hazard, and advance the cycle until at least +/// one node is ready. If multiple instructions are ready, return NULL. +SUnit *SchedBoundary::pickOnlyChoice() { +  if (CheckPending) +    releasePending(); + +  // Defer any ready instrs that now have a hazard. +  for (ReadyQueue::iterator I = Available.begin(); I != Available.end();) { +    if (checkHazard(*I)) { +      Pending.push(*I); +      I = Available.remove(I); +      continue; +    } +    ++I; +  } +  for (unsigned i = 0; Available.empty(); ++i) { +//  FIXME: Re-enable assert once PR20057 is resolved. +//    assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedStall) && +//           "permanent hazard"); +    (void)i; +    bumpCycle(CurrCycle + 1); +    releasePending(); +  } + +  LLVM_DEBUG(Pending.dump()); +  LLVM_DEBUG(Available.dump()); + +  if (Available.size() == 1) +    return *Available.begin(); +  return nullptr; +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +// This is useful information to dump after bumpNode. +// Note that the Queue contents are more useful before pickNodeFromQueue. +LLVM_DUMP_METHOD void SchedBoundary::dumpScheduledState() const { +  unsigned ResFactor; +  unsigned ResCount; +  if (ZoneCritResIdx) { +    ResFactor = SchedModel->getResourceFactor(ZoneCritResIdx); +    ResCount = getResourceCount(ZoneCritResIdx); +  } else { +    ResFactor = SchedModel->getMicroOpFactor(); +    ResCount = RetiredMOps * ResFactor; +  } +  unsigned LFactor = SchedModel->getLatencyFactor(); +  dbgs() << Available.getName() << " @" << CurrCycle << "c\n" +         << "  Retired: " << RetiredMOps; +  dbgs() << "\n  Executed: " << getExecutedCount() / LFactor << "c"; +  dbgs() << "\n  Critical: " << ResCount / LFactor << "c, " +         << ResCount / ResFactor << " " +         << SchedModel->getResourceName(ZoneCritResIdx) +         << "\n  ExpectedLatency: " << ExpectedLatency << "c\n" +         << (IsResourceLimited ? "  - Resource" : "  - Latency") +         << " limited.\n"; +} +#endif + +//===----------------------------------------------------------------------===// +// GenericScheduler - Generic implementation of MachineSchedStrategy. +//===----------------------------------------------------------------------===// + +void GenericSchedulerBase::SchedCandidate:: +initResourceDelta(const ScheduleDAGMI *DAG, +                  const TargetSchedModel *SchedModel) { +  if (!Policy.ReduceResIdx && !Policy.DemandResIdx) +    return; + +  const MCSchedClassDesc *SC = DAG->getSchedClass(SU); +  for (TargetSchedModel::ProcResIter +         PI = SchedModel->getWriteProcResBegin(SC), +         PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { +    if (PI->ProcResourceIdx == Policy.ReduceResIdx) +      ResDelta.CritResources += PI->Cycles; +    if (PI->ProcResourceIdx == Policy.DemandResIdx) +      ResDelta.DemandedResources += PI->Cycles; +  } +} + +/// Compute remaining latency. We need this both to determine whether the +/// overall schedule has become latency-limited and whether the instructions +/// outside this zone are resource or latency limited. +/// +/// The "dependent" latency is updated incrementally during scheduling as the +/// max height/depth of scheduled nodes minus the cycles since it was +/// scheduled: +///   DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone +/// +/// The "independent" latency is the max ready queue depth: +///   ILat = max N.depth for N in Available|Pending +/// +/// RemainingLatency is the greater of independent and dependent latency. +/// +/// These computations are expensive, especially in DAGs with many edges, so +/// only do them if necessary. +static unsigned computeRemLatency(SchedBoundary &CurrZone) { +  unsigned RemLatency = CurrZone.getDependentLatency(); +  RemLatency = std::max(RemLatency, +                        CurrZone.findMaxLatency(CurrZone.Available.elements())); +  RemLatency = std::max(RemLatency, +                        CurrZone.findMaxLatency(CurrZone.Pending.elements())); +  return RemLatency; +} + +/// Returns true if the current cycle plus remaning latency is greater than +/// the critical path in the scheduling region. +bool GenericSchedulerBase::shouldReduceLatency(const CandPolicy &Policy, +                                               SchedBoundary &CurrZone, +                                               bool ComputeRemLatency, +                                               unsigned &RemLatency) const { +  // The current cycle is already greater than the critical path, so we are +  // already latency limited and don't need to compute the remaining latency. +  if (CurrZone.getCurrCycle() > Rem.CriticalPath) +    return true; + +  // If we haven't scheduled anything yet, then we aren't latency limited. +  if (CurrZone.getCurrCycle() == 0) +    return false; + +  if (ComputeRemLatency) +    RemLatency = computeRemLatency(CurrZone); + +  return RemLatency + CurrZone.getCurrCycle() > Rem.CriticalPath; +} + +/// Set the CandPolicy given a scheduling zone given the current resources and +/// latencies inside and outside the zone. +void GenericSchedulerBase::setPolicy(CandPolicy &Policy, bool IsPostRA, +                                     SchedBoundary &CurrZone, +                                     SchedBoundary *OtherZone) { +  // Apply preemptive heuristics based on the total latency and resources +  // inside and outside this zone. Potential stalls should be considered before +  // following this policy. + +  // Compute the critical resource outside the zone. +  unsigned OtherCritIdx = 0; +  unsigned OtherCount = +    OtherZone ? OtherZone->getOtherResourceCount(OtherCritIdx) : 0; + +  bool OtherResLimited = false; +  unsigned RemLatency = 0; +  bool RemLatencyComputed = false; +  if (SchedModel->hasInstrSchedModel() && OtherCount != 0) { +    RemLatency = computeRemLatency(CurrZone); +    RemLatencyComputed = true; +    OtherResLimited = checkResourceLimit(SchedModel->getLatencyFactor(), +                                         OtherCount, RemLatency, false); +  } + +  // Schedule aggressively for latency in PostRA mode. We don't check for +  // acyclic latency during PostRA, and highly out-of-order processors will +  // skip PostRA scheduling. +  if (!OtherResLimited && +      (IsPostRA || shouldReduceLatency(Policy, CurrZone, !RemLatencyComputed, +                                       RemLatency))) { +    Policy.ReduceLatency |= true; +    LLVM_DEBUG(dbgs() << "  " << CurrZone.Available.getName() +                      << " RemainingLatency " << RemLatency << " + " +                      << CurrZone.getCurrCycle() << "c > CritPath " +                      << Rem.CriticalPath << "\n"); +  } +  // If the same resource is limiting inside and outside the zone, do nothing. +  if (CurrZone.getZoneCritResIdx() == OtherCritIdx) +    return; + +  LLVM_DEBUG(if (CurrZone.isResourceLimited()) { +    dbgs() << "  " << CurrZone.Available.getName() << " ResourceLimited: " +           << SchedModel->getResourceName(CurrZone.getZoneCritResIdx()) << "\n"; +  } if (OtherResLimited) dbgs() +                 << "  RemainingLimit: " +                 << SchedModel->getResourceName(OtherCritIdx) << "\n"; +             if (!CurrZone.isResourceLimited() && !OtherResLimited) dbgs() +             << "  Latency limited both directions.\n"); + +  if (CurrZone.isResourceLimited() && !Policy.ReduceResIdx) +    Policy.ReduceResIdx = CurrZone.getZoneCritResIdx(); + +  if (OtherResLimited) +    Policy.DemandResIdx = OtherCritIdx; +} + +#ifndef NDEBUG +const char *GenericSchedulerBase::getReasonStr( +  GenericSchedulerBase::CandReason Reason) { +  switch (Reason) { +  case NoCand:         return "NOCAND    "; +  case Only1:          return "ONLY1     "; +  case PhysReg:        return "PHYS-REG  "; +  case RegExcess:      return "REG-EXCESS"; +  case RegCritical:    return "REG-CRIT  "; +  case Stall:          return "STALL     "; +  case Cluster:        return "CLUSTER   "; +  case Weak:           return "WEAK      "; +  case RegMax:         return "REG-MAX   "; +  case ResourceReduce: return "RES-REDUCE"; +  case ResourceDemand: return "RES-DEMAND"; +  case TopDepthReduce: return "TOP-DEPTH "; +  case TopPathReduce:  return "TOP-PATH  "; +  case BotHeightReduce:return "BOT-HEIGHT"; +  case BotPathReduce:  return "BOT-PATH  "; +  case NextDefUse:     return "DEF-USE   "; +  case NodeOrder:      return "ORDER     "; +  }; +  llvm_unreachable("Unknown reason!"); +} + +void GenericSchedulerBase::traceCandidate(const SchedCandidate &Cand) { +  PressureChange P; +  unsigned ResIdx = 0; +  unsigned Latency = 0; +  switch (Cand.Reason) { +  default: +    break; +  case RegExcess: +    P = Cand.RPDelta.Excess; +    break; +  case RegCritical: +    P = Cand.RPDelta.CriticalMax; +    break; +  case RegMax: +    P = Cand.RPDelta.CurrentMax; +    break; +  case ResourceReduce: +    ResIdx = Cand.Policy.ReduceResIdx; +    break; +  case ResourceDemand: +    ResIdx = Cand.Policy.DemandResIdx; +    break; +  case TopDepthReduce: +    Latency = Cand.SU->getDepth(); +    break; +  case TopPathReduce: +    Latency = Cand.SU->getHeight(); +    break; +  case BotHeightReduce: +    Latency = Cand.SU->getHeight(); +    break; +  case BotPathReduce: +    Latency = Cand.SU->getDepth(); +    break; +  } +  dbgs() << "  Cand SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason); +  if (P.isValid()) +    dbgs() << " " << TRI->getRegPressureSetName(P.getPSet()) +           << ":" << P.getUnitInc() << " "; +  else +    dbgs() << "      "; +  if (ResIdx) +    dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " "; +  else +    dbgs() << "         "; +  if (Latency) +    dbgs() << " " << Latency << " cycles "; +  else +    dbgs() << "          "; +  dbgs() << '\n'; +} +#endif + +namespace llvm { +/// Return true if this heuristic determines order. +bool tryLess(int TryVal, int CandVal, +             GenericSchedulerBase::SchedCandidate &TryCand, +             GenericSchedulerBase::SchedCandidate &Cand, +             GenericSchedulerBase::CandReason Reason) { +  if (TryVal < CandVal) { +    TryCand.Reason = Reason; +    return true; +  } +  if (TryVal > CandVal) { +    if (Cand.Reason > Reason) +      Cand.Reason = Reason; +    return true; +  } +  return false; +} + +bool tryGreater(int TryVal, int CandVal, +                GenericSchedulerBase::SchedCandidate &TryCand, +                GenericSchedulerBase::SchedCandidate &Cand, +                GenericSchedulerBase::CandReason Reason) { +  if (TryVal > CandVal) { +    TryCand.Reason = Reason; +    return true; +  } +  if (TryVal < CandVal) { +    if (Cand.Reason > Reason) +      Cand.Reason = Reason; +    return true; +  } +  return false; +} + +bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand, +                GenericSchedulerBase::SchedCandidate &Cand, +                SchedBoundary &Zone) { +  if (Zone.isTop()) {      // Prefer the candidate with the lesser depth, but only if one of them has      // depth greater than the total latency scheduled so far, otherwise either      // of them could be scheduled now with no stall.      if (std::max(TryCand.SU->getDepth(), Cand.SU->getDepth()) >          Zone.getScheduledLatency()) { -      if (tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(),  -                  TryCand, Cand, GenericSchedulerBase::TopDepthReduce))  -        return true;  -    }  -    if (tryGreater(TryCand.SU->getHeight(), Cand.SU->getHeight(),  -                   TryCand, Cand, GenericSchedulerBase::TopPathReduce))  -      return true;  -  } else {  +      if (tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(), +                  TryCand, Cand, GenericSchedulerBase::TopDepthReduce)) +        return true; +    } +    if (tryGreater(TryCand.SU->getHeight(), Cand.SU->getHeight(), +                   TryCand, Cand, GenericSchedulerBase::TopPathReduce)) +      return true; +  } else {      // Prefer the candidate with the lesser height, but only if one of them has      // height greater than the total latency scheduled so far, otherwise either      // of them could be scheduled now with no stall.      if (std::max(TryCand.SU->getHeight(), Cand.SU->getHeight()) >          Zone.getScheduledLatency()) { -      if (tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(),  -                  TryCand, Cand, GenericSchedulerBase::BotHeightReduce))  -        return true;  -    }  -    if (tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(),  -                   TryCand, Cand, GenericSchedulerBase::BotPathReduce))  -      return true;  -  }  -  return false;  -}  -} // end namespace llvm  -  -static void tracePick(GenericSchedulerBase::CandReason Reason, bool IsTop) {  -  LLVM_DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ")  -                    << GenericSchedulerBase::getReasonStr(Reason) << '\n');  -}  -  -static void tracePick(const GenericSchedulerBase::SchedCandidate &Cand) {  -  tracePick(Cand.Reason, Cand.AtTop);  -}  -  -void GenericScheduler::initialize(ScheduleDAGMI *dag) {  -  assert(dag->hasVRegLiveness() &&  -         "(PreRA)GenericScheduler needs vreg liveness");  -  DAG = static_cast<ScheduleDAGMILive*>(dag);  -  SchedModel = DAG->getSchedModel();  -  TRI = DAG->TRI;  -  -  if (RegionPolicy.ComputeDFSResult)  -    DAG->computeDFSResult();  -  -  Rem.init(DAG, SchedModel);  -  Top.init(DAG, SchedModel, &Rem);  -  Bot.init(DAG, SchedModel, &Rem);  -  -  // Initialize resource counts.  -  -  // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or  -  // are disabled, then these HazardRecs will be disabled.  -  const InstrItineraryData *Itin = SchedModel->getInstrItineraries();  -  if (!Top.HazardRec) {  -    Top.HazardRec =  -        DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(  -            Itin, DAG);  -  }  -  if (!Bot.HazardRec) {  -    Bot.HazardRec =  -        DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(  -            Itin, DAG);  -  }  -  TopCand.SU = nullptr;  -  BotCand.SU = nullptr;  -}  -  -/// Initialize the per-region scheduling policy.  -void GenericScheduler::initPolicy(MachineBasicBlock::iterator Begin,  -                                  MachineBasicBlock::iterator End,  -                                  unsigned NumRegionInstrs) {  -  const MachineFunction &MF = *Begin->getMF();  -  const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();  -  -  // Avoid setting up the register pressure tracker for small regions to save  -  // compile time. As a rough heuristic, only track pressure when the number of  -  // schedulable instructions exceeds half the integer register file.  -  RegionPolicy.ShouldTrackPressure = true;  -  for (unsigned VT = MVT::i32; VT > (unsigned)MVT::i1; --VT) {  -    MVT::SimpleValueType LegalIntVT = (MVT::SimpleValueType)VT;  -    if (TLI->isTypeLegal(LegalIntVT)) {  -      unsigned NIntRegs = Context->RegClassInfo->getNumAllocatableRegs(  -        TLI->getRegClassFor(LegalIntVT));  -      RegionPolicy.ShouldTrackPressure = NumRegionInstrs > (NIntRegs / 2);  -    }  -  }  -  -  // For generic targets, we default to bottom-up, because it's simpler and more  -  // compile-time optimizations have been implemented in that direction.  -  RegionPolicy.OnlyBottomUp = true;  -  -  // Allow the subtarget to override default policy.  -  MF.getSubtarget().overrideSchedPolicy(RegionPolicy, NumRegionInstrs);  -  -  // After subtarget overrides, apply command line options.  -  if (!EnableRegPressure) {  -    RegionPolicy.ShouldTrackPressure = false;  -    RegionPolicy.ShouldTrackLaneMasks = false;  -  }  -  -  // Check -misched-topdown/bottomup can force or unforce scheduling direction.  -  // e.g. -misched-bottomup=false allows scheduling in both directions.  -  assert((!ForceTopDown || !ForceBottomUp) &&  -         "-misched-topdown incompatible with -misched-bottomup");  -  if (ForceBottomUp.getNumOccurrences() > 0) {  -    RegionPolicy.OnlyBottomUp = ForceBottomUp;  -    if (RegionPolicy.OnlyBottomUp)  -      RegionPolicy.OnlyTopDown = false;  -  }  -  if (ForceTopDown.getNumOccurrences() > 0) {  -    RegionPolicy.OnlyTopDown = ForceTopDown;  -    if (RegionPolicy.OnlyTopDown)  -      RegionPolicy.OnlyBottomUp = false;  -  }  -}  -  -void GenericScheduler::dumpPolicy() const {  -  // Cannot completely remove virtual function even in release mode.  -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)  -  dbgs() << "GenericScheduler RegionPolicy: "  -         << " ShouldTrackPressure=" << RegionPolicy.ShouldTrackPressure  -         << " OnlyTopDown=" << RegionPolicy.OnlyTopDown  -         << " OnlyBottomUp=" << RegionPolicy.OnlyBottomUp  -         << "\n";  -#endif  -}  -  -/// Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic  -/// critical path by more cycles than it takes to drain the instruction buffer.  -/// We estimate an upper bounds on in-flight instructions as:  -///  -/// CyclesPerIteration = max( CyclicPath, Loop-Resource-Height )  -/// InFlightIterations = AcyclicPath / CyclesPerIteration  -/// InFlightResources = InFlightIterations * LoopResources  -///  -/// TODO: Check execution resources in addition to IssueCount.  -void GenericScheduler::checkAcyclicLatency() {  -  if (Rem.CyclicCritPath == 0 || Rem.CyclicCritPath >= Rem.CriticalPath)  -    return;  -  -  // Scaled number of cycles per loop iteration.  -  unsigned IterCount =  -    std::max(Rem.CyclicCritPath * SchedModel->getLatencyFactor(),  -             Rem.RemIssueCount);  -  // Scaled acyclic critical path.  -  unsigned AcyclicCount = Rem.CriticalPath * SchedModel->getLatencyFactor();  -  // InFlightCount = (AcyclicPath / IterCycles) * InstrPerLoop  -  unsigned InFlightCount =  -    (AcyclicCount * Rem.RemIssueCount + IterCount-1) / IterCount;  -  unsigned BufferLimit =  -    SchedModel->getMicroOpBufferSize() * SchedModel->getMicroOpFactor();  -  -  Rem.IsAcyclicLatencyLimited = InFlightCount > BufferLimit;  -  -  LLVM_DEBUG(  -      dbgs() << "IssueCycles="  -             << Rem.RemIssueCount / SchedModel->getLatencyFactor() << "c "  -             << "IterCycles=" << IterCount / SchedModel->getLatencyFactor()  -             << "c NumIters=" << (AcyclicCount + IterCount - 1) / IterCount  -             << " InFlight=" << InFlightCount / SchedModel->getMicroOpFactor()  -             << "m BufferLim=" << SchedModel->getMicroOpBufferSize() << "m\n";  -      if (Rem.IsAcyclicLatencyLimited) dbgs() << "  ACYCLIC LATENCY LIMIT\n");  -}  -  -void GenericScheduler::registerRoots() {  -  Rem.CriticalPath = DAG->ExitSU.getDepth();  -  -  // Some roots may not feed into ExitSU. Check all of them in case.  -  for (const SUnit *SU : Bot.Available) {  -    if (SU->getDepth() > Rem.CriticalPath)  -      Rem.CriticalPath = SU->getDepth();  -  }  -  LLVM_DEBUG(dbgs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << '\n');  -  if (DumpCriticalPathLength) {  -    errs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << " \n";  -  }  -  -  if (EnableCyclicPath && SchedModel->getMicroOpBufferSize() > 0) {  -    Rem.CyclicCritPath = DAG->computeCyclicCriticalPath();  -    checkAcyclicLatency();  -  }  -}  -  -namespace llvm {  -bool tryPressure(const PressureChange &TryP,  -                 const PressureChange &CandP,  -                 GenericSchedulerBase::SchedCandidate &TryCand,  -                 GenericSchedulerBase::SchedCandidate &Cand,  -                 GenericSchedulerBase::CandReason Reason,  -                 const TargetRegisterInfo *TRI,  -                 const MachineFunction &MF) {  -  // If one candidate decreases and the other increases, go with it.  -  // Invalid candidates have UnitInc==0.  -  if (tryGreater(TryP.getUnitInc() < 0, CandP.getUnitInc() < 0, TryCand, Cand,  -                 Reason)) {  -    return true;  -  }  -  // Do not compare the magnitude of pressure changes between top and bottom  -  // boundary.  -  if (Cand.AtTop != TryCand.AtTop)  -    return false;  -  -  // If both candidates affect the same set in the same boundary, go with the  -  // smallest increase.  -  unsigned TryPSet = TryP.getPSetOrMax();  -  unsigned CandPSet = CandP.getPSetOrMax();  -  if (TryPSet == CandPSet) {  -    return tryLess(TryP.getUnitInc(), CandP.getUnitInc(), TryCand, Cand,  -                   Reason);  -  }  -  -  int TryRank = TryP.isValid() ? TRI->getRegPressureSetScore(MF, TryPSet) :  -                                 std::numeric_limits<int>::max();  -  -  int CandRank = CandP.isValid() ? TRI->getRegPressureSetScore(MF, CandPSet) :  -                                   std::numeric_limits<int>::max();  -  -  // If the candidates are decreasing pressure, reverse priority.  -  if (TryP.getUnitInc() < 0)  -    std::swap(TryRank, CandRank);  -  return tryGreater(TryRank, CandRank, TryCand, Cand, Reason);  -}  -  -unsigned getWeakLeft(const SUnit *SU, bool isTop) {  -  return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft;  -}  -  -/// Minimize physical register live ranges. Regalloc wants them adjacent to  -/// their physreg def/use.  -///  -/// FIXME: This is an unnecessary check on the critical path. Most are root/leaf  -/// copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled  -/// with the operation that produces or consumes the physreg. We'll do this when  -/// regalloc has support for parallel copies.  -int biasPhysReg(const SUnit *SU, bool isTop) {  -  const MachineInstr *MI = SU->getInstr();  -  -  if (MI->isCopy()) {  -    unsigned ScheduledOper = isTop ? 1 : 0;  -    unsigned UnscheduledOper = isTop ? 0 : 1;  -    // If we have already scheduled the physreg produce/consumer, immediately  -    // schedule the copy.  -    if (Register::isPhysicalRegister(MI->getOperand(ScheduledOper).getReg()))  -      return 1;  -    // If the physreg is at the boundary, defer it. Otherwise schedule it  -    // immediately to free the dependent. We can hoist the copy later.  -    bool AtBoundary = isTop ? !SU->NumSuccsLeft : !SU->NumPredsLeft;  -    if (Register::isPhysicalRegister(MI->getOperand(UnscheduledOper).getReg()))  -      return AtBoundary ? -1 : 1;  -  }  -  -  if (MI->isMoveImmediate()) {  -    // If we have a move immediate and all successors have been assigned, bias  -    // towards scheduling this later. Make sure all register defs are to  -    // physical registers.  -    bool DoBias = true;  -    for (const MachineOperand &Op : MI->defs()) {  -      if (Op.isReg() && !Register::isPhysicalRegister(Op.getReg())) {  -        DoBias = false;  -        break;  -      }  -    }  -  -    if (DoBias)  -      return isTop ? -1 : 1;  -  }  -  -  return 0;  -}  -} // end namespace llvm  -  -void GenericScheduler::initCandidate(SchedCandidate &Cand, SUnit *SU,  -                                     bool AtTop,  -                                     const RegPressureTracker &RPTracker,  -                                     RegPressureTracker &TempTracker) {  -  Cand.SU = SU;  -  Cand.AtTop = AtTop;  -  if (DAG->isTrackingPressure()) {  -    if (AtTop) {  -      TempTracker.getMaxDownwardPressureDelta(  -        Cand.SU->getInstr(),  -        Cand.RPDelta,  -        DAG->getRegionCriticalPSets(),  -        DAG->getRegPressure().MaxSetPressure);  -    } else {  -      if (VerifyScheduling) {  -        TempTracker.getMaxUpwardPressureDelta(  -          Cand.SU->getInstr(),  -          &DAG->getPressureDiff(Cand.SU),  -          Cand.RPDelta,  -          DAG->getRegionCriticalPSets(),  -          DAG->getRegPressure().MaxSetPressure);  -      } else {  -        RPTracker.getUpwardPressureDelta(  -          Cand.SU->getInstr(),  -          DAG->getPressureDiff(Cand.SU),  -          Cand.RPDelta,  -          DAG->getRegionCriticalPSets(),  -          DAG->getRegPressure().MaxSetPressure);  -      }  -    }  -  }  -  LLVM_DEBUG(if (Cand.RPDelta.Excess.isValid()) dbgs()  -             << "  Try  SU(" << Cand.SU->NodeNum << ") "  -             << TRI->getRegPressureSetName(Cand.RPDelta.Excess.getPSet()) << ":"  -             << Cand.RPDelta.Excess.getUnitInc() << "\n");  -}  -  -/// Apply a set of heuristics to a new candidate. Heuristics are currently  -/// hierarchical. This may be more efficient than a graduated cost model because  -/// we don't need to evaluate all aspects of the model for each node in the  -/// queue. But it's really done to make the heuristics easier to debug and  -/// statistically analyze.  -///  -/// \param Cand provides the policy and current best candidate.  -/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.  -/// \param Zone describes the scheduled zone that we are extending, or nullptr  -//              if Cand is from a different zone than TryCand.  -void GenericScheduler::tryCandidate(SchedCandidate &Cand,  -                                    SchedCandidate &TryCand,  -                                    SchedBoundary *Zone) const {  -  // Initialize the candidate if needed.  -  if (!Cand.isValid()) {  -    TryCand.Reason = NodeOrder;  -    return;  -  }  -  -  // Bias PhysReg Defs and copies to their uses and defined respectively.  -  if (tryGreater(biasPhysReg(TryCand.SU, TryCand.AtTop),  -                 biasPhysReg(Cand.SU, Cand.AtTop), TryCand, Cand, PhysReg))  -    return;  -  -  // Avoid exceeding the target's limit.  -  if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.Excess,  -                                               Cand.RPDelta.Excess,  -                                               TryCand, Cand, RegExcess, TRI,  -                                               DAG->MF))  -    return;  -  -  // Avoid increasing the max critical pressure in the scheduled region.  -  if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CriticalMax,  -                                               Cand.RPDelta.CriticalMax,  -                                               TryCand, Cand, RegCritical, TRI,  -                                               DAG->MF))  -    return;  -  -  // We only compare a subset of features when comparing nodes between  -  // Top and Bottom boundary. Some properties are simply incomparable, in many  -  // other instances we should only override the other boundary if something  -  // is a clear good pick on one boundary. Skip heuristics that are more  -  // "tie-breaking" in nature.  -  bool SameBoundary = Zone != nullptr;  -  if (SameBoundary) {  -    // For loops that are acyclic path limited, aggressively schedule for  -    // latency. Within an single cycle, whenever CurrMOps > 0, allow normal  -    // heuristics to take precedence.  -    if (Rem.IsAcyclicLatencyLimited && !Zone->getCurrMOps() &&  -        tryLatency(TryCand, Cand, *Zone))  -      return;  -  -    // Prioritize instructions that read unbuffered resources by stall cycles.  -    if (tryLess(Zone->getLatencyStallCycles(TryCand.SU),  -                Zone->getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))  -      return;  -  }  -  -  // Keep clustered nodes together to encourage downstream peephole  -  // optimizations which may reduce resource requirements.  -  //  -  // This is a best effort to set things up for a post-RA pass. Optimizations  -  // like generating loads of multiple registers should ideally be done within  -  // the scheduler pass by combining the loads during DAG postprocessing.  -  const SUnit *CandNextClusterSU =  -    Cand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();  -  const SUnit *TryCandNextClusterSU =  -    TryCand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();  -  if (tryGreater(TryCand.SU == TryCandNextClusterSU,  -                 Cand.SU == CandNextClusterSU,  -                 TryCand, Cand, Cluster))  -    return;  -  -  if (SameBoundary) {  -    // Weak edges are for clustering and other constraints.  -    if (tryLess(getWeakLeft(TryCand.SU, TryCand.AtTop),  -                getWeakLeft(Cand.SU, Cand.AtTop),  -                TryCand, Cand, Weak))  -      return;  -  }  -  -  // Avoid increasing the max pressure of the entire region.  -  if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CurrentMax,  -                                               Cand.RPDelta.CurrentMax,  -                                               TryCand, Cand, RegMax, TRI,  -                                               DAG->MF))  -    return;  -  -  if (SameBoundary) {  -    // Avoid critical resource consumption and balance the schedule.  -    TryCand.initResourceDelta(DAG, SchedModel);  -    if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,  -                TryCand, Cand, ResourceReduce))  -      return;  -    if (tryGreater(TryCand.ResDelta.DemandedResources,  -                   Cand.ResDelta.DemandedResources,  -                   TryCand, Cand, ResourceDemand))  -      return;  -  -    // Avoid serializing long latency dependence chains.  -    // For acyclic path limited loops, latency was already checked above.  -    if (!RegionPolicy.DisableLatencyHeuristic && TryCand.Policy.ReduceLatency &&  -        !Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, *Zone))  -      return;  -  -    // Fall through to original instruction order.  -    if ((Zone->isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum)  -        || (!Zone->isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {  -      TryCand.Reason = NodeOrder;  -    }  -  }  -}  -  -/// Pick the best candidate from the queue.  -///  -/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during  -/// DAG building. To adjust for the current scheduling location we need to  -/// maintain the number of vreg uses remaining to be top-scheduled.  -void GenericScheduler::pickNodeFromQueue(SchedBoundary &Zone,  -                                         const CandPolicy &ZonePolicy,  -                                         const RegPressureTracker &RPTracker,  -                                         SchedCandidate &Cand) {  -  // getMaxPressureDelta temporarily modifies the tracker.  -  RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);  -  -  ReadyQueue &Q = Zone.Available;  -  for (SUnit *SU : Q) {  -  -    SchedCandidate TryCand(ZonePolicy);  -    initCandidate(TryCand, SU, Zone.isTop(), RPTracker, TempTracker);  -    // Pass SchedBoundary only when comparing nodes from the same boundary.  -    SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;  -    tryCandidate(Cand, TryCand, ZoneArg);  -    if (TryCand.Reason != NoCand) {  -      // Initialize resource delta if needed in case future heuristics query it.  -      if (TryCand.ResDelta == SchedResourceDelta())  -        TryCand.initResourceDelta(DAG, SchedModel);  -      Cand.setBest(TryCand);  -      LLVM_DEBUG(traceCandidate(Cand));  -    }  -  }  -}  -  -/// Pick the best candidate node from either the top or bottom queue.  -SUnit *GenericScheduler::pickNodeBidirectional(bool &IsTopNode) {  -  // Schedule as far as possible in the direction of no choice. This is most  -  // efficient, but also provides the best heuristics for CriticalPSets.  -  if (SUnit *SU = Bot.pickOnlyChoice()) {  -    IsTopNode = false;  -    tracePick(Only1, false);  -    return SU;  -  }  -  if (SUnit *SU = Top.pickOnlyChoice()) {  -    IsTopNode = true;  -    tracePick(Only1, true);  -    return SU;  -  }  -  // Set the bottom-up policy based on the state of the current bottom zone and  -  // the instructions outside the zone, including the top zone.  -  CandPolicy BotPolicy;  -  setPolicy(BotPolicy, /*IsPostRA=*/false, Bot, &Top);  -  // Set the top-down policy based on the state of the current top zone and  -  // the instructions outside the zone, including the bottom zone.  -  CandPolicy TopPolicy;  -  setPolicy(TopPolicy, /*IsPostRA=*/false, Top, &Bot);  -  -  // See if BotCand is still valid (because we previously scheduled from Top).  -  LLVM_DEBUG(dbgs() << "Picking from Bot:\n");  -  if (!BotCand.isValid() || BotCand.SU->isScheduled ||  -      BotCand.Policy != BotPolicy) {  -    BotCand.reset(CandPolicy());  -    pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), BotCand);  -    assert(BotCand.Reason != NoCand && "failed to find the first candidate");  -  } else {  -    LLVM_DEBUG(traceCandidate(BotCand));  -#ifndef NDEBUG  -    if (VerifyScheduling) {  -      SchedCandidate TCand;  -      TCand.reset(CandPolicy());  -      pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), TCand);  -      assert(TCand.SU == BotCand.SU &&  -             "Last pick result should correspond to re-picking right now");  -    }  -#endif  -  }  -  -  // Check if the top Q has a better candidate.  -  LLVM_DEBUG(dbgs() << "Picking from Top:\n");  -  if (!TopCand.isValid() || TopCand.SU->isScheduled ||  -      TopCand.Policy != TopPolicy) {  -    TopCand.reset(CandPolicy());  -    pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TopCand);  -    assert(TopCand.Reason != NoCand && "failed to find the first candidate");  -  } else {  -    LLVM_DEBUG(traceCandidate(TopCand));  -#ifndef NDEBUG  -    if (VerifyScheduling) {  -      SchedCandidate TCand;  -      TCand.reset(CandPolicy());  -      pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TCand);  -      assert(TCand.SU == TopCand.SU &&  -           "Last pick result should correspond to re-picking right now");  -    }  -#endif  -  }  -  -  // Pick best from BotCand and TopCand.  -  assert(BotCand.isValid());  -  assert(TopCand.isValid());  -  SchedCandidate Cand = BotCand;  -  TopCand.Reason = NoCand;  -  tryCandidate(Cand, TopCand, nullptr);  -  if (TopCand.Reason != NoCand) {  -    Cand.setBest(TopCand);  -    LLVM_DEBUG(traceCandidate(Cand));  -  }  -  -  IsTopNode = Cand.AtTop;  -  tracePick(Cand);  -  return Cand.SU;  -}  -  -/// Pick the best node to balance the schedule. Implements MachineSchedStrategy.  -SUnit *GenericScheduler::pickNode(bool &IsTopNode) {  -  if (DAG->top() == DAG->bottom()) {  -    assert(Top.Available.empty() && Top.Pending.empty() &&  -           Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");  -    return nullptr;  -  }  -  SUnit *SU;  -  do {  -    if (RegionPolicy.OnlyTopDown) {  -      SU = Top.pickOnlyChoice();  -      if (!SU) {  -        CandPolicy NoPolicy;  -        TopCand.reset(NoPolicy);  -        pickNodeFromQueue(Top, NoPolicy, DAG->getTopRPTracker(), TopCand);  -        assert(TopCand.Reason != NoCand && "failed to find a candidate");  -        tracePick(TopCand);  -        SU = TopCand.SU;  -      }  -      IsTopNode = true;  -    } else if (RegionPolicy.OnlyBottomUp) {  -      SU = Bot.pickOnlyChoice();  -      if (!SU) {  -        CandPolicy NoPolicy;  -        BotCand.reset(NoPolicy);  -        pickNodeFromQueue(Bot, NoPolicy, DAG->getBotRPTracker(), BotCand);  -        assert(BotCand.Reason != NoCand && "failed to find a candidate");  -        tracePick(BotCand);  -        SU = BotCand.SU;  -      }  -      IsTopNode = false;  -    } else {  -      SU = pickNodeBidirectional(IsTopNode);  -    }  -  } while (SU->isScheduled);  -  -  if (SU->isTopReady())  -    Top.removeReady(SU);  -  if (SU->isBottomReady())  -    Bot.removeReady(SU);  -  -  LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "  -                    << *SU->getInstr());  -  return SU;  -}  -  -void GenericScheduler::reschedulePhysReg(SUnit *SU, bool isTop) {  -  MachineBasicBlock::iterator InsertPos = SU->getInstr();  -  if (!isTop)  -    ++InsertPos;  -  SmallVectorImpl<SDep> &Deps = isTop ? SU->Preds : SU->Succs;  -  -  // Find already scheduled copies with a single physreg dependence and move  -  // them just above the scheduled instruction.  -  for (SDep &Dep : Deps) {  -    if (Dep.getKind() != SDep::Data ||  -        !Register::isPhysicalRegister(Dep.getReg()))  -      continue;  -    SUnit *DepSU = Dep.getSUnit();  -    if (isTop ? DepSU->Succs.size() > 1 : DepSU->Preds.size() > 1)  -      continue;  -    MachineInstr *Copy = DepSU->getInstr();  -    if (!Copy->isCopy() && !Copy->isMoveImmediate())  -      continue;  -    LLVM_DEBUG(dbgs() << "  Rescheduling physreg copy ";  -               DAG->dumpNode(*Dep.getSUnit()));  -    DAG->moveInstruction(Copy, InsertPos);  -  }  -}  -  -/// Update the scheduler's state after scheduling a node. This is the same node  -/// that was just returned by pickNode(). However, ScheduleDAGMILive needs to  -/// update it's state based on the current cycle before MachineSchedStrategy  -/// does.  -///  -/// FIXME: Eventually, we may bundle physreg copies rather than rescheduling  -/// them here. See comments in biasPhysReg.  -void GenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {  -  if (IsTopNode) {  -    SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.getCurrCycle());  -    Top.bumpNode(SU);  -    if (SU->hasPhysRegUses)  -      reschedulePhysReg(SU, true);  -  } else {  -    SU->BotReadyCycle = std::max(SU->BotReadyCycle, Bot.getCurrCycle());  -    Bot.bumpNode(SU);  -    if (SU->hasPhysRegDefs)  -      reschedulePhysReg(SU, false);  -  }  -}  -  -/// Create the standard converging machine scheduler. This will be used as the  -/// default scheduler if the target does not set a default.  -ScheduleDAGMILive *llvm::createGenericSchedLive(MachineSchedContext *C) {  -  ScheduleDAGMILive *DAG =  -      new ScheduleDAGMILive(C, std::make_unique<GenericScheduler>(C));  -  // Register DAG post-processors.  -  //  -  // FIXME: extend the mutation API to allow earlier mutations to instantiate  -  // data and pass it to later mutations. Have a single mutation that gathers  -  // the interesting nodes in one pass.  -  DAG->addMutation(createCopyConstrainDAGMutation(DAG->TII, DAG->TRI));  -  return DAG;  -}  -  +      if (tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(), +                  TryCand, Cand, GenericSchedulerBase::BotHeightReduce)) +        return true; +    } +    if (tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(), +                   TryCand, Cand, GenericSchedulerBase::BotPathReduce)) +      return true; +  } +  return false; +} +} // end namespace llvm + +static void tracePick(GenericSchedulerBase::CandReason Reason, bool IsTop) { +  LLVM_DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ") +                    << GenericSchedulerBase::getReasonStr(Reason) << '\n'); +} + +static void tracePick(const GenericSchedulerBase::SchedCandidate &Cand) { +  tracePick(Cand.Reason, Cand.AtTop); +} + +void GenericScheduler::initialize(ScheduleDAGMI *dag) { +  assert(dag->hasVRegLiveness() && +         "(PreRA)GenericScheduler needs vreg liveness"); +  DAG = static_cast<ScheduleDAGMILive*>(dag); +  SchedModel = DAG->getSchedModel(); +  TRI = DAG->TRI; + +  if (RegionPolicy.ComputeDFSResult) +    DAG->computeDFSResult(); + +  Rem.init(DAG, SchedModel); +  Top.init(DAG, SchedModel, &Rem); +  Bot.init(DAG, SchedModel, &Rem); + +  // Initialize resource counts. + +  // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or +  // are disabled, then these HazardRecs will be disabled. +  const InstrItineraryData *Itin = SchedModel->getInstrItineraries(); +  if (!Top.HazardRec) { +    Top.HazardRec = +        DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer( +            Itin, DAG); +  } +  if (!Bot.HazardRec) { +    Bot.HazardRec = +        DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer( +            Itin, DAG); +  } +  TopCand.SU = nullptr; +  BotCand.SU = nullptr; +} + +/// Initialize the per-region scheduling policy. +void GenericScheduler::initPolicy(MachineBasicBlock::iterator Begin, +                                  MachineBasicBlock::iterator End, +                                  unsigned NumRegionInstrs) { +  const MachineFunction &MF = *Begin->getMF(); +  const TargetLowering *TLI = MF.getSubtarget().getTargetLowering(); + +  // Avoid setting up the register pressure tracker for small regions to save +  // compile time. As a rough heuristic, only track pressure when the number of +  // schedulable instructions exceeds half the integer register file. +  RegionPolicy.ShouldTrackPressure = true; +  for (unsigned VT = MVT::i32; VT > (unsigned)MVT::i1; --VT) { +    MVT::SimpleValueType LegalIntVT = (MVT::SimpleValueType)VT; +    if (TLI->isTypeLegal(LegalIntVT)) { +      unsigned NIntRegs = Context->RegClassInfo->getNumAllocatableRegs( +        TLI->getRegClassFor(LegalIntVT)); +      RegionPolicy.ShouldTrackPressure = NumRegionInstrs > (NIntRegs / 2); +    } +  } + +  // For generic targets, we default to bottom-up, because it's simpler and more +  // compile-time optimizations have been implemented in that direction. +  RegionPolicy.OnlyBottomUp = true; + +  // Allow the subtarget to override default policy. +  MF.getSubtarget().overrideSchedPolicy(RegionPolicy, NumRegionInstrs); + +  // After subtarget overrides, apply command line options. +  if (!EnableRegPressure) { +    RegionPolicy.ShouldTrackPressure = false; +    RegionPolicy.ShouldTrackLaneMasks = false; +  } + +  // Check -misched-topdown/bottomup can force or unforce scheduling direction. +  // e.g. -misched-bottomup=false allows scheduling in both directions. +  assert((!ForceTopDown || !ForceBottomUp) && +         "-misched-topdown incompatible with -misched-bottomup"); +  if (ForceBottomUp.getNumOccurrences() > 0) { +    RegionPolicy.OnlyBottomUp = ForceBottomUp; +    if (RegionPolicy.OnlyBottomUp) +      RegionPolicy.OnlyTopDown = false; +  } +  if (ForceTopDown.getNumOccurrences() > 0) { +    RegionPolicy.OnlyTopDown = ForceTopDown; +    if (RegionPolicy.OnlyTopDown) +      RegionPolicy.OnlyBottomUp = false; +  } +} + +void GenericScheduler::dumpPolicy() const { +  // Cannot completely remove virtual function even in release mode. +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +  dbgs() << "GenericScheduler RegionPolicy: " +         << " ShouldTrackPressure=" << RegionPolicy.ShouldTrackPressure +         << " OnlyTopDown=" << RegionPolicy.OnlyTopDown +         << " OnlyBottomUp=" << RegionPolicy.OnlyBottomUp +         << "\n"; +#endif +} + +/// Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic +/// critical path by more cycles than it takes to drain the instruction buffer. +/// We estimate an upper bounds on in-flight instructions as: +/// +/// CyclesPerIteration = max( CyclicPath, Loop-Resource-Height ) +/// InFlightIterations = AcyclicPath / CyclesPerIteration +/// InFlightResources = InFlightIterations * LoopResources +/// +/// TODO: Check execution resources in addition to IssueCount. +void GenericScheduler::checkAcyclicLatency() { +  if (Rem.CyclicCritPath == 0 || Rem.CyclicCritPath >= Rem.CriticalPath) +    return; + +  // Scaled number of cycles per loop iteration. +  unsigned IterCount = +    std::max(Rem.CyclicCritPath * SchedModel->getLatencyFactor(), +             Rem.RemIssueCount); +  // Scaled acyclic critical path. +  unsigned AcyclicCount = Rem.CriticalPath * SchedModel->getLatencyFactor(); +  // InFlightCount = (AcyclicPath / IterCycles) * InstrPerLoop +  unsigned InFlightCount = +    (AcyclicCount * Rem.RemIssueCount + IterCount-1) / IterCount; +  unsigned BufferLimit = +    SchedModel->getMicroOpBufferSize() * SchedModel->getMicroOpFactor(); + +  Rem.IsAcyclicLatencyLimited = InFlightCount > BufferLimit; + +  LLVM_DEBUG( +      dbgs() << "IssueCycles=" +             << Rem.RemIssueCount / SchedModel->getLatencyFactor() << "c " +             << "IterCycles=" << IterCount / SchedModel->getLatencyFactor() +             << "c NumIters=" << (AcyclicCount + IterCount - 1) / IterCount +             << " InFlight=" << InFlightCount / SchedModel->getMicroOpFactor() +             << "m BufferLim=" << SchedModel->getMicroOpBufferSize() << "m\n"; +      if (Rem.IsAcyclicLatencyLimited) dbgs() << "  ACYCLIC LATENCY LIMIT\n"); +} + +void GenericScheduler::registerRoots() { +  Rem.CriticalPath = DAG->ExitSU.getDepth(); + +  // Some roots may not feed into ExitSU. Check all of them in case. +  for (const SUnit *SU : Bot.Available) { +    if (SU->getDepth() > Rem.CriticalPath) +      Rem.CriticalPath = SU->getDepth(); +  } +  LLVM_DEBUG(dbgs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << '\n'); +  if (DumpCriticalPathLength) { +    errs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << " \n"; +  } + +  if (EnableCyclicPath && SchedModel->getMicroOpBufferSize() > 0) { +    Rem.CyclicCritPath = DAG->computeCyclicCriticalPath(); +    checkAcyclicLatency(); +  } +} + +namespace llvm { +bool tryPressure(const PressureChange &TryP, +                 const PressureChange &CandP, +                 GenericSchedulerBase::SchedCandidate &TryCand, +                 GenericSchedulerBase::SchedCandidate &Cand, +                 GenericSchedulerBase::CandReason Reason, +                 const TargetRegisterInfo *TRI, +                 const MachineFunction &MF) { +  // If one candidate decreases and the other increases, go with it. +  // Invalid candidates have UnitInc==0. +  if (tryGreater(TryP.getUnitInc() < 0, CandP.getUnitInc() < 0, TryCand, Cand, +                 Reason)) { +    return true; +  } +  // Do not compare the magnitude of pressure changes between top and bottom +  // boundary. +  if (Cand.AtTop != TryCand.AtTop) +    return false; + +  // If both candidates affect the same set in the same boundary, go with the +  // smallest increase. +  unsigned TryPSet = TryP.getPSetOrMax(); +  unsigned CandPSet = CandP.getPSetOrMax(); +  if (TryPSet == CandPSet) { +    return tryLess(TryP.getUnitInc(), CandP.getUnitInc(), TryCand, Cand, +                   Reason); +  } + +  int TryRank = TryP.isValid() ? TRI->getRegPressureSetScore(MF, TryPSet) : +                                 std::numeric_limits<int>::max(); + +  int CandRank = CandP.isValid() ? TRI->getRegPressureSetScore(MF, CandPSet) : +                                   std::numeric_limits<int>::max(); + +  // If the candidates are decreasing pressure, reverse priority. +  if (TryP.getUnitInc() < 0) +    std::swap(TryRank, CandRank); +  return tryGreater(TryRank, CandRank, TryCand, Cand, Reason); +} + +unsigned getWeakLeft(const SUnit *SU, bool isTop) { +  return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft; +} + +/// Minimize physical register live ranges. Regalloc wants them adjacent to +/// their physreg def/use. +/// +/// FIXME: This is an unnecessary check on the critical path. Most are root/leaf +/// copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled +/// with the operation that produces or consumes the physreg. We'll do this when +/// regalloc has support for parallel copies. +int biasPhysReg(const SUnit *SU, bool isTop) { +  const MachineInstr *MI = SU->getInstr(); + +  if (MI->isCopy()) { +    unsigned ScheduledOper = isTop ? 1 : 0; +    unsigned UnscheduledOper = isTop ? 0 : 1; +    // If we have already scheduled the physreg produce/consumer, immediately +    // schedule the copy. +    if (Register::isPhysicalRegister(MI->getOperand(ScheduledOper).getReg())) +      return 1; +    // If the physreg is at the boundary, defer it. Otherwise schedule it +    // immediately to free the dependent. We can hoist the copy later. +    bool AtBoundary = isTop ? !SU->NumSuccsLeft : !SU->NumPredsLeft; +    if (Register::isPhysicalRegister(MI->getOperand(UnscheduledOper).getReg())) +      return AtBoundary ? -1 : 1; +  } + +  if (MI->isMoveImmediate()) { +    // If we have a move immediate and all successors have been assigned, bias +    // towards scheduling this later. Make sure all register defs are to +    // physical registers. +    bool DoBias = true; +    for (const MachineOperand &Op : MI->defs()) { +      if (Op.isReg() && !Register::isPhysicalRegister(Op.getReg())) { +        DoBias = false; +        break; +      } +    } + +    if (DoBias) +      return isTop ? -1 : 1; +  } + +  return 0; +} +} // end namespace llvm + +void GenericScheduler::initCandidate(SchedCandidate &Cand, SUnit *SU, +                                     bool AtTop, +                                     const RegPressureTracker &RPTracker, +                                     RegPressureTracker &TempTracker) { +  Cand.SU = SU; +  Cand.AtTop = AtTop; +  if (DAG->isTrackingPressure()) { +    if (AtTop) { +      TempTracker.getMaxDownwardPressureDelta( +        Cand.SU->getInstr(), +        Cand.RPDelta, +        DAG->getRegionCriticalPSets(), +        DAG->getRegPressure().MaxSetPressure); +    } else { +      if (VerifyScheduling) { +        TempTracker.getMaxUpwardPressureDelta( +          Cand.SU->getInstr(), +          &DAG->getPressureDiff(Cand.SU), +          Cand.RPDelta, +          DAG->getRegionCriticalPSets(), +          DAG->getRegPressure().MaxSetPressure); +      } else { +        RPTracker.getUpwardPressureDelta( +          Cand.SU->getInstr(), +          DAG->getPressureDiff(Cand.SU), +          Cand.RPDelta, +          DAG->getRegionCriticalPSets(), +          DAG->getRegPressure().MaxSetPressure); +      } +    } +  } +  LLVM_DEBUG(if (Cand.RPDelta.Excess.isValid()) dbgs() +             << "  Try  SU(" << Cand.SU->NodeNum << ") " +             << TRI->getRegPressureSetName(Cand.RPDelta.Excess.getPSet()) << ":" +             << Cand.RPDelta.Excess.getUnitInc() << "\n"); +} + +/// Apply a set of heuristics to a new candidate. Heuristics are currently +/// hierarchical. This may be more efficient than a graduated cost model because +/// we don't need to evaluate all aspects of the model for each node in the +/// queue. But it's really done to make the heuristics easier to debug and +/// statistically analyze. +/// +/// \param Cand provides the policy and current best candidate. +/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized. +/// \param Zone describes the scheduled zone that we are extending, or nullptr +//              if Cand is from a different zone than TryCand. +void GenericScheduler::tryCandidate(SchedCandidate &Cand, +                                    SchedCandidate &TryCand, +                                    SchedBoundary *Zone) const { +  // Initialize the candidate if needed. +  if (!Cand.isValid()) { +    TryCand.Reason = NodeOrder; +    return; +  } + +  // Bias PhysReg Defs and copies to their uses and defined respectively. +  if (tryGreater(biasPhysReg(TryCand.SU, TryCand.AtTop), +                 biasPhysReg(Cand.SU, Cand.AtTop), TryCand, Cand, PhysReg)) +    return; + +  // Avoid exceeding the target's limit. +  if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.Excess, +                                               Cand.RPDelta.Excess, +                                               TryCand, Cand, RegExcess, TRI, +                                               DAG->MF)) +    return; + +  // Avoid increasing the max critical pressure in the scheduled region. +  if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CriticalMax, +                                               Cand.RPDelta.CriticalMax, +                                               TryCand, Cand, RegCritical, TRI, +                                               DAG->MF)) +    return; + +  // We only compare a subset of features when comparing nodes between +  // Top and Bottom boundary. Some properties are simply incomparable, in many +  // other instances we should only override the other boundary if something +  // is a clear good pick on one boundary. Skip heuristics that are more +  // "tie-breaking" in nature. +  bool SameBoundary = Zone != nullptr; +  if (SameBoundary) { +    // For loops that are acyclic path limited, aggressively schedule for +    // latency. Within an single cycle, whenever CurrMOps > 0, allow normal +    // heuristics to take precedence. +    if (Rem.IsAcyclicLatencyLimited && !Zone->getCurrMOps() && +        tryLatency(TryCand, Cand, *Zone)) +      return; + +    // Prioritize instructions that read unbuffered resources by stall cycles. +    if (tryLess(Zone->getLatencyStallCycles(TryCand.SU), +                Zone->getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall)) +      return; +  } + +  // Keep clustered nodes together to encourage downstream peephole +  // optimizations which may reduce resource requirements. +  // +  // This is a best effort to set things up for a post-RA pass. Optimizations +  // like generating loads of multiple registers should ideally be done within +  // the scheduler pass by combining the loads during DAG postprocessing. +  const SUnit *CandNextClusterSU = +    Cand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred(); +  const SUnit *TryCandNextClusterSU = +    TryCand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred(); +  if (tryGreater(TryCand.SU == TryCandNextClusterSU, +                 Cand.SU == CandNextClusterSU, +                 TryCand, Cand, Cluster)) +    return; + +  if (SameBoundary) { +    // Weak edges are for clustering and other constraints. +    if (tryLess(getWeakLeft(TryCand.SU, TryCand.AtTop), +                getWeakLeft(Cand.SU, Cand.AtTop), +                TryCand, Cand, Weak)) +      return; +  } + +  // Avoid increasing the max pressure of the entire region. +  if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CurrentMax, +                                               Cand.RPDelta.CurrentMax, +                                               TryCand, Cand, RegMax, TRI, +                                               DAG->MF)) +    return; + +  if (SameBoundary) { +    // Avoid critical resource consumption and balance the schedule. +    TryCand.initResourceDelta(DAG, SchedModel); +    if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources, +                TryCand, Cand, ResourceReduce)) +      return; +    if (tryGreater(TryCand.ResDelta.DemandedResources, +                   Cand.ResDelta.DemandedResources, +                   TryCand, Cand, ResourceDemand)) +      return; + +    // Avoid serializing long latency dependence chains. +    // For acyclic path limited loops, latency was already checked above. +    if (!RegionPolicy.DisableLatencyHeuristic && TryCand.Policy.ReduceLatency && +        !Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, *Zone)) +      return; + +    // Fall through to original instruction order. +    if ((Zone->isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum) +        || (!Zone->isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) { +      TryCand.Reason = NodeOrder; +    } +  } +} + +/// Pick the best candidate from the queue. +/// +/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during +/// DAG building. To adjust for the current scheduling location we need to +/// maintain the number of vreg uses remaining to be top-scheduled. +void GenericScheduler::pickNodeFromQueue(SchedBoundary &Zone, +                                         const CandPolicy &ZonePolicy, +                                         const RegPressureTracker &RPTracker, +                                         SchedCandidate &Cand) { +  // getMaxPressureDelta temporarily modifies the tracker. +  RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker); + +  ReadyQueue &Q = Zone.Available; +  for (SUnit *SU : Q) { + +    SchedCandidate TryCand(ZonePolicy); +    initCandidate(TryCand, SU, Zone.isTop(), RPTracker, TempTracker); +    // Pass SchedBoundary only when comparing nodes from the same boundary. +    SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr; +    tryCandidate(Cand, TryCand, ZoneArg); +    if (TryCand.Reason != NoCand) { +      // Initialize resource delta if needed in case future heuristics query it. +      if (TryCand.ResDelta == SchedResourceDelta()) +        TryCand.initResourceDelta(DAG, SchedModel); +      Cand.setBest(TryCand); +      LLVM_DEBUG(traceCandidate(Cand)); +    } +  } +} + +/// Pick the best candidate node from either the top or bottom queue. +SUnit *GenericScheduler::pickNodeBidirectional(bool &IsTopNode) { +  // Schedule as far as possible in the direction of no choice. This is most +  // efficient, but also provides the best heuristics for CriticalPSets. +  if (SUnit *SU = Bot.pickOnlyChoice()) { +    IsTopNode = false; +    tracePick(Only1, false); +    return SU; +  } +  if (SUnit *SU = Top.pickOnlyChoice()) { +    IsTopNode = true; +    tracePick(Only1, true); +    return SU; +  } +  // Set the bottom-up policy based on the state of the current bottom zone and +  // the instructions outside the zone, including the top zone. +  CandPolicy BotPolicy; +  setPolicy(BotPolicy, /*IsPostRA=*/false, Bot, &Top); +  // Set the top-down policy based on the state of the current top zone and +  // the instructions outside the zone, including the bottom zone. +  CandPolicy TopPolicy; +  setPolicy(TopPolicy, /*IsPostRA=*/false, Top, &Bot); + +  // See if BotCand is still valid (because we previously scheduled from Top). +  LLVM_DEBUG(dbgs() << "Picking from Bot:\n"); +  if (!BotCand.isValid() || BotCand.SU->isScheduled || +      BotCand.Policy != BotPolicy) { +    BotCand.reset(CandPolicy()); +    pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), BotCand); +    assert(BotCand.Reason != NoCand && "failed to find the first candidate"); +  } else { +    LLVM_DEBUG(traceCandidate(BotCand)); +#ifndef NDEBUG +    if (VerifyScheduling) { +      SchedCandidate TCand; +      TCand.reset(CandPolicy()); +      pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), TCand); +      assert(TCand.SU == BotCand.SU && +             "Last pick result should correspond to re-picking right now"); +    } +#endif +  } + +  // Check if the top Q has a better candidate. +  LLVM_DEBUG(dbgs() << "Picking from Top:\n"); +  if (!TopCand.isValid() || TopCand.SU->isScheduled || +      TopCand.Policy != TopPolicy) { +    TopCand.reset(CandPolicy()); +    pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TopCand); +    assert(TopCand.Reason != NoCand && "failed to find the first candidate"); +  } else { +    LLVM_DEBUG(traceCandidate(TopCand)); +#ifndef NDEBUG +    if (VerifyScheduling) { +      SchedCandidate TCand; +      TCand.reset(CandPolicy()); +      pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TCand); +      assert(TCand.SU == TopCand.SU && +           "Last pick result should correspond to re-picking right now"); +    } +#endif +  } + +  // Pick best from BotCand and TopCand. +  assert(BotCand.isValid()); +  assert(TopCand.isValid()); +  SchedCandidate Cand = BotCand; +  TopCand.Reason = NoCand; +  tryCandidate(Cand, TopCand, nullptr); +  if (TopCand.Reason != NoCand) { +    Cand.setBest(TopCand); +    LLVM_DEBUG(traceCandidate(Cand)); +  } + +  IsTopNode = Cand.AtTop; +  tracePick(Cand); +  return Cand.SU; +} + +/// Pick the best node to balance the schedule. Implements MachineSchedStrategy. +SUnit *GenericScheduler::pickNode(bool &IsTopNode) { +  if (DAG->top() == DAG->bottom()) { +    assert(Top.Available.empty() && Top.Pending.empty() && +           Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage"); +    return nullptr; +  } +  SUnit *SU; +  do { +    if (RegionPolicy.OnlyTopDown) { +      SU = Top.pickOnlyChoice(); +      if (!SU) { +        CandPolicy NoPolicy; +        TopCand.reset(NoPolicy); +        pickNodeFromQueue(Top, NoPolicy, DAG->getTopRPTracker(), TopCand); +        assert(TopCand.Reason != NoCand && "failed to find a candidate"); +        tracePick(TopCand); +        SU = TopCand.SU; +      } +      IsTopNode = true; +    } else if (RegionPolicy.OnlyBottomUp) { +      SU = Bot.pickOnlyChoice(); +      if (!SU) { +        CandPolicy NoPolicy; +        BotCand.reset(NoPolicy); +        pickNodeFromQueue(Bot, NoPolicy, DAG->getBotRPTracker(), BotCand); +        assert(BotCand.Reason != NoCand && "failed to find a candidate"); +        tracePick(BotCand); +        SU = BotCand.SU; +      } +      IsTopNode = false; +    } else { +      SU = pickNodeBidirectional(IsTopNode); +    } +  } while (SU->isScheduled); + +  if (SU->isTopReady()) +    Top.removeReady(SU); +  if (SU->isBottomReady()) +    Bot.removeReady(SU); + +  LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " +                    << *SU->getInstr()); +  return SU; +} + +void GenericScheduler::reschedulePhysReg(SUnit *SU, bool isTop) { +  MachineBasicBlock::iterator InsertPos = SU->getInstr(); +  if (!isTop) +    ++InsertPos; +  SmallVectorImpl<SDep> &Deps = isTop ? SU->Preds : SU->Succs; + +  // Find already scheduled copies with a single physreg dependence and move +  // them just above the scheduled instruction. +  for (SDep &Dep : Deps) { +    if (Dep.getKind() != SDep::Data || +        !Register::isPhysicalRegister(Dep.getReg())) +      continue; +    SUnit *DepSU = Dep.getSUnit(); +    if (isTop ? DepSU->Succs.size() > 1 : DepSU->Preds.size() > 1) +      continue; +    MachineInstr *Copy = DepSU->getInstr(); +    if (!Copy->isCopy() && !Copy->isMoveImmediate()) +      continue; +    LLVM_DEBUG(dbgs() << "  Rescheduling physreg copy "; +               DAG->dumpNode(*Dep.getSUnit())); +    DAG->moveInstruction(Copy, InsertPos); +  } +} + +/// Update the scheduler's state after scheduling a node. This is the same node +/// that was just returned by pickNode(). However, ScheduleDAGMILive needs to +/// update it's state based on the current cycle before MachineSchedStrategy +/// does. +/// +/// FIXME: Eventually, we may bundle physreg copies rather than rescheduling +/// them here. See comments in biasPhysReg. +void GenericScheduler::schedNode(SUnit *SU, bool IsTopNode) { +  if (IsTopNode) { +    SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.getCurrCycle()); +    Top.bumpNode(SU); +    if (SU->hasPhysRegUses) +      reschedulePhysReg(SU, true); +  } else { +    SU->BotReadyCycle = std::max(SU->BotReadyCycle, Bot.getCurrCycle()); +    Bot.bumpNode(SU); +    if (SU->hasPhysRegDefs) +      reschedulePhysReg(SU, false); +  } +} + +/// Create the standard converging machine scheduler. This will be used as the +/// default scheduler if the target does not set a default. +ScheduleDAGMILive *llvm::createGenericSchedLive(MachineSchedContext *C) { +  ScheduleDAGMILive *DAG = +      new ScheduleDAGMILive(C, std::make_unique<GenericScheduler>(C)); +  // Register DAG post-processors. +  // +  // FIXME: extend the mutation API to allow earlier mutations to instantiate +  // data and pass it to later mutations. Have a single mutation that gathers +  // the interesting nodes in one pass. +  DAG->addMutation(createCopyConstrainDAGMutation(DAG->TII, DAG->TRI)); +  return DAG; +} +  static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C) { -  return createGenericSchedLive(C);  -}  -  -static MachineSchedRegistry  -GenericSchedRegistry("converge", "Standard converging scheduler.",  +  return createGenericSchedLive(C); +} + +static MachineSchedRegistry +GenericSchedRegistry("converge", "Standard converging scheduler.",                       createConvergingSched); -  -//===----------------------------------------------------------------------===//  -// PostGenericScheduler - Generic PostRA implementation of MachineSchedStrategy.  -//===----------------------------------------------------------------------===//  -  -void PostGenericScheduler::initialize(ScheduleDAGMI *Dag) {  -  DAG = Dag;  -  SchedModel = DAG->getSchedModel();  -  TRI = DAG->TRI;  -  -  Rem.init(DAG, SchedModel);  -  Top.init(DAG, SchedModel, &Rem);  -  BotRoots.clear();  -  -  // Initialize the HazardRecognizers. If itineraries don't exist, are empty,  -  // or are disabled, then these HazardRecs will be disabled.  -  const InstrItineraryData *Itin = SchedModel->getInstrItineraries();  -  if (!Top.HazardRec) {  -    Top.HazardRec =  -        DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(  -            Itin, DAG);  -  }  -}  -  -void PostGenericScheduler::registerRoots() {  -  Rem.CriticalPath = DAG->ExitSU.getDepth();  -  -  // Some roots may not feed into ExitSU. Check all of them in case.  -  for (const SUnit *SU : BotRoots) {  -    if (SU->getDepth() > Rem.CriticalPath)  -      Rem.CriticalPath = SU->getDepth();  -  }  -  LLVM_DEBUG(dbgs() << "Critical Path: (PGS-RR) " << Rem.CriticalPath << '\n');  -  if (DumpCriticalPathLength) {  -    errs() << "Critical Path(PGS-RR ): " << Rem.CriticalPath << " \n";  -  }  -}  -  -/// Apply a set of heuristics to a new candidate for PostRA scheduling.  -///  -/// \param Cand provides the policy and current best candidate.  -/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.  -void PostGenericScheduler::tryCandidate(SchedCandidate &Cand,  -                                        SchedCandidate &TryCand) {  -  // Initialize the candidate if needed.  -  if (!Cand.isValid()) {  -    TryCand.Reason = NodeOrder;  -    return;  -  }  -  -  // Prioritize instructions that read unbuffered resources by stall cycles.  -  if (tryLess(Top.getLatencyStallCycles(TryCand.SU),  -              Top.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))  -    return;  -  -  // Keep clustered nodes together.  -  if (tryGreater(TryCand.SU == DAG->getNextClusterSucc(),  -                 Cand.SU == DAG->getNextClusterSucc(),  -                 TryCand, Cand, Cluster))  -    return;  -  -  // Avoid critical resource consumption and balance the schedule.  -  if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,  -              TryCand, Cand, ResourceReduce))  -    return;  -  if (tryGreater(TryCand.ResDelta.DemandedResources,  -                 Cand.ResDelta.DemandedResources,  -                 TryCand, Cand, ResourceDemand))  -    return;  -  -  // Avoid serializing long latency dependence chains.  -  if (Cand.Policy.ReduceLatency && tryLatency(TryCand, Cand, Top)) {  -    return;  -  }  -  -  // Fall through to original instruction order.  -  if (TryCand.SU->NodeNum < Cand.SU->NodeNum)  -    TryCand.Reason = NodeOrder;  -}  -  -void PostGenericScheduler::pickNodeFromQueue(SchedCandidate &Cand) {  -  ReadyQueue &Q = Top.Available;  -  for (SUnit *SU : Q) {  -    SchedCandidate TryCand(Cand.Policy);  -    TryCand.SU = SU;  -    TryCand.AtTop = true;  -    TryCand.initResourceDelta(DAG, SchedModel);  -    tryCandidate(Cand, TryCand);  -    if (TryCand.Reason != NoCand) {  -      Cand.setBest(TryCand);  -      LLVM_DEBUG(traceCandidate(Cand));  -    }  -  }  -}  -  -/// Pick the next node to schedule.  -SUnit *PostGenericScheduler::pickNode(bool &IsTopNode) {  -  if (DAG->top() == DAG->bottom()) {  -    assert(Top.Available.empty() && Top.Pending.empty() && "ReadyQ garbage");  -    return nullptr;  -  }  -  SUnit *SU;  -  do {  -    SU = Top.pickOnlyChoice();  -    if (SU) {  -      tracePick(Only1, true);  -    } else {  -      CandPolicy NoPolicy;  -      SchedCandidate TopCand(NoPolicy);  -      // Set the top-down policy based on the state of the current top zone and  -      // the instructions outside the zone, including the bottom zone.  -      setPolicy(TopCand.Policy, /*IsPostRA=*/true, Top, nullptr);  -      pickNodeFromQueue(TopCand);  -      assert(TopCand.Reason != NoCand && "failed to find a candidate");  -      tracePick(TopCand);  -      SU = TopCand.SU;  -    }  -  } while (SU->isScheduled);  -  -  IsTopNode = true;  -  Top.removeReady(SU);  -  -  LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "  -                    << *SU->getInstr());  -  return SU;  -}  -  -/// Called after ScheduleDAGMI has scheduled an instruction and updated  -/// scheduled/remaining flags in the DAG nodes.  -void PostGenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {  -  SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.getCurrCycle());  -  Top.bumpNode(SU);  -}  -  -ScheduleDAGMI *llvm::createGenericSchedPostRA(MachineSchedContext *C) {  -  return new ScheduleDAGMI(C, std::make_unique<PostGenericScheduler>(C),  -                           /*RemoveKillFlags=*/true);  -}  -  -//===----------------------------------------------------------------------===//  -// ILP Scheduler. Currently for experimental analysis of heuristics.  -//===----------------------------------------------------------------------===//  -  -namespace {  -  -/// Order nodes by the ILP metric.  -struct ILPOrder {  -  const SchedDFSResult *DFSResult = nullptr;  -  const BitVector *ScheduledTrees = nullptr;  -  bool MaximizeILP;  -  -  ILPOrder(bool MaxILP) : MaximizeILP(MaxILP) {}  -  -  /// Apply a less-than relation on node priority.  -  ///  -  /// (Return true if A comes after B in the Q.)  -  bool operator()(const SUnit *A, const SUnit *B) const {  -    unsigned SchedTreeA = DFSResult->getSubtreeID(A);  -    unsigned SchedTreeB = DFSResult->getSubtreeID(B);  -    if (SchedTreeA != SchedTreeB) {  -      // Unscheduled trees have lower priority.  -      if (ScheduledTrees->test(SchedTreeA) != ScheduledTrees->test(SchedTreeB))  -        return ScheduledTrees->test(SchedTreeB);  -  -      // Trees with shallower connections have have lower priority.  -      if (DFSResult->getSubtreeLevel(SchedTreeA)  -          != DFSResult->getSubtreeLevel(SchedTreeB)) {  -        return DFSResult->getSubtreeLevel(SchedTreeA)  -          < DFSResult->getSubtreeLevel(SchedTreeB);  -      }  -    }  -    if (MaximizeILP)  -      return DFSResult->getILP(A) < DFSResult->getILP(B);  -    else  -      return DFSResult->getILP(A) > DFSResult->getILP(B);  -  }  -};  -  -/// Schedule based on the ILP metric.  -class ILPScheduler : public MachineSchedStrategy {  -  ScheduleDAGMILive *DAG = nullptr;  -  ILPOrder Cmp;  -  -  std::vector<SUnit*> ReadyQ;  -  -public:  -  ILPScheduler(bool MaximizeILP) : Cmp(MaximizeILP) {}  -  -  void initialize(ScheduleDAGMI *dag) override {  -    assert(dag->hasVRegLiveness() && "ILPScheduler needs vreg liveness");  -    DAG = static_cast<ScheduleDAGMILive*>(dag);  -    DAG->computeDFSResult();  -    Cmp.DFSResult = DAG->getDFSResult();  -    Cmp.ScheduledTrees = &DAG->getScheduledTrees();  -    ReadyQ.clear();  -  }  -  -  void registerRoots() override {  -    // Restore the heap in ReadyQ with the updated DFS results.  -    std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);  -  }  -  -  /// Implement MachineSchedStrategy interface.  -  /// -----------------------------------------  -  -  /// Callback to select the highest priority node from the ready Q.  -  SUnit *pickNode(bool &IsTopNode) override {  -    if (ReadyQ.empty()) return nullptr;  -    std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);  -    SUnit *SU = ReadyQ.back();  -    ReadyQ.pop_back();  -    IsTopNode = false;  -    LLVM_DEBUG(dbgs() << "Pick node "  -                      << "SU(" << SU->NodeNum << ") "  -                      << " ILP: " << DAG->getDFSResult()->getILP(SU)  -                      << " Tree: " << DAG->getDFSResult()->getSubtreeID(SU)  -                      << " @"  -                      << DAG->getDFSResult()->getSubtreeLevel(  -                             DAG->getDFSResult()->getSubtreeID(SU))  -                      << '\n'  -                      << "Scheduling " << *SU->getInstr());  -    return SU;  -  }  -  -  /// Scheduler callback to notify that a new subtree is scheduled.  -  void scheduleTree(unsigned SubtreeID) override {  -    std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);  -  }  -  -  /// Callback after a node is scheduled. Mark a newly scheduled tree, notify  -  /// DFSResults, and resort the priority Q.  -  void schedNode(SUnit *SU, bool IsTopNode) override {  -    assert(!IsTopNode && "SchedDFSResult needs bottom-up");  -  }  -  -  void releaseTopNode(SUnit *) override { /*only called for top roots*/ }  -  -  void releaseBottomNode(SUnit *SU) override {  -    ReadyQ.push_back(SU);  -    std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);  -  }  -};  -  -} // end anonymous namespace  -  -static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) {  -  return new ScheduleDAGMILive(C, std::make_unique<ILPScheduler>(true));  -}  -static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) {  -  return new ScheduleDAGMILive(C, std::make_unique<ILPScheduler>(false));  -}  -  -static MachineSchedRegistry ILPMaxRegistry(  -  "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler);  -static MachineSchedRegistry ILPMinRegistry(  -  "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler);  -  -//===----------------------------------------------------------------------===//  -// Machine Instruction Shuffler for Correctness Testing  -//===----------------------------------------------------------------------===//  -  -#ifndef NDEBUG  -namespace {  -  -/// Apply a less-than relation on the node order, which corresponds to the  -/// instruction order prior to scheduling. IsReverse implements greater-than.  -template<bool IsReverse>  -struct SUnitOrder {  -  bool operator()(SUnit *A, SUnit *B) const {  -    if (IsReverse)  -      return A->NodeNum > B->NodeNum;  -    else  -      return A->NodeNum < B->NodeNum;  -  }  -};  -  -/// Reorder instructions as much as possible.  -class InstructionShuffler : public MachineSchedStrategy {  -  bool IsAlternating;  -  bool IsTopDown;  -  -  // Using a less-than relation (SUnitOrder<false>) for the TopQ priority  -  // gives nodes with a higher number higher priority causing the latest  -  // instructions to be scheduled first.  -  PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false>>  -    TopQ;  -  -  // When scheduling bottom-up, use greater-than as the queue priority.  -  PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true>>  -    BottomQ;  -  -public:  -  InstructionShuffler(bool alternate, bool topdown)  -    : IsAlternating(alternate), IsTopDown(topdown) {}  -  -  void initialize(ScheduleDAGMI*) override {  -    TopQ.clear();  -    BottomQ.clear();  -  }  -  -  /// Implement MachineSchedStrategy interface.  -  /// -----------------------------------------  -  -  SUnit *pickNode(bool &IsTopNode) override {  -    SUnit *SU;  -    if (IsTopDown) {  -      do {  -        if (TopQ.empty()) return nullptr;  -        SU = TopQ.top();  -        TopQ.pop();  -      } while (SU->isScheduled);  -      IsTopNode = true;  -    } else {  -      do {  -        if (BottomQ.empty()) return nullptr;  -        SU = BottomQ.top();  -        BottomQ.pop();  -      } while (SU->isScheduled);  -      IsTopNode = false;  -    }  -    if (IsAlternating)  -      IsTopDown = !IsTopDown;  -    return SU;  -  }  -  -  void schedNode(SUnit *SU, bool IsTopNode) override {}  -  -  void releaseTopNode(SUnit *SU) override {  -    TopQ.push(SU);  -  }  -  void releaseBottomNode(SUnit *SU) override {  -    BottomQ.push(SU);  -  }  -};  -  -} // end anonymous namespace  -  -static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) {  -  bool Alternate = !ForceTopDown && !ForceBottomUp;  -  bool TopDown = !ForceBottomUp;  -  assert((TopDown || !ForceTopDown) &&  -         "-misched-topdown incompatible with -misched-bottomup");  -  return new ScheduleDAGMILive(  -      C, std::make_unique<InstructionShuffler>(Alternate, TopDown));  -}  -  -static MachineSchedRegistry ShufflerRegistry(  -  "shuffle", "Shuffle machine instructions alternating directions",  -  createInstructionShuffler);  -#endif // !NDEBUG  -  -//===----------------------------------------------------------------------===//  -// GraphWriter support for ScheduleDAGMILive.  -//===----------------------------------------------------------------------===//  -  -#ifndef NDEBUG  -namespace llvm {  -  -template<> struct GraphTraits<  -  ScheduleDAGMI*> : public GraphTraits<ScheduleDAG*> {};  -  -template<>  -struct DOTGraphTraits<ScheduleDAGMI*> : public DefaultDOTGraphTraits {  -  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}  -  -  static std::string getGraphName(const ScheduleDAG *G) {  -    return std::string(G->MF.getName());  -  }  -  -  static bool renderGraphFromBottomUp() {  -    return true;  -  }  -  + +//===----------------------------------------------------------------------===// +// PostGenericScheduler - Generic PostRA implementation of MachineSchedStrategy. +//===----------------------------------------------------------------------===// + +void PostGenericScheduler::initialize(ScheduleDAGMI *Dag) { +  DAG = Dag; +  SchedModel = DAG->getSchedModel(); +  TRI = DAG->TRI; + +  Rem.init(DAG, SchedModel); +  Top.init(DAG, SchedModel, &Rem); +  BotRoots.clear(); + +  // Initialize the HazardRecognizers. If itineraries don't exist, are empty, +  // or are disabled, then these HazardRecs will be disabled. +  const InstrItineraryData *Itin = SchedModel->getInstrItineraries(); +  if (!Top.HazardRec) { +    Top.HazardRec = +        DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer( +            Itin, DAG); +  } +} + +void PostGenericScheduler::registerRoots() { +  Rem.CriticalPath = DAG->ExitSU.getDepth(); + +  // Some roots may not feed into ExitSU. Check all of them in case. +  for (const SUnit *SU : BotRoots) { +    if (SU->getDepth() > Rem.CriticalPath) +      Rem.CriticalPath = SU->getDepth(); +  } +  LLVM_DEBUG(dbgs() << "Critical Path: (PGS-RR) " << Rem.CriticalPath << '\n'); +  if (DumpCriticalPathLength) { +    errs() << "Critical Path(PGS-RR ): " << Rem.CriticalPath << " \n"; +  } +} + +/// Apply a set of heuristics to a new candidate for PostRA scheduling. +/// +/// \param Cand provides the policy and current best candidate. +/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized. +void PostGenericScheduler::tryCandidate(SchedCandidate &Cand, +                                        SchedCandidate &TryCand) { +  // Initialize the candidate if needed. +  if (!Cand.isValid()) { +    TryCand.Reason = NodeOrder; +    return; +  } + +  // Prioritize instructions that read unbuffered resources by stall cycles. +  if (tryLess(Top.getLatencyStallCycles(TryCand.SU), +              Top.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall)) +    return; + +  // Keep clustered nodes together. +  if (tryGreater(TryCand.SU == DAG->getNextClusterSucc(), +                 Cand.SU == DAG->getNextClusterSucc(), +                 TryCand, Cand, Cluster)) +    return; + +  // Avoid critical resource consumption and balance the schedule. +  if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources, +              TryCand, Cand, ResourceReduce)) +    return; +  if (tryGreater(TryCand.ResDelta.DemandedResources, +                 Cand.ResDelta.DemandedResources, +                 TryCand, Cand, ResourceDemand)) +    return; + +  // Avoid serializing long latency dependence chains. +  if (Cand.Policy.ReduceLatency && tryLatency(TryCand, Cand, Top)) { +    return; +  } + +  // Fall through to original instruction order. +  if (TryCand.SU->NodeNum < Cand.SU->NodeNum) +    TryCand.Reason = NodeOrder; +} + +void PostGenericScheduler::pickNodeFromQueue(SchedCandidate &Cand) { +  ReadyQueue &Q = Top.Available; +  for (SUnit *SU : Q) { +    SchedCandidate TryCand(Cand.Policy); +    TryCand.SU = SU; +    TryCand.AtTop = true; +    TryCand.initResourceDelta(DAG, SchedModel); +    tryCandidate(Cand, TryCand); +    if (TryCand.Reason != NoCand) { +      Cand.setBest(TryCand); +      LLVM_DEBUG(traceCandidate(Cand)); +    } +  } +} + +/// Pick the next node to schedule. +SUnit *PostGenericScheduler::pickNode(bool &IsTopNode) { +  if (DAG->top() == DAG->bottom()) { +    assert(Top.Available.empty() && Top.Pending.empty() && "ReadyQ garbage"); +    return nullptr; +  } +  SUnit *SU; +  do { +    SU = Top.pickOnlyChoice(); +    if (SU) { +      tracePick(Only1, true); +    } else { +      CandPolicy NoPolicy; +      SchedCandidate TopCand(NoPolicy); +      // Set the top-down policy based on the state of the current top zone and +      // the instructions outside the zone, including the bottom zone. +      setPolicy(TopCand.Policy, /*IsPostRA=*/true, Top, nullptr); +      pickNodeFromQueue(TopCand); +      assert(TopCand.Reason != NoCand && "failed to find a candidate"); +      tracePick(TopCand); +      SU = TopCand.SU; +    } +  } while (SU->isScheduled); + +  IsTopNode = true; +  Top.removeReady(SU); + +  LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " +                    << *SU->getInstr()); +  return SU; +} + +/// Called after ScheduleDAGMI has scheduled an instruction and updated +/// scheduled/remaining flags in the DAG nodes. +void PostGenericScheduler::schedNode(SUnit *SU, bool IsTopNode) { +  SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.getCurrCycle()); +  Top.bumpNode(SU); +} + +ScheduleDAGMI *llvm::createGenericSchedPostRA(MachineSchedContext *C) { +  return new ScheduleDAGMI(C, std::make_unique<PostGenericScheduler>(C), +                           /*RemoveKillFlags=*/true); +} + +//===----------------------------------------------------------------------===// +// ILP Scheduler. Currently for experimental analysis of heuristics. +//===----------------------------------------------------------------------===// + +namespace { + +/// Order nodes by the ILP metric. +struct ILPOrder { +  const SchedDFSResult *DFSResult = nullptr; +  const BitVector *ScheduledTrees = nullptr; +  bool MaximizeILP; + +  ILPOrder(bool MaxILP) : MaximizeILP(MaxILP) {} + +  /// Apply a less-than relation on node priority. +  /// +  /// (Return true if A comes after B in the Q.) +  bool operator()(const SUnit *A, const SUnit *B) const { +    unsigned SchedTreeA = DFSResult->getSubtreeID(A); +    unsigned SchedTreeB = DFSResult->getSubtreeID(B); +    if (SchedTreeA != SchedTreeB) { +      // Unscheduled trees have lower priority. +      if (ScheduledTrees->test(SchedTreeA) != ScheduledTrees->test(SchedTreeB)) +        return ScheduledTrees->test(SchedTreeB); + +      // Trees with shallower connections have have lower priority. +      if (DFSResult->getSubtreeLevel(SchedTreeA) +          != DFSResult->getSubtreeLevel(SchedTreeB)) { +        return DFSResult->getSubtreeLevel(SchedTreeA) +          < DFSResult->getSubtreeLevel(SchedTreeB); +      } +    } +    if (MaximizeILP) +      return DFSResult->getILP(A) < DFSResult->getILP(B); +    else +      return DFSResult->getILP(A) > DFSResult->getILP(B); +  } +}; + +/// Schedule based on the ILP metric. +class ILPScheduler : public MachineSchedStrategy { +  ScheduleDAGMILive *DAG = nullptr; +  ILPOrder Cmp; + +  std::vector<SUnit*> ReadyQ; + +public: +  ILPScheduler(bool MaximizeILP) : Cmp(MaximizeILP) {} + +  void initialize(ScheduleDAGMI *dag) override { +    assert(dag->hasVRegLiveness() && "ILPScheduler needs vreg liveness"); +    DAG = static_cast<ScheduleDAGMILive*>(dag); +    DAG->computeDFSResult(); +    Cmp.DFSResult = DAG->getDFSResult(); +    Cmp.ScheduledTrees = &DAG->getScheduledTrees(); +    ReadyQ.clear(); +  } + +  void registerRoots() override { +    // Restore the heap in ReadyQ with the updated DFS results. +    std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); +  } + +  /// Implement MachineSchedStrategy interface. +  /// ----------------------------------------- + +  /// Callback to select the highest priority node from the ready Q. +  SUnit *pickNode(bool &IsTopNode) override { +    if (ReadyQ.empty()) return nullptr; +    std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); +    SUnit *SU = ReadyQ.back(); +    ReadyQ.pop_back(); +    IsTopNode = false; +    LLVM_DEBUG(dbgs() << "Pick node " +                      << "SU(" << SU->NodeNum << ") " +                      << " ILP: " << DAG->getDFSResult()->getILP(SU) +                      << " Tree: " << DAG->getDFSResult()->getSubtreeID(SU) +                      << " @" +                      << DAG->getDFSResult()->getSubtreeLevel( +                             DAG->getDFSResult()->getSubtreeID(SU)) +                      << '\n' +                      << "Scheduling " << *SU->getInstr()); +    return SU; +  } + +  /// Scheduler callback to notify that a new subtree is scheduled. +  void scheduleTree(unsigned SubtreeID) override { +    std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); +  } + +  /// Callback after a node is scheduled. Mark a newly scheduled tree, notify +  /// DFSResults, and resort the priority Q. +  void schedNode(SUnit *SU, bool IsTopNode) override { +    assert(!IsTopNode && "SchedDFSResult needs bottom-up"); +  } + +  void releaseTopNode(SUnit *) override { /*only called for top roots*/ } + +  void releaseBottomNode(SUnit *SU) override { +    ReadyQ.push_back(SU); +    std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); +  } +}; + +} // end anonymous namespace + +static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) { +  return new ScheduleDAGMILive(C, std::make_unique<ILPScheduler>(true)); +} +static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) { +  return new ScheduleDAGMILive(C, std::make_unique<ILPScheduler>(false)); +} + +static MachineSchedRegistry ILPMaxRegistry( +  "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler); +static MachineSchedRegistry ILPMinRegistry( +  "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler); + +//===----------------------------------------------------------------------===// +// Machine Instruction Shuffler for Correctness Testing +//===----------------------------------------------------------------------===// + +#ifndef NDEBUG +namespace { + +/// Apply a less-than relation on the node order, which corresponds to the +/// instruction order prior to scheduling. IsReverse implements greater-than. +template<bool IsReverse> +struct SUnitOrder { +  bool operator()(SUnit *A, SUnit *B) const { +    if (IsReverse) +      return A->NodeNum > B->NodeNum; +    else +      return A->NodeNum < B->NodeNum; +  } +}; + +/// Reorder instructions as much as possible. +class InstructionShuffler : public MachineSchedStrategy { +  bool IsAlternating; +  bool IsTopDown; + +  // Using a less-than relation (SUnitOrder<false>) for the TopQ priority +  // gives nodes with a higher number higher priority causing the latest +  // instructions to be scheduled first. +  PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false>> +    TopQ; + +  // When scheduling bottom-up, use greater-than as the queue priority. +  PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true>> +    BottomQ; + +public: +  InstructionShuffler(bool alternate, bool topdown) +    : IsAlternating(alternate), IsTopDown(topdown) {} + +  void initialize(ScheduleDAGMI*) override { +    TopQ.clear(); +    BottomQ.clear(); +  } + +  /// Implement MachineSchedStrategy interface. +  /// ----------------------------------------- + +  SUnit *pickNode(bool &IsTopNode) override { +    SUnit *SU; +    if (IsTopDown) { +      do { +        if (TopQ.empty()) return nullptr; +        SU = TopQ.top(); +        TopQ.pop(); +      } while (SU->isScheduled); +      IsTopNode = true; +    } else { +      do { +        if (BottomQ.empty()) return nullptr; +        SU = BottomQ.top(); +        BottomQ.pop(); +      } while (SU->isScheduled); +      IsTopNode = false; +    } +    if (IsAlternating) +      IsTopDown = !IsTopDown; +    return SU; +  } + +  void schedNode(SUnit *SU, bool IsTopNode) override {} + +  void releaseTopNode(SUnit *SU) override { +    TopQ.push(SU); +  } +  void releaseBottomNode(SUnit *SU) override { +    BottomQ.push(SU); +  } +}; + +} // end anonymous namespace + +static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) { +  bool Alternate = !ForceTopDown && !ForceBottomUp; +  bool TopDown = !ForceBottomUp; +  assert((TopDown || !ForceTopDown) && +         "-misched-topdown incompatible with -misched-bottomup"); +  return new ScheduleDAGMILive( +      C, std::make_unique<InstructionShuffler>(Alternate, TopDown)); +} + +static MachineSchedRegistry ShufflerRegistry( +  "shuffle", "Shuffle machine instructions alternating directions", +  createInstructionShuffler); +#endif // !NDEBUG + +//===----------------------------------------------------------------------===// +// GraphWriter support for ScheduleDAGMILive. +//===----------------------------------------------------------------------===// + +#ifndef NDEBUG +namespace llvm { + +template<> struct GraphTraits< +  ScheduleDAGMI*> : public GraphTraits<ScheduleDAG*> {}; + +template<> +struct DOTGraphTraits<ScheduleDAGMI*> : public DefaultDOTGraphTraits { +  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} + +  static std::string getGraphName(const ScheduleDAG *G) { +    return std::string(G->MF.getName()); +  } + +  static bool renderGraphFromBottomUp() { +    return true; +  } +    static bool isNodeHidden(const SUnit *Node, const ScheduleDAG *G) { -    if (ViewMISchedCutoff == 0)  -      return false;  -    return (Node->Preds.size() > ViewMISchedCutoff  -         || Node->Succs.size() > ViewMISchedCutoff);  -  }  -  -  /// If you want to override the dot attributes printed for a particular  -  /// edge, override this method.  -  static std::string getEdgeAttributes(const SUnit *Node,  -                                       SUnitIterator EI,  -                                       const ScheduleDAG *Graph) {  -    if (EI.isArtificialDep())  -      return "color=cyan,style=dashed";  -    if (EI.isCtrlDep())  -      return "color=blue,style=dashed";  -    return "";  -  }  -  -  static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G) {  -    std::string Str;  -    raw_string_ostream SS(Str);  -    const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);  -    const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?  -      static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;  -    SS << "SU:" << SU->NodeNum;  -    if (DFS)  -      SS << " I:" << DFS->getNumInstrs(SU);  -    return SS.str();  -  }  -  -  static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G) {  -    return G->getGraphNodeLabel(SU);  -  }  -  -  static std::string getNodeAttributes(const SUnit *N, const ScheduleDAG *G) {  -    std::string Str("shape=Mrecord");  -    const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);  -    const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?  -      static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;  -    if (DFS) {  -      Str += ",style=filled,fillcolor=\"#";  -      Str += DOT::getColorString(DFS->getSubtreeID(N));  -      Str += '"';  -    }  -    return Str;  -  }  -};  -  -} // end namespace llvm  -#endif // NDEBUG  -  -/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG  -/// rendered using 'dot'.  -void ScheduleDAGMI::viewGraph(const Twine &Name, const Twine &Title) {  -#ifndef NDEBUG  -  ViewGraph(this, Name, false, Title);  -#else  -  errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on "  -         << "systems with Graphviz or gv!\n";  -#endif  // NDEBUG  -}  -  -/// Out-of-line implementation with no arguments is handy for gdb.  -void ScheduleDAGMI::viewGraph() {  -  viewGraph(getDAGName(), "Scheduling-Units Graph for " + getDAGName());  -}  +    if (ViewMISchedCutoff == 0) +      return false; +    return (Node->Preds.size() > ViewMISchedCutoff +         || Node->Succs.size() > ViewMISchedCutoff); +  } + +  /// If you want to override the dot attributes printed for a particular +  /// edge, override this method. +  static std::string getEdgeAttributes(const SUnit *Node, +                                       SUnitIterator EI, +                                       const ScheduleDAG *Graph) { +    if (EI.isArtificialDep()) +      return "color=cyan,style=dashed"; +    if (EI.isCtrlDep()) +      return "color=blue,style=dashed"; +    return ""; +  } + +  static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G) { +    std::string Str; +    raw_string_ostream SS(Str); +    const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G); +    const SchedDFSResult *DFS = DAG->hasVRegLiveness() ? +      static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr; +    SS << "SU:" << SU->NodeNum; +    if (DFS) +      SS << " I:" << DFS->getNumInstrs(SU); +    return SS.str(); +  } + +  static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G) { +    return G->getGraphNodeLabel(SU); +  } + +  static std::string getNodeAttributes(const SUnit *N, const ScheduleDAG *G) { +    std::string Str("shape=Mrecord"); +    const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G); +    const SchedDFSResult *DFS = DAG->hasVRegLiveness() ? +      static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr; +    if (DFS) { +      Str += ",style=filled,fillcolor=\"#"; +      Str += DOT::getColorString(DFS->getSubtreeID(N)); +      Str += '"'; +    } +    return Str; +  } +}; + +} // end namespace llvm +#endif // NDEBUG + +/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG +/// rendered using 'dot'. +void ScheduleDAGMI::viewGraph(const Twine &Name, const Twine &Title) { +#ifndef NDEBUG +  ViewGraph(this, Name, false, Title); +#else +  errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on " +         << "systems with Graphviz or gv!\n"; +#endif  // NDEBUG +} + +/// Out-of-line implementation with no arguments is handy for gdb. +void ScheduleDAGMI::viewGraph() { +  viewGraph(getDAGName(), "Scheduling-Units Graph for " + getDAGName()); +}  | 
