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 a hazard recognizer using the instructions itineraries
11 // defined for the current target.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "exact-hazards"
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::ExactHazardRecognizer(const InstrItineraryData &LItinData) :
26 ScheduleHazardRecognizer(), ItinData(LItinData)
28 // Determine the maximum depth of any itinerary. This determines the
29 // depth of the scoreboard. We always make the scoreboard at least 1
30 // cycle deep to avoid dealing with the boundary condition.
32 if (!ItinData.isEmpty()) {
33 for (unsigned idx = 0; ; ++idx) {
34 if (ItinData.isEndMarker(idx))
37 const InstrStage *IS = ItinData.beginStage(idx);
38 const InstrStage *E = ItinData.endStage(idx);
39 unsigned ItinDepth = 0;
41 ItinDepth += IS->getCycles();
43 ScoreboardDepth = std::max(ScoreboardDepth, ItinDepth);
47 Scoreboard = new unsigned[ScoreboardDepth];
50 DEBUG(errs() << "Using exact hazard recognizer: ScoreboardDepth = "
51 << ScoreboardDepth << '\n');
54 ExactHazardRecognizer::~ExactHazardRecognizer() {
58 void ExactHazardRecognizer::Reset() {
59 memset(Scoreboard, 0, ScoreboardDepth * sizeof(unsigned));
63 unsigned ExactHazardRecognizer::getFutureIndex(unsigned offset) {
64 return (ScoreboardHead + offset) % ScoreboardDepth;
67 void ExactHazardRecognizer::dumpScoreboard() {
68 errs() << "Scoreboard:\n";
70 unsigned last = ScoreboardDepth - 1;
71 while ((last > 0) && (Scoreboard[getFutureIndex(last)] == 0))
74 for (unsigned i = 0; i <= last; i++) {
75 unsigned FUs = Scoreboard[getFutureIndex(i)];
77 for (int j = 31; j >= 0; j--)
78 errs() << ((FUs & (1 << j)) ? '1' : '0');
83 ExactHazardRecognizer::HazardType ExactHazardRecognizer::getHazardType(SUnit *SU) {
84 if (ItinData.isEmpty())
89 // Use the itinerary for the underlying instruction to check for
90 // free FU's in the scoreboard at the appropriate future cycles.
91 unsigned idx = SU->getInstr()->getDesc().getSchedClass();
92 for (const InstrStage *IS = ItinData.beginStage(idx),
93 *E = ItinData.endStage(idx); IS != E; ++IS) {
94 // We must find one of the stage's units free for every cycle the
95 // stage is occupied. FIXME it would be more accurate to find the
96 // same unit free in all the cycles.
97 for (unsigned int i = 0; i < IS->getCycles(); ++i) {
98 assert(((cycle + i) < ScoreboardDepth) &&
99 "Scoreboard depth exceeded!");
101 unsigned index = getFutureIndex(cycle + i);
102 unsigned freeUnits = IS->getUnits() & ~Scoreboard[index];
104 DEBUG(errs() << "*** Hazard in cycle " << (cycle + i) << ", ");
105 DEBUG(errs() << "SU(" << SU->NodeNum << "): ");
106 DEBUG(SU->getInstr()->dump());
111 // Advance the cycle to the next stage.
112 cycle += IS->getNextCycles();
118 void ExactHazardRecognizer::EmitInstruction(SUnit *SU) {
119 if (ItinData.isEmpty())
124 // Use the itinerary for the underlying instruction to reserve FU's
125 // in the scoreboard at the appropriate future cycles.
126 unsigned idx = SU->getInstr()->getDesc().getSchedClass();
127 for (const InstrStage *IS = ItinData.beginStage(idx),
128 *E = ItinData.endStage(idx); IS != E; ++IS) {
129 // We must reserve one of the stage's units for every cycle the
130 // stage is occupied. FIXME it would be more accurate to reserve
131 // the same unit free in all the cycles.
132 for (unsigned int i = 0; i < IS->getCycles(); ++i) {
133 assert(((cycle + i) < ScoreboardDepth) &&
134 "Scoreboard depth exceeded!");
136 unsigned index = getFutureIndex(cycle + i);
137 unsigned freeUnits = IS->getUnits() & ~Scoreboard[index];
139 // reduce to a single unit
140 unsigned freeUnit = 0;
142 freeUnit = freeUnits;
143 freeUnits = freeUnit & (freeUnit - 1);
146 assert(freeUnit && "No function unit available!");
147 Scoreboard[index] |= freeUnit;
150 // Advance the cycle to the next stage.
151 cycle += IS->getNextCycles();
154 DEBUG(dumpScoreboard());
157 void ExactHazardRecognizer::AdvanceCycle() {
158 Scoreboard[ScoreboardHead] = 0;
159 ScoreboardHead = getFutureIndex(1);