blob: 61959bba0e2314e368f1818499976b69de8d3787 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
//===----- ExactHazardRecognizer.cpp - hazard recognizer -------- ---------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This implements a hazard recognizer using the instructions itineraries
// defined for the current target.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "post-RA-sched"
#include "ExactHazardRecognizer.h"
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrItineraries.h"
using namespace llvm;
ExactHazardRecognizer::
ExactHazardRecognizer(const InstrItineraryData &LItinData) :
ScheduleHazardRecognizer(), ItinData(LItinData)
{
// Determine the maximum depth of any itinerary. This determines the
// depth of the scoreboard. We always make the scoreboard at least 1
// cycle deep to avoid dealing with the boundary condition.
ScoreboardDepth = 1;
if (!ItinData.isEmpty()) {
for (unsigned idx = 0; ; ++idx) {
if (ItinData.isEndMarker(idx))
break;
const InstrStage *IS = ItinData.beginStage(idx);
const InstrStage *E = ItinData.endStage(idx);
unsigned ItinDepth = 0;
for (; IS != E; ++IS)
ItinDepth += IS->getCycles();
ScoreboardDepth = std::max(ScoreboardDepth, ItinDepth);
}
}
Scoreboard = new unsigned[ScoreboardDepth];
ScoreboardHead = 0;
DEBUG(dbgs() << "Using exact hazard recognizer: ScoreboardDepth = "
<< ScoreboardDepth << '\n');
}
ExactHazardRecognizer::~ExactHazardRecognizer() {
delete [] Scoreboard;
}
void ExactHazardRecognizer::Reset() {
memset(Scoreboard, 0, ScoreboardDepth * sizeof(unsigned));
ScoreboardHead = 0;
}
unsigned ExactHazardRecognizer::getFutureIndex(unsigned offset) {
return (ScoreboardHead + offset) % ScoreboardDepth;
}
void ExactHazardRecognizer::dumpScoreboard() {
dbgs() << "Scoreboard:\n";
unsigned last = ScoreboardDepth - 1;
while ((last > 0) && (Scoreboard[getFutureIndex(last)] == 0))
last--;
for (unsigned i = 0; i <= last; i++) {
unsigned FUs = Scoreboard[getFutureIndex(i)];
dbgs() << "\t";
for (int j = 31; j >= 0; j--)
dbgs() << ((FUs & (1 << j)) ? '1' : '0');
dbgs() << '\n';
}
}
ExactHazardRecognizer::HazardType ExactHazardRecognizer::getHazardType(SUnit *SU) {
if (ItinData.isEmpty())
return NoHazard;
unsigned cycle = 0;
// Use the itinerary for the underlying instruction to check for
// free FU's in the scoreboard at the appropriate future cycles.
unsigned idx = SU->getInstr()->getDesc().getSchedClass();
for (const InstrStage *IS = ItinData.beginStage(idx),
*E = ItinData.endStage(idx); IS != E; ++IS) {
// We must find one of the stage's units free for every cycle the
// stage is occupied. FIXME it would be more accurate to find the
// same unit free in all the cycles.
for (unsigned int i = 0; i < IS->getCycles(); ++i) {
assert(((cycle + i) < ScoreboardDepth) &&
"Scoreboard depth exceeded!");
unsigned index = getFutureIndex(cycle + i);
unsigned freeUnits = IS->getUnits() & ~Scoreboard[index];
if (!freeUnits) {
DEBUG(dbgs() << "*** Hazard in cycle " << (cycle + i) << ", ");
DEBUG(dbgs() << "SU(" << SU->NodeNum << "): ");
DEBUG(SU->getInstr()->dump());
return Hazard;
}
}
// Advance the cycle to the next stage.
cycle += IS->getNextCycles();
}
return NoHazard;
}
void ExactHazardRecognizer::EmitInstruction(SUnit *SU) {
if (ItinData.isEmpty())
return;
unsigned cycle = 0;
// Use the itinerary for the underlying instruction to reserve FU's
// in the scoreboard at the appropriate future cycles.
unsigned idx = SU->getInstr()->getDesc().getSchedClass();
for (const InstrStage *IS = ItinData.beginStage(idx),
*E = ItinData.endStage(idx); IS != E; ++IS) {
// We must reserve one of the stage's units for every cycle the
// stage is occupied. FIXME it would be more accurate to reserve
// the same unit free in all the cycles.
for (unsigned int i = 0; i < IS->getCycles(); ++i) {
assert(((cycle + i) < ScoreboardDepth) &&
"Scoreboard depth exceeded!");
unsigned index = getFutureIndex(cycle + i);
unsigned freeUnits = IS->getUnits() & ~Scoreboard[index];
// reduce to a single unit
unsigned freeUnit = 0;
do {
freeUnit = freeUnits;
freeUnits = freeUnit & (freeUnit - 1);
} while (freeUnits);
assert(freeUnit && "No function unit available!");
Scoreboard[index] |= freeUnit;
}
// Advance the cycle to the next stage.
cycle += IS->getNextCycles();
}
DEBUG(dumpScoreboard());
}
void ExactHazardRecognizer::AdvanceCycle() {
Scoreboard[ScoreboardHead] = 0;
ScoreboardHead = getFutureIndex(1);
}
|
