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 16343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/LatencyPriorityQueue.h" 17ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman#include "llvm/Support/Debug.h" 182da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick#include "llvm/Support/raw_ostream.h" 19ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohmanusing namespace llvm; 20ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 21dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "scheduler" 22dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 23ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohmanbool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { 248749b61178228ba1fb2668034d79da1b247173d7Dan Gohman // The isScheduleHigh flag allows nodes with wraparound dependencies that 258749b61178228ba1fb2668034d79da1b247173d7Dan Gohman // cannot easily be modeled as edges with latencies to be scheduled as 268749b61178228ba1fb2668034d79da1b247173d7Dan Gohman // soon as possible in a top-down schedule. 278749b61178228ba1fb2668034d79da1b247173d7Dan Gohman if (LHS->isScheduleHigh && !RHS->isScheduleHigh) 288749b61178228ba1fb2668034d79da1b247173d7Dan Gohman return false; 298749b61178228ba1fb2668034d79da1b247173d7Dan Gohman if (!LHS->isScheduleHigh && RHS->isScheduleHigh) 308749b61178228ba1fb2668034d79da1b247173d7Dan Gohman return true; 318749b61178228ba1fb2668034d79da1b247173d7Dan Gohman 32ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned LHSNum = LHS->NodeNum; 33ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned RHSNum = RHS->NodeNum; 34ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 35ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // The most important heuristic is scheduling the critical path. 36ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned LHSLatency = PQ->getLatency(LHSNum); 37ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned RHSLatency = PQ->getLatency(RHSNum); 38ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (LHSLatency < RHSLatency) return true; 39ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (LHSLatency > RHSLatency) return false; 406e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 41ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // After that, if two nodes have identical latencies, look to see if one will 42ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // unblock more other nodes than the other. 43ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum); 44ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum); 45ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (LHSBlocked < RHSBlocked) return true; 46ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (LHSBlocked > RHSBlocked) return false; 476e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 48ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // Finally, just to provide a stable ordering, use the node number as a 49ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // deciding factor. 50b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick return RHSNum < LHSNum; 51ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman} 52ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 53ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 54ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor 55ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// of SU, return it, otherwise return null. 56ade9f1893412184c164aa3eb55a3e007ec647303Dan GohmanSUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { 57dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SUnit *OnlyAvailablePred = nullptr; 58ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 59ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman I != E; ++I) { 6054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit &Pred = *I->getSUnit(); 61ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (!Pred.isScheduled) { 62ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // We found an available, but not scheduled, predecessor. If it's the 63ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // only one we have found, keep track of it... otherwise give up. 64ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman if (OnlyAvailablePred && OnlyAvailablePred != &Pred) 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 66ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman OnlyAvailablePred = &Pred; 67ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman } 68ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman } 696e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 70ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman return OnlyAvailablePred; 71ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman} 72ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 73a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohmanvoid LatencyPriorityQueue::push(SUnit *SU) { 74ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // Look at all of the successors of this node. Count the number of nodes that 75ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // this node is the sole unscheduled node for. 76ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned NumNodesBlocking = 0; 77ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 784de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin I != E; ++I) { 7954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (getSingleUnscheduledPred(I->getSUnit()) == SU) 80ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman ++NumNodesBlocking; 814de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin } 82ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; 836e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 8493d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman Queue.push_back(SU); 85ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman} 86ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 87ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 88953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick// scheduledNode - As nodes are scheduled, we look to see if there are any 89ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// successor nodes that have a single unscheduled predecessor. If so, that 90ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// single predecessor has a higher priority, since scheduling it will make 91ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// the node available. 92953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trickvoid LatencyPriorityQueue::scheduledNode(SUnit *SU) { 93ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 944de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin I != E; ++I) { 9554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AdjustPriorityOfUnscheduledPreds(I->getSUnit()); 964de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin } 97ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman} 98ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 99ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just 100ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// scheduled. If SU is not itself available, then there is at least one 101ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// predecessor node that has not been scheduled yet. If SU has exactly ONE 102ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// unscheduled predecessor, we want to increase its priority: it getting 103ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// scheduled will make this node available, so it is better than some other 104ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman/// node of the same priority that will not make a node available. 105ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohmanvoid LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { 1066560c000a1327b6a023badafed974f35fa1bdc3bDan Gohman if (SU->isAvailable) return; // All preds scheduled. 1076e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 108ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU); 109dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!OnlyAvailablePred || !OnlyAvailablePred->isAvailable) return; 1106e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 111ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // Okay, we found a single predecessor that is available, but not scheduled. 112ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // Since it is available, it must be in the priority queue. First remove it. 113ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman remove(OnlyAvailablePred); 114ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 115ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // Reinsert the node into the priority queue, which recomputes its 116ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // NumNodesSolelyBlocking value. 117ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman push(OnlyAvailablePred); 118ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman} 11993d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman 12093d343357944beb701d425fc7ef00dd7b0a32bd7Dan GohmanSUnit *LatencyPriorityQueue::pop() { 121dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (empty()) return nullptr; 12293d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman std::vector<SUnit *>::iterator Best = Queue.begin(); 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (std::vector<SUnit *>::iterator I = std::next(Queue.begin()), 12493d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman E = Queue.end(); I != E; ++I) 12593d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman if (Picker(*Best, *I)) 12693d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman Best = I; 12793d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman SUnit *V = *Best; 12836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Best != std::prev(Queue.end())) 12993d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman std::swap(*Best, Queue.back()); 13093d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman Queue.pop_back(); 13193d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman return V; 13293d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman} 13393d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman 13493d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohmanvoid LatencyPriorityQueue::remove(SUnit *SU) { 13593d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman assert(!Queue.empty() && "Queue is empty!"); 13693d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman std::vector<SUnit *>::iterator I = std::find(Queue.begin(), Queue.end(), SU); 13736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I != std::prev(Queue.end())) 13893d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman std::swap(*I, Queue.back()); 13993d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman Queue.pop_back(); 14093d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman} 1412da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 1422da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick#ifdef NDEBUG 1432da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trickvoid LatencyPriorityQueue::dump(ScheduleDAG *DAG) const {} 1442da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick#else 1452da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trickvoid LatencyPriorityQueue::dump(ScheduleDAG *DAG) const { 1462da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick LatencyPriorityQueue q = *this; 1472da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick while (!q.empty()) { 1482da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick SUnit *su = q.pop(); 1492da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick dbgs() << "Height " << su->getHeight() << ": "; 1502da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick su->dump(DAG); 1512da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick } 1522da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick} 1532da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick#endif 154