Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LatencyPriorityQueue.cpp
Line
Count
Source (jump to first uncovered line)
1
//===---- LatencyPriorityQueue.cpp - A latency-oriented priority queue ----===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file implements the LatencyPriorityQueue class, which is a
10
// SchedulingPriorityQueue that schedules using latency information to
11
// reduce the length of the critical path through the basic block.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "llvm/CodeGen/LatencyPriorityQueue.h"
16
#include "llvm/Config/llvm-config.h"
17
#include "llvm/Support/Debug.h"
18
#include "llvm/Support/raw_ostream.h"
19
using namespace llvm;
20
21
#define DEBUG_TYPE "scheduler"
22
23
1.22M
bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
24
1.22M
  // The isScheduleHigh flag allows nodes with wraparound dependencies that
25
1.22M
  // cannot easily be modeled as edges with latencies to be scheduled as
26
1.22M
  // soon as possible in a top-down schedule.
27
1.22M
  if (LHS->isScheduleHigh && 
!RHS->isScheduleHigh0
)
28
0
    return false;
29
1.22M
  if (!LHS->isScheduleHigh && RHS->isScheduleHigh)
30
0
    return true;
31
1.22M
32
1.22M
  unsigned LHSNum = LHS->NodeNum;
33
1.22M
  unsigned RHSNum = RHS->NodeNum;
34
1.22M
35
1.22M
  // The most important heuristic is scheduling the critical path.
36
1.22M
  unsigned LHSLatency = PQ->getLatency(LHSNum);
37
1.22M
  unsigned RHSLatency = PQ->getLatency(RHSNum);
38
1.22M
  if (LHSLatency < RHSLatency) 
return true180k
;
39
1.04M
  if (LHSLatency > RHSLatency) 
return false401k
;
40
638k
41
638k
  // After that, if two nodes have identical latencies, look to see if one will
42
638k
  // unblock more other nodes than the other.
43
638k
  unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum);
44
638k
  unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum);
45
638k
  if (LHSBlocked < RHSBlocked) 
return true31.3k
;
46
607k
  if (LHSBlocked > RHSBlocked) 
return false36.8k
;
47
570k
48
570k
  // Finally, just to provide a stable ordering, use the node number as a
49
570k
  // deciding factor.
50
570k
  return RHSNum < LHSNum;
51
570k
}
52
53
54
/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
55
/// of SU, return it, otherwise return null.
56
4.32M
SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
57
4.32M
  SUnit *OnlyAvailablePred = nullptr;
58
4.32M
  for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
59
23.0M
       I != E; 
++I18.7M
) {
60
21.2M
    SUnit &Pred = *I->getSUnit();
61
21.2M
    if (!Pred.isScheduled) {
62
7.12M
      // We found an available, but not scheduled, predecessor.  If it's the
63
7.12M
      // only one we have found, keep track of it... otherwise give up.
64
7.12M
      if (OnlyAvailablePred && 
OnlyAvailablePred != &Pred3.50M
)
65
2.49M
        return nullptr;
66
4.62M
      OnlyAvailablePred = &Pred;
67
4.62M
    }
68
21.2M
  }
69
4.32M
70
4.32M
  
return OnlyAvailablePred1.82M
;
71
4.32M
}
72
73
806k
void LatencyPriorityQueue::push(SUnit *SU) {
74
806k
  // Look at all of the successors of this node.  Count the number of nodes that
75
806k
  // this node is the sole unscheduled node for.
76
806k
  unsigned NumNodesBlocking = 0;
77
806k
  for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
78
3.20M
       I != E; 
++I2.39M
) {
79
2.39M
    if (getSingleUnscheduledPred(I->getSUnit()) == SU)
80
775k
      ++NumNodesBlocking;
81
2.39M
  }
82
806k
  NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
83
806k
84
806k
  Queue.push_back(SU);
85
806k
}
86
87
88
// scheduledNode - As nodes are scheduled, we look to see if there are any
89
// successor nodes that have a single unscheduled predecessor.  If so, that
90
// single predecessor has a higher priority, since scheduling it will make
91
// the node available.
92
653k
void LatencyPriorityQueue::scheduledNode(SUnit *SU) {
93
653k
  for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
94
2.57M
       I != E; 
++I1.92M
) {
95
1.92M
    AdjustPriorityOfUnscheduledPreds(I->getSUnit());
96
1.92M
  }
97
653k
}
98
99
/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
100
/// scheduled.  If SU is not itself available, then there is at least one
101
/// predecessor node that has not been scheduled yet.  If SU has exactly ONE
102
/// unscheduled predecessor, we want to increase its priority: it getting
103
/// scheduled will make this node available, so it is better than some other
104
/// node of the same priority that will not make a node available.
105
1.92M
void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) {
106
1.92M
  if (SU->isAvailable) 
return0
; // All preds scheduled.
107
1.92M
108
1.92M
  SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
109
1.92M
  if (!OnlyAvailablePred || 
!OnlyAvailablePred->isAvailable347k
)
return1.84M
;
110
78.9k
111
78.9k
  // Okay, we found a single predecessor that is available, but not scheduled.
112
78.9k
  // Since it is available, it must be in the priority queue.  First remove it.
113
78.9k
  remove(OnlyAvailablePred);
114
78.9k
115
78.9k
  // Reinsert the node into the priority queue, which recomputes its
116
78.9k
  // NumNodesSolelyBlocking value.
117
78.9k
  push(OnlyAvailablePred);
118
78.9k
}
119
120
727k
SUnit *LatencyPriorityQueue::pop() {
121
727k
  if (empty()) 
return nullptr0
;
122
727k
  std::vector<SUnit *>::iterator Best = Queue.begin();
123
727k
  for (std::vector<SUnit *>::iterator I = std::next(Queue.begin()),
124
1.94M
       E = Queue.end(); I != E; 
++I1.22M
)
125
1.22M
    if (Picker(*Best, *I))
126
417k
      Best = I;
127
727k
  SUnit *V = *Best;
128
727k
  if (Best != std::prev(Queue.end()))
129
164k
    std::swap(*Best, Queue.back());
130
727k
  Queue.pop_back();
131
727k
  return V;
132
727k
}
133
134
78.9k
void LatencyPriorityQueue::remove(SUnit *SU) {
135
78.9k
  assert(!Queue.empty() && "Queue is empty!");
136
78.9k
  std::vector<SUnit *>::iterator I = find(Queue, SU);
137
78.9k
  assert(I != Queue.end() && "Queue doesn't contain the SU being removed!");
138
78.9k
  if (I != std::prev(Queue.end()))
139
14.6k
    std::swap(*I, Queue.back());
140
78.9k
  Queue.pop_back();
141
78.9k
}
142
143
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
144
LLVM_DUMP_METHOD void LatencyPriorityQueue::dump(ScheduleDAG *DAG) const {
145
  dbgs() << "Latency Priority Queue\n";
146
  dbgs() << "  Number of Queue Entries: " << Queue.size() << "\n";
147
  for (const SUnit *SU : Queue) {
148
    dbgs() << "    ";
149
    DAG->dumpNode(*SU);
150
  }
151
}
152
#endif