Added class MachineSchedInfo and several supporting classes
as a machine description for instruction scheduling.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@397 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/llvm/CodeGen/TargetMachine.h b/include/llvm/CodeGen/TargetMachine.h
index 5776656..6eece1e 100644
--- a/include/llvm/CodeGen/TargetMachine.h
+++ b/include/llvm/CodeGen/TargetMachine.h
@@ -12,15 +12,28 @@
#ifndef LLVM_CODEGEN_TARGETMACHINE_H
#define LLVM_CODEGEN_TARGETMACHINE_H
+//*********************** System Include Files *****************************/
+
+#include <string>
+#include <vector>
+#include <hash_map>
+#include <hash_set>
+#include <algorithm>
+
+//************************ User Include Files *****************************/
+
#include "llvm/CodeGen/TargetData.h"
#include "llvm/Support/NonCopyable.h"
#include "llvm/Support/DataTypes.h"
-#include <string>
+
+//************************ Opaque Declarations*****************************/
class Type;
class StructType;
struct MachineInstrDescriptor;
+class TargetMachine;
+//************************ Exported Data Types *****************************/
//---------------------------------------------------------------------------
// Data types used to define information about a single machine instruction
@@ -28,6 +41,34 @@
typedef int MachineOpCode;
typedef int OpCodeMask;
+typedef int InstrSchedClass;
+
+static const unsigned MAX_OPCODE_SIZE = 16;
+
+typedef long long cycles_t;
+const cycles_t HUGE_LATENCY = ~((unsigned long long) 1 << sizeof(cycles_t)-1);
+const cycles_t INVALID_LATENCY = -HUGE_LATENCY;
+
+
+class OpCodePair {
+public:
+ long val; // make long by concatenating two opcodes
+ OpCodePair(MachineOpCode op1, MachineOpCode op2)
+ : val((op1 < 0 || op2 < 0)?
+ -1 : (long)((((unsigned) op1) << MAX_OPCODE_SIZE) | (unsigned) op2)) {}
+ bool operator==(const OpCodePair& op) const {
+ return val == op.val;
+ }
+private:
+ OpCodePair(); // disable for now
+};
+
+
+template <> struct hash<OpCodePair> {
+ size_t operator()(const OpCodePair& pair) const {
+ return hash<long>()(pair.val);
+ }
+};
// Global variable holding an array of descriptors for machine instructions.
@@ -38,7 +79,7 @@
//---------------------------------------------------------------------------
-// struct MachineInstrInfo:
+// struct MachineInstrDescriptor:
// Predefined information about each machine instruction.
// Designed to initialized statically.
//
@@ -61,6 +102,7 @@
const unsigned int M_LOAD_FLAG = 1 << 10;
const unsigned int M_PREFETCH_FLAG = 1 << 11;
const unsigned int M_STORE_FLAG = 1 << 12;
+const unsigned int M_DUMMY_PHI_FLAG = 1 << 13;
struct MachineInstrDescriptor {
@@ -72,52 +114,140 @@
// smallest -ve value is -(maxImmedConst+1).
unsigned int numDelaySlots; // Number of delay slots after instruction
unsigned int latency; // Latency in machine cycles
- unsigned int iclass; // Flags identifying instruction class
+ InstrSchedClass schedClass; // enum identifying instr sched class
+ unsigned int iclass; // flags identifying machine instr class
};
class MachineInstrInfo : public NonCopyableV {
protected:
const MachineInstrDescriptor* desc; // raw array to allow static init'n
- unsigned int descSize; // number of entries in the array
+ unsigned int descSize; // number of entries in the desc array
+ unsigned int numRealOpCodes; // number of non-dummy op codes
public:
/*ctor*/ MachineInstrInfo(const MachineInstrDescriptor* _desc,
- unsigned int _descSize);
+ unsigned int _descSize,
+ unsigned int _numRealOpCodes);
/*dtor*/ virtual ~MachineInstrInfo();
- const MachineInstrDescriptor& getDescriptor (MachineOpCode opCode) const {
- assert(opCode < (int) descSize);
- return desc[opCode]; }
+ unsigned int getNumRealOpCodes() const {
+ return numRealOpCodes;
+ }
- virtual bool isBranch (MachineOpCode opCode) const {
- return desc[opCode].iclass & M_BRANCH_FLAG;}
+ unsigned int getNumTotalOpCodes() const {
+ return descSize;
+ }
- virtual bool isLoad (MachineOpCode opCode) const {
- return desc[opCode].iclass & M_LOAD_FLAG
- || desc[opCode].iclass & M_PREFETCH_FLAG;}
+ const MachineInstrDescriptor& getDescriptor(MachineOpCode opCode) const {
+ assert(opCode >= 0 && opCode < (int) descSize);
+ return desc[opCode];
+ }
- virtual bool isStore (MachineOpCode opCode) const {
- return desc[opCode].iclass & M_STORE_FLAG;}
+ int getNumOperands (MachineOpCode opCode) const {
+ return getDescriptor(opCode).numOperands;
+ }
+ int getResultPos (MachineOpCode opCode) const {
+ return getDescriptor(opCode).resultPos;
+ }
+
+ unsigned int getNumDelaySlots(MachineOpCode opCode) const {
+ return getDescriptor(opCode).numDelaySlots;
+ }
+
+ InstrSchedClass getSchedClass (MachineOpCode opCode) const {
+ return getDescriptor(opCode).schedClass;
+ }
+
+ //
+ // Query instruction class flags according to the machine-independent
+ // flags listed above.
+ //
+ unsigned int getIClass (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass;
+ }
+ bool isNop (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_NOP_FLAG;
+ }
+ bool isBranch (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_BRANCH_FLAG;
+ }
+ bool isCall (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_CALL_FLAG;
+ }
+ bool isReturn (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_RET_FLAG;
+ }
+ bool isControlFlow (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_BRANCH_FLAG
+ || getDescriptor(opCode).iclass & M_CALL_FLAG
+ || getDescriptor(opCode).iclass & M_RET_FLAG;
+ }
+ bool isArith (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_RET_FLAG;
+ }
+ bool isCCInstr (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_CC_FLAG;
+ }
+ bool isLogical (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_LOGICAL_FLAG;
+ }
+ bool isIntInstr (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_INT_FLAG;
+ }
+ bool isFloatInstr (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_FLOAT_FLAG;
+ }
+ bool isConditional (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_CONDL_FLAG;
+ }
+ bool isLoad (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_LOAD_FLAG;
+ }
+ bool isPrefetch (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_PREFETCH_FLAG;
+ }
+ bool isLoadOrPrefetch (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_LOAD_FLAG
+ || getDescriptor(opCode).iclass & M_PREFETCH_FLAG;
+ }
+ bool isStore (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_STORE_FLAG;
+ }
+ bool isMemoryAccess (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_LOAD_FLAG
+ || getDescriptor(opCode).iclass & M_PREFETCH_FLAG
+ || getDescriptor(opCode).iclass & M_STORE_FLAG;
+ }
+ bool isDummyPhiInstr (MachineOpCode opCode) const {
+ return getDescriptor(opCode).iclass & M_DUMMY_PHI_FLAG;
+ }
+
+ //
// Check if an instruction can be issued before its operands are ready,
// or if a subsequent instruction that uses its result can be issued
// before the results are ready.
// Default to true since most instructions on many architectures allow this.
//
virtual bool hasOperandInterlock(MachineOpCode opCode) const {
- return true; }
+ return true;
+ }
+
virtual bool hasResultInterlock(MachineOpCode opCode) const {
- return true; }
+ return true;
+ }
//
// Latencies for individual instructions and instruction pairs
//
virtual int minLatency (MachineOpCode opCode) const {
- return desc[opCode].latency; }
+ return getDescriptor(opCode).latency;
+ }
virtual int maxLatency (MachineOpCode opCode) const {
- return desc[opCode].latency; }
+ return getDescriptor(opCode).latency;
+ }
// Check if the specified constant fits in the immediate field
// of this machine instruction
@@ -133,8 +263,368 @@
//
virtual uint64_t maxImmedConstant(MachineOpCode opCode,
bool& isSignExtended) const {
- isSignExtended = desc[opCode].immedIsSignExtended;
- return desc[opCode].maxImmedConst; }
+ isSignExtended = getDescriptor(opCode).immedIsSignExtended;
+ return getDescriptor(opCode).maxImmedConst;
+ }
+};
+
+
+//---------------------------------------------------------------------------
+// class MachineResource
+// class CPUResource
+//
+// Purpose:
+// Representation of a single machine resource used in specifying
+// resource usages of machine instructions for scheduling.
+//---------------------------------------------------------------------------
+
+
+typedef unsigned int resourceId_t;
+
+class MachineResource {
+public:
+ const string rname;
+ resourceId_t rid;
+
+ /*ctor*/ MachineResource(const string& resourceName)
+ : rname(resourceName), rid(nextId++) {}
+
+private:
+ static resourceId_t nextId;
+ MachineResource(); // disable
+};
+
+
+class CPUResource : public MachineResource {
+public:
+ int maxNumUsers; // MAXINT if no restriction
+
+ /*ctor*/ CPUResource(const string& rname, int maxUsers)
+ : MachineResource(rname), maxNumUsers(maxUsers) {}
+};
+
+
+//---------------------------------------------------------------------------
+// struct InstrClassRUsage
+// struct InstrRUsageDelta
+// struct InstrIssueDelta
+// struct InstrRUsage
+//
+// Purpose:
+// The first three are structures used to specify machine resource
+// usages for each instruction in a machine description file:
+// InstrClassRUsage : resource usages common to all instrs. in a class
+// InstrRUsageDelta : add/delete resource usage for individual instrs.
+// InstrIssueDelta : add/delete instr. issue info for individual instrs
+//
+// The last one (InstrRUsage) is the internal representation of
+// instruction resource usage constructed from the above three.
+//---------------------------------------------------------------------------
+
+const int MAX_NUM_SLOTS = 32;
+const int MAX_NUM_CYCLES = 32;
+
+struct InstrClassRUsage {
+ InstrSchedClass schedClass;
+ int totCycles;
+
+ // Issue restrictions common to instructions in this class
+ unsigned int maxNumIssue;
+ bool isSingleIssue;
+ bool breaksGroup;
+ cycles_t numBubbles;
+
+ // Feasible slots to use for instructions in this class.
+ // The size of vector S[] is `numSlots'.
+ unsigned int numSlots;
+ unsigned int feasibleSlots[MAX_NUM_SLOTS];
+
+ // Resource usages common to instructions in this class.
+ // The size of vector V[] is `numRUEntries'.
+ unsigned int numRUEntries;
+ struct {
+ resourceId_t resourceId;
+ unsigned int startCycle;
+ int numCycles;
+ } V[MAX_NUM_CYCLES];
+};
+
+struct InstrRUsageDelta {
+ MachineOpCode opCode;
+ resourceId_t resourceId;
+ unsigned int startCycle;
+ int numCycles;
+};
+
+// Specify instruction issue restrictions for individual instructions
+// that differ from the common rules for the class.
+//
+struct InstrIssueDelta {
+ MachineOpCode opCode;
+ bool isSingleIssue;
+ bool breaksGroup;
+ cycles_t numBubbles;
+};
+
+
+struct InstrRUsage {
+ /*ctor*/ InstrRUsage () {}
+ /*ctor*/ InstrRUsage (const InstrRUsage& instrRU);
+ InstrRUsage& operator= (const InstrRUsage& instrRU);
+
+ bool sameAsClass;
+
+ // Issue restrictions for this instruction
+ bool isSingleIssue;
+ bool breaksGroup;
+ cycles_t numBubbles;
+
+ // Feasible slots to use for this instruction.
+ vector<bool> feasibleSlots;
+
+ // Resource usages for this instruction, with one resource vector per cycle.
+ cycles_t numCycles;
+ vector<vector<resourceId_t> > resourcesByCycle;
+
+private:
+ // Conveniences for initializing this structure
+ InstrRUsage& operator= (const InstrClassRUsage& classRU);
+ void addIssueDelta (const InstrIssueDelta& delta);
+ void addUsageDelta (const InstrRUsageDelta& delta);
+ void setMaxSlots (int maxNumSlots);
+
+ friend class MachineSchedInfo; // give access to these functions
+};
+
+
+inline void
+InstrRUsage::setMaxSlots(int maxNumSlots)
+{
+ feasibleSlots.resize(maxNumSlots);
+}
+
+inline InstrRUsage&
+InstrRUsage::operator=(const InstrRUsage& instrRU)
+{
+ sameAsClass = instrRU.sameAsClass;
+ isSingleIssue = instrRU.isSingleIssue;
+ breaksGroup = instrRU.breaksGroup;
+ numBubbles = instrRU.numBubbles;
+ feasibleSlots = instrRU.feasibleSlots;
+ numCycles = instrRU.numCycles;
+ resourcesByCycle = instrRU.resourcesByCycle;
+ return *this;
+}
+
+inline /*ctor*/
+InstrRUsage::InstrRUsage(const InstrRUsage& instrRU)
+{
+ *this = instrRU;
+}
+
+inline InstrRUsage&
+InstrRUsage::operator=(const InstrClassRUsage& classRU)
+{
+ sameAsClass = true;
+ isSingleIssue = classRU.isSingleIssue;
+ breaksGroup = classRU.breaksGroup;
+ numBubbles = classRU.numBubbles;
+
+ for (unsigned i=0; i < classRU.numSlots; i++)
+ {
+ unsigned slot = classRU.feasibleSlots[i];
+ assert(slot < feasibleSlots.size() && "Invalid slot specified!");
+ this->feasibleSlots[slot] = true;
+ }
+
+ this->numCycles = classRU.totCycles;
+ this->resourcesByCycle.resize(this->numCycles);
+
+ for (unsigned i=0; i < classRU.numRUEntries; i++)
+ for (unsigned c=classRU.V[i].startCycle, NC = c + classRU.V[i].numCycles;
+ c < NC; c++)
+ this->resourcesByCycle[c].push_back(classRU.V[i].resourceId);
+
+ // Sort each resource usage vector by resourceId_t to speed up conflict checking
+ for (unsigned i=0; i < this->resourcesByCycle.size(); i++)
+ sort(resourcesByCycle[i].begin(), resourcesByCycle[i].end());
+
+ return *this;
+}
+
+
+inline void
+InstrRUsage::addIssueDelta(const InstrIssueDelta& delta)
+{
+ sameAsClass = false;
+ isSingleIssue = delta.isSingleIssue;
+ breaksGroup = delta.breaksGroup;
+ numBubbles = delta.numBubbles;
+}
+
+
+// Add the extra resource usage requirements specified in the delta.
+// Note that a negative value of `numCycles' means one entry for that
+// resource should be deleted for each cycle.
+//
+inline void
+InstrRUsage::addUsageDelta(const InstrRUsageDelta& delta)
+{
+ int NC = delta.numCycles;
+
+ this->sameAsClass = false;
+
+ // resize the resources vector if more cycles are specified
+ unsigned maxCycles = this->numCycles;
+ maxCycles = max(maxCycles, delta.startCycle + abs(NC) - 1);
+ if (maxCycles > this->numCycles)
+ {
+ this->resourcesByCycle.resize(maxCycles);
+ this->numCycles = maxCycles;
+ }
+
+ if (NC >= 0)
+ for (unsigned c=delta.startCycle, last=c+NC-1; c <= last; c++)
+ this->resourcesByCycle[c].push_back(delta.resourceId);
+ else
+ // Remove the resource from all NC cycles.
+ for (unsigned c=delta.startCycle, last=(c-NC)-1; c <= last; c++)
+ {
+ // Look for the resource backwards so we remove the last entry
+ // for that resource in each cycle.
+ vector<resourceId_t>& rvec = this->resourcesByCycle[c];
+ int r;
+ for (r = (int) rvec.size(); r >= 0; r--)
+ if (rvec[r] == delta.resourceId)
+ {// found last entry for the resource
+ rvec.erase(rvec.begin() + r);
+ break;
+ }
+ assert(r >= 0 && "Resource to remove was unused in cycle c!");
+ }
+}
+
+
+//---------------------------------------------------------------------------
+// class MachineSchedInfo
+//
+// Purpose:
+// Common interface to machine information for instruction scheduling
+//---------------------------------------------------------------------------
+
+class MachineSchedInfo : public NonCopyableV {
+public:
+ unsigned int maxNumIssueTotal;
+ int longestIssueConflict;
+
+ int branchMispredictPenalty; // 4 for SPARC IIi
+ int branchTargetUnknownPenalty; // 2 for SPARC IIi
+ int l1DCacheMissPenalty; // 7 or 9 for SPARC IIi
+ int l1ICacheMissPenalty; // ? for SPARC IIi
+
+ bool inOrderLoads ; // true for SPARC IIi
+ bool inOrderIssue; // true for SPARC IIi
+ bool inOrderExec; // false for most architectures
+ bool inOrderRetire; // true for most architectures
+
+protected:
+ inline const InstrRUsage& getInstrRUsage(MachineOpCode opCode) const {
+ assert(opCode >= 0 && opCode < (int) instrRUsages.size());
+ return instrRUsages[opCode];
+ }
+ inline const InstrClassRUsage&
+ getClassRUsage(const InstrSchedClass& sc) const {
+ assert(sc >= 0 && sc < numSchedClasses);
+ return classRUsages[sc];
+ }
+
+public:
+ /*ctor*/ MachineSchedInfo (int _numSchedClasses,
+ const MachineInstrInfo* _mii,
+ const InstrClassRUsage* _classRUsages,
+ const InstrRUsageDelta* _usageDeltas,
+ const InstrIssueDelta* _issueDeltas,
+ unsigned int _numUsageDeltas,
+ unsigned int _numIssueDeltas);
+ /*dtor*/ virtual ~MachineSchedInfo () {}
+
+ inline const MachineInstrInfo& getInstrInfo() const {
+ return *mii;
+ }
+
+ inline int getNumSchedClasses() const {
+ return numSchedClasses;
+ }
+
+ inline unsigned int getMaxNumIssueTotal() const {
+ return maxNumIssueTotal;
+ }
+
+ inline unsigned int getMaxIssueForClass(const InstrSchedClass& sc) const {
+ assert(sc >= 0 && sc < numSchedClasses);
+ return classRUsages[sc].maxNumIssue;
+ }
+
+ inline InstrSchedClass getSchedClass (MachineOpCode opCode) const {
+ return getInstrInfo().getSchedClass(opCode);
+ }
+
+ inline bool instrCanUseSlot (MachineOpCode opCode,
+ unsigned s) const {
+ assert(s < getInstrRUsage(opCode).feasibleSlots.size() && "Invalid slot!");
+ return getInstrRUsage(opCode).feasibleSlots[s];
+ }
+
+ inline int getLongestIssueConflict () const {
+ return longestIssueConflict;
+ }
+
+ inline int getMinIssueGap (MachineOpCode fromOp,
+ MachineOpCode toOp) const {
+ hash_map<OpCodePair,int>::const_iterator
+ I = issueGaps.find(OpCodePair(fromOp, toOp));
+ return (I == issueGaps.end())? 0 : (*I).second;
+ }
+
+ inline const vector<MachineOpCode>*
+ getConflictList(MachineOpCode opCode) const {
+ hash_map<MachineOpCode,vector<MachineOpCode> >::const_iterator
+ I = conflictLists.find(opCode);
+ return (I == conflictLists.end())? NULL : & (*I).second;
+ }
+
+ inline bool isSingleIssue (MachineOpCode opCode) const {
+ return getInstrRUsage(opCode).isSingleIssue;
+ }
+
+ inline bool breaksIssueGroup (MachineOpCode opCode) const {
+ return getInstrRUsage(opCode).breaksGroup;
+ }
+
+ inline unsigned int numBubblesAfter (MachineOpCode opCode) const {
+ return getInstrRUsage(opCode).numBubbles;
+ }
+
+protected:
+ virtual void initializeResources ();
+
+private:
+ void computeInstrResources(const vector<InstrRUsage>& instrRUForClasses);
+ void computeIssueGaps(const vector<InstrRUsage>& instrRUForClasses);
+
+protected:
+ int numSchedClasses;
+ const MachineInstrInfo* mii;
+ const InstrClassRUsage* classRUsages; // raw array by sclass
+ const InstrRUsageDelta* usageDeltas; // raw array [1:numUsageDeltas]
+ const InstrIssueDelta* issueDeltas; // raw array [1:numIssueDeltas]
+ unsigned int numUsageDeltas;
+ unsigned int numIssueDeltas;
+
+ vector<InstrRUsage> instrRUsages; // indexed by opcode
+ hash_map<OpCodePair,int> issueGaps; // indexed by opcode pair
+ hash_map<MachineOpCode,vector<MachineOpCode> >
+ conflictLists; // indexed by opcode
};
@@ -149,7 +639,7 @@
class TargetMachine : public NonCopyableV {
public:
const string TargetName;
- const TargetData DataLayout; // Calculates type size & alignment
+ const TargetData DataLayout; // Calculates type size & alignment
int optSizeForSubWordData;
int minMemOpWordSize;
int maxAtomicMemOpWordSize;
@@ -158,34 +648,37 @@
int zeroRegNum; // register that gives 0 if any (-1 if none)
public:
- TargetMachine(const string &targetname, MachineInstrInfo* mii,
- unsigned char PtrSize = 8, unsigned char PtrAl = 8,
- unsigned char DoubleAl = 8, unsigned char FloatAl = 4,
- unsigned char LongAl = 8, unsigned char IntAl = 4,
- unsigned char ShortAl = 2, unsigned char ByteAl = 1)
+ /*ctor*/ TargetMachine(const string &targetname,
+ unsigned char PtrSize = 8, unsigned char PtrAl = 8,
+ unsigned char DoubleAl = 8, unsigned char FloatAl = 4,
+ unsigned char LongAl = 8, unsigned char IntAl = 4,
+ unsigned char ShortAl = 2, unsigned char ByteAl = 1)
: TargetName(targetname), DataLayout(targetname, PtrSize, PtrAl,
DoubleAl, FloatAl, LongAl, IntAl,
- ShortAl, ByteAl),
- machineInstrInfo(mii) {
- }
- virtual ~TargetMachine() {
- delete machineInstrInfo;
- }
+ ShortAl, ByteAl)
+ {}
+
+ /*dtor*/ virtual ~TargetMachine() {}
const MachineInstrInfo& getInstrInfo () const { return *machineInstrInfo; }
- // const MachineSchedInfo& getSchedInfo() const { return *machineSchedInfo; }
+ const MachineSchedInfo& getSchedInfo() const { return *machineSchedInfo; }
virtual unsigned int findOptimalStorageSize (const Type* ty) const;
+ // This really should be in the register info class
+ virtual bool regsMayBeAliased (unsigned int regNum1,
+ unsigned int regNum2) const {
+ return (regNum1 == regNum2);
+ }
+
protected:
// Description of machine instructions
// Protect so that subclass can control alloc/dealloc
MachineInstrInfo* machineInstrInfo;
- // MachineSchedInfo* machineSchedInfo;
+ MachineSchedInfo* machineSchedInfo;
};
-
//**************************************************************************/
#endif
diff --git a/lib/CodeGen/TargetMachine/TargetMachine.cpp b/lib/CodeGen/TargetMachine/TargetMachine.cpp
index cf4cbc6..0a9a739 100644
--- a/lib/CodeGen/TargetMachine/TargetMachine.cpp
+++ b/lib/CodeGen/TargetMachine/TargetMachine.cpp
@@ -24,6 +24,16 @@
//
const MachineInstrDescriptor* TargetInstrDescriptors = NULL;
+resourceId_t MachineResource::nextId = 0;
+
+//************************* Forward Declarations **************************/
+
+static cycles_t ComputeMinGap (const InstrRUsage& fromRU,
+ const InstrRUsage& toRU);
+
+static bool RUConflict (const vector<resourceId_t>& fromRVec,
+ const vector<resourceId_t>& fromRVec);
+
//************************ Class Implementations **************************/
@@ -66,8 +76,9 @@
/*ctor*/
MachineInstrInfo::MachineInstrInfo(const MachineInstrDescriptor* _desc,
- unsigned int _descSize)
- : desc(_desc), descSize(_descSize)
+ unsigned int _descSize,
+ unsigned int _numRealOpCodes)
+ : desc(_desc), descSize(_descSize), numRealOpCodes(_numRealOpCodes)
{
assert(TargetInstrDescriptors == NULL && desc != NULL);
TargetInstrDescriptors = desc; // initialize global variable
@@ -99,4 +110,186 @@
return false;
}
+
+//---------------------------------------------------------------------------
+// class MachineSchedInfo
+// Interface to machine description for instruction scheduling
+//---------------------------------------------------------------------------
+
+/*ctor*/
+MachineSchedInfo::MachineSchedInfo(int _numSchedClasses,
+ const MachineInstrInfo* _mii,
+ const InstrClassRUsage* _classRUsages,
+ const InstrRUsageDelta* _usageDeltas,
+ const InstrIssueDelta* _issueDeltas,
+ unsigned int _numUsageDeltas,
+ unsigned int _numIssueDeltas)
+ : numSchedClasses(_numSchedClasses),
+ mii(_mii),
+ classRUsages(_classRUsages),
+ usageDeltas(_usageDeltas),
+ issueDeltas(_issueDeltas),
+ numUsageDeltas(_numUsageDeltas),
+ numIssueDeltas(_numIssueDeltas)
+{
+}
+
+void
+MachineSchedInfo::initializeResources()
+{
+ assert(MAX_NUM_SLOTS >= (int) getMaxNumIssueTotal()
+ && "Insufficient slots for static data! Increase MAX_NUM_SLOTS");
+
+ // First, compute common resource usage info for each class because
+ // most instructions will probably behave the same as their class.
+ // Cannot allocate a vector of InstrRUsage so new each one.
+ //
+ vector<InstrRUsage> instrRUForClasses;
+ instrRUForClasses.resize(numSchedClasses);
+ for (InstrSchedClass sc=0; sc < numSchedClasses; sc++)
+ {
+ // instrRUForClasses.push_back(new InstrRUsage);
+ instrRUForClasses[sc].setMaxSlots(getMaxNumIssueTotal());
+ instrRUForClasses[sc] = classRUsages[sc];
+ }
+
+ computeInstrResources(instrRUForClasses);
+
+ computeIssueGaps(instrRUForClasses);
+}
+
+
+void
+MachineSchedInfo::computeInstrResources(const vector<InstrRUsage>& instrRUForClasses)
+{
+ int numOpCodes = mii->getNumRealOpCodes();
+ instrRUsages.resize(numOpCodes);
+
+ // First get the resource usage information from the class resource usages.
+ for (MachineOpCode op=0; op < numOpCodes; op++)
+ {
+ InstrSchedClass sc = getSchedClass(op);
+ assert(sc >= 0 && sc < numSchedClasses);
+ instrRUsages[op] = instrRUForClasses[sc];
+ }
+
+ // Now, modify the resource usages as specified in the deltas.
+ for (unsigned i=0; i < numUsageDeltas; i++)
+ {
+ MachineOpCode op = usageDeltas[i].opCode;
+ assert(op < numOpCodes);
+ instrRUsages[op].addUsageDelta(usageDeltas[i]);
+ }
+
+ // Then modify the issue restrictions as specified in the deltas.
+ for (unsigned i=0; i < numIssueDeltas; i++)
+ {
+ MachineOpCode op = issueDeltas[i].opCode;
+ assert(op < numOpCodes);
+ instrRUsages[issueDeltas[i].opCode].addIssueDelta(issueDeltas[i]);
+ }
+}
+
+
+void
+MachineSchedInfo::computeIssueGaps(const vector<InstrRUsage>& instrRUForClasses)
+{
+ int numOpCodes = mii->getNumRealOpCodes();
+ instrRUsages.resize(numOpCodes);
+
+ assert(numOpCodes < (1 << MAX_OPCODE_SIZE) - 1
+ && "numOpCodes invalid for implementation of class OpCodePair!");
+
+ // First, compute issue gaps between pairs of classes based on common
+ // resources usages for each class, because most instruction pairs will
+ // usually behave the same as their class.
+ //
+ int classPairGaps[numSchedClasses][numSchedClasses];
+ for (InstrSchedClass fromSC=0; fromSC < numSchedClasses; fromSC++)
+ for (InstrSchedClass toSC=0; toSC < numSchedClasses; toSC++)
+ {
+ int classPairGap = ComputeMinGap(instrRUForClasses[fromSC],
+ instrRUForClasses[toSC]);
+ classPairGaps[fromSC][toSC] = classPairGap;
+ }
+
+ // Now, for each pair of instructions, use the class pair gap if both
+ // instructions have identical resource usage as their respective classes.
+ // If not, recompute the gap for the pair from scratch.
+
+ longestIssueConflict = 0;
+
+ for (MachineOpCode fromOp=0; fromOp < numOpCodes; fromOp++)
+ for (MachineOpCode toOp=0; toOp < numOpCodes; toOp++)
+ {
+ int instrPairGap =
+ (instrRUsages[fromOp].sameAsClass && instrRUsages[toOp].sameAsClass)
+ ? classPairGaps[getSchedClass(fromOp)][getSchedClass(toOp)]
+ : ComputeMinGap(instrRUsages[fromOp], instrRUsages[toOp]);
+
+ if (instrPairGap > 0)
+ {
+ issueGaps[OpCodePair(fromOp,toOp)] = instrPairGap;
+ conflictLists[fromOp].push_back(toOp);
+ longestIssueConflict = max(longestIssueConflict, instrPairGap);
+ }
+ }
+}
+
+
+// Check if fromRVec and toRVec have *any* common entries.
+// Assume the vectors are sorted in increasing order.
+// Algorithm copied from function set_intersection() for sorted ranges (stl_algo.h).
+inline static bool
+RUConflict(const vector<resourceId_t>& fromRVec,
+ const vector<resourceId_t>& toRVec)
+{
+ bool commonElementFound = false;
+
+ unsigned fN = fromRVec.size(), tN = toRVec.size();
+ unsigned fi = 0, ti = 0;
+ while (fi < fN && ti < tN)
+ if (fromRVec[fi] < toRVec[ti])
+ ++fi;
+ else if (toRVec[ti] < fromRVec[fi])
+ ++ti;
+ else
+ {
+ commonElementFound = true;
+ break;
+ }
+
+ return commonElementFound;
+}
+
+
+static cycles_t
+ComputeMinGap(const InstrRUsage& fromRU, const InstrRUsage& toRU)
+{
+ cycles_t minGap = 0;
+
+ if (fromRU.numBubbles > 0)
+ minGap = fromRU.numBubbles;
+
+ if (minGap < fromRU.numCycles)
+ {
+ // only need to check from cycle `minGap' onwards
+ for (cycles_t gap=minGap; gap <= fromRU.numCycles-1; gap++)
+ {
+ // check if instr. #2 can start executing `gap' cycles after #1
+ // by checking for resource conflicts in each overlapping cycle
+ cycles_t numOverlap = min(fromRU.numCycles - gap, toRU.numCycles);
+ for (cycles_t c = 0; c <= numOverlap-1; c++)
+ if (RUConflict(fromRU.resourcesByCycle[gap + c],
+ toRU.resourcesByCycle[c]))
+ {// conflict found so minGap must be more than `gap'
+ minGap = gap+1;
+ break;
+ }
+ }
+ }
+
+ return minGap;
+}
+
//---------------------------------------------------------------------------