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] = 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);