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 // External object describing the machine instructions
12 // Initialized only when the TargetMachine class is created
13 // and reset when that class is destroyed.
15 const MachineInstrDescriptor* TargetInstrDescriptors = 0;
17 resourceId_t MachineResource::nextId = 0;
19 // Check if fromRVec and toRVec have *any* common entries.
20 // Assume the vectors are sorted in increasing order.
21 // Algorithm copied from function set_intersection() for sorted ranges
25 RUConflict(const std::vector<resourceId_t>& fromRVec,
26 const std::vector<resourceId_t>& toRVec)
29 unsigned fN = fromRVec.size(), tN = toRVec.size();
30 unsigned fi = 0, ti = 0;
32 while (fi < fN && ti < tN)
34 if (fromRVec[fi] < toRVec[ti])
36 else if (toRVec[ti] < fromRVec[fi])
46 ComputeMinGap(const InstrRUsage &fromRU,
47 const InstrRUsage &toRU)
51 if (fromRU.numBubbles > 0)
52 minGap = fromRU.numBubbles;
54 if (minGap < fromRU.numCycles)
56 // only need to check from cycle `minGap' onwards
57 for (cycles_t gap=minGap; gap <= fromRU.numCycles-1; gap++)
59 // check if instr. #2 can start executing `gap' cycles after #1
60 // by checking for resource conflicts in each overlapping cycle
61 cycles_t numOverlap =std::min(fromRU.numCycles - gap, toRU.numCycles);
62 for (cycles_t c = 0; c <= numOverlap-1; c++)
63 if (RUConflict(fromRU.resourcesByCycle[gap + c],
64 toRU.resourcesByCycle[c]))
66 // conflict found so minGap must be more than `gap'
77 //---------------------------------------------------------------------------
78 // class MachineSchedInfo
79 // Interface to machine description for instruction scheduling
80 //---------------------------------------------------------------------------
82 MachineSchedInfo::MachineSchedInfo(const TargetMachine& tgt,
84 const InstrClassRUsage* ClassRUsages,
85 const InstrRUsageDelta* UsageDeltas,
86 const InstrIssueDelta* IssueDeltas,
87 unsigned int NumUsageDeltas,
88 unsigned int NumIssueDeltas)
90 numSchedClasses(NumSchedClasses), mii(& tgt.getInstrInfo()),
91 classRUsages(ClassRUsages), usageDeltas(UsageDeltas),
92 issueDeltas(IssueDeltas), numUsageDeltas(NumUsageDeltas),
93 numIssueDeltas(NumIssueDeltas)
97 MachineSchedInfo::initializeResources()
99 assert(MAX_NUM_SLOTS >= (int)getMaxNumIssueTotal()
100 && "Insufficient slots for static data! Increase MAX_NUM_SLOTS");
102 // First, compute common resource usage info for each class because
103 // most instructions will probably behave the same as their class.
104 // Cannot allocate a vector of InstrRUsage so new each one.
106 std::vector<InstrRUsage> instrRUForClasses;
107 instrRUForClasses.resize(numSchedClasses);
108 for (InstrSchedClass sc = 0; sc < numSchedClasses; sc++) {
109 // instrRUForClasses.push_back(new InstrRUsage);
110 instrRUForClasses[sc].setMaxSlots(getMaxNumIssueTotal());
111 instrRUForClasses[sc].setTo(classRUsages[sc]);
114 computeInstrResources(instrRUForClasses);
115 computeIssueGaps(instrRUForClasses);
120 MachineSchedInfo::computeInstrResources(const std::vector<InstrRUsage>&
123 int numOpCodes = mii->getNumRealOpCodes();
124 instrRUsages.resize(numOpCodes);
126 // First get the resource usage information from the class resource usages.
127 for (MachineOpCode op = 0; op < numOpCodes; ++op) {
128 InstrSchedClass sc = getSchedClass(op);
129 assert(sc >= 0 && sc < numSchedClasses);
130 instrRUsages[op] = instrRUForClasses[sc];
133 // Now, modify the resource usages as specified in the deltas.
134 for (unsigned i = 0; i < numUsageDeltas; ++i) {
135 MachineOpCode op = usageDeltas[i].opCode;
136 assert(op < numOpCodes);
137 instrRUsages[op].addUsageDelta(usageDeltas[i]);
140 // Then modify the issue restrictions as specified in the deltas.
141 for (unsigned i = 0; i < numIssueDeltas; ++i) {
142 MachineOpCode op = issueDeltas[i].opCode;
143 assert(op < numOpCodes);
144 instrRUsages[issueDeltas[i].opCode].addIssueDelta(issueDeltas[i]);
150 MachineSchedInfo::computeIssueGaps(const std::vector<InstrRUsage>&
153 int numOpCodes = mii->getNumRealOpCodes();
154 instrRUsages.resize(numOpCodes);
156 assert(numOpCodes < (1 << MAX_OPCODE_SIZE) - 1
157 && "numOpCodes invalid for implementation of class OpCodePair!");
159 // First, compute issue gaps between pairs of classes based on common
160 // resources usages for each class, because most instruction pairs will
161 // usually behave the same as their class.
163 int classPairGaps[numSchedClasses][numSchedClasses];
164 for (InstrSchedClass fromSC=0; fromSC < numSchedClasses; fromSC++)
165 for (InstrSchedClass toSC=0; toSC < numSchedClasses; toSC++)
167 int classPairGap = ComputeMinGap(instrRUForClasses[fromSC],
168 instrRUForClasses[toSC]);
169 classPairGaps[fromSC][toSC] = classPairGap;
172 // Now, for each pair of instructions, use the class pair gap if both
173 // instructions have identical resource usage as their respective classes.
174 // If not, recompute the gap for the pair from scratch.
176 longestIssueConflict = 0;
178 for (MachineOpCode fromOp=0; fromOp < numOpCodes; fromOp++)
179 for (MachineOpCode toOp=0; toOp < numOpCodes; toOp++)
182 (instrRUsages[fromOp].sameAsClass && instrRUsages[toOp].sameAsClass)
183 ? classPairGaps[getSchedClass(fromOp)][getSchedClass(toOp)]
184 : ComputeMinGap(instrRUsages[fromOp], instrRUsages[toOp]);
186 if (instrPairGap > 0)
188 issueGaps[OpCodePair(fromOp,toOp)] = instrPairGap;
189 conflictLists[fromOp].push_back(toOp);
190 longestIssueConflict = std::max(longestIssueConflict, instrPairGap);
196 void InstrRUsage::setTo(const InstrClassRUsage& classRU) {
198 isSingleIssue = classRU.isSingleIssue;
199 breaksGroup = classRU.breaksGroup;
200 numBubbles = classRU.numBubbles;
202 for (unsigned i=0; i < classRU.numSlots; i++)
204 unsigned slot = classRU.feasibleSlots[i];
205 assert(slot < feasibleSlots.size() && "Invalid slot specified!");
206 this->feasibleSlots[slot] = true;
209 numCycles = classRU.totCycles;
210 resourcesByCycle.resize(this->numCycles);
212 for (unsigned i=0; i < classRU.numRUEntries; i++)
213 for (unsigned c=classRU.V[i].startCycle, NC = c + classRU.V[i].numCycles;
215 this->resourcesByCycle[c].push_back(classRU.V[i].resourceId);
217 // Sort each resource usage vector by resourceId_t to speed up conflict checking
218 for (unsigned i=0; i < this->resourcesByCycle.size(); i++)
219 sort(resourcesByCycle[i].begin(), resourcesByCycle[i].end());
223 // Add the extra resource usage requirements specified in the delta.
224 // Note that a negative value of `numCycles' means one entry for that
225 // resource should be deleted for each cycle.
227 void InstrRUsage::addUsageDelta(const InstrRUsageDelta &delta) {
228 int NC = delta.numCycles;
231 // resize the resources vector if more cycles are specified
232 unsigned maxCycles = this->numCycles;
233 maxCycles = std::max(maxCycles, delta.startCycle + abs(NC) - 1);
234 if (maxCycles > this->numCycles)
236 this->resourcesByCycle.resize(maxCycles);
237 this->numCycles = maxCycles;
241 for (unsigned c=delta.startCycle, last=c+NC-1; c <= last; c++)
242 this->resourcesByCycle[c].push_back(delta.resourceId);
244 // Remove the resource from all NC cycles.
245 for (unsigned c=delta.startCycle, last=(c-NC)-1; c <= last; c++)
247 // Look for the resource backwards so we remove the last entry
248 // for that resource in each cycle.
249 std::vector<resourceId_t>& rvec = this->resourcesByCycle[c];
251 for (r = (int) rvec.size(); r >= 0; r--)
252 if (rvec[r] == delta.resourceId)
253 {// found last entry for the resource
254 rvec.erase(rvec.begin() + r);
257 assert(r >= 0 && "Resource to remove was unused in cycle c!");