Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/ScoreboardHazardRecognizer.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ScoreboardHazardRecognizer.cpp - Scheduler Support -----------------===//
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 ScoreboardHazardRecognizer class, which
10
// encapsultes hazard-avoidance heuristics for scheduling, based on the
11
// scheduling itineraries specified for the target.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "llvm/CodeGen/ScoreboardHazardRecognizer.h"
16
#include "llvm/CodeGen/ScheduleDAG.h"
17
#include "llvm/CodeGen/TargetInstrInfo.h"
18
#include "llvm/Config/llvm-config.h"
19
#include "llvm/MC/MCInstrDesc.h"
20
#include "llvm/MC/MCInstrItineraries.h"
21
#include "llvm/Support/Compiler.h"
22
#include "llvm/Support/Debug.h"
23
#include "llvm/Support/raw_ostream.h"
24
#include <cassert>
25
26
using namespace llvm;
27
28
#define DEBUG_TYPE DebugType
29
30
ScoreboardHazardRecognizer::ScoreboardHazardRecognizer(
31
    const InstrItineraryData *II, const ScheduleDAG *SchedDAG,
32
    const char *ParentDebugType)
33
    : ScheduleHazardRecognizer(), DebugType(ParentDebugType), ItinData(II),
34
941k
      DAG(SchedDAG) {
35
941k
  (void)DebugType;
36
941k
  // Determine the maximum depth of any itinerary. This determines the depth of
37
941k
  // the scoreboard. We always make the scoreboard at least 1 cycle deep to
38
941k
  // avoid dealing with the boundary condition.
39
941k
  unsigned ScoreboardDepth = 1;
40
941k
  if (ItinData && 
!ItinData->isEmpty()124k
) {
41
97.2M
    for (unsigned idx = 0; ; 
++idx97.0M
) {
42
97.2M
      if (ItinData->isEndMarker(idx))
43
123k
        break;
44
97.0M
45
97.0M
      const InstrStage *IS = ItinData->beginStage(idx);
46
97.0M
      const InstrStage *E = ItinData->endStage(idx);
47
97.0M
      unsigned CurCycle = 0;
48
97.0M
      unsigned ItinDepth = 0;
49
272M
      for (; IS != E; 
++IS175M
) {
50
175M
        unsigned StageDepth = CurCycle + IS->getCycles();
51
175M
        if (ItinDepth < StageDepth) 
ItinDepth = StageDepth112M
;
52
175M
        CurCycle += IS->getNextCycles();
53
175M
      }
54
97.0M
55
97.0M
      // Find the next power-of-2 >= ItinDepth
56
97.6M
      while (ItinDepth > ScoreboardDepth) {
57
580k
        ScoreboardDepth *= 2;
58
580k
        // Don't set MaxLookAhead until we find at least one nonzero stage.
59
580k
        // This way, an itinerary with no stages has MaxLookAhead==0, which
60
580k
        // completely bypasses the scoreboard hazard logic.
61
580k
        MaxLookAhead = ScoreboardDepth;
62
580k
      }
63
97.0M
    }
64
123k
  }
65
941k
66
941k
  ReservedScoreboard.reset(ScoreboardDepth);
67
941k
  RequiredScoreboard.reset(ScoreboardDepth);
68
941k
69
941k
  // If MaxLookAhead is not set above, then we are not enabled.
70
941k
  if (!isEnabled())
71
941k
    LLVM_DEBUG(dbgs() << "Disabled scoreboard hazard recognizer\n");
72
941k
  else {
73
112k
    // A nonempty itinerary must have a SchedModel.
74
112k
    IssueWidth = ItinData->SchedModel.IssueWidth;
75
112k
    LLVM_DEBUG(dbgs() << "Using scoreboard hazard recognizer: Depth = "
76
112k
                      << ScoreboardDepth << '\n');
77
112k
  }
78
941k
}
79
80
388k
void ScoreboardHazardRecognizer::Reset() {
81
388k
  IssueCount = 0;
82
388k
  RequiredScoreboard.reset();
83
388k
  ReservedScoreboard.reset();
84
388k
}
85
86
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
87
LLVM_DUMP_METHOD void ScoreboardHazardRecognizer::Scoreboard::dump() const {
88
  dbgs() << "Scoreboard:\n";
89
90
  unsigned last = Depth - 1;
91
  while ((last > 0) && ((*this)[last] == 0))
92
    last--;
93
94
  for (unsigned i = 0; i <= last; i++) {
95
    unsigned FUs = (*this)[i];
96
    dbgs() << "\t";
97
    for (int j = 31; j >= 0; j--)
98
      dbgs() << ((FUs & (1 << j)) ? '1' : '0');
99
    dbgs() << '\n';
100
  }
101
}
102
#endif
103
104
913k
bool ScoreboardHazardRecognizer::atIssueLimit() const {
105
913k
  if (IssueWidth == 0)
106
10.0k
    return false;
107
903k
108
903k
  return IssueCount == IssueWidth;
109
903k
}
110
111
ScheduleHazardRecognizer::HazardType
112
1.77M
ScoreboardHazardRecognizer::getHazardType(SUnit *SU, int Stalls) {
113
1.77M
  if (!ItinData || 
ItinData->isEmpty()1.77M
)
114
16.2k
    return NoHazard;
115
1.76M
116
1.76M
  // Note that stalls will be negative for bottom-up scheduling.
117
1.76M
  int cycle = Stalls;
118
1.76M
119
1.76M
  // Use the itinerary for the underlying instruction to check for
120
1.76M
  // free FU's in the scoreboard at the appropriate future cycles.
121
1.76M
122
1.76M
  const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
123
1.76M
  if (!MCID) {
124
316k
    // Don't check hazards for non-machineinstr Nodes.
125
316k
    return NoHazard;
126
316k
  }
127
1.44M
  unsigned idx = MCID->getSchedClass();
128
1.44M
  for (const InstrStage *IS = ItinData->beginStage(idx),
129
3.46M
         *E = ItinData->endStage(idx); IS != E; 
++IS2.01M
) {
130
2.32M
    // We must find one of the stage's units free for every cycle the
131
2.32M
    // stage is occupied. FIXME it would be more accurate to find the
132
2.32M
    // same unit free in all the cycles.
133
4.58M
    for (unsigned int i = 0; i < IS->getCycles(); 
++i2.25M
) {
134
2.57M
      int StageCycle = cycle + (int)i;
135
2.57M
      if (StageCycle < 0)
136
131k
        continue;
137
2.43M
138
2.43M
      if (StageCycle >= (int)RequiredScoreboard.getDepth()) {
139
0
        assert((StageCycle - Stalls) < (int)RequiredScoreboard.getDepth() &&
140
0
               "Scoreboard depth exceeded!");
141
0
        // This stage was stalled beyond pipeline depth, so cannot conflict.
142
0
        break;
143
0
      }
144
2.43M
145
2.43M
      unsigned freeUnits = IS->getUnits();
146
2.43M
      switch (IS->getReservationKind()) {
147
2.43M
      case InstrStage::Required:
148
2.42M
        // Required FUs conflict with both reserved and required ones
149
2.42M
        freeUnits &= ~ReservedScoreboard[StageCycle];
150
2.42M
        LLVM_FALLTHROUGH;
151
2.43M
      case InstrStage::Reserved:
152
2.43M
        // Reserved FUs can conflict only with required ones.
153
2.43M
        freeUnits &= ~RequiredScoreboard[StageCycle];
154
2.43M
        break;
155
2.43M
      }
156
2.43M
157
2.43M
      if (!freeUnits) {
158
312k
        LLVM_DEBUG(dbgs() << "*** Hazard in cycle +" << StageCycle << ", ");
159
312k
        LLVM_DEBUG(DAG->dumpNode(*SU));
160
312k
        return Hazard;
161
312k
      }
162
2.43M
    }
163
2.32M
164
2.32M
    // Advance the cycle to the next stage.
165
2.32M
    cycle += IS->getNextCycles();
166
2.01M
  }
167
1.44M
168
1.44M
  
return NoHazard1.13M
;
169
1.44M
}
170
171
827k
void ScoreboardHazardRecognizer::EmitInstruction(SUnit *SU) {
172
827k
  if (!ItinData || 
ItinData->isEmpty()822k
)
173
10.0k
    return;
174
817k
175
817k
  // Use the itinerary for the underlying instruction to reserve FU's
176
817k
  // in the scoreboard at the appropriate future cycles.
177
817k
  const MCInstrDesc *MCID = DAG->getInstrDesc(SU);
178
817k
  assert(MCID && "The scheduler must filter non-machineinstrs");
179
817k
  if (DAG->TII->isZeroCost(MCID->Opcode))
180
34.1k
    return;
181
783k
182
783k
  ++IssueCount;
183
783k
184
783k
  unsigned cycle = 0;
185
783k
186
783k
  unsigned idx = MCID->getSchedClass();
187
783k
  for (const InstrStage *IS = ItinData->beginStage(idx),
188
1.83M
         *E = ItinData->endStage(idx); IS != E; 
++IS1.04M
) {
189
1.04M
    // We must reserve one of the stage's units for every cycle the
190
1.04M
    // stage is occupied. FIXME it would be more accurate to reserve
191
1.04M
    // the same unit free in all the cycles.
192
2.23M
    for (unsigned int i = 0; i < IS->getCycles(); 
++i1.18M
) {
193
1.18M
      assert(((cycle + i) < RequiredScoreboard.getDepth()) &&
194
1.18M
             "Scoreboard depth exceeded!");
195
1.18M
196
1.18M
      unsigned freeUnits = IS->getUnits();
197
1.18M
      switch (IS->getReservationKind()) {
198
1.18M
      case InstrStage::Required:
199
1.17M
        // Required FUs conflict with both reserved and required ones
200
1.17M
        freeUnits &= ~ReservedScoreboard[cycle + i];
201
1.17M
        LLVM_FALLTHROUGH;
202
1.18M
      case InstrStage::Reserved:
203
1.18M
        // Reserved FUs can conflict only with required ones.
204
1.18M
        freeUnits &= ~RequiredScoreboard[cycle + i];
205
1.18M
        break;
206
1.18M
      }
207
1.18M
208
1.18M
      // reduce to a single unit
209
1.18M
      unsigned freeUnit = 0;
210
2.01M
      do {
211
2.01M
        freeUnit = freeUnits;
212
2.01M
        freeUnits = freeUnit & (freeUnit - 1);
213
2.01M
      } while (freeUnits);
214
1.18M
215
1.18M
      if (IS->getReservationKind() == InstrStage::Required)
216
1.17M
        RequiredScoreboard[cycle + i] |= freeUnit;
217
5.26k
      else
218
5.26k
        ReservedScoreboard[cycle + i] |= freeUnit;
219
1.18M
    }
220
1.04M
221
1.04M
    // Advance the cycle to the next stage.
222
1.04M
    cycle += IS->getNextCycles();
223
1.04M
  }
224
783k
225
783k
  LLVM_DEBUG(ReservedScoreboard.dump());
226
783k
  LLVM_DEBUG(RequiredScoreboard.dump());
227
783k
}
228
229
333k
void ScoreboardHazardRecognizer::AdvanceCycle() {
230
333k
  IssueCount = 0;
231
333k
  ReservedScoreboard[0] = 0; ReservedScoreboard.advance();
232
333k
  RequiredScoreboard[0] = 0; RequiredScoreboard.advance();
233
333k
}
234
235
506k
void ScoreboardHazardRecognizer::RecedeCycle() {
236
506k
  IssueCount = 0;
237
506k
  ReservedScoreboard[ReservedScoreboard.getDepth()-1] = 0;
238
506k
  ReservedScoreboard.recede();
239
506k
  RequiredScoreboard[RequiredScoreboard.getDepth()-1] = 0;
240
506k
  RequiredScoreboard.recede();
241
506k
}