LCOV - code coverage report
Current view: top level - lib/CodeGen - PostRASchedulerList.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 187 194 96.4 %
Date: 2018-02-19 03:08:00 Functions: 20 25 80.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===----- SchedulePostRAList.cpp - list scheduler ------------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This implements a top-down list scheduler, using standard algorithms.
      11             : // The basic approach uses a priority queue of available nodes to schedule.
      12             : // One at a time, nodes are taken from the priority queue (thus in priority
      13             : // order), checked for legality to schedule, and emitted if legal.
      14             : //
      15             : // Nodes may not be legal to schedule either due to structural hazards (e.g.
      16             : // pipeline or resource constraints) or because an input to the instruction has
      17             : // not completed execution.
      18             : //
      19             : //===----------------------------------------------------------------------===//
      20             : 
      21             : #include "AggressiveAntiDepBreaker.h"
      22             : #include "AntiDepBreaker.h"
      23             : #include "CriticalAntiDepBreaker.h"
      24             : #include "llvm/ADT/Statistic.h"
      25             : #include "llvm/Analysis/AliasAnalysis.h"
      26             : #include "llvm/CodeGen/LatencyPriorityQueue.h"
      27             : #include "llvm/CodeGen/MachineDominators.h"
      28             : #include "llvm/CodeGen/MachineFunctionPass.h"
      29             : #include "llvm/CodeGen/MachineLoopInfo.h"
      30             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      31             : #include "llvm/CodeGen/Passes.h"
      32             : #include "llvm/CodeGen/RegisterClassInfo.h"
      33             : #include "llvm/CodeGen/ScheduleDAGInstrs.h"
      34             : #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
      35             : #include "llvm/CodeGen/SchedulerRegistry.h"
      36             : #include "llvm/CodeGen/TargetInstrInfo.h"
      37             : #include "llvm/CodeGen/TargetLowering.h"
      38             : #include "llvm/CodeGen/TargetPassConfig.h"
      39             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      40             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      41             : #include "llvm/Support/CommandLine.h"
      42             : #include "llvm/Support/Debug.h"
      43             : #include "llvm/Support/ErrorHandling.h"
      44             : #include "llvm/Support/raw_ostream.h"
      45             : using namespace llvm;
      46             : 
      47             : #define DEBUG_TYPE "post-RA-sched"
      48             : 
      49             : STATISTIC(NumNoops, "Number of noops inserted");
      50             : STATISTIC(NumStalls, "Number of pipeline stalls");
      51             : STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies");
      52             : 
      53             : // Post-RA scheduling is enabled with
      54             : // TargetSubtargetInfo.enablePostRAScheduler(). This flag can be used to
      55             : // override the target.
      56             : static cl::opt<bool>
      57       97324 : EnablePostRAScheduler("post-RA-scheduler",
      58       97324 :                        cl::desc("Enable scheduling after register allocation"),
      59      291972 :                        cl::init(false), cl::Hidden);
      60             : static cl::opt<std::string>
      61       97324 : EnableAntiDepBreaking("break-anti-dependencies",
      62       97324 :                       cl::desc("Break post-RA scheduling anti-dependencies: "
      63             :                                "\"critical\", \"all\", or \"none\""),
      64      291972 :                       cl::init("none"), cl::Hidden);
      65             : 
      66             : // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
      67             : static cl::opt<int>
      68       97324 : DebugDiv("postra-sched-debugdiv",
      69       97324 :                       cl::desc("Debug control MBBs that are scheduled"),
      70      291972 :                       cl::init(0), cl::Hidden);
      71             : static cl::opt<int>
      72       97324 : DebugMod("postra-sched-debugmod",
      73       97324 :                       cl::desc("Debug control MBBs that are scheduled"),
      74      291972 :                       cl::init(0), cl::Hidden);
      75             : 
      76       15543 : AntiDepBreaker::~AntiDepBreaker() { }
      77             : 
      78             : namespace {
      79       15243 :   class PostRAScheduler : public MachineFunctionPass {
      80             :     const TargetInstrInfo *TII;
      81             :     RegisterClassInfo RegClassInfo;
      82             : 
      83             :   public:
      84             :     static char ID;
      85       15319 :     PostRAScheduler() : MachineFunctionPass(ID) {}
      86             : 
      87       15231 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
      88       15231 :       AU.setPreservesCFG();
      89             :       AU.addRequired<AAResultsWrapperPass>();
      90             :       AU.addRequired<TargetPassConfig>();
      91             :       AU.addRequired<MachineDominatorTree>();
      92             :       AU.addPreserved<MachineDominatorTree>();
      93             :       AU.addRequired<MachineLoopInfo>();
      94             :       AU.addPreserved<MachineLoopInfo>();
      95       15231 :       MachineFunctionPass::getAnalysisUsage(AU);
      96       15231 :     }
      97             : 
      98       15235 :     MachineFunctionProperties getRequiredProperties() const override {
      99       30470 :       return MachineFunctionProperties().set(
     100       15235 :           MachineFunctionProperties::Property::NoVRegs);
     101             :     }
     102             : 
     103             :     bool runOnMachineFunction(MachineFunction &Fn) override;
     104             : 
     105             :   private:
     106             :     bool enablePostRAScheduler(
     107             :         const TargetSubtargetInfo &ST, CodeGenOpt::Level OptLevel,
     108             :         TargetSubtargetInfo::AntiDepBreakMode &Mode,
     109             :         TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const;
     110             :   };
     111             :   char PostRAScheduler::ID = 0;
     112             : 
     113             :   class SchedulePostRATDList : public ScheduleDAGInstrs {
     114             :     /// AvailableQueue - The priority queue to use for the available SUnits.
     115             :     ///
     116             :     LatencyPriorityQueue AvailableQueue;
     117             : 
     118             :     /// PendingQueue - This contains all of the instructions whose operands have
     119             :     /// been issued, but their results are not ready yet (due to the latency of
     120             :     /// the operation).  Once the operands becomes available, the instruction is
     121             :     /// added to the AvailableQueue.
     122             :     std::vector<SUnit*> PendingQueue;
     123             : 
     124             :     /// HazardRec - The hazard recognizer to use.
     125             :     ScheduleHazardRecognizer *HazardRec;
     126             : 
     127             :     /// AntiDepBreak - Anti-dependence breaking object, or NULL if none
     128             :     AntiDepBreaker *AntiDepBreak;
     129             : 
     130             :     /// AA - AliasAnalysis for making memory reference queries.
     131             :     AliasAnalysis *AA;
     132             : 
     133             :     /// The schedule. Null SUnit*'s represent noop instructions.
     134             :     std::vector<SUnit*> Sequence;
     135             : 
     136             :     /// Ordered list of DAG postprocessing steps.
     137             :     std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
     138             : 
     139             :     /// The index in BB of RegionEnd.
     140             :     ///
     141             :     /// This is the instruction number from the top of the current block, not
     142             :     /// the SlotIndex. It is only used by the AntiDepBreaker.
     143             :     unsigned EndIndex;
     144             : 
     145             :   public:
     146             :     SchedulePostRATDList(
     147             :         MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
     148             :         const RegisterClassInfo &,
     149             :         TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
     150             :         SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs);
     151             : 
     152             :     ~SchedulePostRATDList() override;
     153             : 
     154             :     /// startBlock - Initialize register live-range state for scheduling in
     155             :     /// this block.
     156             :     ///
     157             :     void startBlock(MachineBasicBlock *BB) override;
     158             : 
     159             :     // Set the index of RegionEnd within the current BB.
     160      644280 :     void setEndIndex(unsigned EndIdx) { EndIndex = EndIdx; }
     161             : 
     162             :     /// Initialize the scheduler state for the next scheduling region.
     163             :     void enterRegion(MachineBasicBlock *bb,
     164             :                      MachineBasicBlock::iterator begin,
     165             :                      MachineBasicBlock::iterator end,
     166             :                      unsigned regioninstrs) override;
     167             : 
     168             :     /// Notify that the scheduler has finished scheduling the current region.
     169             :     void exitRegion() override;
     170             : 
     171             :     /// Schedule - Schedule the instruction range using list scheduling.
     172             :     ///
     173             :     void schedule() override;
     174             : 
     175             :     void EmitSchedule();
     176             : 
     177             :     /// Observe - Update liveness information to account for the current
     178             :     /// instruction, which will not be scheduled.
     179             :     ///
     180             :     void Observe(MachineInstr &MI, unsigned Count);
     181             : 
     182             :     /// finishBlock - Clean up register live-range state.
     183             :     ///
     184             :     void finishBlock() override;
     185             : 
     186             :   private:
     187             :     /// Apply each ScheduleDAGMutation step in order.
     188             :     void postprocessDAG();
     189             : 
     190             :     void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
     191             :     void ReleaseSuccessors(SUnit *SU);
     192             :     void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
     193             :     void ListScheduleTopDown();
     194             : 
     195             :     void dumpSchedule() const;
     196             :     void emitNoop(unsigned CurCycle);
     197             :   };
     198             : }
     199             : 
     200             : char &llvm::PostRASchedulerID = PostRAScheduler::ID;
     201             : 
     202      134326 : INITIALIZE_PASS(PostRAScheduler, DEBUG_TYPE,
     203             :                 "Post RA top-down list latency scheduler", false, false)
     204             : 
     205       38714 : SchedulePostRATDList::SchedulePostRATDList(
     206             :     MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
     207             :     const RegisterClassInfo &RCI,
     208             :     TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
     209       38714 :     SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs)
     210      154856 :     : ScheduleDAGInstrs(MF, &MLI), AA(AA), EndIndex(0) {
     211             : 
     212             :   const InstrItineraryData *InstrItins =
     213       38714 :       MF.getSubtarget().getInstrItineraryData();
     214       38714 :   HazardRec =
     215       77428 :       MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(
     216       38714 :           InstrItins, this);
     217       38714 :   MF.getSubtarget().getPostRAMutations(Mutations);
     218             : 
     219             :   assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE ||
     220             :           MRI.tracksLiveness()) &&
     221             :          "Live-ins must be accurate for anti-dependency breaking");
     222       38714 :   AntiDepBreak =
     223       38714 :     ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ?
     224        9595 :      (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) :
     225       29119 :      ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ?
     226        5948 :       (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : nullptr));
     227       38714 : }
     228             : 
     229      116142 : SchedulePostRATDList::~SchedulePostRATDList() {
     230       38714 :   delete HazardRec;
     231       38714 :   delete AntiDepBreak;
     232       38714 : }
     233             : 
     234             : /// Initialize state associated with the next scheduling region.
     235           0 : void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb,
     236             :                  MachineBasicBlock::iterator begin,
     237             :                  MachineBasicBlock::iterator end,
     238             :                  unsigned regioninstrs) {
     239      644280 :   ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);
     240             :   Sequence.clear();
     241           0 : }
     242             : 
     243             : /// Print the schedule before exiting the region.
     244           0 : void SchedulePostRATDList::exitRegion() {
     245             :   DEBUG({
     246             :       dbgs() << "*** Final schedule ***\n";
     247             :       dumpSchedule();
     248             :       dbgs() << '\n';
     249             :     });
     250      644280 :   ScheduleDAGInstrs::exitRegion();
     251           0 : }
     252             : 
     253             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     254             : /// dumpSchedule - dump the scheduled Sequence.
     255             : LLVM_DUMP_METHOD void SchedulePostRATDList::dumpSchedule() const {
     256             :   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
     257             :     if (SUnit *SU = Sequence[i])
     258             :       SU->dump(this);
     259             :     else
     260             :       dbgs() << "**** NOOP ****\n";
     261             :   }
     262             : }
     263             : #endif
     264             : 
     265      139022 : bool PostRAScheduler::enablePostRAScheduler(
     266             :     const TargetSubtargetInfo &ST,
     267             :     CodeGenOpt::Level OptLevel,
     268             :     TargetSubtargetInfo::AntiDepBreakMode &Mode,
     269             :     TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const {
     270      139022 :   Mode = ST.getAntiDepBreakMode();
     271      139022 :   ST.getCriticalPathRCs(CriticalPathRCs);
     272             : 
     273             :   // Check for explicit enable/disable of post-ra scheduling.
     274      139022 :   if (EnablePostRAScheduler.getPosition() > 0)
     275             :     return EnablePostRAScheduler;
     276             : 
     277      189933 :   return ST.enablePostRAScheduler() &&
     278       50959 :          OptLevel >= ST.getOptLevelToEnablePostRAScheduler();
     279             : }
     280             : 
     281      139132 : bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) {
     282      139132 :   if (skipFunction(Fn.getFunction()))
     283             :     return false;
     284             : 
     285      139022 :   TII = Fn.getSubtarget().getInstrInfo();
     286      139022 :   MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
     287      139022 :   AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
     288      139022 :   TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
     289             : 
     290      139022 :   RegClassInfo.runOnMachineFunction(Fn);
     291             : 
     292      139022 :   TargetSubtargetInfo::AntiDepBreakMode AntiDepMode =
     293             :     TargetSubtargetInfo::ANTIDEP_NONE;
     294             :   SmallVector<const TargetRegisterClass*, 4> CriticalPathRCs;
     295             : 
     296             :   // Check that post-RA scheduling is enabled for this target.
     297             :   // This may upgrade the AntiDepMode.
     298      139022 :   if (!enablePostRAScheduler(Fn.getSubtarget(), PassConfig->getOptLevel(),
     299             :                              AntiDepMode, CriticalPathRCs))
     300             :     return false;
     301             : 
     302             :   // Check for antidep breaking override...
     303       38714 :   if (EnableAntiDepBreaking.getPosition() > 0) {
     304           6 :     AntiDepMode = (EnableAntiDepBreaking == "all")
     305           6 :       ? TargetSubtargetInfo::ANTIDEP_ALL
     306             :       : ((EnableAntiDepBreaking == "critical")
     307           5 :          ? TargetSubtargetInfo::ANTIDEP_CRITICAL
     308             :          : TargetSubtargetInfo::ANTIDEP_NONE);
     309             :   }
     310             : 
     311             :   DEBUG(dbgs() << "PostRAScheduler\n");
     312             : 
     313             :   SchedulePostRATDList Scheduler(Fn, MLI, AA, RegClassInfo, AntiDepMode,
     314       77428 :                                  CriticalPathRCs);
     315             : 
     316             :   // Loop over all of the basic blocks
     317      143737 :   for (auto &MBB : Fn) {
     318             : #ifndef NDEBUG
     319             :     // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
     320             :     if (DebugDiv > 0) {
     321             :       static int bbcnt = 0;
     322             :       if (bbcnt++ % DebugDiv != DebugMod)
     323             :         continue;
     324             :       dbgs() << "*** DEBUG scheduling " << Fn.getName() << ":"
     325             :              << printMBBReference(MBB) << " ***\n";
     326             :     }
     327             : #endif
     328             : 
     329             :     // Initialize register live-range state for scheduling in this block.
     330      105023 :     Scheduler.startBlock(&MBB);
     331             : 
     332             :     // Schedule each sequence of instructions not interrupted by a label
     333             :     // or anything else that effectively needs to shut down scheduling.
     334             :     MachineBasicBlock::iterator Current = MBB.end();
     335             :     unsigned Count = MBB.size(), CurrentCount = Count;
     336     1511358 :     for (MachineBasicBlock::iterator I = Current; I != MBB.begin();) {
     337             :       MachineInstr &MI = *std::prev(I);
     338     1406335 :       --Count;
     339             :       // Calls are not scheduling boundaries before register allocation, but
     340             :       // post-ra we don't gain anything by scheduling across calls since we
     341             :       // don't need to worry about register pressure.
     342     1406335 :       if (MI.isCall() || TII->isSchedulingBoundary(MI, &MBB, Fn)) {
     343      539257 :         Scheduler.enterRegion(&MBB, I, Current, CurrentCount - Count);
     344             :         Scheduler.setEndIndex(CurrentCount);
     345      539257 :         Scheduler.schedule();
     346             :         Scheduler.exitRegion();
     347      539257 :         Scheduler.EmitSchedule();
     348             :         Current = &MI;
     349             :         CurrentCount = Count;
     350      539257 :         Scheduler.Observe(MI, CurrentCount);
     351             :       }
     352             :       I = MI;
     353     1406335 :       if (MI.isBundle())
     354        1147 :         Count -= MI.getBundleSize();
     355             :     }
     356             :     assert(Count == 0 && "Instruction count mismatch!");
     357             :     assert((MBB.begin() == Current || CurrentCount != 0) &&
     358             :            "Instruction count mismatch!");
     359             :     Scheduler.enterRegion(&MBB, MBB.begin(), Current, CurrentCount);
     360             :     Scheduler.setEndIndex(CurrentCount);
     361      105023 :     Scheduler.schedule();
     362             :     Scheduler.exitRegion();
     363      105023 :     Scheduler.EmitSchedule();
     364             : 
     365             :     // Clean up register live-range state.
     366      105023 :     Scheduler.finishBlock();
     367             : 
     368             :     // Update register kills
     369      105023 :     Scheduler.fixupKills(MBB);
     370             :   }
     371             : 
     372             :   return true;
     373             : }
     374             : 
     375             : /// StartBlock - Initialize register live-range state for scheduling in
     376             : /// this block.
     377             : ///
     378      105023 : void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) {
     379             :   // Call the superclass.
     380      105023 :   ScheduleDAGInstrs::startBlock(BB);
     381             : 
     382             :   // Reset the hazard recognizer and anti-dep breaker.
     383      105023 :   HazardRec->Reset();
     384      105023 :   if (AntiDepBreak)
     385       77480 :     AntiDepBreak->StartBlock(BB);
     386      105023 : }
     387             : 
     388             : /// Schedule - Schedule the instruction range using list scheduling.
     389             : ///
     390      644280 : void SchedulePostRATDList::schedule() {
     391             :   // Build the scheduling graph.
     392      644280 :   buildSchedGraph(AA);
     393             : 
     394      644280 :   if (AntiDepBreak) {
     395             :     unsigned Broken =
     396      563911 :       AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd,
     397      563911 :                                           EndIndex, DbgValues);
     398             : 
     399      563911 :     if (Broken != 0) {
     400             :       // We made changes. Update the dependency graph.
     401             :       // Theoretically we could update the graph in place:
     402             :       // When a live range is changed to use a different register, remove
     403             :       // the def's anti-dependence *and* output-dependence edges due to
     404             :       // that register, and add new anti-dependence and output-dependence
     405             :       // edges based on the next live range of the register.
     406        8209 :       ScheduleDAG::clearDAG();
     407        8209 :       buildSchedGraph(AA);
     408             : 
     409             :       NumFixedAnti += Broken;
     410             :     }
     411             :   }
     412             : 
     413             :   postprocessDAG();
     414             : 
     415             :   DEBUG(dbgs() << "********** List Scheduling **********\n");
     416             :   DEBUG(
     417             :     for (const SUnit &SU : SUnits) {
     418             :       SU.dumpAll(this);
     419             :       dbgs() << '\n';
     420             :     }
     421             :   );
     422             : 
     423      644280 :   AvailableQueue.initNodes(SUnits);
     424      644280 :   ListScheduleTopDown();
     425             :   AvailableQueue.releaseState();
     426      644280 : }
     427             : 
     428             : /// Observe - Update liveness information to account for the current
     429             : /// instruction, which will not be scheduled.
     430             : ///
     431             : void SchedulePostRATDList::Observe(MachineInstr &MI, unsigned Count) {
     432      539257 :   if (AntiDepBreak)
     433      486431 :     AntiDepBreak->Observe(MI, Count, EndIndex);
     434             : }
     435             : 
     436             : /// FinishBlock - Clean up register live-range state.
     437             : ///
     438      105023 : void SchedulePostRATDList::finishBlock() {
     439      105023 :   if (AntiDepBreak)
     440       77480 :     AntiDepBreak->FinishBlock();
     441             : 
     442             :   // Call the superclass.
     443      105023 :   ScheduleDAGInstrs::finishBlock();
     444      105023 : }
     445             : 
     446             : /// Apply each ScheduleDAGMutation step in order.
     447             : void SchedulePostRATDList::postprocessDAG() {
     448      689843 :   for (auto &M : Mutations)
     449       45563 :     M->apply(this);
     450             : }
     451             : 
     452             : //===----------------------------------------------------------------------===//
     453             : //  Top-Down Scheduling
     454             : //===----------------------------------------------------------------------===//
     455             : 
     456             : /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
     457             : /// the PendingQueue if the count reaches zero.
     458     2234623 : void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
     459     2234623 :   SUnit *SuccSU = SuccEdge->getSUnit();
     460             : 
     461             :   if (SuccEdge->isWeak()) {
     462           0 :     --SuccSU->WeakPredsLeft;
     463           0 :     return;
     464             :   }
     465             : #ifndef NDEBUG
     466             :   if (SuccSU->NumPredsLeft == 0) {
     467             :     dbgs() << "*** Scheduling failed! ***\n";
     468             :     SuccSU->dump(this);
     469             :     dbgs() << " has been released too many times!\n";
     470             :     llvm_unreachable(nullptr);
     471             :   }
     472             : #endif
     473     2234623 :   --SuccSU->NumPredsLeft;
     474             : 
     475             :   // Standard scheduler algorithms will recompute the depth of the successor
     476             :   // here as such:
     477             :   //   SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency());
     478             :   //
     479             :   // However, we lazily compute node depth instead. Note that
     480             :   // ScheduleNodeTopDown has already updated the depth of this node which causes
     481             :   // all descendents to be marked dirty. Setting the successor depth explicitly
     482             :   // here would cause depth to be recomputed for all its ancestors. If the
     483             :   // successor is not yet ready (because of a transitively redundant edge) then
     484             :   // this causes depth computation to be quadratic in the size of the DAG.
     485             : 
     486             :   // If all the node's predecessors are scheduled, this node is ready
     487             :   // to be scheduled. Ignore the special ExitSU node.
     488     2234623 :   if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
     489      522206 :     PendingQueue.push_back(SuccSU);
     490             : }
     491             : 
     492             : /// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors.
     493             : void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) {
     494     2234623 :   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
     495     3745775 :        I != E; ++I) {
     496     2234623 :     ReleaseSucc(SU, &*I);
     497             :   }
     498             : }
     499             : 
     500             : /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
     501             : /// count of its successors. If a successor pending count is zero, add it to
     502             : /// the Available queue.
     503      866872 : void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
     504             :   DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
     505             :   DEBUG(SU->dump(this));
     506             : 
     507      866872 :   Sequence.push_back(SU);
     508             :   assert(CurCycle >= SU->getDepth() &&
     509             :          "Node scheduled above its depth!");
     510      866872 :   SU->setDepthToAtLeast(CurCycle);
     511             : 
     512      866872 :   ReleaseSuccessors(SU);
     513      866872 :   SU->isScheduled = true;
     514      866872 :   AvailableQueue.scheduledNode(SU);
     515      866872 : }
     516             : 
     517             : /// emitNoop - Add a noop to the current instruction sequence.
     518         958 : void SchedulePostRATDList::emitNoop(unsigned CurCycle) {
     519             :   DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n');
     520         958 :   HazardRec->EmitNoop();
     521        1916 :   Sequence.push_back(nullptr);   // NULL here means noop
     522             :   ++NumNoops;
     523         958 : }
     524             : 
     525             : /// ListScheduleTopDown - The main loop of list scheduling for top-down
     526             : /// schedulers.
     527      644280 : void SchedulePostRATDList::ListScheduleTopDown() {
     528             :   unsigned CurCycle = 0;
     529             : 
     530             :   // We're scheduling top-down but we're visiting the regions in
     531             :   // bottom-up order, so we don't know the hazards at the start of a
     532             :   // region. So assume no hazards (this should usually be ok as most
     533             :   // blocks are a single region).
     534      644280 :   HazardRec->Reset();
     535             : 
     536             :   // Release any successors of the special Entry node.
     537             :   ReleaseSuccessors(&EntrySU);
     538             : 
     539             :   // Add all leaves to Available queue.
     540     2155432 :   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
     541             :     // It is available if it has no predecessors.
     542     1733744 :     if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) {
     543      344666 :       AvailableQueue.push(&SUnits[i]);
     544      689332 :       SUnits[i].isAvailable = true;
     545             :     }
     546             :   }
     547             : 
     548             :   // In any cycle where we can't schedule any instructions, we must
     549             :   // stall or emit a noop, depending on the target.
     550             :   bool CycleHasInsts = false;
     551             : 
     552             :   // While Available queue is not empty, grab the node with the highest
     553             :   // priority. If it is not ready put it back.  Schedule the node.
     554             :   std::vector<SUnit*> NotReady;
     555     1288560 :   Sequence.reserve(SUnits.size());
     556     4513991 :   while (!AvailableQueue.empty() || !PendingQueue.empty()) {
     557             :     // Check to see if any of the pending instructions are ready to issue.  If
     558             :     // so, add them to the available queue.
     559             :     unsigned MinDepth = ~0u;
     560     7112193 :     for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
     561    10005723 :       if (PendingQueue[i]->getDepth() <= CurCycle) {
     562     1044412 :         AvailableQueue.push(PendingQueue[i]);
     563     1044412 :         PendingQueue[i]->isAvailable = true;
     564     1044412 :         PendingQueue[i] = PendingQueue.back();
     565             :         PendingQueue.pop_back();
     566      522206 :         --i; --e;
     567     8439105 :       } else if (PendingQueue[i]->getDepth() < MinDepth)
     568     2596116 :         MinDepth = PendingQueue[i]->getDepth();
     569             :     }
     570             : 
     571             :     DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this));
     572             : 
     573             :     SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;
     574             :     bool HasNoopHazards = false;
     575     1958331 :     while (!AvailableQueue.empty()) {
     576      935791 :       SUnit *CurSUnit = AvailableQueue.pop();
     577             : 
     578             :       ScheduleHazardRecognizer::HazardType HT =
     579      935791 :         HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
     580      935791 :       if (HT == ScheduleHazardRecognizer::NoHazard) {
     581      866914 :         if (HazardRec->ShouldPreferAnother(CurSUnit)) {
     582        1946 :           if (!NotPreferredSUnit) {
     583             :             // If this is the first non-preferred node for this cycle, then
     584             :             // record it and continue searching for a preferred node. If this
     585             :             // is not the first non-preferred node, then treat it as though
     586             :             // there had been a hazard.
     587         968 :             NotPreferredSUnit = CurSUnit;
     588         968 :             continue;
     589             :           }
     590             :         } else {
     591      865936 :           FoundSUnit = CurSUnit;
     592      865936 :           break;
     593             :         }
     594             :       }
     595             : 
     596             :       // Remember if this is a noop hazard.
     597       68887 :       HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
     598             : 
     599       68887 :       NotReady.push_back(CurSUnit);
     600             :     }
     601             : 
     602             :     // If we have a non-preferred node, push it back onto the available list.
     603             :     // If we did not find a preferred node, then schedule this first
     604             :     // non-preferred node.
     605     1888476 :     if (NotPreferredSUnit) {
     606         968 :       if (!FoundSUnit) {
     607             :         DEBUG(dbgs() << "*** Will schedule a non-preferred instruction...\n");
     608             :         FoundSUnit = NotPreferredSUnit;
     609             :       } else {
     610          32 :         AvailableQueue.push(NotPreferredSUnit);
     611             :       }
     612             : 
     613             :       NotPreferredSUnit = nullptr;
     614             :     }
     615             : 
     616             :     // Add the nodes that aren't ready back onto the available list.
     617     1888476 :     if (!NotReady.empty()) {
     618       23438 :       AvailableQueue.push_all(NotReady);
     619             :       NotReady.clear();
     620             :     }
     621             : 
     622             :     // If we found a node to schedule...
     623     1888476 :     if (FoundSUnit) {
     624             :       // If we need to emit noops prior to this instruction, then do so.
     625      866872 :       unsigned NumPreNoops = HazardRec->PreEmitNoops(FoundSUnit);
     626      866872 :       for (unsigned i = 0; i != NumPreNoops; ++i)
     627           0 :         emitNoop(CurCycle);
     628             : 
     629             :       // ... schedule the node...
     630      866872 :       ScheduleNodeTopDown(FoundSUnit, CurCycle);
     631      866872 :       HazardRec->EmitInstruction(FoundSUnit);
     632             :       CycleHasInsts = true;
     633      866872 :       if (HazardRec->atIssueLimit()) {
     634             :         DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle << '\n');
     635      197350 :         HazardRec->AdvanceCycle();
     636      197350 :         ++CurCycle;
     637             :         CycleHasInsts = false;
     638             :       }
     639             :     } else {
     640     1021604 :       if (CycleHasInsts) {
     641             :         DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n');
     642      224999 :         HazardRec->AdvanceCycle();
     643      796605 :       } else if (!HasNoopHazards) {
     644             :         // Otherwise, we have a pipeline stall, but no other problem,
     645             :         // just advance the current cycle and try again.
     646             :         DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n');
     647      795647 :         HazardRec->AdvanceCycle();
     648             :         ++NumStalls;
     649             :       } else {
     650             :         // Otherwise, we have no instructions to issue and we have instructions
     651             :         // that will fault if we don't do this right.  This is the case for
     652             :         // processors without pipeline interlocks and other cases.
     653         958 :         emitNoop(CurCycle);
     654             :       }
     655             : 
     656     1021604 :       ++CurCycle;
     657             :       CycleHasInsts = false;
     658             :     }
     659             :   }
     660             : 
     661             : #ifndef NDEBUG
     662             :   unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false);
     663             :   unsigned Noops = 0;
     664             :   for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
     665             :     if (!Sequence[i])
     666             :       ++Noops;
     667             :   assert(Sequence.size() - Noops == ScheduledNodes &&
     668             :          "The number of nodes scheduled doesn't match the expected number!");
     669             : #endif // NDEBUG
     670      644280 : }
     671             : 
     672             : // EmitSchedule - Emit the machine code in scheduled order.
     673      644280 : void SchedulePostRATDList::EmitSchedule() {
     674      644280 :   RegionBegin = RegionEnd;
     675             : 
     676             :   // If first instruction was a DBG_VALUE then put it back.
     677      644280 :   if (FirstDbgValue)
     678          80 :     BB->splice(RegionEnd, BB, FirstDbgValue);
     679             : 
     680             :   // Then re-insert them according to the given schedule.
     681     2156390 :   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
     682     1735660 :     if (SUnit *SU = Sequence[i])
     683     1733744 :       BB->splice(RegionEnd, BB, SU->getInstr());
     684             :     else
     685             :       // Null SUnit* is a noop.
     686         958 :       TII->insertNoop(*BB, RegionEnd);
     687             : 
     688             :     // Update the Begin iterator, as the first instruction in the block
     689             :     // may have been scheduled later.
     690      867830 :     if (i == 0)
     691      171570 :       RegionBegin = std::prev(RegionEnd);
     692             :   }
     693             : 
     694             :   // Reinsert any remaining debug_values.
     695             :   for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
     696      644446 :          DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
     697         166 :     std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);
     698             :     MachineInstr *DbgValue = P.first;
     699             :     MachineBasicBlock::iterator OrigPrivMI = P.second;
     700         332 :     BB->splice(++OrigPrivMI, BB, DbgValue);
     701             :   }
     702             :   DbgValues.clear();
     703      644280 :   FirstDbgValue = nullptr;
     704      936252 : }

Generated by: LCOV version 1.13