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

2 files changed, 724 insertions, 38 deletions

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 @@ struct MachineInstrDescriptor;
 
 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 @@ extern const MachineInstrDescriptor* TargetInstrDescriptors;
 
 
 //---------------------------------------------------------------------------
-// struct MachineInstrInfo:
+// struct MachineInstrDescriptor:
 //	Predefined information about each machine instruction.
 //	Designed to initialized statically.
 // 
@@ -61,6 +102,7 @@ const unsigned int	M_CONDL_FLAG		= 1 << 9;
 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 @@ struct MachineInstrDescriptor {
 				//   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 @@ public:
   // 
   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 @@ public:
 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 @@ public:
   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 @@ unsigned int TargetMachine::findOptimalStorageSize(const Type* ty) const {
 
 /*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 @@ MachineInstrInfo::constantFitsInImmedField(MachineOpCode opCode,
   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;
+}
+
 //---------------------------------------------------------------------------