Line data Source code
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 : #include "llvm/CodeGen/LatencyPriorityQueue.h"
17 : #include "llvm/Config/llvm-config.h"
18 : #include "llvm/Support/Debug.h"
19 : #include "llvm/Support/raw_ostream.h"
20 : using namespace llvm;
21 :
22 : #define DEBUG_TYPE "scheduler"
23 :
24 4516510 : bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
25 : // The isScheduleHigh flag allows nodes with wraparound dependencies that
26 : // cannot easily be modeled as edges with latencies to be scheduled as
27 : // soon as possible in a top-down schedule.
28 4516510 : if (LHS->isScheduleHigh && !RHS->isScheduleHigh)
29 : return false;
30 4516510 : if (!LHS->isScheduleHigh && RHS->isScheduleHigh)
31 : return true;
32 :
33 4516510 : unsigned LHSNum = LHS->NodeNum;
34 4516510 : unsigned RHSNum = RHS->NodeNum;
35 :
36 : // The most important heuristic is scheduling the critical path.
37 4516510 : unsigned LHSLatency = PQ->getLatency(LHSNum);
38 4516510 : unsigned RHSLatency = PQ->getLatency(RHSNum);
39 4516510 : if (LHSLatency < RHSLatency) return true;
40 4337256 : if (LHSLatency > RHSLatency) return false;
41 :
42 : // After that, if two nodes have identical latencies, look to see if one will
43 : // unblock more other nodes than the other.
44 3882374 : unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum);
45 : unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum);
46 3882374 : if (LHSBlocked < RHSBlocked) return true;
47 3860696 : if (LHSBlocked > RHSBlocked) return false;
48 :
49 : // Finally, just to provide a stable ordering, use the node number as a
50 : // deciding factor.
51 3830733 : return RHSNum < LHSNum;
52 : }
53 :
54 :
55 : /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
56 : /// of SU, return it, otherwise return null.
57 5053708 : SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
58 : SUnit *OnlyAvailablePred = nullptr;
59 20883934 : for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
60 25937642 : I != E; ++I) {
61 : SUnit &Pred = *I->getSUnit();
62 23266108 : if (!Pred.isScheduled) {
63 : // We found an available, but not scheduled, predecessor. If it's the
64 : // only one we have found, keep track of it... otherwise give up.
65 8293485 : if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
66 : return nullptr;
67 : OnlyAvailablePred = &Pred;
68 : }
69 : }
70 :
71 : return OnlyAvailablePred;
72 : }
73 :
74 1029088 : void LatencyPriorityQueue::push(SUnit *SU) {
75 : // Look at all of the successors of this node. Count the number of nodes that
76 : // this node is the sole unscheduled node for.
77 : unsigned NumNodesBlocking = 0;
78 3741884 : for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
79 3741884 : I != E; ++I) {
80 2712796 : if (getSingleUnscheduledPred(I->getSUnit()) == SU)
81 1133415 : ++NumNodesBlocking;
82 : }
83 1029088 : NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
84 :
85 1029088 : Queue.push_back(SU);
86 1029088 : }
87 :
88 :
89 : // scheduledNode - As nodes are scheduled, we look to see if there are any
90 : // successor nodes that have a single unscheduled predecessor. If so, that
91 : // single predecessor has a higher priority, since scheduling it will make
92 : // the node available.
93 900223 : void LatencyPriorityQueue::scheduledNode(SUnit *SU) {
94 2340912 : for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
95 3241135 : I != E; ++I) {
96 2340912 : AdjustPriorityOfUnscheduledPreds(I->getSUnit());
97 : }
98 900223 : }
99 :
100 : /// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
101 : /// scheduled. If SU is not itself available, then there is at least one
102 : /// predecessor node that has not been scheduled yet. If SU has exactly ONE
103 : /// unscheduled predecessor, we want to increase its priority: it getting
104 : /// scheduled will make this node available, so it is better than some other
105 : /// node of the same priority that will not make a node available.
106 2340912 : void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) {
107 2340912 : if (SU->isAvailable) return; // All preds scheduled.
108 :
109 2340912 : SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
110 2340912 : if (!OnlyAvailablePred || !OnlyAvailablePred->isAvailable) return;
111 :
112 : // Okay, we found a single predecessor that is available, but not scheduled.
113 : // Since it is available, it must be in the priority queue. First remove it.
114 92971 : remove(OnlyAvailablePred);
115 :
116 : // Reinsert the node into the priority queue, which recomputes its
117 : // NumNodesSolelyBlocking value.
118 92971 : push(OnlyAvailablePred);
119 : }
120 :
121 936117 : SUnit *LatencyPriorityQueue::pop() {
122 936117 : if (empty()) return nullptr;
123 : std::vector<SUnit *>::iterator Best = Queue.begin();
124 : for (std::vector<SUnit *>::iterator I = std::next(Queue.begin()),
125 5452627 : E = Queue.end(); I != E; ++I)
126 4516510 : if (Picker(*Best, *I))
127 : Best = I;
128 936117 : SUnit *V = *Best;
129 936117 : if (Best != std::prev(Queue.end()))
130 : std::swap(*Best, Queue.back());
131 : Queue.pop_back();
132 936117 : return V;
133 : }
134 :
135 92971 : void LatencyPriorityQueue::remove(SUnit *SU) {
136 : assert(!Queue.empty() && "Queue is empty!");
137 : std::vector<SUnit *>::iterator I = find(Queue, SU);
138 : assert(I != Queue.end() && "Queue doesn't contain the SU being removed!");
139 92971 : if (I != std::prev(Queue.end()))
140 : std::swap(*I, Queue.back());
141 : Queue.pop_back();
142 92971 : }
143 :
144 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
145 : LLVM_DUMP_METHOD void LatencyPriorityQueue::dump(ScheduleDAG *DAG) const {
146 : dbgs() << "Latency Priority Queue\n";
147 : dbgs() << " Number of Queue Entries: " << Queue.size() << "\n";
148 : for (const SUnit *SU : Queue) {
149 : dbgs() << " ";
150 : DAG->dumpNode(*SU);
151 : }
152 : }
153 : #endif
|
