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#define DEBUG_TYPE "scheduler" 17193323Sed#include "llvm/CodeGen/LatencyPriorityQueue.h" 18193323Sed#include "llvm/Support/Debug.h" 19218893Sdim#include "llvm/Support/raw_ostream.h" 20193323Sedusing namespace llvm; 21193323Sed 22193323Sedbool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { 23193323Sed // The isScheduleHigh flag allows nodes with wraparound dependencies that 24193323Sed // cannot easily be modeled as edges with latencies to be scheduled as 25193323Sed // soon as possible in a top-down schedule. 26193323Sed if (LHS->isScheduleHigh && !RHS->isScheduleHigh) 27193323Sed return false; 28193323Sed if (!LHS->isScheduleHigh && RHS->isScheduleHigh) 29193323Sed return true; 30193323Sed 31193323Sed unsigned LHSNum = LHS->NodeNum; 32193323Sed unsigned RHSNum = RHS->NodeNum; 33193323Sed 34193323Sed // The most important heuristic is scheduling the critical path. 35193323Sed unsigned LHSLatency = PQ->getLatency(LHSNum); 36193323Sed unsigned RHSLatency = PQ->getLatency(RHSNum); 37193323Sed if (LHSLatency < RHSLatency) return true; 38193323Sed if (LHSLatency > RHSLatency) return false; 39218893Sdim 40193323Sed // After that, if two nodes have identical latencies, look to see if one will 41193323Sed // unblock more other nodes than the other. 42193323Sed unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum); 43193323Sed unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum); 44193323Sed if (LHSBlocked < RHSBlocked) return true; 45193323Sed if (LHSBlocked > RHSBlocked) return false; 46218893Sdim 47193323Sed // Finally, just to provide a stable ordering, use the node number as a 48193323Sed // deciding factor. 49234353Sdim return RHSNum < LHSNum; 50193323Sed} 51193323Sed 52193323Sed 53193323Sed/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor 54193323Sed/// of SU, return it, otherwise return null. 55193323SedSUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { 56193323Sed SUnit *OnlyAvailablePred = 0; 57193323Sed for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 58193323Sed I != E; ++I) { 59193323Sed SUnit &Pred = *I->getSUnit(); 60193323Sed if (!Pred.isScheduled) { 61193323Sed // We found an available, but not scheduled, predecessor. If it's the 62193323Sed // only one we have found, keep track of it... otherwise give up. 63193323Sed if (OnlyAvailablePred && OnlyAvailablePred != &Pred) 64193323Sed return 0; 65193323Sed OnlyAvailablePred = &Pred; 66193323Sed } 67193323Sed } 68218893Sdim 69193323Sed return OnlyAvailablePred; 70193323Sed} 71193323Sed 72208599Srdivackyvoid LatencyPriorityQueue::push(SUnit *SU) { 73193323Sed // Look at all of the successors of this node. Count the number of nodes that 74193323Sed // this node is the sole unscheduled node for. 75193323Sed unsigned NumNodesBlocking = 0; 76193323Sed for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 77198892Srdivacky I != E; ++I) { 78193323Sed if (getSingleUnscheduledPred(I->getSUnit()) == SU) 79193323Sed ++NumNodesBlocking; 80198892Srdivacky } 81193323Sed NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; 82218893Sdim 83208599Srdivacky Queue.push_back(SU); 84193323Sed} 85193323Sed 86193323Sed 87234353Sdim// scheduledNode - As nodes are scheduled, we look to see if there are any 88193323Sed// successor nodes that have a single unscheduled predecessor. If so, that 89193323Sed// single predecessor has a higher priority, since scheduling it will make 90193323Sed// the node available. 91234353Sdimvoid LatencyPriorityQueue::scheduledNode(SUnit *SU) { 92193323Sed for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 93198892Srdivacky I != E; ++I) { 94193323Sed AdjustPriorityOfUnscheduledPreds(I->getSUnit()); 95198892Srdivacky } 96193323Sed} 97193323Sed 98193323Sed/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just 99193323Sed/// scheduled. If SU is not itself available, then there is at least one 100193323Sed/// predecessor node that has not been scheduled yet. If SU has exactly ONE 101193323Sed/// unscheduled predecessor, we want to increase its priority: it getting 102193323Sed/// scheduled will make this node available, so it is better than some other 103193323Sed/// node of the same priority that will not make a node available. 104193323Sedvoid LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { 105193323Sed if (SU->isAvailable) return; // All preds scheduled. 106218893Sdim 107193323Sed SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU); 108193323Sed if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) return; 109218893Sdim 110193323Sed // Okay, we found a single predecessor that is available, but not scheduled. 111193323Sed // Since it is available, it must be in the priority queue. First remove it. 112193323Sed remove(OnlyAvailablePred); 113193323Sed 114193323Sed // Reinsert the node into the priority queue, which recomputes its 115193323Sed // NumNodesSolelyBlocking value. 116193323Sed push(OnlyAvailablePred); 117193323Sed} 118208599Srdivacky 119208599SrdivackySUnit *LatencyPriorityQueue::pop() { 120208599Srdivacky if (empty()) return NULL; 121208599Srdivacky std::vector<SUnit *>::iterator Best = Queue.begin(); 122210299Sed for (std::vector<SUnit *>::iterator I = llvm::next(Queue.begin()), 123208599Srdivacky E = Queue.end(); I != E; ++I) 124208599Srdivacky if (Picker(*Best, *I)) 125208599Srdivacky Best = I; 126208599Srdivacky SUnit *V = *Best; 127208599Srdivacky if (Best != prior(Queue.end())) 128208599Srdivacky std::swap(*Best, Queue.back()); 129208599Srdivacky Queue.pop_back(); 130208599Srdivacky return V; 131208599Srdivacky} 132208599Srdivacky 133208599Srdivackyvoid LatencyPriorityQueue::remove(SUnit *SU) { 134208599Srdivacky assert(!Queue.empty() && "Queue is empty!"); 135208599Srdivacky std::vector<SUnit *>::iterator I = std::find(Queue.begin(), Queue.end(), SU); 136208599Srdivacky if (I != prior(Queue.end())) 137208599Srdivacky std::swap(*I, Queue.back()); 138208599Srdivacky Queue.pop_back(); 139208599Srdivacky} 140218893Sdim 141218893Sdim#ifdef NDEBUG 142218893Sdimvoid LatencyPriorityQueue::dump(ScheduleDAG *DAG) const {} 143218893Sdim#else 144218893Sdimvoid LatencyPriorityQueue::dump(ScheduleDAG *DAG) const { 145218893Sdim LatencyPriorityQueue q = *this; 146218893Sdim while (!q.empty()) { 147218893Sdim SUnit *su = q.pop(); 148218893Sdim dbgs() << "Height " << su->getHeight() << ": "; 149218893Sdim su->dump(DAG); 150218893Sdim } 151218893Sdim} 152218893Sdim#endif 153