1 //===-- llvm/Target/SchedInfo.h - Target Instruction Sched Info --*- C++ -*-==//
3 // This file describes the target machine to the instruction scheduler.
5 //===----------------------------------------------------------------------===//
7 #ifndef LLVM_TARGET_MACHINESCHEDINFO_H
8 #define LLVM_TARGET_MACHINESCHEDINFO_H
10 #include "llvm/Target/MachineInstrInfo.h"
11 #include <ext/hash_map>
13 typedef long long cycles_t;
14 const cycles_t HUGE_LATENCY = ~((unsigned long long) 1 << sizeof(cycles_t)-2);
15 const cycles_t INVALID_LATENCY = -HUGE_LATENCY;
16 static const unsigned MAX_OPCODE_SIZE = 16;
20 long val; // make long by concatenating two opcodes
21 OpCodePair(MachineOpCode op1, MachineOpCode op2)
22 : val((op1 < 0 || op2 < 0)?
23 -1 : (long)((((unsigned) op1) << MAX_OPCODE_SIZE) | (unsigned) op2)) {}
24 bool operator==(const OpCodePair& op) const {
28 OpCodePair(); // disable for now
32 template <> struct hash<OpCodePair> {
33 size_t operator()(const OpCodePair& pair) const {
34 return hash<long>()(pair.val);
39 //---------------------------------------------------------------------------
40 // class MachineResource
44 // Representation of a single machine resource used in specifying
45 // resource usages of machine instructions for scheduling.
46 //---------------------------------------------------------------------------
49 typedef unsigned int resourceId_t;
51 class MachineResource {
53 const std::string rname;
56 /*ctor*/ MachineResource(const std::string& resourceName)
57 : rname(resourceName), rid(nextId++) {}
60 static resourceId_t nextId;
61 MachineResource(); // disable
65 class CPUResource : public MachineResource {
67 int maxNumUsers; // MAXINT if no restriction
69 /*ctor*/ CPUResource(const std::string& rname, int maxUsers)
70 : MachineResource(rname), maxNumUsers(maxUsers) {}
74 //---------------------------------------------------------------------------
75 // struct InstrClassRUsage
76 // struct InstrRUsageDelta
77 // struct InstrIssueDelta
81 // The first three are structures used to specify machine resource
82 // usages for each instruction in a machine description file:
83 // InstrClassRUsage : resource usages common to all instrs. in a class
84 // InstrRUsageDelta : add/delete resource usage for individual instrs.
85 // InstrIssueDelta : add/delete instr. issue info for individual instrs
87 // The last one (InstrRUsage) is the internal representation of
88 // instruction resource usage constructed from the above three.
89 //---------------------------------------------------------------------------
91 const int MAX_NUM_SLOTS = 32;
92 const int MAX_NUM_CYCLES = 32;
94 struct InstrClassRUsage {
95 InstrSchedClass schedClass;
98 // Issue restrictions common to instructions in this class
99 unsigned int maxNumIssue;
104 // Feasible slots to use for instructions in this class.
105 // The size of vector S[] is `numSlots'.
106 unsigned int numSlots;
107 unsigned int feasibleSlots[MAX_NUM_SLOTS];
109 // Resource usages common to instructions in this class.
110 // The size of vector V[] is `numRUEntries'.
111 unsigned int numRUEntries;
113 resourceId_t resourceId;
114 unsigned int startCycle;
119 struct InstrRUsageDelta {
120 MachineOpCode opCode;
121 resourceId_t resourceId;
122 unsigned int startCycle;
126 // Specify instruction issue restrictions for individual instructions
127 // that differ from the common rules for the class.
129 struct InstrIssueDelta {
130 MachineOpCode opCode;
138 /*ctor*/ InstrRUsage () {}
139 /*ctor*/ InstrRUsage (const InstrRUsage& instrRU);
140 InstrRUsage& operator= (const InstrRUsage& instrRU);
144 // Issue restrictions for this instruction
149 // Feasible slots to use for this instruction.
150 std::vector<bool> feasibleSlots;
152 // Resource usages for this instruction, with one resource vector per cycle.
154 std::vector<std::vector<resourceId_t> > resourcesByCycle;
157 // Conveniences for initializing this structure
158 InstrRUsage& operator= (const InstrClassRUsage& classRU);
159 void addIssueDelta (const InstrIssueDelta& delta);
160 void addUsageDelta (const InstrRUsageDelta& delta);
161 void setMaxSlots (int maxNumSlots);
163 friend class MachineSchedInfo; // give access to these functions
168 InstrRUsage::setMaxSlots(int maxNumSlots)
170 feasibleSlots.resize(maxNumSlots);
174 InstrRUsage::operator=(const InstrRUsage& instrRU)
176 sameAsClass = instrRU.sameAsClass;
177 isSingleIssue = instrRU.isSingleIssue;
178 breaksGroup = instrRU.breaksGroup;
179 numBubbles = instrRU.numBubbles;
180 feasibleSlots = instrRU.feasibleSlots;
181 numCycles = instrRU.numCycles;
182 resourcesByCycle = instrRU.resourcesByCycle;
187 InstrRUsage::InstrRUsage(const InstrRUsage& instrRU)
193 InstrRUsage::operator=(const InstrClassRUsage& classRU)
196 isSingleIssue = classRU.isSingleIssue;
197 breaksGroup = classRU.breaksGroup;
198 numBubbles = classRU.numBubbles;
200 for (unsigned i=0; i < classRU.numSlots; i++)
202 unsigned slot = classRU.feasibleSlots[i];
203 assert(slot < feasibleSlots.size() && "Invalid slot specified!");
204 this->feasibleSlots[slot] = true;
207 this->numCycles = classRU.totCycles;
208 this->resourcesByCycle.resize(this->numCycles);
210 for (unsigned i=0; i < classRU.numRUEntries; i++)
211 for (unsigned c=classRU.V[i].startCycle, NC = c + classRU.V[i].numCycles;
213 this->resourcesByCycle[c].push_back(classRU.V[i].resourceId);
215 // Sort each resource usage vector by resourceId_t to speed up conflict checking
216 for (unsigned i=0; i < this->resourcesByCycle.size(); i++)
217 sort(resourcesByCycle[i].begin(), resourcesByCycle[i].end());
224 InstrRUsage::addIssueDelta(const InstrIssueDelta& delta)
227 isSingleIssue = delta.isSingleIssue;
228 breaksGroup = delta.breaksGroup;
229 numBubbles = delta.numBubbles;
233 // Add the extra resource usage requirements specified in the delta.
234 // Note that a negative value of `numCycles' means one entry for that
235 // resource should be deleted for each cycle.
238 InstrRUsage::addUsageDelta(const InstrRUsageDelta& delta)
240 int NC = delta.numCycles;
242 this->sameAsClass = false;
244 // resize the resources vector if more cycles are specified
245 unsigned maxCycles = this->numCycles;
246 maxCycles = std::max(maxCycles, delta.startCycle + abs(NC) - 1);
247 if (maxCycles > this->numCycles)
249 this->resourcesByCycle.resize(maxCycles);
250 this->numCycles = maxCycles;
254 for (unsigned c=delta.startCycle, last=c+NC-1; c <= last; c++)
255 this->resourcesByCycle[c].push_back(delta.resourceId);
257 // Remove the resource from all NC cycles.
258 for (unsigned c=delta.startCycle, last=(c-NC)-1; c <= last; c++)
260 // Look for the resource backwards so we remove the last entry
261 // for that resource in each cycle.
262 std::vector<resourceId_t>& rvec = this->resourcesByCycle[c];
264 for (r = (int) rvec.size(); r >= 0; r--)
265 if (rvec[r] == delta.resourceId)
266 {// found last entry for the resource
267 rvec.erase(rvec.begin() + r);
270 assert(r >= 0 && "Resource to remove was unused in cycle c!");
274 //---------------------------------------------------------------------------
275 // class MachineSchedInfo
278 // Common interface to machine information for instruction scheduling
279 //---------------------------------------------------------------------------
281 class MachineSchedInfo : public NonCopyableV {
283 const TargetMachine& target;
285 unsigned int maxNumIssueTotal;
286 int longestIssueConflict;
288 int branchMispredictPenalty; // 4 for SPARC IIi
289 int branchTargetUnknownPenalty; // 2 for SPARC IIi
290 int l1DCacheMissPenalty; // 7 or 9 for SPARC IIi
291 int l1ICacheMissPenalty; // ? for SPARC IIi
293 bool inOrderLoads; // true for SPARC IIi
294 bool inOrderIssue; // true for SPARC IIi
295 bool inOrderExec; // false for most architectures
296 bool inOrderRetire; // true for most architectures
299 inline const InstrRUsage& getInstrRUsage(MachineOpCode opCode) const {
300 assert(opCode >= 0 && opCode < (int) instrRUsages.size());
301 return instrRUsages[opCode];
303 inline const InstrClassRUsage&
304 getClassRUsage(const InstrSchedClass& sc) const {
305 assert(sc >= 0 && sc < numSchedClasses);
306 return classRUsages[sc];
310 /*ctor*/ MachineSchedInfo (const TargetMachine& tgt,
311 int _numSchedClasses,
312 const InstrClassRUsage* _classRUsages,
313 const InstrRUsageDelta* _usageDeltas,
314 const InstrIssueDelta* _issueDeltas,
315 unsigned int _numUsageDeltas,
316 unsigned int _numIssueDeltas);
317 /*dtor*/ virtual ~MachineSchedInfo () {}
319 inline const MachineInstrInfo& getInstrInfo() const {
323 inline int getNumSchedClasses() const {
324 return numSchedClasses;
327 inline unsigned int getMaxNumIssueTotal() const {
328 return maxNumIssueTotal;
331 inline unsigned int getMaxIssueForClass(const InstrSchedClass& sc) const {
332 assert(sc >= 0 && sc < numSchedClasses);
333 return classRUsages[sc].maxNumIssue;
336 inline InstrSchedClass getSchedClass (MachineOpCode opCode) const {
337 return getInstrInfo().getSchedClass(opCode);
340 inline bool instrCanUseSlot (MachineOpCode opCode,
342 assert(s < getInstrRUsage(opCode).feasibleSlots.size() && "Invalid slot!");
343 return getInstrRUsage(opCode).feasibleSlots[s];
346 inline int getLongestIssueConflict () const {
347 return longestIssueConflict;
350 inline int getMinIssueGap (MachineOpCode fromOp,
351 MachineOpCode toOp) const {
352 std::hash_map<OpCodePair,int>::const_iterator
353 I = issueGaps.find(OpCodePair(fromOp, toOp));
354 return (I == issueGaps.end())? 0 : (*I).second;
357 inline const std::vector<MachineOpCode>*
358 getConflictList(MachineOpCode opCode) const {
359 std::hash_map<MachineOpCode, std::vector<MachineOpCode> >::const_iterator
360 I = conflictLists.find(opCode);
361 return (I == conflictLists.end())? NULL : & (*I).second;
364 inline bool isSingleIssue (MachineOpCode opCode) const {
365 return getInstrRUsage(opCode).isSingleIssue;
368 inline bool breaksIssueGroup (MachineOpCode opCode) const {
369 return getInstrRUsage(opCode).breaksGroup;
372 inline unsigned int numBubblesAfter (MachineOpCode opCode) const {
373 return getInstrRUsage(opCode).numBubbles;
377 virtual void initializeResources ();
380 void computeInstrResources(const std::vector<InstrRUsage>& instrRUForClasses);
381 void computeIssueGaps(const std::vector<InstrRUsage>& instrRUForClasses);
385 const MachineInstrInfo* mii;
386 const InstrClassRUsage* classRUsages; // raw array by sclass
387 const InstrRUsageDelta* usageDeltas; // raw array [1:numUsageDeltas]
388 const InstrIssueDelta* issueDeltas; // raw array [1:numIssueDeltas]
389 unsigned int numUsageDeltas;
390 unsigned int numIssueDeltas;
392 std::vector<InstrRUsage> instrRUsages; // indexed by opcode
393 std::hash_map<OpCodePair,int> issueGaps; // indexed by opcode pair
394 std::hash_map<MachineOpCode, std::vector<MachineOpCode> >
395 conflictLists; // indexed by opcode