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