1 //===----- ExactHazardRecognizer.cpp - hazard recognizer -------- ---------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements a hazard recognizer using the instructions itineraries
11 // defined for the current target.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "post-RA-sched"
16 #include "ExactHazardRecognizer.h"
17 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/ErrorHandling.h"
20 #include "llvm/Support/raw_ostream.h"
21 #include "llvm/Target/TargetInstrItineraries.h"
25 ExactHazardRecognizer::
26 ExactHazardRecognizer(const InstrItineraryData
&LItinData
) :
27 ScheduleHazardRecognizer(), ItinData(LItinData
)
29 // Determine the maximum depth of any itinerary. This determines the
30 // depth of the scoreboard. We always make the scoreboard at least 1
31 // cycle deep to avoid dealing with the boundary condition.
32 unsigned ScoreboardDepth
= 1;
33 if (!ItinData
.isEmpty()) {
34 for (unsigned idx
= 0; ; ++idx
) {
35 if (ItinData
.isEndMarker(idx
))
38 const InstrStage
*IS
= ItinData
.beginStage(idx
);
39 const InstrStage
*E
= ItinData
.endStage(idx
);
40 unsigned ItinDepth
= 0;
42 ItinDepth
+= IS
->getCycles();
44 ScoreboardDepth
= std::max(ScoreboardDepth
, ItinDepth
);
48 ReservedScoreboard
.reset(ScoreboardDepth
);
49 RequiredScoreboard
.reset(ScoreboardDepth
);
51 DEBUG(dbgs() << "Using exact hazard recognizer: ScoreboardDepth = "
52 << ScoreboardDepth
<< '\n');
55 void ExactHazardRecognizer::Reset() {
56 RequiredScoreboard
.reset();
57 ReservedScoreboard
.reset();
60 void ExactHazardRecognizer::ScoreBoard::dump() const {
61 dbgs() << "Scoreboard:\n";
63 unsigned last
= Depth
- 1;
64 while ((last
> 0) && ((*this)[last
] == 0))
67 for (unsigned i
= 0; i
<= last
; i
++) {
68 unsigned FUs
= (*this)[i
];
70 for (int j
= 31; j
>= 0; j
--)
71 dbgs() << ((FUs
& (1 << j
)) ? '1' : '0');
76 ExactHazardRecognizer::HazardType
ExactHazardRecognizer::getHazardType(SUnit
*SU
) {
77 if (ItinData
.isEmpty())
82 // Use the itinerary for the underlying instruction to check for
83 // free FU's in the scoreboard at the appropriate future cycles.
84 unsigned idx
= SU
->getInstr()->getDesc().getSchedClass();
85 for (const InstrStage
*IS
= ItinData
.beginStage(idx
),
86 *E
= ItinData
.endStage(idx
); IS
!= E
; ++IS
) {
87 // We must find one of the stage's units free for every cycle the
88 // stage is occupied. FIXME it would be more accurate to find the
89 // same unit free in all the cycles.
90 for (unsigned int i
= 0; i
< IS
->getCycles(); ++i
) {
91 assert(((cycle
+ i
) < RequiredScoreboard
.getDepth()) &&
92 "Scoreboard depth exceeded!");
94 unsigned freeUnits
= IS
->getUnits();
95 switch (IS
->getReservationKind()) {
97 assert(0 && "Invalid FU reservation");
98 case InstrStage::Required
:
99 // Required FUs conflict with both reserved and required ones
100 freeUnits
&= ~ReservedScoreboard
[cycle
+ i
];
102 case InstrStage::Reserved
:
103 // Reserved FUs can conflict only with required ones.
104 freeUnits
&= ~RequiredScoreboard
[cycle
+ i
];
109 DEBUG(dbgs() << "*** Hazard in cycle " << (cycle
+ i
) << ", ");
110 DEBUG(dbgs() << "SU(" << SU
->NodeNum
<< "): ");
111 DEBUG(SU
->getInstr()->dump());
116 // Advance the cycle to the next stage.
117 cycle
+= IS
->getNextCycles();
123 void ExactHazardRecognizer::EmitInstruction(SUnit
*SU
) {
124 if (ItinData
.isEmpty())
129 // Use the itinerary for the underlying instruction to reserve FU's
130 // in the scoreboard at the appropriate future cycles.
131 unsigned idx
= SU
->getInstr()->getDesc().getSchedClass();
132 for (const InstrStage
*IS
= ItinData
.beginStage(idx
),
133 *E
= ItinData
.endStage(idx
); IS
!= E
; ++IS
) {
134 // We must reserve one of the stage's units for every cycle the
135 // stage is occupied. FIXME it would be more accurate to reserve
136 // the same unit free in all the cycles.
137 for (unsigned int i
= 0; i
< IS
->getCycles(); ++i
) {
138 assert(((cycle
+ i
) < RequiredScoreboard
.getDepth()) &&
139 "Scoreboard depth exceeded!");
141 unsigned freeUnits
= IS
->getUnits();
142 switch (IS
->getReservationKind()) {
144 assert(0 && "Invalid FU reservation");
145 case InstrStage::Required
:
146 // Required FUs conflict with both reserved and required ones
147 freeUnits
&= ~ReservedScoreboard
[cycle
+ i
];
149 case InstrStage::Reserved
:
150 // Reserved FUs can conflict only with required ones.
151 freeUnits
&= ~RequiredScoreboard
[cycle
+ i
];
155 // reduce to a single unit
156 unsigned freeUnit
= 0;
158 freeUnit
= freeUnits
;
159 freeUnits
= freeUnit
& (freeUnit
- 1);
162 assert(freeUnit
&& "No function unit available!");
163 if (IS
->getReservationKind() == InstrStage::Required
)
164 RequiredScoreboard
[cycle
+ i
] |= freeUnit
;
166 ReservedScoreboard
[cycle
+ i
] |= freeUnit
;
169 // Advance the cycle to the next stage.
170 cycle
+= IS
->getNextCycles();
173 DEBUG(ReservedScoreboard
.dump());
174 DEBUG(RequiredScoreboard
.dump());
177 void ExactHazardRecognizer::AdvanceCycle() {
178 ReservedScoreboard
[0] = 0; ReservedScoreboard
.advance();
179 RequiredScoreboard
[0] = 0; RequiredScoreboard
.advance();