LatencyPriorityQueue.cpp revision 54e4c36a7349e94a84773afb56eccd4ca65b49e9
1//===---- LatencyPriorityQueue.cpp - A latency-oriented priority queue ----===// 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 file implements the LatencyPriorityQueue class, which is a 11// SchedulingPriorityQueue that schedules using latency information to 12// reduce the length of the critical path through the basic block. 13// 14//===----------------------------------------------------------------------===// 15 16#define DEBUG_TYPE "scheduler" 17#include "llvm/CodeGen/LatencyPriorityQueue.h" 18#include "llvm/Support/Debug.h" 19using namespace llvm; 20 21bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { 22 unsigned LHSNum = LHS->NodeNum; 23 unsigned RHSNum = RHS->NodeNum; 24 25 // The most important heuristic is scheduling the critical path. 26 unsigned LHSLatency = PQ->getLatency(LHSNum); 27 unsigned RHSLatency = PQ->getLatency(RHSNum); 28 if (LHSLatency < RHSLatency) return true; 29 if (LHSLatency > RHSLatency) return false; 30 31 // After that, if two nodes have identical latencies, look to see if one will 32 // unblock more other nodes than the other. 33 unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum); 34 unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum); 35 if (LHSBlocked < RHSBlocked) return true; 36 if (LHSBlocked > RHSBlocked) return false; 37 38 // Finally, just to provide a stable ordering, use the node number as a 39 // deciding factor. 40 return LHSNum < RHSNum; 41} 42 43 44/// CalcNodePriority - Calculate the maximal path from the node to the exit. 45/// 46int LatencyPriorityQueue::CalcLatency(const SUnit &SU) { 47 int &Latency = Latencies[SU.NodeNum]; 48 if (Latency != -1) 49 return Latency; 50 51 std::vector<const SUnit*> WorkList; 52 WorkList.push_back(&SU); 53 while (!WorkList.empty()) { 54 const SUnit *Cur = WorkList.back(); 55 unsigned CurLatency = Cur->Latency; 56 bool AllDone = true; 57 unsigned MaxSuccLatency = 0; 58 for (SUnit::const_succ_iterator I = Cur->Succs.begin(),E = Cur->Succs.end(); 59 I != E; ++I) { 60 int SuccLatency = Latencies[I->getSUnit()->NodeNum]; 61 if (SuccLatency == -1) { 62 AllDone = false; 63 WorkList.push_back(I->getSUnit()); 64 } else { 65 // This assumes that there's no delay for reusing registers. 66 unsigned NewLatency = SuccLatency + CurLatency; 67 MaxSuccLatency = std::max(MaxSuccLatency, NewLatency); 68 } 69 } 70 if (AllDone) { 71 Latencies[Cur->NodeNum] = MaxSuccLatency; 72 WorkList.pop_back(); 73 } 74 } 75 76 return Latency; 77} 78 79/// CalculatePriorities - Calculate priorities of all scheduling units. 80void LatencyPriorityQueue::CalculatePriorities() { 81 Latencies.assign(SUnits->size(), -1); 82 NumNodesSolelyBlocking.assign(SUnits->size(), 0); 83 84 // For each node, calculate the maximal path from the node to the exit. 85 std::vector<std::pair<const SUnit*, unsigned> > WorkList; 86 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { 87 const SUnit *SU = &(*SUnits)[i]; 88 if (SU->Succs.empty()) 89 WorkList.push_back(std::make_pair(SU, 0U)); 90 } 91 92 while (!WorkList.empty()) { 93 const SUnit *SU = WorkList.back().first; 94 unsigned SuccLat = WorkList.back().second; 95 WorkList.pop_back(); 96 int &Latency = Latencies[SU->NodeNum]; 97 if (Latency == -1 || (SU->Latency + SuccLat) > (unsigned)Latency) { 98 Latency = SU->Latency + SuccLat; 99 for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end(); 100 I != E; ++I) 101 WorkList.push_back(std::make_pair(I->getSUnit(), Latency)); 102 } 103 } 104} 105 106/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor 107/// of SU, return it, otherwise return null. 108SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { 109 SUnit *OnlyAvailablePred = 0; 110 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 111 I != E; ++I) { 112 SUnit &Pred = *I->getSUnit(); 113 if (!Pred.isScheduled) { 114 // We found an available, but not scheduled, predecessor. If it's the 115 // only one we have found, keep track of it... otherwise give up. 116 if (OnlyAvailablePred && OnlyAvailablePred != &Pred) 117 return 0; 118 OnlyAvailablePred = &Pred; 119 } 120 } 121 122 return OnlyAvailablePred; 123} 124 125void LatencyPriorityQueue::push_impl(SUnit *SU) { 126 // Look at all of the successors of this node. Count the number of nodes that 127 // this node is the sole unscheduled node for. 128 unsigned NumNodesBlocking = 0; 129 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 130 I != E; ++I) 131 if (getSingleUnscheduledPred(I->getSUnit()) == SU) 132 ++NumNodesBlocking; 133 NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; 134 135 Queue.push(SU); 136} 137 138 139// ScheduledNode - As nodes are scheduled, we look to see if there are any 140// successor nodes that have a single unscheduled predecessor. If so, that 141// single predecessor has a higher priority, since scheduling it will make 142// the node available. 143void LatencyPriorityQueue::ScheduledNode(SUnit *SU) { 144 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 145 I != E; ++I) 146 AdjustPriorityOfUnscheduledPreds(I->getSUnit()); 147} 148 149/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just 150/// scheduled. If SU is not itself available, then there is at least one 151/// predecessor node that has not been scheduled yet. If SU has exactly ONE 152/// unscheduled predecessor, we want to increase its priority: it getting 153/// scheduled will make this node available, so it is better than some other 154/// node of the same priority that will not make a node available. 155void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { 156 if (SU->isAvailable) return; // All preds scheduled. 157 158 SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU); 159 if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) return; 160 161 // Okay, we found a single predecessor that is available, but not scheduled. 162 // Since it is available, it must be in the priority queue. First remove it. 163 remove(OnlyAvailablePred); 164 165 // Reinsert the node into the priority queue, which recomputes its 166 // NumNodesSolelyBlocking value. 167 push(OnlyAvailablePred); 168} 169