LatencyPriorityQueue.cpp revision 953be893e8cffa0ef9bf410036cd96aeb526e98a
1ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman//===---- LatencyPriorityQueue.cpp - A latency-oriented priority queue ----===// 2ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// 3ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// The LLVM Compiler Infrastructure 4ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// 5ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// This file is distributed under the University of Illinois Open Source 6ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// License. See LICENSE.TXT for details. 7ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// 8ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman//===----------------------------------------------------------------------===// 9ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// 10ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// This file implements the LatencyPriorityQueue class, which is a 11ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// SchedulingPriorityQueue that schedules using latency information to 12ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// reduce the length of the critical path through the basic block. 13ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// 14ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman//===----------------------------------------------------------------------===// 15ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 16ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman#define DEBUG_TYPE "scheduler" 17343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/LatencyPriorityQueue.h" 18ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman#include "llvm/Support/Debug.h" 192da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick#include "llvm/Support/raw_ostream.h" 20ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohmanusing namespace llvm; 21ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 22ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohmanbool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { 238749b61178228ba1fb2668034d79da1b247173d7Dan Gohman // The isScheduleHigh flag allows nodes with wraparound dependencies that 248749b61178228ba1fb2668034d79da1b247173d7Dan Gohman // cannot easily be modeled as edges with latencies to be scheduled as 258749b61178228ba1fb2668034d79da1b247173d7Dan Gohman // soon as possible in a top-down schedule. 268749b61178228ba1fb2668034d79da1b247173d7Dan Gohman if (LHS->isScheduleHigh && !RHS->isScheduleHigh) 278749b61178228ba1fb2668034d79da1b247173d7Dan Gohman return false; 288749b61178228ba1fb2668034d79da1b247173d7Dan Gohman if (!LHS->isScheduleHigh && RHS->isScheduleHigh) 298749b61178228ba1fb2668034d79da1b247173d7Dan Gohman return true; 308749b61178228ba1fb2668034d79da1b247173d7Dan Gohman 31ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned LHSNum = LHS->NodeNum; 32ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned RHSNum = RHS->NodeNum; 33ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 34ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // The most important heuristic is scheduling the critical path. 35ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned LHSLatency = PQ->getLatency(LHSNum); 36ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned RHSLatency = PQ->getLatency(RHSNum); 37ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (LHSLatency < RHSLatency) return true; 38ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (LHSLatency > RHSLatency) return false; 396e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 40ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // After that, if two nodes have identical latencies, look to see if one will 41ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // unblock more other nodes than the other. 42ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum); 43ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum); 44ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (LHSBlocked < RHSBlocked) return true; 45ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (LHSBlocked > RHSBlocked) return false; 466e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 47ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // Finally, just to provide a stable ordering, use the node number as a 48ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // deciding factor. 49b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick return RHSNum < LHSNum; 50ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman} 51ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 52ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 53ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor 54ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// of SU, return it, otherwise return null. 55ade9f1893412184c164aa3eb55a3e007ec647303Dan GohmanSUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { 56ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman SUnit *OnlyAvailablePred = 0; 57ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 58ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman I != E; ++I) { 5954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit &Pred = *I->getSUnit(); 60ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (!Pred.isScheduled) { 61ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // We found an available, but not scheduled, predecessor. If it's the 62ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // only one we have found, keep track of it... otherwise give up. 63ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (OnlyAvailablePred && OnlyAvailablePred != &Pred) 64ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman return 0; 65ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman OnlyAvailablePred = &Pred; 66ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman } 67ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman } 686e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 69ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman return OnlyAvailablePred; 70ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman} 71ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 72a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohmanvoid LatencyPriorityQueue::push(SUnit *SU) { 73ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // Look at all of the successors of this node. Count the number of nodes that 74ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // this node is the sole unscheduled node for. 75ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned NumNodesBlocking = 0; 76ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 774de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin I != E; ++I) { 7854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (getSingleUnscheduledPred(I->getSUnit()) == SU) 79ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman ++NumNodesBlocking; 804de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin } 81ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; 826e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 8393d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman Queue.push_back(SU); 84ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman} 85ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 86ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 87953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick// scheduledNode - As nodes are scheduled, we look to see if there are any 88ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// successor nodes that have a single unscheduled predecessor. If so, that 89ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// single predecessor has a higher priority, since scheduling it will make 90ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// the node available. 91953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trickvoid LatencyPriorityQueue::scheduledNode(SUnit *SU) { 92ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 934de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin I != E; ++I) { 9454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AdjustPriorityOfUnscheduledPreds(I->getSUnit()); 954de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin } 96ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman} 97ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 98ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just 99ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// scheduled. If SU is not itself available, then there is at least one 100ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// predecessor node that has not been scheduled yet. If SU has exactly ONE 101ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// unscheduled predecessor, we want to increase its priority: it getting 102ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// scheduled will make this node available, so it is better than some other 103ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// node of the same priority that will not make a node available. 104ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohmanvoid LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { 1056560c000a1327b6a023badafed974f35fa1bdc3bDan Gohman if (SU->isAvailable) return; // All preds scheduled. 1066e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 107ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU); 108ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) return; 1096e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 110ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // Okay, we found a single predecessor that is available, but not scheduled. 111ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // Since it is available, it must be in the priority queue. First remove it. 112ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman remove(OnlyAvailablePred); 113ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 114ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // Reinsert the node into the priority queue, which recomputes its 115ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // NumNodesSolelyBlocking value. 116ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman push(OnlyAvailablePred); 117ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman} 11893d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman 11993d343357944beb701d425fc7ef00dd7b0a32bd7Dan GohmanSUnit *LatencyPriorityQueue::pop() { 12093d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman if (empty()) return NULL; 12193d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman std::vector<SUnit *>::iterator Best = Queue.begin(); 12210e02a017a877b750d4cdf0ebf11b90dee5e0d61Oscar Fuentes for (std::vector<SUnit *>::iterator I = llvm::next(Queue.begin()), 12393d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman E = Queue.end(); I != E; ++I) 12493d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman if (Picker(*Best, *I)) 12593d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman Best = I; 12693d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman SUnit *V = *Best; 12793d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman if (Best != prior(Queue.end())) 12893d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman std::swap(*Best, Queue.back()); 12993d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman Queue.pop_back(); 13093d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman return V; 13193d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman} 13293d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman 13393d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohmanvoid LatencyPriorityQueue::remove(SUnit *SU) { 13493d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman assert(!Queue.empty() && "Queue is empty!"); 13593d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman std::vector<SUnit *>::iterator I = std::find(Queue.begin(), Queue.end(), SU); 13693d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman if (I != prior(Queue.end())) 13793d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman std::swap(*I, Queue.back()); 13893d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman Queue.pop_back(); 13993d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman} 1402da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 1412da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick#ifdef NDEBUG 1422da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trickvoid LatencyPriorityQueue::dump(ScheduleDAG *DAG) const {} 1432da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick#else 1442da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trickvoid LatencyPriorityQueue::dump(ScheduleDAG *DAG) const { 1452da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick LatencyPriorityQueue q = *this; 1462da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick while (!q.empty()) { 1472da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick SUnit *su = q.pop(); 1482da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick dbgs() << "Height " << su->getHeight() << ": "; 1492da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick su->dump(DAG); 1502da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick } 1512da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick} 1522da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick#endif 153