LatencyPriorityQueue.cpp revision f55a2101e300d1b4d420a1e71ca839e3146bdf70 
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///
46void LatencyPriorityQueue::CalcLatency(const SUnit &SU) {
47  int &Latency = Latencies[SU.NodeNum];
48  if (Latency != -1)
49    return;
50
51  std::vector<const SUnit*> WorkList;
52  WorkList.push_back(&SU);
53  while (!WorkList.empty()) {
54    const SUnit *Cur = WorkList.back();
55    bool AllDone = true;
56    unsigned MaxSuccLatency = 0;
57    for (SUnit::const_succ_iterator I = Cur->Succs.begin(),E = Cur->Succs.end();
58         I != E; ++I) {
59      int SuccLatency = Latencies[I->getSUnit()->NodeNum];
60      if (SuccLatency == -1) {
61        AllDone = false;
62        WorkList.push_back(I->getSUnit());
63      } else {
64        unsigned NewLatency = SuccLatency + I->getLatency();
65        MaxSuccLatency = std::max(MaxSuccLatency, NewLatency);
66      }
67    }
68    if (AllDone) {
69      Latencies[Cur->NodeNum] = MaxSuccLatency;
70      WorkList.pop_back();
71    }
72  }
73}
74
75/// CalculatePriorities - Calculate priorities of all scheduling units.
76void LatencyPriorityQueue::CalculatePriorities() {
77  Latencies.assign(SUnits->size(), -1);
78  NumNodesSolelyBlocking.assign(SUnits->size(), 0);
79
80  // For each node, calculate the maximal path from the node to the exit.
81  for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
82    CalcLatency((*SUnits)[i]);
83}
84
85/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
86/// of SU, return it, otherwise return null.
87SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
88  SUnit *OnlyAvailablePred = 0;
89  for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
90       I != E; ++I) {
91    SUnit &Pred = *I->getSUnit();
92    if (!Pred.isScheduled) {
93      // We found an available, but not scheduled, predecessor.  If it's the
94      // only one we have found, keep track of it... otherwise give up.
95      if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
96        return 0;
97      OnlyAvailablePred = &Pred;
98    }
99  }
100
101  return OnlyAvailablePred;
102}
103
104void LatencyPriorityQueue::push_impl(SUnit *SU) {
105  // Look at all of the successors of this node.  Count the number of nodes that
106  // this node is the sole unscheduled node for.
107  unsigned NumNodesBlocking = 0;
108  for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
109       I != E; ++I)
110    if (getSingleUnscheduledPred(I->getSUnit()) == SU)
111      ++NumNodesBlocking;
112  NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
113
114  Queue.push(SU);
115}
116
117
118// ScheduledNode - As nodes are scheduled, we look to see if there are any
119// successor nodes that have a single unscheduled predecessor.  If so, that
120// single predecessor has a higher priority, since scheduling it will make
121// the node available.
122void LatencyPriorityQueue::ScheduledNode(SUnit *SU) {
123  for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
124       I != E; ++I)
125    AdjustPriorityOfUnscheduledPreds(I->getSUnit());
126}
127
128/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
129/// scheduled.  If SU is not itself available, then there is at least one
130/// predecessor node that has not been scheduled yet.  If SU has exactly ONE
131/// unscheduled predecessor, we want to increase its priority: it getting
132/// scheduled will make this node available, so it is better than some other
133/// node of the same priority that will not make a node available.
134void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) {
135  if (SU->isAvailable) return;  // All preds scheduled.
136
137  SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
138  if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) return;
139
140  // Okay, we found a single predecessor that is available, but not scheduled.
141  // Since it is available, it must be in the priority queue.  First remove it.
142  remove(OnlyAvailablePred);
143
144  // Reinsert the node into the priority queue, which recomputes its
145  // NumNodesSolelyBlocking value.
146  push(OnlyAvailablePred);
147}
148