LatencyPriorityQueue.cpp revision 341825
1193323Sed//===---- LatencyPriorityQueue.cpp - A latency-oriented priority queue ----===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the LatencyPriorityQueue class, which is a 11193323Sed// SchedulingPriorityQueue that schedules using latency information to 12193323Sed// reduce the length of the critical path through the basic block. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16193323Sed#include "llvm/CodeGen/LatencyPriorityQueue.h" 17341825Sdim#include "llvm/Config/llvm-config.h" 18193323Sed#include "llvm/Support/Debug.h" 19218893Sdim#include "llvm/Support/raw_ostream.h" 20193323Sedusing namespace llvm; 21193323Sed 22276479Sdim#define DEBUG_TYPE "scheduler" 23276479Sdim 24193323Sedbool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { 25193323Sed // The isScheduleHigh flag allows nodes with wraparound dependencies that 26193323Sed // cannot easily be modeled as edges with latencies to be scheduled as 27193323Sed // soon as possible in a top-down schedule. 28193323Sed if (LHS->isScheduleHigh && !RHS->isScheduleHigh) 29193323Sed return false; 30193323Sed if (!LHS->isScheduleHigh && RHS->isScheduleHigh) 31193323Sed return true; 32193323Sed 33193323Sed unsigned LHSNum = LHS->NodeNum; 34193323Sed unsigned RHSNum = RHS->NodeNum; 35193323Sed 36193323Sed // The most important heuristic is scheduling the critical path. 37193323Sed unsigned LHSLatency = PQ->getLatency(LHSNum); 38193323Sed unsigned RHSLatency = PQ->getLatency(RHSNum); 39193323Sed if (LHSLatency < RHSLatency) return true; 40193323Sed if (LHSLatency > RHSLatency) return false; 41218893Sdim 42193323Sed // After that, if two nodes have identical latencies, look to see if one will 43193323Sed // unblock more other nodes than the other. 44193323Sed unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum); 45193323Sed unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum); 46193323Sed if (LHSBlocked < RHSBlocked) return true; 47193323Sed if (LHSBlocked > RHSBlocked) return false; 48218893Sdim 49193323Sed // Finally, just to provide a stable ordering, use the node number as a 50193323Sed // deciding factor. 51234353Sdim return RHSNum < LHSNum; 52193323Sed} 53193323Sed 54193323Sed 55193323Sed/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor 56193323Sed/// of SU, return it, otherwise return null. 57193323SedSUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { 58276479Sdim SUnit *OnlyAvailablePred = nullptr; 59193323Sed for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 60193323Sed I != E; ++I) { 61193323Sed SUnit &Pred = *I->getSUnit(); 62193323Sed if (!Pred.isScheduled) { 63193323Sed // We found an available, but not scheduled, predecessor. If it's the 64193323Sed // only one we have found, keep track of it... otherwise give up. 65193323Sed if (OnlyAvailablePred && OnlyAvailablePred != &Pred) 66276479Sdim return nullptr; 67193323Sed OnlyAvailablePred = &Pred; 68193323Sed } 69193323Sed } 70218893Sdim 71193323Sed return OnlyAvailablePred; 72193323Sed} 73193323Sed 74208599Srdivackyvoid LatencyPriorityQueue::push(SUnit *SU) { 75193323Sed // Look at all of the successors of this node. Count the number of nodes that 76193323Sed // this node is the sole unscheduled node for. 77193323Sed unsigned NumNodesBlocking = 0; 78193323Sed for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 79198892Srdivacky I != E; ++I) { 80193323Sed if (getSingleUnscheduledPred(I->getSUnit()) == SU) 81193323Sed ++NumNodesBlocking; 82198892Srdivacky } 83193323Sed NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; 84218893Sdim 85208599Srdivacky Queue.push_back(SU); 86193323Sed} 87193323Sed 88193323Sed 89234353Sdim// scheduledNode - As nodes are scheduled, we look to see if there are any 90193323Sed// successor nodes that have a single unscheduled predecessor. If so, that 91193323Sed// single predecessor has a higher priority, since scheduling it will make 92193323Sed// the node available. 93234353Sdimvoid LatencyPriorityQueue::scheduledNode(SUnit *SU) { 94193323Sed for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 95198892Srdivacky I != E; ++I) { 96193323Sed AdjustPriorityOfUnscheduledPreds(I->getSUnit()); 97198892Srdivacky } 98193323Sed} 99193323Sed 100193323Sed/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just 101193323Sed/// scheduled. If SU is not itself available, then there is at least one 102193323Sed/// predecessor node that has not been scheduled yet. If SU has exactly ONE 103193323Sed/// unscheduled predecessor, we want to increase its priority: it getting 104193323Sed/// scheduled will make this node available, so it is better than some other 105193323Sed/// node of the same priority that will not make a node available. 106193323Sedvoid LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { 107193323Sed if (SU->isAvailable) return; // All preds scheduled. 108218893Sdim 109193323Sed SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU); 110276479Sdim if (!OnlyAvailablePred || !OnlyAvailablePred->isAvailable) return; 111218893Sdim 112193323Sed // Okay, we found a single predecessor that is available, but not scheduled. 113193323Sed // Since it is available, it must be in the priority queue. First remove it. 114193323Sed remove(OnlyAvailablePred); 115193323Sed 116193323Sed // Reinsert the node into the priority queue, which recomputes its 117193323Sed // NumNodesSolelyBlocking value. 118193323Sed push(OnlyAvailablePred); 119193323Sed} 120208599Srdivacky 121208599SrdivackySUnit *LatencyPriorityQueue::pop() { 122276479Sdim if (empty()) return nullptr; 123208599Srdivacky std::vector<SUnit *>::iterator Best = Queue.begin(); 124276479Sdim for (std::vector<SUnit *>::iterator I = std::next(Queue.begin()), 125208599Srdivacky E = Queue.end(); I != E; ++I) 126208599Srdivacky if (Picker(*Best, *I)) 127208599Srdivacky Best = I; 128208599Srdivacky SUnit *V = *Best; 129276479Sdim if (Best != std::prev(Queue.end())) 130208599Srdivacky std::swap(*Best, Queue.back()); 131208599Srdivacky Queue.pop_back(); 132208599Srdivacky return V; 133208599Srdivacky} 134208599Srdivacky 135208599Srdivackyvoid LatencyPriorityQueue::remove(SUnit *SU) { 136208599Srdivacky assert(!Queue.empty() && "Queue is empty!"); 137314564Sdim std::vector<SUnit *>::iterator I = find(Queue, SU); 138327952Sdim assert(I != Queue.end() && "Queue doesn't contain the SU being removed!"); 139276479Sdim if (I != std::prev(Queue.end())) 140208599Srdivacky std::swap(*I, Queue.back()); 141208599Srdivacky Queue.pop_back(); 142208599Srdivacky} 143341825Sdim 144341825Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 145341825SdimLLVM_DUMP_METHOD void LatencyPriorityQueue::dump(ScheduleDAG *DAG) const { 146341825Sdim dbgs() << "Latency Priority Queue\n"; 147341825Sdim dbgs() << " Number of Queue Entries: " << Queue.size() << "\n"; 148341825Sdim for (auto const &SU : Queue) { 149341825Sdim dbgs() << " "; 150341825Sdim SU->dump(DAG); 151341825Sdim } 152341825Sdim} 153341825Sdim#endif 154