LCOV - code coverage report
Current view: top level - lib/CodeGen - PostRASchedulerList.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 225 232 97.0 %
Date: 2017-09-14 15:23:50 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/MachineFrameInfo.h"
      29             : #include "llvm/CodeGen/MachineFunctionPass.h"
      30             : #include "llvm/CodeGen/MachineLoopInfo.h"
      31             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      32             : #include "llvm/CodeGen/Passes.h"
      33             : #include "llvm/CodeGen/RegisterClassInfo.h"
      34             : #include "llvm/CodeGen/ScheduleDAGInstrs.h"
      35             : #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
      36             : #include "llvm/CodeGen/SchedulerRegistry.h"
      37             : #include "llvm/CodeGen/TargetPassConfig.h"
      38             : #include "llvm/Support/CommandLine.h"
      39             : #include "llvm/Support/Debug.h"
      40             : #include "llvm/Support/ErrorHandling.h"
      41             : #include "llvm/Support/raw_ostream.h"
      42             : #include "llvm/Target/TargetInstrInfo.h"
      43             : #include "llvm/Target/TargetLowering.h"
      44             : #include "llvm/Target/TargetRegisterInfo.h"
      45             : #include "llvm/Target/TargetSubtargetInfo.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       72306 : EnablePostRAScheduler("post-RA-scheduler",
      59      216918 :                        cl::desc("Enable scheduling after register allocation"),
      60      289224 :                        cl::init(false), cl::Hidden);
      61             : static cl::opt<std::string>
      62       72306 : EnableAntiDepBreaking("break-anti-dependencies",
      63      216918 :                       cl::desc("Break post-RA scheduling anti-dependencies: "
      64             :                                "\"critical\", \"all\", or \"none\""),
      65      289224 :                       cl::init("none"), cl::Hidden);
      66             : 
      67             : // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
      68             : static cl::opt<int>
      69       72306 : DebugDiv("postra-sched-debugdiv",
      70      216918 :                       cl::desc("Debug control MBBs that are scheduled"),
      71      289224 :                       cl::init(0), cl::Hidden);
      72             : static cl::opt<int>
      73       72306 : DebugMod("postra-sched-debugmod",
      74      216918 :                       cl::desc("Debug control MBBs that are scheduled"),
      75      289224 :                       cl::init(0), cl::Hidden);
      76             : 
      77       12011 : AntiDepBreaker::~AntiDepBreaker() { }
      78             : 
      79             : namespace {
      80       13585 :   class PostRAScheduler : public MachineFunctionPass {
      81             :     const TargetInstrInfo *TII;
      82             :     RegisterClassInfo RegClassInfo;
      83             : 
      84             :   public:
      85             :     static char ID;
      86       13661 :     PostRAScheduler() : MachineFunctionPass(ID) {}
      87             : 
      88       13620 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
      89       13620 :       AU.setPreservesCFG();
      90       13620 :       AU.addRequired<AAResultsWrapperPass>();
      91       13620 :       AU.addRequired<TargetPassConfig>();
      92       13620 :       AU.addRequired<MachineDominatorTree>();
      93       13620 :       AU.addPreserved<MachineDominatorTree>();
      94       13620 :       AU.addRequired<MachineLoopInfo>();
      95       13620 :       AU.addPreserved<MachineLoopInfo>();
      96       13620 :       MachineFunctionPass::getAnalysisUsage(AU);
      97       13620 :     }
      98             : 
      99       13624 :     MachineFunctionProperties getRequiredProperties() const override {
     100       40872 :       return MachineFunctionProperties().set(
     101       40872 :           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      610624 :     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      151199 : INITIALIZE_PASS(PostRAScheduler, DEBUG_TYPE,
     204             :                 "Post RA top-down list latency scheduler", false, false)
     205             : 
     206       32522 : SchedulePostRATDList::SchedulePostRATDList(
     207             :     MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
     208             :     const RegisterClassInfo &RCI,
     209             :     TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
     210       32522 :     SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs)
     211      162610 :     : ScheduleDAGInstrs(MF, &MLI), AA(AA), EndIndex(0) {
     212             : 
     213             :   const InstrItineraryData *InstrItins =
     214       32522 :       MF.getSubtarget().getInstrItineraryData();
     215       32522 :   HazardRec =
     216       65044 :       MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(
     217       32522 :           InstrItins, this);
     218       32522 :   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       32522 :   AntiDepBreak =
     224       32522 :     ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ?
     225        7427 :      (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) :
     226       25095 :      ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ?
     227        4584 :       (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : nullptr));
     228       32522 : }
     229             : 
     230      130088 : SchedulePostRATDList::~SchedulePostRATDList() {
     231       32522 :   delete HazardRec;
     232       32522 :   delete AntiDepBreak;
     233       32522 : }
     234             : 
     235             : /// Initialize state associated with the next scheduling region.
     236           0 : void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb,
     237             :                  MachineBasicBlock::iterator begin,
     238             :                  MachineBasicBlock::iterator end,
     239             :                  unsigned regioninstrs) {
     240      610624 :   ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);
     241     1221248 :   Sequence.clear();
     242           0 : }
     243             : 
     244             : /// Print the schedule before exiting the region.
     245           0 : void SchedulePostRATDList::exitRegion() {
     246             :   DEBUG({
     247             :       dbgs() << "*** Final schedule ***\n";
     248             :       dumpSchedule();
     249             :       dbgs() << '\n';
     250             :     });
     251      610624 :   ScheduleDAGInstrs::exitRegion();
     252           0 : }
     253             : 
     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             :       SU->dump(this);
     260             :     else
     261             :       dbgs() << "**** NOOP ****\n";
     262             :   }
     263             : }
     264             : #endif
     265             : 
     266      116962 : bool PostRAScheduler::enablePostRAScheduler(
     267             :     const TargetSubtargetInfo &ST,
     268             :     CodeGenOpt::Level OptLevel,
     269             :     TargetSubtargetInfo::AntiDepBreakMode &Mode,
     270             :     TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const {
     271      116962 :   Mode = ST.getAntiDepBreakMode();
     272      116962 :   ST.getCriticalPathRCs(CriticalPathRCs);
     273             : 
     274             :   // Check for explicit enable/disable of post-ra scheduling.
     275      116962 :   if (EnablePostRAScheduler.getPosition() > 0)
     276          44 :     return EnablePostRAScheduler;
     277             : 
     278      161776 :   return ST.enablePostRAScheduler() &&
     279       44858 :          OptLevel >= ST.getOptLevelToEnablePostRAScheduler();
     280             : }
     281             : 
     282      117018 : bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) {
     283      117018 :   if (skipFunction(*Fn.getFunction()))
     284             :     return false;
     285             : 
     286      116962 :   TII = Fn.getSubtarget().getInstrInfo();
     287      116962 :   MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
     288      233924 :   AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
     289      116962 :   TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
     290             : 
     291      116962 :   RegClassInfo.runOnMachineFunction(Fn);
     292             : 
     293      116962 :   TargetSubtargetInfo::AntiDepBreakMode AntiDepMode =
     294             :     TargetSubtargetInfo::ANTIDEP_NONE;
     295      116962 :   SmallVector<const TargetRegisterClass*, 4> CriticalPathRCs;
     296             : 
     297             :   // Check that post-RA scheduling is enabled for this target.
     298             :   // This may upgrade the AntiDepMode.
     299      116962 :   if (!enablePostRAScheduler(Fn.getSubtarget(), PassConfig->getOptLevel(),
     300             :                              AntiDepMode, CriticalPathRCs))
     301             :     return false;
     302             : 
     303             :   // Check for antidep breaking override...
     304       32522 :   if (EnableAntiDepBreaking.getPosition() > 0) {
     305          12 :     AntiDepMode = (EnableAntiDepBreaking == "all")
     306           6 :       ? TargetSubtargetInfo::ANTIDEP_ALL
     307           5 :       : ((EnableAntiDepBreaking == "critical")
     308           5 :          ? TargetSubtargetInfo::ANTIDEP_CRITICAL
     309             :          : TargetSubtargetInfo::ANTIDEP_NONE);
     310             :   }
     311             : 
     312             :   DEBUG(dbgs() << "PostRAScheduler\n");
     313             : 
     314             :   SchedulePostRATDList Scheduler(Fn, MLI, AA, RegClassInfo, AntiDepMode,
     315       65044 :                                  CriticalPathRCs);
     316             : 
     317             :   // Loop over all of the basic blocks
     318      195562 :   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             :       if (bbcnt++ % DebugDiv != DebugMod)
     324             :         continue;
     325             :       dbgs() << "*** DEBUG scheduling " << Fn.getName()
     326             :              << ":BB#" << MBB.getNumber() << " ***\n";
     327             :     }
     328             : #endif
     329             : 
     330             :     // Initialize register live-range state for scheduling in this block.
     331       97996 :     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       97996 :     MachineBasicBlock::iterator Current = MBB.end();
     336       97996 :     unsigned Count = MBB.size(), CurrentCount = Count;
     337     2985742 :     for (MachineBasicBlock::iterator I = Current; I != MBB.begin();) {
     338     2691754 :       MachineInstr &MI = *std::prev(I);
     339     1345877 :       --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     1345877 :       if (MI.isCall() || TII->isSchedulingBoundary(MI, &MBB, Fn)) {
     344     1025256 :         Scheduler.enterRegion(&MBB, I, Current, CurrentCount - Count);
     345     1025256 :         Scheduler.setEndIndex(CurrentCount);
     346      512628 :         Scheduler.schedule();
     347      512628 :         Scheduler.exitRegion();
     348      512628 :         Scheduler.EmitSchedule();
     349      512628 :         Current = &MI;
     350      512628 :         CurrentCount = Count;
     351      512628 :         Scheduler.Observe(MI, CurrentCount);
     352             :       }
     353     1345877 :       I = MI;
     354     1345877 :       if (MI.isBundle())
     355        1101 :         Count -= MI.getBundleSize();
     356             :     }
     357             :     assert(Count == 0 && "Instruction count mismatch!");
     358             :     assert((MBB.begin() == Current || CurrentCount != 0) &&
     359             :            "Instruction count mismatch!");
     360      195992 :     Scheduler.enterRegion(&MBB, MBB.begin(), Current, CurrentCount);
     361      195992 :     Scheduler.setEndIndex(CurrentCount);
     362       97996 :     Scheduler.schedule();
     363       97996 :     Scheduler.exitRegion();
     364       97996 :     Scheduler.EmitSchedule();
     365             : 
     366             :     // Clean up register live-range state.
     367       97996 :     Scheduler.finishBlock();
     368             : 
     369             :     // Update register kills
     370       97996 :     Scheduler.fixupKills(MBB);
     371             :   }
     372             : 
     373             :   return true;
     374             : }
     375             : 
     376             : /// StartBlock - Initialize register live-range state for scheduling in
     377             : /// this block.
     378             : ///
     379       97996 : void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) {
     380             :   // Call the superclass.
     381       97996 :   ScheduleDAGInstrs::startBlock(BB);
     382             : 
     383             :   // Reset the hazard recognizer and anti-dep breaker.
     384       97996 :   HazardRec->Reset();
     385       97996 :   if (AntiDepBreak)
     386       73317 :     AntiDepBreak->StartBlock(BB);
     387       97996 : }
     388             : 
     389             : /// Schedule - Schedule the instruction range using list scheduling.
     390             : ///
     391      610624 : void SchedulePostRATDList::schedule() {
     392             :   // Build the scheduling graph.
     393      610624 :   buildSchedGraph(AA);
     394             : 
     395      610624 :   if (AntiDepBreak) {
     396             :     unsigned Broken =
     397      538088 :       AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd,
     398     1076176 :                                           EndIndex, DbgValues);
     399             : 
     400      538088 :     if (Broken != 0) {
     401             :       // We made changes. Update the dependency graph.
     402             :       // Theoretically we could update the graph in place:
     403             :       // 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             :       // that register, and add new anti-dependence and output-dependence
     406             :       // edges based on the next live range of the register.
     407        7936 :       ScheduleDAG::clearDAG();
     408        7936 :       buildSchedGraph(AA);
     409             : 
     410        7936 :       NumFixedAnti += Broken;
     411             :     }
     412             :   }
     413             : 
     414      610624 :   postprocessDAG();
     415             : 
     416             :   DEBUG(dbgs() << "********** List Scheduling **********\n");
     417             :   DEBUG(
     418             :     for (const SUnit &SU : SUnits) {
     419             :       SU.dumpAll(this);
     420             :       dbgs() << '\n';
     421             :     }
     422             :   );
     423             : 
     424     1221248 :   AvailableQueue.initNodes(SUnits);
     425      610624 :   ListScheduleTopDown();
     426     1221248 :   AvailableQueue.releaseState();
     427      610624 : }
     428             : 
     429             : /// Observe - Update liveness information to account for the current
     430             : /// instruction, which will not be scheduled.
     431             : ///
     432             : void SchedulePostRATDList::Observe(MachineInstr &MI, unsigned Count) {
     433      512628 :   if (AntiDepBreak)
     434      464771 :     AntiDepBreak->Observe(MI, Count, EndIndex);
     435             : }
     436             : 
     437             : /// FinishBlock - Clean up register live-range state.
     438             : ///
     439       97996 : void SchedulePostRATDList::finishBlock() {
     440       97996 :   if (AntiDepBreak)
     441       73317 :     AntiDepBreak->FinishBlock();
     442             : 
     443             :   // Call the superclass.
     444       97996 :   ScheduleDAGInstrs::finishBlock();
     445       97996 : }
     446             : 
     447             : /// Apply each ScheduleDAGMutation step in order.
     448             : void SchedulePostRATDList::postprocessDAG() {
     449     2452507 :   for (auto &M : Mutations)
     450       10011 :     M->apply(this);
     451             : }
     452             : 
     453             : //===----------------------------------------------------------------------===//
     454             : //  Top-Down Scheduling
     455             : //===----------------------------------------------------------------------===//
     456             : 
     457             : /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
     458             : /// the PendingQueue if the count reaches zero.
     459     1931624 : void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
     460     1931624 :   SUnit *SuccSU = SuccEdge->getSUnit();
     461             : 
     462     1931624 :   if (SuccEdge->isWeak()) {
     463           0 :     --SuccSU->WeakPredsLeft;
     464           0 :     return;
     465             :   }
     466             : #ifndef NDEBUG
     467             :   if (SuccSU->NumPredsLeft == 0) {
     468             :     dbgs() << "*** Scheduling failed! ***\n";
     469             :     SuccSU->dump(this);
     470             :     dbgs() << " has been released too many times!\n";
     471             :     llvm_unreachable(nullptr);
     472             :   }
     473             : #endif
     474     1931624 :   --SuccSU->NumPredsLeft;
     475             : 
     476             :   // Standard scheduler algorithms will recompute the depth of the successor
     477             :   // here as such:
     478             :   //   SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency());
     479             :   //
     480             :   // However, we lazily compute node depth instead. Note that
     481             :   // ScheduleNodeTopDown has already updated the depth of this node which causes
     482             :   // all descendents to be marked dirty. Setting the successor depth explicitly
     483             :   // here would cause depth to be recomputed for all its ancestors. If the
     484             :   // successor is not yet ready (because of a transitively redundant edge) then
     485             :   // this causes depth computation to be quadratic in the size of the DAG.
     486             : 
     487             :   // If all the node's predecessors are scheduled, this node is ready
     488             :   // to be scheduled. Ignore the special ExitSU node.
     489     1931624 :   if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
     490      496772 :     PendingQueue.push_back(SuccSU);
     491             : }
     492             : 
     493             : /// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors.
     494             : void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) {
     495     6262826 :   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
     496     3375358 :        I != E; ++I) {
     497     1931624 :     ReleaseSucc(SU, &*I);
     498             :   }
     499             : }
     500             : 
     501             : /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
     502             : /// count of its successors. If a successor pending count is zero, add it to
     503             : /// the Available queue.
     504      833110 : void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
     505             :   DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
     506             :   DEBUG(SU->dump(this));
     507             : 
     508      833110 :   Sequence.push_back(SU);
     509             :   assert(CurCycle >= SU->getDepth() &&
     510             :          "Node scheduled above its depth!");
     511      833110 :   SU->setDepthToAtLeast(CurCycle);
     512             : 
     513     1666220 :   ReleaseSuccessors(SU);
     514      833110 :   SU->isScheduled = true;
     515      833110 :   AvailableQueue.scheduledNode(SU);
     516      833110 : }
     517             : 
     518             : /// emitNoop - Add a noop to the current instruction sequence.
     519        1726 : void SchedulePostRATDList::emitNoop(unsigned CurCycle) {
     520             :   DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n');
     521        1726 :   HazardRec->EmitNoop();
     522        3452 :   Sequence.push_back(nullptr);   // NULL here means noop
     523        1726 :   ++NumNoops;
     524        1726 : }
     525             : 
     526             : /// ListScheduleTopDown - The main loop of list scheduling for top-down
     527             : /// schedulers.
     528      610624 : void SchedulePostRATDList::ListScheduleTopDown() {
     529      610624 :   unsigned CurCycle = 0;
     530             : 
     531             :   // We're scheduling top-down but we're visiting the regions in
     532             :   // bottom-up order, so we don't know the hazards at the start of a
     533             :   // region. So assume no hazards (this should usually be ok as most
     534             :   // blocks are a single region).
     535      610624 :   HazardRec->Reset();
     536             : 
     537             :   // Release any successors of the special Entry node.
     538     1221248 :   ReleaseSuccessors(&EntrySU);
     539             : 
     540             :   // Add all leaves to Available queue.
     541     2054358 :   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
     542             :     // It is available if it has no predecessors.
     543     1666220 :     if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) {
     544      336338 :       AvailableQueue.push(&SUnits[i]);
     545      672676 :       SUnits[i].isAvailable = true;
     546             :     }
     547             :   }
     548             : 
     549             :   // In any cycle where we can't schedule any instructions, we must
     550             :   // stall or emit a noop, depending on the target.
     551      610624 :   bool CycleHasInsts = false;
     552             : 
     553             :   // While Available queue is not empty, grab the node with the highest
     554             :   // priority. If it is not ready put it back.  Schedule the node.
     555     1221248 :   std::vector<SUnit*> NotReady;
     556     1221248 :   Sequence.reserve(SUnits.size());
     557     6652410 :   while (!AvailableQueue.empty() || !PendingQueue.empty()) {
     558             :     // Check to see if any of the pending instructions are ready to issue.  If
     559             :     // so, add them to the available queue.
     560     1786138 :     unsigned MinDepth = ~0u;
     561     6838675 :     for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
     562     9799197 :       if (PendingQueue[i]->getDepth() <= CurCycle) {
     563      993544 :         AvailableQueue.push(PendingQueue[i]);
     564      993544 :         PendingQueue[i]->isAvailable = true;
     565     1490316 :         PendingQueue[i] = PendingQueue.back();
     566      496772 :         PendingQueue.pop_back();
     567      496772 :         --i; --e;
     568     8308881 :       } else if (PendingQueue[i]->getDepth() < MinDepth)
     569     3553569 :         MinDepth = PendingQueue[i]->getDepth();
     570             :     }
     571             : 
     572             :     DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this));
     573             : 
     574             :     SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;
     575             :     bool HasNoopHazards = false;
     576     3712678 :     while (!AvailableQueue.empty()) {
     577      902393 :       SUnit *CurSUnit = AvailableQueue.pop();
     578             : 
     579             :       ScheduleHazardRecognizer::HazardType HT =
     580      902393 :         HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
     581      902393 :       if (HT == ScheduleHazardRecognizer::NoHazard) {
     582      833158 :         if (HazardRec->ShouldPreferAnother(CurSUnit)) {
     583        1926 :           if (!NotPreferredSUnit) {
     584             :             // If this is the first non-preferred node for this cycle, then
     585             :             // record it and continue searching for a preferred node. If this
     586             :             // is not the first non-preferred node, then treat it as though
     587             :             // there had been a hazard.
     588         960 :             NotPreferredSUnit = CurSUnit;
     589         960 :             continue;
     590             :           }
     591             :         } else {
     592      832192 :           FoundSUnit = CurSUnit;
     593      832192 :           break;
     594             :         }
     595             :       }
     596             : 
     597             :       // Remember if this is a noop hazard.
     598       69241 :       HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
     599             : 
     600       69241 :       NotReady.push_back(CurSUnit);
     601             :     }
     602             : 
     603             :     // If we have a non-preferred node, push it back onto the available list.
     604             :     // If we did not find a preferred node, then schedule this first
     605             :     // non-preferred node.
     606     1786138 :     if (NotPreferredSUnit) {
     607         960 :       if (!FoundSUnit) {
     608             :         DEBUG(dbgs() << "*** Will schedule a non-preferred instruction...\n");
     609             :         FoundSUnit = NotPreferredSUnit;
     610             :       } else {
     611          42 :         AvailableQueue.push(NotPreferredSUnit);
     612             :       }
     613             : 
     614             :       NotPreferredSUnit = nullptr;
     615             :     }
     616             : 
     617             :     // Add the nodes that aren't ready back onto the available list.
     618     1786138 :     if (!NotReady.empty()) {
     619       49838 :       AvailableQueue.push_all(NotReady);
     620             :       NotReady.clear();
     621             :     }
     622             : 
     623             :     // If we found a node to schedule...
     624     1786138 :     if (FoundSUnit) {
     625             :       // If we need to emit noops prior to this instruction, then do so.
     626      833110 :       unsigned NumPreNoops = HazardRec->PreEmitNoops(FoundSUnit);
     627      833110 :       for (unsigned i = 0; i != NumPreNoops; ++i)
     628           0 :         emitNoop(CurCycle);
     629             : 
     630             :       // ... schedule the node...
     631      833110 :       ScheduleNodeTopDown(FoundSUnit, CurCycle);
     632      833110 :       HazardRec->EmitInstruction(FoundSUnit);
     633      833110 :       CycleHasInsts = true;
     634      833110 :       if (HazardRec->atIssueLimit()) {
     635             :         DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle << '\n');
     636      184052 :         HazardRec->AdvanceCycle();
     637      184052 :         ++CurCycle;
     638      184052 :         CycleHasInsts = false;
     639             :       }
     640             :     } else {
     641      953028 :       if (CycleHasInsts) {
     642             :         DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n');
     643      217665 :         HazardRec->AdvanceCycle();
     644      735363 :       } else if (!HasNoopHazards) {
     645             :         // Otherwise, we have a pipeline stall, but no other problem,
     646             :         // just advance the current cycle and try again.
     647             :         DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n');
     648      733637 :         HazardRec->AdvanceCycle();
     649             :         ++NumStalls;
     650             :       } else {
     651             :         // Otherwise, we have no instructions to issue and we have instructions
     652             :         // that will fault if we don't do this right.  This is the case for
     653             :         // processors without pipeline interlocks and other cases.
     654        1726 :         emitNoop(CurCycle);
     655             :       }
     656             : 
     657      953028 :       ++CurCycle;
     658      953028 :       CycleHasInsts = false;
     659             :     }
     660             :   }
     661             : 
     662             : #ifndef NDEBUG
     663             :   unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false);
     664             :   unsigned Noops = 0;
     665             :   for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
     666             :     if (!Sequence[i])
     667             :       ++Noops;
     668             :   assert(Sequence.size() - Noops == ScheduledNodes &&
     669             :          "The number of nodes scheduled doesn't match the expected number!");
     670             : #endif // NDEBUG
     671      610624 : }
     672             : 
     673             : // EmitSchedule - Emit the machine code in scheduled order.
     674      610624 : void SchedulePostRATDList::EmitSchedule() {
     675      610624 :   RegionBegin = RegionEnd;
     676             : 
     677             :   // If first instruction was a DBG_VALUE then put it back.
     678      610624 :   if (FirstDbgValue)
     679          68 :     BB->splice(RegionEnd, BB, FirstDbgValue);
     680             : 
     681             :   // Then re-insert them according to the given schedule.
     682     2056084 :   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
     683     1669672 :     if (SUnit *SU = Sequence[i])
     684     1666220 :       BB->splice(RegionEnd, BB, SU->getInstr());
     685             :     else
     686             :       // Null SUnit* is a noop.
     687        1726 :       TII->insertNoop(*BB, RegionEnd);
     688             : 
     689             :     // Update the Begin iterator, as the first instruction in the block
     690             :     // may have been scheduled later.
     691      834836 :     if (i == 0)
     692      162752 :       RegionBegin = std::prev(RegionEnd);
     693             :   }
     694             : 
     695             :   // Reinsert any remaining debug_values.
     696             :   for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
     697     2442601 :          DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
     698         105 :     std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);
     699         105 :     MachineInstr *DbgValue = P.first;
     700         210 :     MachineBasicBlock::iterator OrigPrivMI = P.second;
     701         315 :     BB->splice(++OrigPrivMI, BB, DbgValue);
     702             :   }
     703     1221248 :   DbgValues.clear();
     704      610624 :   FirstDbgValue = nullptr;
     705      827542 : }

Generated by: LCOV version 1.13