2 //***************************************************************************
9 // 7/12/01 - Vikram Adve - Created
10 //**************************************************************************/
12 #ifndef LLVM_CODEGEN_TARGETMACHINE_H
13 #define LLVM_CODEGEN_TARGETMACHINE_H
15 #include "llvm/CodeGen/TargetData.h"
16 #include "llvm/Support/NonCopyable.h"
17 #include "llvm/Support/DataTypes.h"
24 struct MachineInstrDescriptor;
27 //************************ Exported Data Types *****************************/
29 //---------------------------------------------------------------------------
30 // Data types used to define information about a single machine instruction
31 //---------------------------------------------------------------------------
33 typedef int MachineOpCode;
34 typedef int OpCodeMask;
35 typedef int InstrSchedClass;
37 static const unsigned MAX_OPCODE_SIZE = 16;
39 typedef long long cycles_t;
40 const cycles_t HUGE_LATENCY = ~((unsigned long long) 1 << sizeof(cycles_t)-1);
41 const cycles_t INVALID_LATENCY = -HUGE_LATENCY;
46 long val; // make long by concatenating two opcodes
47 OpCodePair(MachineOpCode op1, MachineOpCode op2)
48 : val((op1 < 0 || op2 < 0)?
49 -1 : (long)((((unsigned) op1) << MAX_OPCODE_SIZE) | (unsigned) op2)) {}
50 bool operator==(const OpCodePair& op) const {
54 OpCodePair(); // disable for now
58 template <> struct hash<OpCodePair> {
59 size_t operator()(const OpCodePair& pair) const {
60 return hash<long>()(pair.val);
65 // Global variable holding an array of descriptors for machine instructions.
66 // The actual object needs to be created separately for each target machine.
67 // This variable is initialized and reset by class MachineInstrInfo.
69 extern const MachineInstrDescriptor* TargetInstrDescriptors;
72 //---------------------------------------------------------------------------
73 // struct MachineInstrDescriptor:
74 // Predefined information about each machine instruction.
75 // Designed to initialized statically.
77 // class MachineInstructionInfo
78 // Interface to description of machine instructions
80 //---------------------------------------------------------------------------
83 const unsigned int M_NOP_FLAG = 1;
84 const unsigned int M_BRANCH_FLAG = 1 << 1;
85 const unsigned int M_CALL_FLAG = 1 << 2;
86 const unsigned int M_RET_FLAG = 1 << 3;
87 const unsigned int M_ARITH_FLAG = 1 << 4;
88 const unsigned int M_CC_FLAG = 1 << 6;
89 const unsigned int M_LOGICAL_FLAG = 1 << 6;
90 const unsigned int M_INT_FLAG = 1 << 7;
91 const unsigned int M_FLOAT_FLAG = 1 << 8;
92 const unsigned int M_CONDL_FLAG = 1 << 9;
93 const unsigned int M_LOAD_FLAG = 1 << 10;
94 const unsigned int M_PREFETCH_FLAG = 1 << 11;
95 const unsigned int M_STORE_FLAG = 1 << 12;
96 const unsigned int M_DUMMY_PHI_FLAG = 1 << 13;
99 struct MachineInstrDescriptor {
100 string opCodeString; // Assembly language mnemonic for the opcode.
101 int numOperands; // Number of args; -1 if variable #args
102 int resultPos; // Position of the result; -1 if no result
103 unsigned int maxImmedConst; // Largest +ve constant in IMMMED field or 0.
104 bool immedIsSignExtended; // Is IMMED field sign-extended? If so,
105 // smallest -ve value is -(maxImmedConst+1).
106 unsigned int numDelaySlots; // Number of delay slots after instruction
107 unsigned int latency; // Latency in machine cycles
108 InstrSchedClass schedClass; // enum identifying instr sched class
109 unsigned int iclass; // flags identifying machine instr class
113 class MachineInstrInfo : public NonCopyableV {
115 const MachineInstrDescriptor* desc; // raw array to allow static init'n
116 unsigned int descSize; // number of entries in the desc array
117 unsigned int numRealOpCodes; // number of non-dummy op codes
120 /*ctor*/ MachineInstrInfo(const MachineInstrDescriptor* _desc,
121 unsigned int _descSize,
122 unsigned int _numRealOpCodes);
123 /*dtor*/ virtual ~MachineInstrInfo();
125 unsigned int getNumRealOpCodes() const {
126 return numRealOpCodes;
129 unsigned int getNumTotalOpCodes() const {
133 const MachineInstrDescriptor& getDescriptor(MachineOpCode opCode) const {
134 assert(opCode >= 0 && opCode < (int) descSize);
138 int getNumOperands (MachineOpCode opCode) const {
139 return getDescriptor(opCode).numOperands;
142 int getResultPos (MachineOpCode opCode) const {
143 return getDescriptor(opCode).resultPos;
146 unsigned int getNumDelaySlots(MachineOpCode opCode) const {
147 return getDescriptor(opCode).numDelaySlots;
150 InstrSchedClass getSchedClass (MachineOpCode opCode) const {
151 return getDescriptor(opCode).schedClass;
155 // Query instruction class flags according to the machine-independent
156 // flags listed above.
158 unsigned int getIClass (MachineOpCode opCode) const {
159 return getDescriptor(opCode).iclass;
161 bool isNop (MachineOpCode opCode) const {
162 return getDescriptor(opCode).iclass & M_NOP_FLAG;
164 bool isBranch (MachineOpCode opCode) const {
165 return getDescriptor(opCode).iclass & M_BRANCH_FLAG;
167 bool isCall (MachineOpCode opCode) const {
168 return getDescriptor(opCode).iclass & M_CALL_FLAG;
170 bool isReturn (MachineOpCode opCode) const {
171 return getDescriptor(opCode).iclass & M_RET_FLAG;
173 bool isControlFlow (MachineOpCode opCode) const {
174 return getDescriptor(opCode).iclass & M_BRANCH_FLAG
175 || getDescriptor(opCode).iclass & M_CALL_FLAG
176 || getDescriptor(opCode).iclass & M_RET_FLAG;
178 bool isArith (MachineOpCode opCode) const {
179 return getDescriptor(opCode).iclass & M_RET_FLAG;
181 bool isCCInstr (MachineOpCode opCode) const {
182 return getDescriptor(opCode).iclass & M_CC_FLAG;
184 bool isLogical (MachineOpCode opCode) const {
185 return getDescriptor(opCode).iclass & M_LOGICAL_FLAG;
187 bool isIntInstr (MachineOpCode opCode) const {
188 return getDescriptor(opCode).iclass & M_INT_FLAG;
190 bool isFloatInstr (MachineOpCode opCode) const {
191 return getDescriptor(opCode).iclass & M_FLOAT_FLAG;
193 bool isConditional (MachineOpCode opCode) const {
194 return getDescriptor(opCode).iclass & M_CONDL_FLAG;
196 bool isLoad (MachineOpCode opCode) const {
197 return getDescriptor(opCode).iclass & M_LOAD_FLAG;
199 bool isPrefetch (MachineOpCode opCode) const {
200 return getDescriptor(opCode).iclass & M_PREFETCH_FLAG;
202 bool isLoadOrPrefetch (MachineOpCode opCode) const {
203 return getDescriptor(opCode).iclass & M_LOAD_FLAG
204 || getDescriptor(opCode).iclass & M_PREFETCH_FLAG;
206 bool isStore (MachineOpCode opCode) const {
207 return getDescriptor(opCode).iclass & M_STORE_FLAG;
209 bool isMemoryAccess (MachineOpCode opCode) const {
210 return getDescriptor(opCode).iclass & M_LOAD_FLAG
211 || getDescriptor(opCode).iclass & M_PREFETCH_FLAG
212 || getDescriptor(opCode).iclass & M_STORE_FLAG;
214 bool isDummyPhiInstr (MachineOpCode opCode) const {
215 return getDescriptor(opCode).iclass & M_DUMMY_PHI_FLAG;
219 // delete this later *******
220 bool isPhi(MachineOpCode opCode) { return isDummyPhiInstr(opCode); }
224 // Check if an instruction can be issued before its operands are ready,
225 // or if a subsequent instruction that uses its result can be issued
226 // before the results are ready.
227 // Default to true since most instructions on many architectures allow this.
229 virtual bool hasOperandInterlock(MachineOpCode opCode) const {
233 virtual bool hasResultInterlock(MachineOpCode opCode) const {
238 // Latencies for individual instructions and instruction pairs
240 virtual int minLatency (MachineOpCode opCode) const {
241 return getDescriptor(opCode).latency;
244 virtual int maxLatency (MachineOpCode opCode) const {
245 return getDescriptor(opCode).latency;
248 // Check if the specified constant fits in the immediate field
249 // of this machine instruction
251 virtual bool constantFitsInImmedField(MachineOpCode opCode,
252 int64_t intValue) const;
254 // Return the largest +ve constant that can be held in the IMMMED field
255 // of this machine instruction.
256 // isSignExtended is set to true if the value is sign-extended before use
257 // (this is true for all immediate fields in SPARC instructions).
258 // Return 0 if the instruction has no IMMED field.
260 virtual uint64_t maxImmedConstant(MachineOpCode opCode,
261 bool& isSignExtended) const {
262 isSignExtended = getDescriptor(opCode).immedIsSignExtended;
263 return getDescriptor(opCode).maxImmedConst;
268 //---------------------------------------------------------------------------
269 // class MachineResource
273 // Representation of a single machine resource used in specifying
274 // resource usages of machine instructions for scheduling.
275 //---------------------------------------------------------------------------
278 typedef unsigned int resourceId_t;
280 class MachineResource {
285 /*ctor*/ MachineResource(const string& resourceName)
286 : rname(resourceName), rid(nextId++) {}
289 static resourceId_t nextId;
290 MachineResource(); // disable
294 class CPUResource : public MachineResource {
296 int maxNumUsers; // MAXINT if no restriction
298 /*ctor*/ CPUResource(const string& rname, int maxUsers)
299 : MachineResource(rname), maxNumUsers(maxUsers) {}
303 //---------------------------------------------------------------------------
304 // struct InstrClassRUsage
305 // struct InstrRUsageDelta
306 // struct InstrIssueDelta
307 // struct InstrRUsage
310 // The first three are structures used to specify machine resource
311 // usages for each instruction in a machine description file:
312 // InstrClassRUsage : resource usages common to all instrs. in a class
313 // InstrRUsageDelta : add/delete resource usage for individual instrs.
314 // InstrIssueDelta : add/delete instr. issue info for individual instrs
316 // The last one (InstrRUsage) is the internal representation of
317 // instruction resource usage constructed from the above three.
318 //---------------------------------------------------------------------------
320 const int MAX_NUM_SLOTS = 32;
321 const int MAX_NUM_CYCLES = 32;
323 struct InstrClassRUsage {
324 InstrSchedClass schedClass;
327 // Issue restrictions common to instructions in this class
328 unsigned int maxNumIssue;
333 // Feasible slots to use for instructions in this class.
334 // The size of vector S[] is `numSlots'.
335 unsigned int numSlots;
336 unsigned int feasibleSlots[MAX_NUM_SLOTS];
338 // Resource usages common to instructions in this class.
339 // The size of vector V[] is `numRUEntries'.
340 unsigned int numRUEntries;
342 resourceId_t resourceId;
343 unsigned int startCycle;
348 struct InstrRUsageDelta {
349 MachineOpCode opCode;
350 resourceId_t resourceId;
351 unsigned int startCycle;
355 // Specify instruction issue restrictions for individual instructions
356 // that differ from the common rules for the class.
358 struct InstrIssueDelta {
359 MachineOpCode opCode;
367 /*ctor*/ InstrRUsage () {}
368 /*ctor*/ InstrRUsage (const InstrRUsage& instrRU);
369 InstrRUsage& operator= (const InstrRUsage& instrRU);
373 // Issue restrictions for this instruction
378 // Feasible slots to use for this instruction.
379 vector<bool> feasibleSlots;
381 // Resource usages for this instruction, with one resource vector per cycle.
383 vector<vector<resourceId_t> > resourcesByCycle;
386 // Conveniences for initializing this structure
387 InstrRUsage& operator= (const InstrClassRUsage& classRU);
388 void addIssueDelta (const InstrIssueDelta& delta);
389 void addUsageDelta (const InstrRUsageDelta& delta);
390 void setMaxSlots (int maxNumSlots);
392 friend class MachineSchedInfo; // give access to these functions
397 InstrRUsage::setMaxSlots(int maxNumSlots)
399 feasibleSlots.resize(maxNumSlots);
403 InstrRUsage::operator=(const InstrRUsage& instrRU)
405 sameAsClass = instrRU.sameAsClass;
406 isSingleIssue = instrRU.isSingleIssue;
407 breaksGroup = instrRU.breaksGroup;
408 numBubbles = instrRU.numBubbles;
409 feasibleSlots = instrRU.feasibleSlots;
410 numCycles = instrRU.numCycles;
411 resourcesByCycle = instrRU.resourcesByCycle;
416 InstrRUsage::InstrRUsage(const InstrRUsage& instrRU)
422 InstrRUsage::operator=(const InstrClassRUsage& classRU)
425 isSingleIssue = classRU.isSingleIssue;
426 breaksGroup = classRU.breaksGroup;
427 numBubbles = classRU.numBubbles;
429 for (unsigned i=0; i < classRU.numSlots; i++)
431 unsigned slot = classRU.feasibleSlots[i];
432 assert(slot < feasibleSlots.size() && "Invalid slot specified!");
433 this->feasibleSlots[slot] = true;
436 this->numCycles = classRU.totCycles;
437 this->resourcesByCycle.resize(this->numCycles);
439 for (unsigned i=0; i < classRU.numRUEntries; i++)
440 for (unsigned c=classRU.V[i].startCycle, NC = c + classRU.V[i].numCycles;
442 this->resourcesByCycle[c].push_back(classRU.V[i].resourceId);
444 // Sort each resource usage vector by resourceId_t to speed up conflict checking
445 for (unsigned i=0; i < this->resourcesByCycle.size(); i++)
446 sort(resourcesByCycle[i].begin(), resourcesByCycle[i].end());
453 InstrRUsage::addIssueDelta(const InstrIssueDelta& delta)
456 isSingleIssue = delta.isSingleIssue;
457 breaksGroup = delta.breaksGroup;
458 numBubbles = delta.numBubbles;
462 // Add the extra resource usage requirements specified in the delta.
463 // Note that a negative value of `numCycles' means one entry for that
464 // resource should be deleted for each cycle.
467 InstrRUsage::addUsageDelta(const InstrRUsageDelta& delta)
469 int NC = delta.numCycles;
471 this->sameAsClass = false;
473 // resize the resources vector if more cycles are specified
474 unsigned maxCycles = this->numCycles;
475 maxCycles = max(maxCycles, delta.startCycle + abs(NC) - 1);
476 if (maxCycles > this->numCycles)
478 this->resourcesByCycle.resize(maxCycles);
479 this->numCycles = maxCycles;
483 for (unsigned c=delta.startCycle, last=c+NC-1; c <= last; c++)
484 this->resourcesByCycle[c].push_back(delta.resourceId);
486 // Remove the resource from all NC cycles.
487 for (unsigned c=delta.startCycle, last=(c-NC)-1; c <= last; c++)
489 // Look for the resource backwards so we remove the last entry
490 // for that resource in each cycle.
491 vector<resourceId_t>& rvec = this->resourcesByCycle[c];
493 for (r = (int) rvec.size(); r >= 0; r--)
494 if (rvec[r] == delta.resourceId)
495 {// found last entry for the resource
496 rvec.erase(rvec.begin() + r);
499 assert(r >= 0 && "Resource to remove was unused in cycle c!");
504 //---------------------------------------------------------------------------
505 // class MachineSchedInfo
508 // Common interface to machine information for instruction scheduling
509 //---------------------------------------------------------------------------
511 class MachineSchedInfo : public NonCopyableV {
513 unsigned int maxNumIssueTotal;
514 int longestIssueConflict;
516 int branchMispredictPenalty; // 4 for SPARC IIi
517 int branchTargetUnknownPenalty; // 2 for SPARC IIi
518 int l1DCacheMissPenalty; // 7 or 9 for SPARC IIi
519 int l1ICacheMissPenalty; // ? for SPARC IIi
521 bool inOrderLoads ; // true for SPARC IIi
522 bool inOrderIssue; // true for SPARC IIi
523 bool inOrderExec; // false for most architectures
524 bool inOrderRetire; // true for most architectures
527 inline const InstrRUsage& getInstrRUsage(MachineOpCode opCode) const {
528 assert(opCode >= 0 && opCode < (int) instrRUsages.size());
529 return instrRUsages[opCode];
531 inline const InstrClassRUsage&
532 getClassRUsage(const InstrSchedClass& sc) const {
533 assert(sc >= 0 && sc < numSchedClasses);
534 return classRUsages[sc];
538 /*ctor*/ MachineSchedInfo (int _numSchedClasses,
539 const MachineInstrInfo* _mii,
540 const InstrClassRUsage* _classRUsages,
541 const InstrRUsageDelta* _usageDeltas,
542 const InstrIssueDelta* _issueDeltas,
543 unsigned int _numUsageDeltas,
544 unsigned int _numIssueDeltas);
545 /*dtor*/ virtual ~MachineSchedInfo () {}
547 inline const MachineInstrInfo& getInstrInfo() const {
551 inline int getNumSchedClasses() const {
552 return numSchedClasses;
555 inline unsigned int getMaxNumIssueTotal() const {
556 return maxNumIssueTotal;
559 inline unsigned int getMaxIssueForClass(const InstrSchedClass& sc) const {
560 assert(sc >= 0 && sc < numSchedClasses);
561 return classRUsages[sc].maxNumIssue;
564 inline InstrSchedClass getSchedClass (MachineOpCode opCode) const {
565 return getInstrInfo().getSchedClass(opCode);
568 inline bool instrCanUseSlot (MachineOpCode opCode,
570 assert(s < getInstrRUsage(opCode).feasibleSlots.size() && "Invalid slot!");
571 return getInstrRUsage(opCode).feasibleSlots[s];
574 inline int getLongestIssueConflict () const {
575 return longestIssueConflict;
578 inline int getMinIssueGap (MachineOpCode fromOp,
579 MachineOpCode toOp) const {
580 hash_map<OpCodePair,int>::const_iterator
581 I = issueGaps.find(OpCodePair(fromOp, toOp));
582 return (I == issueGaps.end())? 0 : (*I).second;
585 inline const vector<MachineOpCode>*
586 getConflictList(MachineOpCode opCode) const {
587 hash_map<MachineOpCode,vector<MachineOpCode> >::const_iterator
588 I = conflictLists.find(opCode);
589 return (I == conflictLists.end())? NULL : & (*I).second;
592 inline bool isSingleIssue (MachineOpCode opCode) const {
593 return getInstrRUsage(opCode).isSingleIssue;
596 inline bool breaksIssueGroup (MachineOpCode opCode) const {
597 return getInstrRUsage(opCode).breaksGroup;
600 inline unsigned int numBubblesAfter (MachineOpCode opCode) const {
601 return getInstrRUsage(opCode).numBubbles;
605 virtual void initializeResources ();
608 void computeInstrResources(const vector<InstrRUsage>& instrRUForClasses);
609 void computeIssueGaps(const vector<InstrRUsage>& instrRUForClasses);
613 const MachineInstrInfo* mii;
614 const InstrClassRUsage* classRUsages; // raw array by sclass
615 const InstrRUsageDelta* usageDeltas; // raw array [1:numUsageDeltas]
616 const InstrIssueDelta* issueDeltas; // raw array [1:numIssueDeltas]
617 unsigned int numUsageDeltas;
618 unsigned int numIssueDeltas;
620 vector<InstrRUsage> instrRUsages; // indexed by opcode
621 hash_map<OpCodePair,int> issueGaps; // indexed by opcode pair
622 hash_map<MachineOpCode,vector<MachineOpCode> >
623 conflictLists; // indexed by opcode
628 //-----------------------------------------------------------------------------
629 // class MachineRegClassInfo
632 // Interface to description of machine register class (e.g., int reg class
633 // float reg class etc)
635 //--------------------------------------------------------------------------
640 class MachineRegClassInfo {
644 const unsigned RegClassID; // integer ID of a reg class
645 const unsigned NumOfAvailRegs; // # of avail for coloring -without SP etc.
646 const unsigned NumOfAllRegs; // # of all registers -including SP,g0 etc.
650 inline unsigned getRegClassID() const { return RegClassID; }
651 inline unsigned getNumOfAvailRegs() const { return NumOfAvailRegs; }
652 inline unsigned getNumOfAllRegs() const { return NumOfAllRegs; }
656 // This method should find a color which is not used by neighbors
657 // (i.e., a false position in IsColorUsedArr) and
658 virtual void colorIGNode(IGNode * Node, bool IsColorUsedArr[] ) const = 0;
661 MachineRegClassInfo(const unsigned ID, const unsigned NVR,
662 const unsigned NAR): RegClassID(ID), NumOfAvailRegs(NVR),
664 { } // empty constructor
671 //---------------------------------------------------------------------------
672 // class MachineRegInfo
675 // Interface to register info of target machine
677 //--------------------------------------------------------------------------
685 typedef hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
687 // A vector of all machine register classes
688 typedef vector<const MachineRegClassInfo *> MachineRegClassArrayType;
691 class MachineRegInfo : public NonCopyableV {
695 MachineRegClassArrayType MachineRegClassArr;
701 inline unsigned int getNumOfRegClasses() const {
702 return MachineRegClassArr.size();
705 const MachineRegClassInfo *const getMachineRegClass(unsigned i) const {
706 return MachineRegClassArr[i];
710 virtual unsigned getRegClassIDOfValue (const Value *const Val) const = 0;
712 virtual void colorArgs(const Method *const Meth,
713 LiveRangeInfo & LRI) const = 0;
715 virtual void colorCallArgs(vector<const Instruction *> & CallInstrList,
717 AddedInstrMapType& AddedInstrMap ) const = 0 ;
719 virtual int getUnifiedRegNum(int RegClassID, int reg) const = 0;
721 virtual const string getUnifiedRegName(int reg) const = 0;
723 //virtual void printReg(const LiveRange *const LR) const =0;
733 //---------------------------------------------------------------------------
734 // class TargetMachine
737 // Primary interface to machine description for the target machine.
739 //---------------------------------------------------------------------------
741 class TargetMachine : public NonCopyableV {
743 const string TargetName;
744 const TargetData DataLayout; // Calculates type size & alignment
745 int optSizeForSubWordData;
746 int minMemOpWordSize;
747 int maxAtomicMemOpWordSize;
749 // Register information. This needs to be reorganized into a single class.
750 int zeroRegNum; // register that gives 0 if any (-1 if none)
753 TargetMachine(const string &targetname,
754 unsigned char PtrSize = 8, unsigned char PtrAl = 8,
755 unsigned char DoubleAl = 8, unsigned char FloatAl = 4,
756 unsigned char LongAl = 8, unsigned char IntAl = 4,
757 unsigned char ShortAl = 2, unsigned char ByteAl = 1)
758 : TargetName(targetname), DataLayout(targetname, PtrSize, PtrAl,
759 DoubleAl, FloatAl, LongAl, IntAl,
761 virtual ~TargetMachine() {}
763 virtual const MachineInstrInfo& getInstrInfo() const = 0;
765 virtual unsigned int findOptimalStorageSize (const Type* ty) const;
767 // This really should be in the register info class
768 virtual bool regsMayBeAliased (unsigned int regNum1,
769 unsigned int regNum2) const {
770 return (regNum1 == regNum2);
773 // compileMethod - This does everything neccesary to compile a method into the
774 // built in representation. This allows the target to have complete control
775 // over how it does compilation. This does not emit assembly or output
776 // machine code however, this is done later.
778 virtual bool compileMethod(Method *M) = 0;
780 // emitAssembly - Output assembly language code (a .s file) for the specified
781 // method. The specified method must have been compiled before this may be
784 virtual void emitAssembly(Method *M, ostream &OutStr) { /* todo */ }