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

Generated by: LCOV version 1.13