1 //===-- SchedInfo.cpp - Generic code to support target schedulers ----------==//
3 // This file implements the generic part of a Scheduler description for a
4 // target. This functionality is defined in the llvm/Target/SchedInfo.h file.
6 //===----------------------------------------------------------------------===//
8 #include "llvm/Target/MachineSchedInfo.h"
9 #include "llvm/Target/TargetMachine.h"
11 resourceId_t MachineResource::nextId = 0;
13 // Check if fromRVec and toRVec have *any* common entries.
14 // Assume the vectors are sorted in increasing order.
15 // Algorithm copied from function set_intersection() for sorted ranges
19 RUConflict(const std::vector<resourceId_t>& fromRVec,
20 const std::vector<resourceId_t>& toRVec)
23 unsigned fN = fromRVec.size(), tN = toRVec.size();
24 unsigned fi = 0, ti = 0;
26 while (fi < fN && ti < tN)
28 if (fromRVec[fi] < toRVec[ti])
30 else if (toRVec[ti] < fromRVec[fi])
40 ComputeMinGap(const InstrRUsage &fromRU,
41 const InstrRUsage &toRU)
45 if (fromRU.numBubbles > 0)
46 minGap = fromRU.numBubbles;
48 if (minGap < fromRU.numCycles)
50 // only need to check from cycle `minGap' onwards
51 for (cycles_t gap=minGap; gap <= fromRU.numCycles-1; gap++)
53 // check if instr. #2 can start executing `gap' cycles after #1
54 // by checking for resource conflicts in each overlapping cycle
55 cycles_t numOverlap =std::min(fromRU.numCycles - gap, toRU.numCycles);
56 for (cycles_t c = 0; c <= numOverlap-1; c++)
57 if (RUConflict(fromRU.resourcesByCycle[gap + c],
58 toRU.resourcesByCycle[c]))
60 // conflict found so minGap must be more than `gap'
71 //---------------------------------------------------------------------------
72 // class MachineSchedInfo
73 // Interface to machine description for instruction scheduling
74 //---------------------------------------------------------------------------
76 MachineSchedInfo::MachineSchedInfo(const TargetMachine& tgt,
78 const InstrClassRUsage* ClassRUsages,
79 const InstrRUsageDelta* UsageDeltas,
80 const InstrIssueDelta* IssueDeltas,
81 unsigned int NumUsageDeltas,
82 unsigned int NumIssueDeltas)
84 numSchedClasses(NumSchedClasses), mii(& tgt.getInstrInfo()),
85 classRUsages(ClassRUsages), usageDeltas(UsageDeltas),
86 issueDeltas(IssueDeltas), numUsageDeltas(NumUsageDeltas),
87 numIssueDeltas(NumIssueDeltas)
91 MachineSchedInfo::initializeResources()
93 assert(MAX_NUM_SLOTS >= (int)getMaxNumIssueTotal()
94 && "Insufficient slots for static data! Increase MAX_NUM_SLOTS");
96 // First, compute common resource usage info for each class because
97 // most instructions will probably behave the same as their class.
98 // Cannot allocate a vector of InstrRUsage so new each one.
100 std::vector<InstrRUsage> instrRUForClasses;
101 instrRUForClasses.resize(numSchedClasses);
102 for (InstrSchedClass sc = 0; sc < numSchedClasses; sc++) {
103 // instrRUForClasses.push_back(new InstrRUsage);
104 instrRUForClasses[sc].setMaxSlots(getMaxNumIssueTotal());
105 instrRUForClasses[sc].setTo(classRUsages[sc]);
108 computeInstrResources(instrRUForClasses);
109 computeIssueGaps(instrRUForClasses);
114 MachineSchedInfo::computeInstrResources(const std::vector<InstrRUsage>&
117 int numOpCodes = mii->getNumRealOpCodes();
118 instrRUsages.resize(numOpCodes);
120 // First get the resource usage information from the class resource usages.
121 for (MachineOpCode op = 0; op < numOpCodes; ++op) {
122 InstrSchedClass sc = getSchedClass(op);
123 assert(sc < numSchedClasses);
124 instrRUsages[op] = instrRUForClasses[sc];
127 // Now, modify the resource usages as specified in the deltas.
128 for (unsigned i = 0; i < numUsageDeltas; ++i) {
129 MachineOpCode op = usageDeltas[i].opCode;
130 assert(op < numOpCodes);
131 instrRUsages[op].addUsageDelta(usageDeltas[i]);
134 // Then modify the issue restrictions as specified in the deltas.
135 for (unsigned i = 0; i < numIssueDeltas; ++i) {
136 MachineOpCode op = issueDeltas[i].opCode;
137 assert(op < numOpCodes);
138 instrRUsages[issueDeltas[i].opCode].addIssueDelta(issueDeltas[i]);
144 MachineSchedInfo::computeIssueGaps(const std::vector<InstrRUsage>&
147 int numOpCodes = mii->getNumRealOpCodes();
148 issueGaps.resize(numOpCodes);
149 conflictLists.resize(numOpCodes);
151 assert(numOpCodes < (1 << MAX_OPCODE_SIZE) - 1
152 && "numOpCodes invalid for implementation of class OpCodePair!");
154 // First, compute issue gaps between pairs of classes based on common
155 // resources usages for each class, because most instruction pairs will
156 // usually behave the same as their class.
158 int classPairGaps[numSchedClasses][numSchedClasses];
159 for (InstrSchedClass fromSC=0; fromSC < numSchedClasses; fromSC++)
160 for (InstrSchedClass toSC=0; toSC < numSchedClasses; toSC++)
162 int classPairGap = ComputeMinGap(instrRUForClasses[fromSC],
163 instrRUForClasses[toSC]);
164 classPairGaps[fromSC][toSC] = classPairGap;
167 // Now, for each pair of instructions, use the class pair gap if both
168 // instructions have identical resource usage as their respective classes.
169 // If not, recompute the gap for the pair from scratch.
171 longestIssueConflict = 0;
173 for (MachineOpCode fromOp=0; fromOp < numOpCodes; fromOp++)
174 for (MachineOpCode toOp=0; toOp < numOpCodes; toOp++)
177 (instrRUsages[fromOp].sameAsClass && instrRUsages[toOp].sameAsClass)
178 ? classPairGaps[getSchedClass(fromOp)][getSchedClass(toOp)]
179 : ComputeMinGap(instrRUsages[fromOp], instrRUsages[toOp]);
181 if (instrPairGap > 0)
183 this->setGap(instrPairGap, fromOp, toOp);
184 conflictLists[fromOp].push_back(toOp);
185 longestIssueConflict=std::max(longestIssueConflict, instrPairGap);
191 void InstrRUsage::setTo(const InstrClassRUsage& classRU) {
193 isSingleIssue = classRU.isSingleIssue;
194 breaksGroup = classRU.breaksGroup;
195 numBubbles = classRU.numBubbles;
197 for (unsigned i=0; i < classRU.numSlots; i++)
199 unsigned slot = classRU.feasibleSlots[i];
200 assert(slot < feasibleSlots.size() && "Invalid slot specified!");
201 this->feasibleSlots[slot] = true;
204 numCycles = classRU.totCycles;
205 resourcesByCycle.resize(this->numCycles);
207 for (unsigned i=0; i < classRU.numRUEntries; i++)
208 for (unsigned c=classRU.V[i].startCycle, NC = c + classRU.V[i].numCycles;
210 this->resourcesByCycle[c].push_back(classRU.V[i].resourceId);
212 // Sort each resource usage vector by resourceId_t to speed up conflict checking
213 for (unsigned i=0; i < this->resourcesByCycle.size(); i++)
214 sort(resourcesByCycle[i].begin(), resourcesByCycle[i].end());
218 // Add the extra resource usage requirements specified in the delta.
219 // Note that a negative value of `numCycles' means one entry for that
220 // resource should be deleted for each cycle.
222 void InstrRUsage::addUsageDelta(const InstrRUsageDelta &delta) {
223 int NC = delta.numCycles;
226 // resize the resources vector if more cycles are specified
227 unsigned maxCycles = this->numCycles;
228 maxCycles = std::max(maxCycles, delta.startCycle + abs(NC) - 1);
229 if (maxCycles > this->numCycles)
231 this->resourcesByCycle.resize(maxCycles);
232 this->numCycles = maxCycles;
236 for (unsigned c=delta.startCycle, last=c+NC-1; c <= last; c++)
237 this->resourcesByCycle[c].push_back(delta.resourceId);
239 // Remove the resource from all NC cycles.
240 for (unsigned c=delta.startCycle, last=(c-NC)-1; c <= last; c++)
242 // Look for the resource backwards so we remove the last entry
243 // for that resource in each cycle.
244 std::vector<resourceId_t>& rvec = this->resourcesByCycle[c];
246 for (r = (int) rvec.size(); r >= 0; r--)
247 if (rvec[r] == delta.resourceId)
248 {// found last entry for the resource
249 rvec.erase(rvec.begin() + r);
252 assert(r >= 0 && "Resource to remove was unused in cycle c!");