1193323Sed//===---- LatencyPriorityQueue.cpp - A latency-oriented priority queue ----===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file implements the LatencyPriorityQueue class, which is a 10193323Sed// SchedulingPriorityQueue that schedules using latency information to 11193323Sed// reduce the length of the critical path through the basic block. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#include "llvm/CodeGen/LatencyPriorityQueue.h" 16341825Sdim#include "llvm/Config/llvm-config.h" 17193323Sed#include "llvm/Support/Debug.h" 18218893Sdim#include "llvm/Support/raw_ostream.h" 19193323Sedusing namespace llvm; 20193323Sed 21276479Sdim#define DEBUG_TYPE "scheduler" 22276479Sdim 23193323Sedbool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { 24193323Sed // The isScheduleHigh flag allows nodes with wraparound dependencies that 25193323Sed // cannot easily be modeled as edges with latencies to be scheduled as 26193323Sed // soon as possible in a top-down schedule. 27193323Sed if (LHS->isScheduleHigh && !RHS->isScheduleHigh) 28193323Sed return false; 29193323Sed if (!LHS->isScheduleHigh && RHS->isScheduleHigh) 30193323Sed return true; 31193323Sed 32193323Sed unsigned LHSNum = LHS->NodeNum; 33193323Sed unsigned RHSNum = RHS->NodeNum; 34193323Sed 35193323Sed // The most important heuristic is scheduling the critical path. 36193323Sed unsigned LHSLatency = PQ->getLatency(LHSNum); 37193323Sed unsigned RHSLatency = PQ->getLatency(RHSNum); 38193323Sed if (LHSLatency < RHSLatency) return true; 39193323Sed if (LHSLatency > RHSLatency) return false; 40218893Sdim 41193323Sed // After that, if two nodes have identical latencies, look to see if one will 42193323Sed // unblock more other nodes than the other. 43193323Sed unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum); 44193323Sed unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum); 45193323Sed if (LHSBlocked < RHSBlocked) return true; 46193323Sed if (LHSBlocked > RHSBlocked) return false; 47218893Sdim 48193323Sed // Finally, just to provide a stable ordering, use the node number as a 49193323Sed // deciding factor. 50234353Sdim return RHSNum < LHSNum; 51193323Sed} 52193323Sed 53193323Sed 54193323Sed/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor 55193323Sed/// of SU, return it, otherwise return null. 56193323SedSUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { 57276479Sdim SUnit *OnlyAvailablePred = nullptr; 58193323Sed for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 59193323Sed I != E; ++I) { 60193323Sed SUnit &Pred = *I->getSUnit(); 61193323Sed if (!Pred.isScheduled) { 62193323Sed // We found an available, but not scheduled, predecessor. If it's the 63193323Sed // only one we have found, keep track of it... otherwise give up. 64193323Sed if (OnlyAvailablePred && OnlyAvailablePred != &Pred) 65276479Sdim return nullptr; 66193323Sed OnlyAvailablePred = &Pred; 67193323Sed } 68193323Sed } 69218893Sdim 70193323Sed return OnlyAvailablePred; 71193323Sed} 72193323Sed 73208599Srdivackyvoid LatencyPriorityQueue::push(SUnit *SU) { 74193323Sed // Look at all of the successors of this node. Count the number of nodes that 75193323Sed // this node is the sole unscheduled node for. 76193323Sed unsigned NumNodesBlocking = 0; 77193323Sed for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 78198892Srdivacky I != E; ++I) { 79193323Sed if (getSingleUnscheduledPred(I->getSUnit()) == SU) 80193323Sed ++NumNodesBlocking; 81198892Srdivacky } 82193323Sed NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; 83218893Sdim 84208599Srdivacky Queue.push_back(SU); 85193323Sed} 86193323Sed 87193323Sed 88234353Sdim// scheduledNode - As nodes are scheduled, we look to see if there are any 89193323Sed// successor nodes that have a single unscheduled predecessor. If so, that 90193323Sed// single predecessor has a higher priority, since scheduling it will make 91193323Sed// the node available. 92234353Sdimvoid LatencyPriorityQueue::scheduledNode(SUnit *SU) { 93193323Sed for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 94198892Srdivacky I != E; ++I) { 95193323Sed AdjustPriorityOfUnscheduledPreds(I->getSUnit()); 96198892Srdivacky } 97193323Sed} 98193323Sed 99193323Sed/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just 100193323Sed/// scheduled. If SU is not itself available, then there is at least one 101193323Sed/// predecessor node that has not been scheduled yet. If SU has exactly ONE 102193323Sed/// unscheduled predecessor, we want to increase its priority: it getting 103193323Sed/// scheduled will make this node available, so it is better than some other 104193323Sed/// node of the same priority that will not make a node available. 105193323Sedvoid LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { 106193323Sed if (SU->isAvailable) return; // All preds scheduled. 107218893Sdim 108193323Sed SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU); 109276479Sdim if (!OnlyAvailablePred || !OnlyAvailablePred->isAvailable) return; 110218893Sdim 111193323Sed // Okay, we found a single predecessor that is available, but not scheduled. 112193323Sed // Since it is available, it must be in the priority queue. First remove it. 113193323Sed remove(OnlyAvailablePred); 114193323Sed 115193323Sed // Reinsert the node into the priority queue, which recomputes its 116193323Sed // NumNodesSolelyBlocking value. 117193323Sed push(OnlyAvailablePred); 118193323Sed} 119208599Srdivacky 120208599SrdivackySUnit *LatencyPriorityQueue::pop() { 121276479Sdim if (empty()) return nullptr; 122208599Srdivacky std::vector<SUnit *>::iterator Best = Queue.begin(); 123276479Sdim for (std::vector<SUnit *>::iterator I = std::next(Queue.begin()), 124208599Srdivacky E = Queue.end(); I != E; ++I) 125208599Srdivacky if (Picker(*Best, *I)) 126208599Srdivacky Best = I; 127208599Srdivacky SUnit *V = *Best; 128276479Sdim if (Best != std::prev(Queue.end())) 129208599Srdivacky std::swap(*Best, Queue.back()); 130208599Srdivacky Queue.pop_back(); 131208599Srdivacky return V; 132208599Srdivacky} 133208599Srdivacky 134208599Srdivackyvoid LatencyPriorityQueue::remove(SUnit *SU) { 135208599Srdivacky assert(!Queue.empty() && "Queue is empty!"); 136314564Sdim std::vector<SUnit *>::iterator I = find(Queue, SU); 137327952Sdim assert(I != Queue.end() && "Queue doesn't contain the SU being removed!"); 138276479Sdim if (I != std::prev(Queue.end())) 139208599Srdivacky std::swap(*I, Queue.back()); 140208599Srdivacky Queue.pop_back(); 141208599Srdivacky} 142341825Sdim 143341825Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 144341825SdimLLVM_DUMP_METHOD void LatencyPriorityQueue::dump(ScheduleDAG *DAG) const { 145341825Sdim dbgs() << "Latency Priority Queue\n"; 146341825Sdim dbgs() << " Number of Queue Entries: " << Queue.size() << "\n"; 147344779Sdim for (const SUnit *SU : Queue) { 148341825Sdim dbgs() << " "; 149344779Sdim DAG->dumpNode(*SU); 150341825Sdim } 151341825Sdim} 152341825Sdim#endif 153